papito

Semana 7
PRIMERA UNIDAD 2
Competencias
Reconocimiento de las diferencias entre estructuras estáticas y dinámicas
Aplicar tipos de datos de acuerdo a la complejidad.
Manipular operaciones enlas estructuras internas
Contenido
Estructuras dinámicas lineales: listas. Fundamentación. Clasificación de listas enlazadas. Listas simples y operaciones. Inserción de un elemento en una lista.Búsqueda en listas enlazadas. Eliminación de un nodo en una lista. Lista ordenada.

.
Mapa Conceptual



















ESTRUCTURA DE DATOS DINAMICAS LINEALES
1. LISTAS ENLAZADASEs una colección de elementos enlazados dispuestos uno detrás de otros en la que cada elemento se conecta al siguiente, la idea es tener un conjunto de elementos llamados nodos, en las cualescontienen la dirección de un nodo y el elemento almacenado. Así como se muestra en la siguiente figura



2. CLASIFICACION DE LAS LISTAS ENLAZADAS
a. Listas simplemente enlazadas

primerob. Listas doblemente enlazadas
primero



c. Listas circular simplemente enlazadas

primero





d. Listas circularmente enlazadas
primero




3.ESPECIFICACIÓN FORMAL DE UN TAD DE UNA LISTA
Matemáticamente una lista es una secuencia de ceros o más elementos de un determinado tipo de elemento:
(a1,a2,a3,a4…..an) donde n˃= 0
Si n=0 lista es vacíaPara formalizar el tipo de dato abstracto de una lista a partir de la notación matemática, se define un conjunto de operaciones básicas con objetos de tipo lista las operaciones son:

L Lista xLista p puntero

listaVacia (L)
esvacia(L)
insertar(L,x,p)
localizar(L,x)
suprimer(L,x)
anterior(L,p)
primero(L)
anula(L)
insertarPrimero(L,x)
insertarFinal(L,x)

Una operaciónde toda estructura de datos es recorrer, consiste en visitar cada nodo de la lista.


4. OPERACIONES EN LISTAS ENLAZADAS

La implementación del TAD de una lista requiere, primer lugar...