Hola

[pic]

“PEDRO RUIZ GALLO”

CURSO: INTELIGENCIA ARTIFICIAL

PROFESOR : Ing. Joaquin More Peña

INTEGRANTES:

➢ Fajardo Guevara, Dennys Zoraida
➢ Heredia García, Patricia
➢ Rojas Pecsén, Miguel Angel
➢ Torres Santa Cruz, Walter

Lambayeque,Marzo del 2011.

INDICE

INTRODUCCION

LISTAS ENLAZADAS
 
1. Definición
 
Es un conjunto de elementos llamados nodos. Un nodo además de manejar la información requerida define el orden o ubicación del siguiente nodo.
 
[pic] [pic]
 
Una lista enlazada se puede implementar mediante arreglos paralelos como sigue:
- Info :arreglo [1..TAM]
- Enlace : arreglo [1..TAM]
Donde:
- Info es el arreglo que almacena la información o datos.
- Enlace es el arreglo que almacena la posición o dirección del siguiente nodo.
- La variable ini indicará la posición inicial de la lista, y,
- La variable dis indicará la posición inicial de la lista de elementos disponibles o vacíos.
 
Cuando ini es Nulo indicará que la lista estávacía, es decir, no hay elementos en la lista. Si dis es Nulo indicará que la lista está llena, es decir, no existen celdas disponibles.
 
[pic]
Lista enlazada con arreglos paralelos
 
Una lista también se puede implementar mediante un arreglo de registros:
Nodo: Registro
Info: tipo
Enlace: entero
Fin_registro
 
L: arreglo [1..TAM] de Nodo
 
Donde L es la lista enlazada implementadacon arreglo de registros. La variableini indicará la posición inicial de la lista de disponibles y la variable dis indicará la posición inicial de la lista de elementos de vacíos.
 
[pic]
 
La forma más adecuada de representar una lista enlazada es usando punteros.
Un puntero, es una variable que contiene la dirección de otra variable. 
 
[pic]
Concepto puntero
[pic]
Lista enlazada conpunteros
 
Nodo: Registro
Info: tipo
Enlace: puntero a nodo
Fin_registro
 
La variable L indicará la dirección del primer nodo de la lista. Cuando L es Nulo indicará que la lista está vacía, es decir, no hay elementos.
 
2. Operaciones
 
Para las operaciones siguientes se ha utilizado la lista enlazada con arreglo de registros.
 
2.1. Algoritmo de recorrido de los nodos
 
[pic]Registro de una lista enlazada
 
{
Objetivo : Acceder y procesar cada elemento de la lista.
Entrada : La lista L y la posición inicial ini.
Precondición : Lista tiene elementos.
Salida : Según proceso.
Postcondición : Ninguna.
}
Procedimiento Recorrido(L,ini)
Inicio
apu = ini
Repetir mientras (apu ? Nulo)
Escribir L[apu].Info {procesar L[apu].Info}
apu = L[apu].Enlace
Fin_repetir
Fin
  
 
2.2. Algoritmo de búsqueda
 
 
[pic]
Búsqueda de una lista enlazada
 
 
{
Objetivo : Determinar la posición en la lista L, donde se encuentra el valor de la variable datoBus en la lista.
Entrada : L, ini, datoBus.
Precondición : Lista no vacía
Salida : Referencia pos para indicar la posición de dato y referencia enco para indicar si lo encontró o no.
Postcondición : Si encuentrael dato: enco tiene valor verdadero y obtiene la posición donde se encuentra. Si no lo encuentra enco es false.
}
Procedimiento Busqueda(L, ini, datoBus, ?pos, ?enco)
Inicio
enco = falso
apu = ini
pos = Nulo
Repetir mientras (enco == falso y apu ? Nulo)
Si (datoBus == L[apu].Info) entonces
pos = apu
enco = verdadero
sino
apu = L[apu].Enlace
Fin_si
Fin_repetir
Si (enco == falso)entonces
Escribir “El elemento no existe”
sino
Escribir “El elemento esta en la posicion ”,pos
Fin_si
Fin
 
Otras implementaciones de algoritmos de búsqueda son las siguientes.
 
[pic]
Búsqueda en una lista enlazada
 
{
Objetivo : Determinar la posición de la variable dato en la lista L.
Entrada : L, ini, datoBus.
Precondición : Lista no vacía.
Salida : Referencia ant para indicar...