Otros tipos de listas
description
Transcript of Otros tipos de listas
Otros tipos de listas
Curso de Introducción a la Computación
Listas circulares
Una lista circular es aquella en la que el último nodo apunta al primero.
listPrimer nodo Ultimo nodo
Prueba de fin de lista
Para probar si ya se llegó al final de la lista se debe probar la condición:
next(p) == list
La inserción y eliminación de nodos debe garantizar que el nodo final debe apuntar al inicio de la lista.
Longitud de una lista circularComo ejemplo de operación de listas circulares considere determinar el número de elementos de una lista circular.
FUNCIÓN LEN(LISTA_CIRCULAR)
1. COUNT <= 0
2. SI LISTA_CIRCULAR != NULL ENTONCES
3. P = LISTA_CIRCULAR
4. HACER
5. COUNT <= COUNT + 1
6. P <= NEXT(P)
7 . MIENTRAS P!= LISTA_CIRCULAR
8. REGRESAR COUNT
OPERACIÓN PUSH
Para poder insertar a la cabeza de una lista circular es necesario recorrer toda la lista hasta el final.
list
Algoritmo DELAFTER para una lista circular
Algoritmo para eliminar el nodo después del nodo P.
SUBRUTINA DELAFTER(P:APUNTADOR;X:..)
1. SI P=NIL OR P=NEXT(P) ENTONCES
a. ERROR " ELIMINACIÓN INVÁLIDA"
2 Q NEXT(P)
3. X INFO(Q)
4. NEXT(P) NEXT(Q)
5. FREENODE(Q)
list P Q1
3
2
X = INFO(Q)
Apuntador al final de una lista circular
Se pueden resolver algunos de los problemas de listas circulares haciendo que el apuntador de una lista circular apunte al último nodo en vez de al primero.
listPrimer nodo Ultimo nodo
Algoritmo para concatenar dos listas circulares
SUBRUTINA CONCAT(LIST2:APUNTADOR;LIST1:APUNTADOR)
1. SI LIST1=NIL ENTONCES
a. REGRESAR
2. SI LIST2=NIL ENTONCES
a. LIST1 LIST2
a. REGRESAR
3. P NEXT(LIST1)
4. NEXT(LIST1) NEXT(LIST2)
5. NEXT(LIST2) P
6. LIST1 LIST2
LIST1
LIST2
P
23
4
LIST1
1
La concatenación de listas puede hacerse sin recorrer toda la lista.
Suma de números grandes
Podemos representar números positivos grandes con listas circulares.
Usaremos un nodo cabecera con un valor especial (-1) para reconocer el inicio o final del número.
Los números se almacenarán en orden inverso, es decir, primero los dígitos menos significativos y así sucesivamente.
8266739027253828700 se almacenará como:
8700 5382 0272 6739-1 0826
Función para sumar dos enteros largos
int addint(int p, int q){ long hunthou = 10000L; long carry, number, total; int s; //asignar a p y q los siguientes nodos a los nodos cabecera p = node[p].next; q = node[q].next; //preparar nodo cabecera para la suma s = getnode(); node[s].info = -1; node[s].next = s; carry = 0;
while(node[p].info!=-1&&node[q].info!=-1){ //sumar los dos nodos y el acarreo total = node[p].info+node[q].info+carry; //truncar e insertar en la lista number = total%hunthou; insafter(s,number); //avanza apuntadores s = node[s].next; p = node[p].next; q = node[q].next; //calcula acarreo carry = total/hunthou; }
//se procesan nodos restantes while(node[p].info!=-1){ total = node[p].info+carry; number = total%hunthou; insafter(s,number); s = node[s].next; p = node[p].next; } while(node[q].info!=-1){ total = node[q].info+carry; number = total%hunthou; insafter(s,number); s = node[s].next; p = node[q].next; }
//si hay acarreo, inserta if(carry==1){ insafter(s,carry); s = node[s].next; } return node[s].next;}