lista encadenadas
DESCRIPTION
LISTA ENCADENADAS. DEFINICIÓN. Las listas están formadas por una serie de nodos; cada nodo tienen un campo de información y un apuntador (puntero) al siguiente nodo de la lista. nodo(p). list. nil. info(p). next(p). OPERACIONES BÁSICAS. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/1.jpg)
LISTA ENCADENADAS
![Page 2: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/2.jpg)
DEFINICIÓN
Las listas están formadas por una serie de nodos; cada nodo tienen un campo de información y un apuntador (puntero) al siguiente nodo de la lista.
list
info(p) next(p)
nodo(p)
nil
![Page 3: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/3.jpg)
OPERACIONES BÁSICAS
Una operación básica es la de obtener un nodo vacío. Esta operación se denomina getnode. La operación regresa un apuntador al nodo vacío.La operación complementaria regresa un nodo al sistema, esta operación es llamada freenode(p) y libera el nodo apuntado por p.
![Page 4: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/4.jpg)
OPERACIÓN PUSHLa operación push, inserta un nodo nuevo a la cabeza de una listaSUBRUTINA PUSH(X:ITEM; LIST:LISTA)1. P GETNODE2. INFO(P) X3. NEXT(P) LIST4. LIST P
P
1
2
3
4
P X
LIST
P X
LIST
P X
Y
Y
![Page 5: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/5.jpg)
OPERACIÓN POPLa operación pop elimina el nodo que se encuentra en la cabeza de la lista.FUNCION POP(LIST LISTA) REGRESA UN ELEMENTO DE LA LISTA1. P LIST2. LIST NEXT(P)3. X INFO(P)4. FREENODE(P)5. REGRESA X
1
2 4
X ALIST
P A Y
LIST
P A Y
3
LIST
P A Y
![Page 6: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/6.jpg)
OPERACIÓN INSAFTER
Algoritmo para insertar un nodo después del nodo P.SUBRUTINA INSAFTER(P:APUNTADOR,X:..)1. Q GETNODE2. INFO(Q) X3. NEXT(Q) NEXT(P)4. NEXT(P) Q
![Page 7: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/7.jpg)
INSAFTER
1 2
43
XQ Q
XQ
P
A Y Z
XQ
P
A Y Z
XA Y ZResultado:
![Page 8: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/8.jpg)
ALGORITMO DELAFTER
Algoritmo para eliminar el nodo después del nodo P.SUBRUTINA DELAFTER(P:APUNTADOR;X:..)1. Q NEXT(P)2. X INFO(Q)3. NEXT(P) NEXT(Q)4. FREENODE(Q)
![Page 9: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/9.jpg)
DELAFTER
1
P
A Y
Q
X Y
2
B
P
A Y
Q
B3
![Page 10: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/10.jpg)
ALGORITMO PARA LA CREACIÓN DE UNA LISTA ORDENADA
SUBRUTINA PLACE(X:INFO; LIST:APUNTADOR)1. FOUND FALSE2. P LIST3. Q NIL4. MIENTRAS (P<>NIL) AND (NOT FOUND) HACER
a. SI X<=INFO(P) ENTONCES1. FOUND FALSE
b. ELSE1. Q P2. P NODE[P].NEXT
5. SI Q=NIL ENTONCESa. PUSH(LIST,X)
6. ELSEb. INSAFTER(Q,X)
![Page 11: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/11.jpg)
Representación de polinomios
Un polinomio en (x, y, z) puede representarse como una lista.
En cada nodo se almacena el exponente de cada variable y el valor del coeficiente. Por tanto cada nodo de la lista será un registro con los campos: C - para el coeficiente y X, Y, Z - para los exponentes de x, y, z respectivamente.
![Page 12: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/12.jpg)
FUNCION POLYINSERT(I:INFOTYPE;FIRST:NODEPTR) REGRESA NODEPTR
1. SI FIRST=NIL ENTONCES
a. PUSH(I,FIRST)
2. SINO
a. A INFO(FIRST).X
b. B INFO(FIRST).Y
c. C INFO(FIRST).Z
d. SI (A < I.X) OR ((A=I.X)AND(B<I.Y)) OR
((A=I.X) AND (B=I.Y) AND (C<I.Z)) THEN
1. PUSH(I,FIRST)
e. SINO
1. S FIRST
2. FOUND FALSO
ALGORITMO DE INSERCIÓN EN POLINOMIO
![Page 13: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/13.jpg)
3. MIENTRAS (NEXT(S)<>NIL) AND (NOT FOUND) HACER
a. Q NEXT(S)
b. A INFO(Q).X
c. B INFO(Q).Y
d. SI (A < I.X) OR ((A=I.X)AND(B<I.Y)) OR
((A=I.X) AND (B=I.Y) AND (C<I.Z)) ENTONCES
1. S NEXT(S)
e. SINO
1. INSAFTER(S,I)
2. FOUND VERDADERO
3. SI NOT FOUND ENTONCES
a. INSAFTER(S,I)
4. REGRESA FIRST
ALGORITMO DE INSERCIÓN EN POLINOMIO
CONTINUACIÓN
![Page 14: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/14.jpg)
Derivada de un polinomioFUNCION POLYDER(POLY:NODEPTR) REGRESA NODEPTR
1. P POLY
2. QX NIL
3. MIENTRAS P<>NIL HACER
a. I INFO(P)
b. XP I.X
c. SI XP<>0 ENTONCES
1. I.C I.C*I.X
2. I.X I.X-1
3. QX POLYINSERT(I,QX)
d. P NEXT(P)
4. REGRESA QX
![Page 15: LISTA ENCADENADAS](https://reader036.vdocumento.com/reader036/viewer/2022072013/56812ac4550346895d8e9622/html5/thumbnails/15.jpg)
Evaluación de un polinomioFUNCION POLYEVAL(POLY:NODEPTR; X1,Y1,Z1:REAL) REGRESA REAL
1. P POLY
2. VALOR 0
3. MIENTRAS P<>NIL HACER
a. I INFO(P)
b. VALOR VALOR + I.C*POT(X1,I.X)*
POT(X1,I.Y)*POT(Z1,I.Z)
c. P NEXT(P)
4. REGRESA VALOR