Codigos pascal

E.T.S. de Ingeniería Informática (Ing. Informática)

Dpto de Lenguajes y C. de la Computación

V.1.- MÁS SOBRE LISTAS ENLAZADAS.
UNIVERSIDAD DE MALAGA
DPTO. DE LENGUAJES Y C. DE LA COMPUTACION E.T.S. DE INGENIERIA INFORMATICA
INGENIERIA INFORMATICA

En esta sección vamos a analizar otros tipos de listas enlazadas diferentes a la estudiada en el tema II de la asignatura. Además, seabordará la forma en la que las listas enlazadas pueden ser implementadas mediante arrays. En una lista enlazada, si disponemos de un puntero a algún nodo de la misma, podemos acceder a todos los nodos que van a continuación, pero a ninguno de los nodos que le preceden. Para poder acceder a todos los elementos de la lista debemos tener un puntero al comienzo de la misma. Las dos siguientes seccionesaportan diferentes mecanismos para evitar este problema, consiguiendo dos tipos diferentes de listas enlazadas: las listas enlazadas circulares y las listas doblemente enlazadas. V.1.1.- Listas enlazadas circulares. Una lista enlazada circular es una lista enlazada en la que cada nodo tiene un sucesor; el sucesor del “ultimo” nodo es el “primero”. Este tipo de lista se consigue haciendo que el campopuntero del último nodo de la lista apunte al primer nodo en vez de contener el valor NULO. Ahora podemos comenzar en cualquier nodo de la lista y recorrer todos sus nodos. En este tipo de listas, en lugar de disponer de un puntero al primer nodo para acceder a la misma, es más adecuado tener un puntero al último nodo. De esta forma, podemos acceder fácilmente a los dos extremos de la lista.METODOLOGÍA DE LA PROGRAMACIÓN
(CURSO 2006-2007)

TEMA V ESTRUCTURAS DE DATOS V.1.- Más sobre listas enlazadas. V.1.1. Listas enlazadas circulares. V.1.2. Listas doblemente enlazadas. V.1.3. Implementación con arrays V.2.- Pilas. V.2.1. Implementación con punteros. V.2.2. Implementación con arrays. V.2.3. Aplicaciones de las pilas. V.3.- Colas. V.3.1. Implementación con punteros. V.3.2.Implementación con arrays. V.3.3. Aplicaciones de las colas. V.4.- Árboles. V.4.1.- Concepto y terminología V.4.2.- Árboles binarios. V.4.2.1. Recorrido de un árbol binario. V.4.2.2. Implementación. V.4.2.3. Aplicaciones. V.4.3.- Árboles binarios de búsqueda. V.4.3.1. Implementación. V.4.3.2. Aplicaciones. Bibliografía: [DALE89b] [JOYA03]

lista

Una lista enlazada circular vacía se reprenta medianteun valor NULO en el puntero de acceso a la misma, al igual que ocurre con una lista enlazada “simple”.
Metodología de la Programación Tema V. Estructuras de Datos. 1

E.T.S. de Ingeniería Informática (Ing. Informática)

Dpto de Lenguajes y C. de la Computación

E.T.S. de Ingeniería Informática (Ing. Informática)

Dpto de Lenguajes y C. de la Computación

Operaciones básicas. Supondremosla siguiente definición de tipos para todas las operaciones: Tipos NodoNum = REGISTRO num : Z sig : ListaNum FINREGISTRO ListaNum = PUNTERO A NodoNum Recorrido completo de la lista circular.
SI (lista ≠ NULO) ENTONCES ptr ← lista^.sig REPETIR // Procesar ptr^ ptr ← ptr ^.sig HASTA QUE (ptr = lista^.sig) FINSI

Recorrido condicional
SI (lista = NULO) ENTONCES ptr ← NULO SINO ptr ← listaREPETIR ptr ← ptr ^.sig HASTA QUE ((ptr = lista) ∨ Cond) SI (¬Cond) ENTONCES ptr ← NULO FINSI FINSI // o bien ptr apunta al primer nodo que cumple Cond // o bien ningún nodo cumple Cond y ptr vale NULO

Ejemplos: Buscar un nodo en una lista. Devuelve NULO si no está, o bien el puntero a su primera aparación si está.
Func BuscarNodo(↓lista:ListaNum; ↓elem:Z):ListaNum Variables ptr: ListaNum Inicio SI(lista = NULO) ENTONCES ptr ← NULO SINO ptr ← lista REPETIR ptr ← ptr ^.sig HASTA QUE ((ptr = lista) ∨ (elem = ptr^.num)) SI (elem ≠ ptr^.num) ENTONCES ptr ← NULO FINSI FINSI RES ← ptr Fin

Ejemplos: Mostrar la lista por pantalla, contar el número de nodos
Proc Mostrar(↓lista: ListaNum) Variables ptr: ListaNum Inicio SI (lista ≠ NULO) ENTONCES ptr ← lista^.sig REPETIR Escribir(ptr^.num) ptr ←...