Lineas

Estructuras Lineales


Contenido


• Listas Simples

• Listas Múltiplemente Enlazadas

• Pila – Stack

• Cola - Queue

Listas Simples


Una lista simple es una secuencia de 0 o más elementos de un tipo de datos determinado. Este tipo de datos se llama el tipo de elemento:

a1, a2, a3, ..., an-1, an

El valor de n es mayor o igual a 0 y cada elemento aies del tipo de elemento. El número n es la cantidad de elementos de la lista y se denomina longitud de la lista. Si n ( 1 se denomina a1 el primer elemento y an el último elemento de la lista. Si n = 0, se tiene una lista vacía, en este caso la longitud es igual a 0.

Una propiedad importante de una lista es que sus elementos pueden estar ordenados según algún criterio. En estos casos aiprecede a ai+1; n = 1, 2, ..., n-1 y ai sucede a ai-1; i = 2, 3, ..., n.

Cada elemento de una lista tiene una posición: el elemento ai está en la posición i. De esta forma, cada elemento tiene una distancia del primer elemento de una lista. El elemento ai tiene la distancia i-1 del primer elemento de una lista. La posición fin(lista) es la posición que sucede a la posición del último elemento de lalista. La posición fin(lista) tiene una distancia variable con respecto al principio de la lista. Esto se debe a que la lista es una estructura de datos en la cual se agregan y se eliminan elementos.

Operaciones representativas de listas son:

• crear una lista

• insertar un elemento

• localizar un elemento

• recuperar la información de un elemento

•eliminar un elemento

• determinar el siguiente elemento o elemento anterior

Detalles sobre el TDA de listas se puede encontrar en la sección 2.1 del texto guía.

Listas se programan con arreglos, con cursores o con punteros. Cada una de estas formas tiene ventajas y desventajas. Es la aplicación específica que permite tomar la decisión sobre como programar una lista.

La utilización dearreglos y cursores se presenta muy bien la sección 2.2 del texto guía.

A continuación se presentan 10 funciones que implementan una lista enlazada por punteros. Primero se declara una estructura que contiene dos campos: dato y puntero. El campo dato permite almacenar un número entero en cada elemento de la lista y el campo puntero permite enlazar los elementos de la lista.
struct nodo
{typedef int tipo;
tipo dato;
nodo *puntero;
};

La definición del tipo tipo a través de typedef permite programar listas con diferentes tipos de datos para los elementos. En este caso los elementos son del tipo int. Si se requiere una lista con elementos de otro tipo, hay que modificar esta declaración de tipo.

En seguida se presentan 10 funciones que permiten procesar una lista:1. listaLargo

2. listaInsertaPrimero

3. listaInserta

4. listaBusca

5. listaLocaliza

6. listaPrimeroRemover

7. listaRemover

8. listaBorrar

9. listaCopiar

10. listaCopiarParte


int listaLargo(nodo* ptrCabecera)
// Precondición: ptrCabecera es el puntero al primer elemento de una lista
// Postcondición: Se retorna el valor de lacantidad de elementos de la lista
// La lista no es modificada
{ nodo *ptr;
int largo;
largo = 0;
for (ptr = ptrCabecera; ptr != NULL; ptr = ptr->puntero)
largo++;
return largo;
}


void listaInsertarPrimero(nodo*& ptrCabecera, const nodo::tipo& valor)
// Precondición: ptrCabecera es el puntero al primer elemento de una lista
// Postcondición: Un nuevo nodocon el valor dado ha sido agregado al comienzo de la lista
// ptrCabecera apunta ahora al nuevo primer elemento de la lista
{ nodo *ptrNuevo;
ptrNuevo = new nodo;
ptrNuevo->dato = valor;
ptrNuevo->puntero = ptrCabecera;
ptrCabecera = ptrNuevo;
}


void listaInsertar(nodo* ptrPrevio, const nodo::tipo& valor)
// Precondición: ptrPrevio es el puntero a un...