Listas ligadas

Embed Size (px)

DESCRIPTION

Descripción básica de listas ligadas

Text of Listas ligadas

Listas ligadasEn las secciones anteriores se contemplaron diferentes estructuras estticas en dnde la manipulacin de datos es a travs de posiciones localizadas secuencialmente. Para de clarar estas estructuras se deba definir un tamao determinado el cual no poda modificarse posteriormente. Esto puede ser un problema en el caso de que: no sepamos de antemano el tamao requerido para nuestra aplicacin hay una gran cantidad de operaciones y manipulaciones de los datos dentro de las estructurasEn estos casos es generalmente m&a acute;s conveniente utilizar estructuras dinmicas, es decir, las cuales pueden aumentar o disminuir de tamao de acuerdo a los requerimientos especficos del procedimiento. As se resuelve el problema de no saber el tama&ntild e;o exacto desde un principio y las manipulaciones de datos se pueden hacer de una manera mas rpida y eficiente.Una lista ligada es entonces un grupo de datos organizados secuencialmente, pero a diferencia de los arreglos, la organizacin no est dada implcitamente por su posicin en el arreglo. En una lista ligada cada elemento es unnodoque contiene el dato y adems unaligaal siguiente dato. Estas ligas son simplemente variables que contienen la(s) direccin(es) de los datos contiguos o relacionados.Para manejar una lista es necesario contar con un apuntador al primer elemento de la lista"head".Las ventajas de las listas ligadas son que: Permiten que sus tamaos cambien durante la ejecucin del programa Proveen una mayor flexibilidad en el manejo de los datos.Este principio de listas ligadas se puede aplicar a cualquiera de los conceptos de estructura de datos vistos anteriormente: arreglos, colas y pilas. Es decir, las operaciones de altas, bajas y cambios, as como bsquedas y ordenamientos se tendrn que adaptar en la cuestin del manejo de localidades nicamente.

Listas ligadas sencillasUna lista ligada sencilla es un grupo de datos en dnde cada dato contiene adems un apuntador hacia el siguiente dato en la lista, es decir, unaligahacia el siguiente dato.

Los siguientes algoritmos fueron tomados de "Estructuras de Datos", Cair - Guardati, 2a. Ed., McGraw Hill, 2002.

Algoritmo 5.1

CREAINICIO(P)

{Este algoritmo crea una lista, agregando cada nuevo nodo al inicio de la misma}{ P y Q son variables de tipo puntero. P apuntar al inicio de la lista}

1.CREA (P) {Crea el primer nodo de la lista}2.Leer P->INFORMACIN3.Hacer P->LIGA=NIL4.RepetirCREA (Q)Leer Q->INFORMACINHacer Q->LIGA= P y P = Q

5.Hasta (que ya no haya informacin)

Algoritmo 5.2

CREAFINAL(P)

{Este algoritmo crea una lista, agregando cada nuevo nodo al final de la misma}{P y Q son variables de tipo puntero. P apuntar al inicio de la lista}

1.CREA (P) {Crea el primer nodo de la lista}2.Leer P->INFORMACIN3.Hacer P->LIGA=NIL y T=P4.RepetirCREA (Q)Leer Q->INFORMACINHacer Q->LIGA=NIL, T->LIGA=Q y T=Q5.Hasta (que ya no haya informacin)

Para poder dar de alta un dato en una lista ligada sencilla es necesario recorrer la lista nodo por nodo hasta encontrar la posicin adecuada. Se crea un nuevo nodo, se inserta el dato y se actualizan las ligas del nodo nuevo y del anterior para intercalar el nuevo nodo en la lista.

Algoritmo 5.3RECORREITERATIVO(P)

{Este algoritmo recorre una lista cuyo primer nodo est apuntado por P}{Q es una variable de tipo puntero}

1.Hacer Q = P2.Repetir mientras Q =! NILEscribir Q->INFORMACUNHacer Q=Q->LIGA {Apunta al siguiente nodo de la lista}3.{Fin del ciclo del paso 2}

Algoritmo 5.4RECORRECURSIVO(P)

{Este algoritmo recorre una lista recursivamente. P es el apuntador al nodo a visitar}

1.Si P =! NIL entoncesEscribir P->INFORMACINLlamar a RECORRECURSIVO con P->LIGA{Llamada recursiva con el apuntador al siguiente nodo de la lista}2.{Fin del condicional del paso 1}

Algoritmo 5.6INSERTAFINAL(P)

{Este algoritmo inserta un nodo al final de la lista. P es el apuntador al primer nodo de la lista, y DATO es la informacin que se almacenar en el nuevo nodo}{Q y T son variables de tipo puntero}

1.Hacer T= P2.Repetir mientras T ->Liga =! NIL{Recorre la lista hasta llegar al ltimo elemento}Hacer T=T->LIGA3.{Fin del ciclo del paso 2}4.CREA (Q)5.Hacer Q->INFORMACIN =DATO, Q->LIGA =NIL y T ->LIGA =Q

Algoritmo 5.7INSERTANTES ( P, DATO, REF )

{Este algoritmo inserta un nodo dado como referencia, REF. P es el apuntador al primer nodo de la lista, y DATO es la informacin que se almacenar en el nuevo nodo}{Q, X y T son variables de tipo puntero, BAND es una variable de tipo booleano}

1.Hacer Q= P y BAND= VERDADERO2.Repetir mientras (Q->INFORMACIN =! REF) y (BAND = VERDADERO)

2.1Si Q -> LIGA =! NILEntoncesHacer T= Q y Q= Q-> LIGASi noHacer BAND = FALSO2.2{Fin del condicional del paso 2.1}3.{Fin del ciclo del paso 2}4. Si BAND = VERDADERO entoncesCREA(X)Hacer X->INFORMACIN = DATO4.1Si P = Q {Es el primer nodo}EntoncesHacer X ->LIGA = P y P = XSi noHacer T ->LIGA =X y X ->LIGA = Q4.2{Fin del condicional del paso 4.1}5.{Fin del condicional del paso 4}

Algoritmo 5.9ELIMINAPRIMERO(P)

{Este algoritmo borra el primer elemento de una lista. P es el apuntador al primer nodo de la lista}{Q es una variable de tipo puntero}

1.Hacer Q = P2.Si Q -> LIGA =! NIL {Verifica si la lista tiene slo un nodo}EntoncesHacer P= Q-> LIGA {Redefine el puntero al inicio}Si noHacer P = NIL3.{Fin del condicional del paso2}4.QUITA(Q)

Algoritmo 5.10ELIMINALTIMO(P)

{Este algoritmo borra el ltimo elemento de una lista. P es el apuntador al primer nodo de la lista}{Q y T son variables de tipo puntero}

1.Si P -> LIGA = NIL {Verifica si la lista tiene slo un elemento}EntoncesQUITA(P)Hacer P = NILSi noHacer Q = P1.1 Repetir mientras ( Q->LIGA =! NIL)Hacer T=Q y Q = Q -> LIGA1.2{Fin del ciclo del paso 1.1}Hacer T -> LIGA = NILQUITA(Q)2.{Fin del condicional del paso 1}

Algoritmo 5.11ELIMINAX( P, X )

{Este algoritmo elimina un nodo con informacin X de una lista. P es el apuntador al primer nodo de la lista}{Q y T son variables de tipo puntero. BAND es una variable de tipo booleano}

1.Hacer Q = P y BAND= VERDADERO2.Repetir mientras (Q->INFORMACIN =! X) y (BAND = VERDADERO)

2.1Si Q ->LIGA =! NILEntoncesHacer T = Q y Q = Q -> LIGASi noHacer BAND = FALSO2.2{Fin del condicional del paso 2.1}3.{Fin del ciclo del paso 2}4.Si BAND = FALSOEntoncesEscribir El elemento no fue encontradoSi no4.1SI P = Q {Verifica si el elemento a eliminar es el primero}EntoncesHacer P = Q->LIGASi noHacer T -> LIGA=Q-> LIGA4.2{Fin del condicional del paso 4.1}QUITA(Q)5.{Fin del condicional del paso 4}

Algoritmo 5.15BUSCARRECURSIVO(P,X)

{Este algoritmo busca recursivamente al elemento con informacin X en una lista que se encuentra desordenada. P es el apuntador del nodo a visitar}

1.Si ( P =! NIL)Entonces1.1Si ( P ->INFORMACIN = X )EntoncesEscribir El elemento se encuentra en la listaSi no Llamar a BUSCARRECURSIVO con P -> LIGA y X1.2{Fin del condicional del paso 1.1}Si no Escribir El elemento no se encuentra en la lista2.{Fin del condicional del paso 1}

index next| previous| Cmo Pensar como un Informtico: El aprender con Python vEd 2 documentationAd by unisales|Close7. Cadenas7.1. Un tipo de datos compuestoHasta ahora hemos visto cinco tipos:int,float,bool,NoneTypeystr. Las cadenas son cualitativamente diferentes de los otros cuatro tipos porque estn hechas de piezas ms pequeas loscaracteres.Los tipos que comprenden piezas mas pequeas se llamantipos de datos compuestos. Dependiendo de lo que hagamos, podemos tratar un tipo de datos compuesto como una nica cosa o podemos acceder a sus partes. Esta ambigedad es til.El operador corchete selecciona slo un carcter de una cadena:>>> fruta = "banana">>> letra = fruta[1]>>> print letraLa expresinfruta[1]selecciona el carcter nmero 1 defruta. La variableletraapunta al resultado. Cuando mostramosletra, nos encontramos con una sorpresa:aLa primera letra de"banana"no esa. A no ser que usted sea un programador. Por perversas razones, los cientficos de la computacin siempre empiezan a contar desde cero. La 0-sima letra (cero- sima) de"banana"esb. La 1-sima (uno- sima) esa, y la 2-sima (dos-sima) letra esn.Nota del traductor:La numeracin ordinal por todos conocida no contempla al cero como parte de su verbalizacin, por lo que se considera apropiada la introduccin de esta forma de expresar la numeracin de caracteres, dado el objetivo que se persigue.Si quiere la cero-sima letra de una cadena, simplemente pone 0, o cualquier expresin de valor 0, entre los corchetes:>>> letra = fruta[0]>>> print letrabA la expresin entre corchetes se le llamandice. Un ndice identifica a un miembro de un conjunto ordenado, en este caso el conjunto de caracteres de la cadena. El ndiceindicacul quiere usted, de ah el nombre. El ndice puede ser cualquier expresin entera.7.2. LongitudLa funcinlendevuelve el nmero de caracteres de una cadena:>>> fruta = "banana">>> len(fruta)6Para obtener la ltima letra de una cadena, puede sentirse tentado a probar algo como esto:longitud = len(fruta)ultima = fruta[longitud] # ERROR!Eso no funcionar. Esto provoca el error en tiempo de ejecucinIndexError:stringindexoutofrange. La razn es que no hay una seis-sima letra en"banana". Como empezamos a contar desde cero, las seis letras estn numeradas del 0 al 5. Para obtener el ltimo carcter tenemos que restar 1 a lalongitud:longitud = len(fruta)ultima = fruta[longitud-1]Alternativamente podemos usar ndices negativos, que cuentan hacia atrs desde el final de la cadena. La expresinfruta[-1]da la ltima letra,fruta[-2]da la penltima, y as sucesivamente.7.3. Recorrido y el bucleforMuchos clculos impli