Download Capítulo 13

Capítulo 13. Listas enlazadas, pilas, colas y árboles.
1. Introducción.
2. Listas enlazadas.
3. Pilas.
4. Colas.
5. Árboles.
5.1. Árboles binarios.
1
1. Introducción.
Algunas soluciones informáticas exigen la utilización de ciertas
estructuras de datos, que permiten la optimización del funcionamiento de los
programas. Vamos a tratar en este capítulo algunas de estas estructuras.
2. Listas enlazadas.
Una lista enlazada consiste en una sucesión de estructuras del mismo
tipo, en las que uno de sus campos será un puntero a estructura del mismo
tipo, de este modo cada estructura podrá apuntar a la siguiente de la lista.
Además del campo de tipo puntero a estructura, existirán otros campos para
guardar la información que sea necesaria. Las estructuras que forman la lista
se irán creando de forma dinámica (malloc) a medida que se van necesitando,
para conseguir el máximo ahorro de memoria.
lista
Para crear este tipo de lista, debe declararse una variable de tipo
puntero a estructura de la lista (puntero lista en la figura anterior), que debe
mantenerse apuntando siempre al primer elemento de la lista, es decir a la
primera estructura, para no perderse el punto de entrada a la lista. Para indicar
que la lista está vacía puede guardarse el valor NULL en dicho puntero.
Ej. Añadir el primer elemento de una lista enlazada.
struct tlista{
long DNI;
char Nombre[25];
int Edad;
struct tlista *psig; //Puntero a siguiente.
};
void main(void)
{
struct tlista *lista = NULL; //Inicialmente vacía.
struct tlista *p; //Puntero auxiliar.
...
//Se crea el nuevo elemento y se carga con datos:
p=(struct tlista *)malloc(1*sizeof(struct tlista));
scanf(“%8ld”,
&p->DNI);
fflush(stdin);
scanf(“%24[^\n]”, p->Nombre); fflush(stdin);
scanf(“%3d”,
&p->Edad);
fflush(stdin);
p->psig = NULL;
//Puntero a sigte. de momento vale NULL.
if (lista == NULL) //Si lista está vacía
{
lista = p; //Es el primer elemento de la lista
}
else
{
2
...
}
}
Generalmente las operaciones sobre la lista enlazada requieren
comprobar si está vacía, como se hace en el ejemplo anterior.
Una lista enlazada tiene un solo punto de entrada, que es el puntero que
apunta al primer elemento de la lista. Para acceder a un elemento cualquiera,
debe recorrerse la lista de forma secuencial hasta encontrar el elemento
buscado. Para reconocer el último elemento suele grabarse el valor NULL en el
campo puntero a siguiente. Esta será la forma de detectar donde finaliza la
lista. Por tanto, puede deducirse que el recorrido de una lista enlazada se
realiza en un solo sentido.
Existe una serie de operaciones que son las básicas a realizar sobre
una lista enlazada. No olvidar que la mayoría requieren verificar si la lista está
vacía. Veamos algunas de estas operaciones:
- Insertar un nuevo elemento. Esta operación tiene dos variantes:
a) Inserción al comienzo de la lista, el elemento nuevo será el primer elemento.
El puntero a siguiente del nuevo elemento apuntará al que era el primer
elemento (1). Esta operación modifica el puntero de acceso a la lista, que
dejará de apuntar al que era el primer elemento, para pasar a apuntar al
elemento nuevo (2).
p
Elemento nuevo
(1)
(2)
//
lista
Ej. Usando el tipo de estructura del ejemplo anterior y suponiendo que el
puntero al comienzo se llama lista:
//Se crea el nuevo elemento y se carga con datos:
p=(struct tlista *)malloc(1*sizeof(struct tlista));
scanf(“%8ld”,
&p->DNI);
fflush(stdin);
scanf(“%24[^\n]”, p->Nombre); fflush(stdin);
scanf(“%3d”,
&p->Edad);
fflush(stdin);
p->psig = lista->psig; //El nuevo elemento apunta al
//que era el primer elemento.
lista = p; //El nuevo elemento ahora es el primero.
b) Inserción en cualquier otro lugar, el elemento nuevo se coloca después de
otro ya existente. Esta operación requiere primero encontrar el lugar donde se
desea insertar el elemento nuevo. Para ello se aplicará la operación de
3
búsqueda que se comentará más adelante. Podemos suponer ahora que la
inserción se va a realizar después del elemento apuntado por un puntero q.
p
Elemento nuevo
(1)
(2)
//
lista
q
Ej.
//Se crea el nuevo elemento y se carga con datos:
p=(struct tlista *)malloc(1*sizeof(struct tlista));
scanf(“%8ld”,
&p->DNI);
fflush(stdin);
scanf(“%24[^\n]”, p->Nombre); fflush(stdin);
scanf(“%3d”,
&p->Edad);
fflush(stdin);
p->psig = q->psig;
q->psig = p;
- Recorrer una lista enlazada. Esta operación consiste en ir accediendo a cada
elemento de la lista de forma secuencial, por ejemplo para ir visualizando todos
los datos de la misma.
Ej. El puntero lista apunta al inicio de la lista:
p = lista; //Comenzar al principio de la lista.
while (p != NULL)
{
printf(“%8ld %25s %3d”, p->DNI,p->Nombre,p->Edad);
p = p->psig; //Avanzar en una lista.
}
- Buscar un elemento de la lista a través de un campo. Se ejecutará un bucle
que finaliza cuando se encuentre el valor buscado o cuando finalice la lista.
Ej. En la lista de los ejemplos anteriores, búsqueda a través de un DNI
tecleado:
scanf(“%8ld”, &DNIBuscado);fflush(stdin);
p = lista; //Comenzar al principio de la lista.
while (p->DNI != DNIBuscado && p != NULL)
p = p->psig; //Avanzar en la lista.
if (p != NULL) //DNI encontrado.
printf(“Nombre:%25s Edad:%3d”, p->Nombre, p->Edad);
4
else
printf(“DNI %8ld no está en la lista”, DNIBuscado);
//Si el elemento es encontrado, queda apuntado por p.
- Borrar un elemento de la lista. Para saber qué elemento debe borrarse,
normalmente se ejecuta una búsqueda como se ha explicado previamente.
Deberá ejecutarse la función free() y con ello liberar la memoria que ocupa el
elemento a eliminar. Existen dos variantes:
a) Borrar el primer elemento de la lista. El puntero al primer elemento de la lista
pasará a apuntar al segundo elemento.
Ej. El elemento a borrar está apuntado por p:
lista = lista->psig;
free(p);
b) Borrar un elemento distinto del primero de la lista. Esta operación afecta al
elemento anterior al que se va a borrar, ya que ese elemento pasará a apuntar
al elemento siguiente al que se va a borrar. Para acceder a ese elemento
anterior, se debe tener un puntero apuntando al mismo. Por ello, en el proceso
de búsqueda, la comprobación del valor que se busca se debe realizar sobre el
elemento siguiente al que se va recorriendo en dicha búsqueda.
Ej. Borrar el elemento cuyo DNI es tecleado:
scanf(“%8ld”, &DNIBuscado);fflush(stdin);
if (lista->DNI == DNIBuscado) //Borra primer elemento
{
p = lista;
lista = lista->psig;
free(p);
}
else //Si no es el primer elemento:
{
p = lista; //Comenzar al principio de la lista.
//El bucle no comprueba el elemento p, sino p->psig
while (p->psig->DNI != DNIBuscado &&
p->psig != NULL)
p = p->psig; //Avanzar en la lista.
if (p->psig != NULL) //DNI encontrado.
{
//p apunta al anterior al elem. a borrar.
q = p->psig;
//q apunta al elem. a borrar.
p->psig = p->psig->psig;
free(q); //Elimina elemento.
}
else
printf(“DNI %8ld no está en lista”, DNIBuscado);
}
5
3. Pilas.
Una pila es un caso particular de una lista enlazada en la que todas las
inserciones y supresiones se realizan siempre por el mismo extremo lista. Se
suele llamar LIFO (Last Input First Output, la última entrada es la primera
salida).
En un pila se mantiene el puntero apuntando al último elemento
añadido, el más nuevo en la pila. El primer elemento de la pila, el más antiguo,
mantiene su puntero con valor NULL. Cada elemento apunta el elemento
añadido previamente, es decir no apunta al siguiente sino al anterior.
Elem.más nuevo
Elem. más antiguo
NULL
pila
Si el puntero pila de la figura vale NULL indica que la pila está vacía.
Añadir o suprimir un elemento implica actualizar ese puntero pila. Por ejemplo,
para añadir un nuevo elemento, éste debe apuntar al que estaba apuntado por
pila y pila apuntará a ese nuevo elemento.
p
Elemento nuevo
(1)
(2)
//
NULL
pila
4. Colas.
Una cola es un caso particular de una lista enlazada en la que todas las
inserciones se realizan por un extremo de la lista y todas las supresiones se
realizan por el otro extremo de la lista. Se suele llamar FIFO (First Input First
Output, la primera entrada es la primera salida).
Se suelen utilizar dos punteros, uno para cada extremo de la cola para
que las operaciones sean más rápidas. Ambos punteros valdrán NULL para
indicar que la cola está vacía. Si ambos punteros tienen el mismo valor y éste
no es NULL, significa que la cola sólo tiene un elemento. Cada elemento
apuntará al siguiente añadido a la cola. El elemento más nuevo tendrá su
puntero con el valor NULL, aunque esto no es necesario ya que al mantener
dos punteros, se puede reconocer en todo momento cuál es el primer y el
último elemento.
Elem. más antiguo
Elem. más nuevo
NULL
Antiguo
Nuevo
6
En la figura vemos cómo el puntero Antiguo apunta al primer elemento
que se añadió a la cola, al más antiguo. El puntero Nuevo apunta al elemento
más reciente añadido a la cola, al más nuevo. Para extraer un elemento de la
cola, se debe actualizar el puntero Antiguo. Para añadir un elemento a la cola
se debe actualizar el puntero Nuevo.
5. Árboles. Árboles binarios.
Las estructuras comentadas previamente son lineales, sin embargo los
árboles son no lineales. Un árbol está formado por una serie de elementos,
llamados nodos que se sitúan en diferentes niveles. Existe un nodo especial
que se denomina raíz, por ser el inicio del árbol y por estar en el nivel 0. Un
puntero al nodo raíz permite el acceso al árbol. Además de la información que
se desee almacenar, cada nodo incluirá una serie de punteros para apuntar a
varios elementos, que pertenecerán al nivel siguiente del árbol. Los punteros
que no se utilicen en un momento dado guardarán el valor NULL. Cada
puntero en uso, que no vale NULL, de un nodo se llama rama. Los nodos que
no apuntan a ningún nodo del siguiente nivel se llaman nodos terminales u
hojas y tendrán el valor NULL en sus punteros. Se puede decir que cada nodo
de un árbol es un nodo raíz de un subárbol del árbol. Como un subárbol es
también un árbol, esta es una definición recursiva, que es un procedimiento
que suele usarse en la programación de árboles.
árbol
nivel 0
raíz
nivel 1
nivel 2
nodo terminal
Como puede deducirse, un árbol sólo puede recorrerse hacia abajo, ya
que no se utilizan punteros que apunten a nodos de niveles superiores,
siempre se apunta a niveles inferiores. Esto quiere decir que si a partir de un
nodo cualquiera se recorre un subárbol, por ejemplo el derecho, y después
partiendo de ese mismo nodo se quiere recorrer otro subárbol, por ejemplo el
izquierdo, la dirección de dicho nodo deberá guardarse, para poder retornar a
ese punto de partida después de realizar el primer recorrido.
5.1. Árboles binarios.
Un árbol binario es un caso particular de árbol en el que cada nodo tiene
dos punteros, con lo que podrá apuntar como máximo a dos nodos del nivel
siguiente del árbol, es decir podrá tener dos ramas como máximo. Cada nodo
apunta a un subárbol izquierdo y un subárbol derecho. Como un subárbol es
un árbol, se suelen aplicar métodos recursivos en su procesamiento. La figura
anterior es un árbol binario.
Ej.
struct tnodo{
7
long DNI;
char Nombre[25];
int Edad;
struct tnodo *pizdo; //Puntero a rama izquierda.
struct tnodo *pdcho; //Puntero a rama derecha.
};
void main(void)
{
struct tnodo *arbol;//Será el puntero al nodo raíz.
arbol = NULL; //De entrada, el árbol está vacío.
...
}
Un tipo especial de árbol binario es aquel que está ordenado por un
determinado campo. Suponiendo por ejemplo que el campo de ordenación es
el DNI, para que el árbol sea ordenado se aplica el siguiente método: un nodo
se colocará apuntado por la izquierda del nodo superior (de nivel superior) si su
DNI es menor que el DNI del nodo superior; si el DNI es mayor, se colocará por
la derecha; este método deberá aplicarse para todos los nodos. Este tipo de
árboles binarios se denomina árboles binarios de búsqueda, ya que la
búsqueda de un elemento cualquiera es muy rápida. En estos árboles todos
los nodos del subárbol izquierdo tendrán un valor (del campo de ordenación)
menor que el del nodo raíz de ese subárbol, así como el subárbol derecho
tendrá nodos cuyo valor será mayor que el del nodo raíz de ese subárbol.
8
EJERCICIOS - CAPITULO 13:
Realizar los siguientes algoritmos en pseudocódigo y en C.
1. Manejar una lista enlazada con el siguiente menú: 1.Añadir elemento;
2.Borrar elemento; 3.Consultar elemento; 4.Finalizar. Al finalizar, grabar
todos los elementos en un fichero binario. Cada elemento tendrá los datos
DNI, Nombre y Edad.
2. Leer el fichero anterior completo y grabarlo en una lista enlazada de forma
que quede ordenada por DNI.
3. Implementar una pila que permita realizar operaciones matemáticas a modo
de calculadora en la que se admitan paréntesis para dar prioridad a ciertas
operaciones sobre otras, por ejemplo: (3 + (5 * 8) – 2) / 4 * (5 * 3).
4. Implementar una cola para mantener las llamadas que se van haciendo con
un teléfono. Cada elemento guardará el número al que se ha llamado y la
duración de la llamada. La cola tendrá como máximo 20 llamadas, de forma
que las nuevas llamadas irán sobrescribiendo a las más antiguas. Se debe
manejar el siguiente menú: 1.Realizar llamada (se solicita el número y debe
contar el tiempo); 2.Eliminar llamada (sólo se podrá eliminar la llamada más
antigua); 3.Consultar todas las llamadas; 4.Salir.
5. Utilizando recursividad y un árbol binario de búsqueda (ordenado por DNI),
manejar el menú siguiente: 1.Añadir elemento; 2.Borrar elemento;
3.Consultar elemento; 4.Finalizar; 5.Salir. Cada elemento tendrá los datos
DNI, Nombre y Edad.
9