listas enlazadas

Download LISTAS ENLAZADAS

Post on 14-Jul-2015

270 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

LISTAS ENLAZADAS* * * * * * * * * Definicin Operaciones bsicas sobre listas Listas ordenadas Listas reorganizables Cabecera ficticia y centinela Listas doblemente enlazadas Listas circulares Algoritmos de ordenacin de listas Conclusin y problemas

DefinicinUna lista es una estructura de datos secuencial. Una manera de clasificarlas es por la forma de acceder al siguiente elemento: - lista densa: la propia estructura determina cul es el siguiente elemento de la lista. Ejemplo: un array. - lista enlazada: la posicin del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posicin de memoria del primer elemento. Adems es dinmica, es decir, su tamao cambia durante la ejecucin del programa. Una lista enlazada se puede definir recursivamente de la siguiente manera: - una lista enlazada es una estructura vaca o - un elemento de informacin y un enlace hacia una lista (un nodo). Grficamente se suele representar as:

Como se ha dicho anteriormente, pueden cambiar de tamao, pero su ventaja fundamental es que son flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora de acceder a cualquier elemento. En la lista de la figura anterior se puede observar que hay dos elementos de informacin, x e y. Supongamos que queremos aadir un nuevo nodo, con la informacin p, al comienzo de la lista. Para hacerlo basta con crear ese nodo, introducir la informacin p, y hacer un enlace hacia el siguiente nodo, que en este caso contiene la informacin x. Qu ocurre si quisiramos hacer lo mismo sobre un array?. En ese caso sera necesario desplazar todos los elementos de informacin "hacia la derecha", para poder introducir el nuevo elemento, una operacin muy engorrosa.

Implementacin Para representar en lenguaje Pascal esta estructura de datos se utilizarn punteros, un tipo de datos que suministra el lenguaje. Se representar una lista vaca con la constante NIL. Se puede definir la lista enlazada de la siguiente manera: Lista = ^Rec; Rec = Record Clave : Integer; Sig : Lista; End; Como se puede observar, en este caso el elemento de informacin es simplemente un nmero entero. Adems se trata de una definicin autorreferencial. Pueden hacerse definiciones ms complejas. Ejemplo: cl = Record nombre : string[20]; edad : Integer; End; Lista = ^Rec; Rec = Record datos : cl; Clave : Integer; Sig : Lista; End; Cuando se crea una lista debe estar vaca. Por tanto para crearla se hace lo siguiente: Var L : Lista L := NIL;

Operaciones bsicas sobre listas- Insercin al comienzo de una lista: Es necesario utilizar una variable auxiliar, que se utiliza para crear el nuevo nodo mediante la reserva de memoria y asignacin de la clave. Posteriormente es necesario reorganizar los enlaces, es decir, el nuevo nodo debe apuntar al que era el primer elemento de la lista y a su vez debe pasar a ser el primer elemento. En el siguiente ejemplo se muestra un programa que crea una lista con cuatro nmeros. Notar que al introducir al comienzo de la lista, los elementos quedan ordenados en sentido inverso al de su llegada. Notar tambin que se ha utilizado un puntero auxiliar p para mantener correctamente los enlaces dentro de la lista. Var L, p : Lista; i : Integer; begin L := NIL; { Crea una lista vacia } for i := 4 downto 1 do begin { Reserva memoria para un nodo }

new(p); p^.clave := i; { Introduce la informacion } p^.sig := L; { reorganiza } L := p; { los enlaces } end - Recorrido de una lista. La idea es ir avanzando desde el primer elemento hasta encontrar la lista vaca. Antes de acceder a la estructura lista es fundamental saber si esa estructura existe, es decir, que no est vaca. En el caso de estarlo o de no estar inicializada es posible que el programa falle y sea difcil detectar donde, y en algunos casos puede abortarse inmediatamente la ejecucin del programa, lo cual suele ser de gran ayuda para la depuracin. Como se ha dicho antes, la lista enlazada es una estructura recursiva, y una posibilidad para su recorrido es hacerlo de forma recursiva. A continuacin se expone el cdigo de un programa que muestra el valor de la clave y almacena la suma de todos los valores en una variable pasada por referencia (un puntero a entero). Por el hecho de ser un proceso recursivo se utiliza un procedimiento para hacer el recorrido. Ntese como antes de hacer una operacin sobre el elemento se comprueba si existe. Procedure recorrer(L : Lista; var suma : Integer); begin if L NIL then begin write(L^.clave, ' '); suma := suma + L^.clave; recorrer(L^.sig, suma) end end; Var L : Lista; Suma : Integer; Begin { Crear la lista } ... Suma := 0; Recorrer(L, Suma); End.

Sin embargo, a la hora de hacer un programa, es ms eficaz si el recorrido se hace de forma iterativa. En este caso se necesita una variable auxiliar que se desplace sobre la lista para no perder la referencia al primer elemento. Se expone un programa que hace la misma operacin que el anterior, pero sin recursin. Var L : Lista; Suma : Integer; Begin { Crear la lista L } ... suma := 0; p := L; while p NIL do begin write(p^.Clave, ' '); suma := suma + p^.Clave;

p := p^.Sig end end. Y si queremos insertar en una posicin arbitraria de la lista o queremos borrar un elemento? Como se trata de operaciones algo ms complicadas (tampoco mucho) se expone su desarrollo y sus variantes en los siguientes tipos de listas: las listas ordenadas y las listas reorganizables. Asimismo se estudiarn despus las listas que incorporan cabecera y centinela. Tambin se estudiarn las listas con doble enlace. Todas las implementaciones se harn de forma iterativa, y se deja propuesta por ser ms sencilla su implementacin recursiva, aunque es recomendable utilizar la versin iterativa.

Listas ordenadasLas listas ordenadas son aquellas en las que la posicin de cada elemento depende de su contenido. Por ejemplo, podemos tener una lista enlazada que contenga el nombre y apellidos de un alumno y queremos que los elementos -los alumnosestn en la lista en orden alfabtico. La creacin de una lista ordenada es igual que antes: var L : Lista; L := NIL; Cuando haya que insertar un nuevo elemento en la lista ordenada hay que hacerlo en el lugar que le corresponda, y esto depende del orden y de la clave escogidos. Este proceso se realiza en tres pasos: 1.- Localizar el lugar correspondiente al elemento a insertar. Se utilizan dos punteros: anterior y actual, que garanticen la correcta posicin de cada enlace. 2.- Reservar memoria para l (puede hacerse como primer paso). Se usa un puntero auxiliar (nuevo) para reservar memoria. 3.- Enlazarlo. Esta es la parte ms complicada, porque hay que considerar la diferencia de insertar al principio, no importa si la lista est vaca, o insertar en otra posicin. Se utilizan los tres punteros antes definidos para actualizar los enlaces. A continuacin se expone un programa que realiza la insercin de un elemento en una lista ordenada. Suponemos claves de tipo entero ordenadas ascendentemente. Procedure insertar(Var L : lista; elem : Integer); var actual, anterior, nuevo : Lista; begin { 1.- se busca su posicion } actual := L; anterior := L; while (actual NIL) And (actual^.clave < elem) do begin anterior := actual; actual := actual^.sig end; { 2.- se crea el nodo } new(nuevo); nuevo^.clave := elem;

{ 3.- Se enlaza } { inserta al principio } if (anterior = NIL) Or (anterior = actual) then begin nuevo^.sig := anterior; L := nuevo { importante: al insertar al principio actuliza la cabecera } end { inserta entre medias o al final } else begin nuevo^.sig := actual; anterior^.sig := nuevo; end end; { Programa de prueba } Var L : Lista; begin L := NIL; { Crea una lista vacia insertar(L, 0); insertar(L, 1); insertar(L, -1) end.

}

Se puede apreciar que se pasa la lista L con el parmetro Var L . La razn para hacer esto es que cuando se inserta al comienzo de la lista (porque est vaca o es donde corresponde) se cambia la cabecera. Un ejemplo de prueba: suponer que se tiene esta lista enlazada: 1 -> 3 -> 5 -> NIL Queremos insertar un 4. Al hacer la bsqueda el puntero actual apunta al 5. El puntero anterior apunta al 3. Y nuevo contiene el valor 4. Como no se inserta al principio se hace que el enlace siguiente a nuevo sea actual, es decir, el 5, y el enlace siguiente a anterior ser nuevo, es decir, el 4. La mejor manera de entender el funcionamiento es haciendo una serie de seguimientos a mano o con la ayuda del depurador. A continuacin se explica el borrado de un elemento. El procedimiento consiste en localizarlo y borrarlo si existe. Aqu tambin se distingue el caso de borrar al principio o borrar en cualquier otra posicin. Se puede observar que el algoritmo no tiene ningn problema si el elemento no existe o la lista est vaca. Procedure borrar(Var L : lista; elem : Integer); Var actual, anterior : Lista; Begin { 1.- busca su posicion. Es casi igual que en la insercion, ojo al ( 2 -> 1 -> 6 -> 9 -> 0 -> 7 -> 4 -> 3 -> 8 se fusiona el primer elemento con el segundo, el tercero con el cuarto, etctera: [(3) -> (2)] -> [(1) -> (6)] -> [(9) -> (0)] -> [(7) -> (4)] -> [(3) -> (8)] queda: 2 -> 3 -> 1 -> 6 -> 0 -> 9 -> 4 -> 7 -> 3 -> 8 se fusionan los dos primeros (primera sublista) con los dos siguientes (segunda sublista), la tercera y cuarta sublista, etctera. Observar que la quinta sublista se fusiona con una lista vaca, lo cual no supone ningn inconveniente para el algoritmo de fusin. [(2 -> 3) -> (1 -> 6)] -> [(0 -> 9) -> (4 -> 7)] -> [(3 -> 8)] queda: 1 -> 2 -> 3 -> 6 -> 0 -> 4 -> 7 -> 9 -> 3 -> 8 se fusionan los cuatro primeros con los cuatro siguientes, y aparte quedan los dos ltimos:

[(1 -> 2 -> 3 -> 6) -> (0 -> 4 -> 7 -> 9)] -> [(3 -> 8)] queda: 0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 7 -&g

Recommended

View more >