Listas ligadas

  • Published on
    03-Oct-2015

  • View
    217

  • Download
    2

Embed Size (px)

DESCRIPTION

Descripcin bsica de listas ligadas

Transcript

<p>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&amp;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&amp;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.</p> <p>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.</p> <p>Los siguientes algoritmos fueron tomados de "Estructuras de Datos", Cair - Guardati, 2a. Ed., McGraw Hill, 2002.</p> <p>Algoritmo 5.1</p> <p>CREAINICIO(P)</p> <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}</p> <p>1.CREA (P) {Crea el primer nodo de la lista}2.Leer P-&gt;INFORMACIN3.Hacer P-&gt;LIGA=NIL4.RepetirCREA (Q)Leer Q-&gt;INFORMACINHacer Q-&gt;LIGA= P y P = Q</p> <p>5.Hasta (que ya no haya informacin)</p> <p>Algoritmo 5.2</p> <p>CREAFINAL(P)</p> <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}</p> <p>1.CREA (P) {Crea el primer nodo de la lista}2.Leer P-&gt;INFORMACIN3.Hacer P-&gt;LIGA=NIL y T=P4.RepetirCREA (Q)Leer Q-&gt;INFORMACINHacer Q-&gt;LIGA=NIL, T-&gt;LIGA=Q y T=Q5.Hasta (que ya no haya informacin)</p> <p>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.</p> <p>Algoritmo 5.3RECORREITERATIVO(P)</p> <p>{Este algoritmo recorre una lista cuyo primer nodo est apuntado por P}{Q es una variable de tipo puntero}</p> <p>1.Hacer Q = P2.Repetir mientras Q =! NILEscribir Q-&gt;INFORMACUNHacer Q=Q-&gt;LIGA {Apunta al siguiente nodo de la lista}3.{Fin del ciclo del paso 2}</p> <p>Algoritmo 5.4RECORRECURSIVO(P)</p> <p>{Este algoritmo recorre una lista recursivamente. P es el apuntador al nodo a visitar}</p> <p>1.Si P =! NIL entoncesEscribir P-&gt;INFORMACINLlamar a RECORRECURSIVO con P-&gt;LIGA{Llamada recursiva con el apuntador al siguiente nodo de la lista}2.{Fin del condicional del paso 1}</p> <p>Algoritmo 5.6INSERTAFINAL(P)</p> <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}</p> <p>1.Hacer T= P2.Repetir mientras T -&gt;Liga =! NIL{Recorre la lista hasta llegar al ltimo elemento}Hacer T=T-&gt;LIGA3.{Fin del ciclo del paso 2}4.CREA (Q)5.Hacer Q-&gt;INFORMACIN =DATO, Q-&gt;LIGA =NIL y T -&gt;LIGA =Q</p> <p>Algoritmo 5.7INSERTANTES ( P, DATO, REF )</p> <p>{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}</p> <p>1.Hacer Q= P y BAND= VERDADERO2.Repetir mientras (Q-&gt;INFORMACIN =! REF) y (BAND = VERDADERO)</p> <p>2.1Si Q -&gt; LIGA =! NILEntoncesHacer T= Q y Q= Q-&gt; 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-&gt;INFORMACIN = DATO4.1Si P = Q {Es el primer nodo}EntoncesHacer X -&gt;LIGA = P y P = XSi noHacer T -&gt;LIGA =X y X -&gt;LIGA = Q4.2{Fin del condicional del paso 4.1}5.{Fin del condicional del paso 4}</p> <p>Algoritmo 5.9ELIMINAPRIMERO(P)</p> <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}</p> <p>1.Hacer Q = P2.Si Q -&gt; LIGA =! NIL {Verifica si la lista tiene slo un nodo}EntoncesHacer P= Q-&gt; LIGA {Redefine el puntero al inicio}Si noHacer P = NIL3.{Fin del condicional del paso2}4.QUITA(Q)</p> <p>Algoritmo 5.10ELIMINALTIMO(P)</p> <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}</p> <p>1.Si P -&gt; LIGA = NIL {Verifica si la lista tiene slo un elemento}EntoncesQUITA(P)Hacer P = NILSi noHacer Q = P1.1 Repetir mientras ( Q-&gt;LIGA =! NIL)Hacer T=Q y Q = Q -&gt; LIGA1.2{Fin del ciclo del paso 1.1}Hacer T -&gt; LIGA = NILQUITA(Q)2.{Fin del condicional del paso 1}</p> <p>Algoritmo 5.11ELIMINAX( P, X )</p> <p>{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}</p> <p>1.Hacer Q = P y BAND= VERDADERO2.Repetir mientras (Q-&gt;INFORMACIN =! X) y (BAND = VERDADERO)</p> <p>2.1Si Q -&gt;LIGA =! NILEntoncesHacer T = Q y Q = Q -&gt; 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-&gt;LIGASi noHacer T -&gt; LIGA=Q-&gt; LIGA4.2{Fin del condicional del paso 4.1}QUITA(Q)5.{Fin del condicional del paso 4}</p> <p>Algoritmo 5.15BUSCARRECURSIVO(P,X)</p> <p>{Este algoritmo busca recursivamente al elemento con informacin X en una lista que se encuentra desordenada. P es el apuntador del nodo a visitar}</p> <p>1.Si ( P =! NIL)Entonces1.1Si ( P -&gt;INFORMACIN = X )EntoncesEscribir El elemento se encuentra en la listaSi no Llamar a BUSCARRECURSIVO con P -&gt; 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}</p> <p> 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:&gt;&gt;&gt; fruta = "banana"&gt;&gt;&gt; letra = fruta[1]&gt;&gt;&gt; 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:&gt;&gt;&gt; letra = fruta[0]&gt;&gt;&gt; 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:&gt;&gt;&gt; fruta = "banana"&gt;&gt;&gt; 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 implican procesar una cadena carcter por carcter. A menudo empiezan por el principio, seleccionan cada carcter por turno, hacen algo con l y siguen hasta el final. Este patrn de proceso se llamarecorrido. Una forma de codificar un recorrido es con una sentenciawhile:indice = 0while indice &lt; len(fruta): letra = fruta[indice] print letra indice += 1Este bucle recorre la cadena y muestra cada letra en una lnea distinta. La condicin del bucle esindice&gt;&gt; s = "Pedro, Pablo, y Mario"&gt;&gt;&gt; print s[0:5]Pedro&gt;&gt;&gt; print s[7:12]Pablo&gt;&gt;&gt; print s[16:21]MarioEl operador[n:m]devuelve la parte de la cadena desde el n-simo carcter hasta el m-simo, incluyendo el primero pero excluyendo el ltimo. Este comportamiento contradice a nuestra intuicin; tiene ms sentido si imagina los ndices sealandoentrelos caracteres, como en el siguiente diagrama:</p> <p>Si omite el primer ndice (antes de los dos puntos), la porcin comienza al principio de la cadena. Si omite el segundo ndice, la porcin llega al final de la cadena. As:&gt;&gt;&gt; fruta = "banana"&gt;&gt;&gt; fruta[:3]'ban'&gt;&gt;&gt; fruta[3:]'ana'Qu cree que significas[:]?7.5. Comparacin de cadenasLos operadores de comparacin trabajan sobre cadenas. Para ver si dos cadenas son iguales:if palabra == "banana": print "S, no tenemos bananas!"Otras operaciones de comparacin son tiles para poner palabras en orden alfabtico:if palabra &lt; "banana": print "Su palabra," + palabra + ", va antes de banana."elif word &gt; "banana": print "Su palabra," + palabra + ", va despus de banana."else: print "S, no tenemos bananas!"Sin embargo, debera ser consciente de que Python no maneja las letras maysculas y minsculas como lo hace la gente. Todas las letras maysculas van antes de las letras minsculas. Por lo tanto:Su palabra, Cebra, va antes de banana.Una forma comn de abordar este problema es convertir las cadenas a un formato estndar como pueden ser las minsculas antes de realizar la comparacin. Un problema mayor es hacer que el programa se de cuenta de que las cebras no son frutas.7.6. Las cadenas son inmutablesEs tentador usar el operador[]en el lado izquierdo de una asignacin, con la intencin de cambiar un carcter en una cadena. Por ejemplo:saludo = "Hola todo el mundo!"saludo[2] = 'L' # ERROR!print saludoNota del traductor:De acuerdo con la codificacin de caracteres en utf-8 latin-1 (vase la Nota del traductor del captulo 2) el carcter de admiracin, , en la variablesaludoocupa dos posiciones, de ah que la letra H est localizada en el ndice 2.En lugar de presentar la salidaLolatodoelmundo!, este cdigo presenta el siguiente error en tiempo de ejecucinTypeError:'str'objectdoesnotsupportitemassignment.Las cadenas soninmutables, lo que significa que no puede cambiar una cadena existente. Lo ms que puede hacer es crear una nueva cadena que sea una variacin de la original:saludo = "Hola todo el mundo!"nuevoSaludo = '' + 'L' + saludo[3:]print nuevoSaludoAqu la solucin es concatenar la apertura del signo de admiracin y una nueva primera letra a una porcin desaludo. Esta operacin no tiene efecto sobre la cadena original.7.7. El operadorinEl operadorinprueba si una cadena es una subcadena de otra:Ad by unisales|Close&gt;&gt;&gt; 'z' in 'manzana'True&gt;&gt;&gt; 'i' in 'manzana'False&gt;&gt;&gt; 'nz' in 'manzana'True&gt;&gt;&gt; 'az' in 'manzana'FalseObserve que una cadena es una subcadena de si misma:&gt;&gt;&gt; 'a' in 'a'True&gt;&gt;&gt; 'manzana' in 'manzana'TrueCombinando el operadorincon la concatenacin de cadenas usando+, podemos escribir una funcin que elimina todas las vocales de una cadena:def elimina_vocales(s): vocales = "aeiouAEIOU" s_sin_vocales = "" for letra in s: if letra not in vocales: s_sin_vocales += letra return s_sin_vocalesPruebe esta funcin para confirmar que realiza lo que queremos que haga.7.8. Una funcinencuentraQu hace la siguiente funcin?def encuentra(cadena, carac): indice = 0 while indice &lt; len(cadena): if cadena[indice] == carac: return indice indice += 1 return -1En cierto sentido,encuentraes lo contrario del operador[]. En lugar de tomar un ndice y extraer el carcter correspondiente, toma un carcter y encuentra el ndice donde aparece el carcter. Si el carcter no se encuentra, la funcin devuelve-1.Este es el primer ejemplo que hemos visto de una sentenciareturn``dentrodeunbucle.Si``cadena[indice]==carac, la funcin devuelve inmediatamente el ndice, escapando del bucle prematuramente.Si el carcter no aparece en la cadena, entonces el programa sale del bucle normalmente y devuelve-1.Este patrn de computacin se llama a veces un recorrido eureka porque tan pronto como encontramos lo que buscamos, podemos gritar Eureka! y dejar de buscar.7.9. Iterando y contandoEl siguiente programa cuenta el nmero de veces que aparece la letraaen una cadena, y es otro ejemplo del patrn de conteo introducido en elContando dgitos:fruta = "banana"cuenta = 0for carac in fruta: if carac == 'a': cuenta += 1print cuenta7.10. Parmetros opcionalesPara encontrar las posiciones de la segunda o tercera ocurrencia de un carcter en una cadena, podemos modificar la funcinencuentra, agregando un tercer parmetro para la posicin inicial en la cadena de bsqueda:Ad by unisales|Closedef encuentra2(cadena, carac, inicio): indice = inicio while indice &lt; len(cadena): if cadena[indice] == carac: return indice indice += 1 return -1La llamada aencue...</p>