Download - LISTA ENCADENADAS
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.
list
info(p) next(p)
nodo(p)
nil
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.
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
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
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
INSAFTER
1 2
43
XQ Q
XQ
P
A Y Z
XQ
P
A Y Z
XA Y ZResultado:
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)
DELAFTER
1
P
A Y
Q
X Y
2
B
P
A Y
Q
B3
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)
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.
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
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
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
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