Ejemplo de proyectos de software

Algoritmos y Estructuras de Datos

3. Estructuras de Datos Básicas

3.3. Listas

Introducción

Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga.
Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo deinformación si este existe.
Un apuntador es la dirección de memoria de un nodo
La figura siguiente muestra la estructura de un nodo:

El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de la lista. Si el nodo fuera el último, este campo recibe como valor NIL (vacío).
A continuación se muestra el esquema de una lista :

Forma de declarar una listaenlazada

struct nodo {
char dato[10];
struct nodo *link;
};

struct nodo *lista; /* lista es un puntero a nodo*/

Ej. Referenciar un miembro de nodo:

lista->dato =”hola”;
lista->link = NULL; */ lista está apuntando a vacío*/

Inicialización y Borrado de variables de tipo Puntero

Cuando se quiere usar una variable tipo puntero no basta sólo condeclararla, es necesario asignarle un espacio en memoria. La funcion new, asigna almacenamiento para una variable de un tipo determinado y guarda la dirección de la celda de memoria en la variable.

Ej. Asignación de memoria para un nodo: lista = new nodo;

Por otro lado, cuando la variable se deja de usar, se debe liberar la posición de memoria ocupada por la variable, para ello se utiliza elprocedimiento delete.

Ej. Libera la posición de memoria ocupada por un nodo: delete lista;

Operaciones en Listas Encadenadas

Las operaciones que podemos realizar sobre listas encadenadas son las siguientes:
• Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista. Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor delcampo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
• Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
o Insertar un nodo al inicio.
o Insertar un nodo antes o después de cierto nodo.
o Insertar un nodo al final.• Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
o Eliminar el primer nodo.
o Eliminar el último nodo.
o Eliminar un nodo con cierta información.
o Eliminar el nodo anterior o posterior al nodo cierta con información.
• Búsqueda. Esta operaciónconsiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.

Algoritmos sobre listas lineales

Las listas lineales encadenadas siempre deben mantener un puntero al inicio el cual se llama raiz o tope. Se usará la variable TOP para referenciar al primer nodo de la lista y TOP->dato y TOP->link para hacer referencia al dato almacenado y al link alsiguiente nodo respectivamente.

struct nodo {
char dato;
struct nodo *link;
};

Algoritmo de Creación

struct nodo *Crea_lista_final()/*donde p es de tipo puntero a nodo}*/
{ struct nodo *p, *top, *q; /*top es un puntero al inicio de la lista de nodos*/
int respuesta; /*q es de tipo puntero a nodo*/
TOP = NULL;
respuesta = 1;
while (respuesta)  {  p = new nodo;
cout > p->dato;
     if (top == NULL)
     { top = p;
q = p;}
     else
     { q->link = p;
      p->link = NULL;
      q = p; }
     cout > respuesta;
}
return(top);
}

struct nodo *Crea_lista_inicio()/*donde p es de tipo puntero a nodo}*/
{ struct nodo *top; /*top es un puntero al inicio de la lista de nodos*/
int respuesta;...