unidad 8 tipos de datos dinámicos: punteros€¦ · unidad 8 lista enlazada simple: nodo struct...

$: UNIDAD 8 Tipos de datos dinámicos: Punteros€¦ · UNIDAD 8 Lista Enlazada Simple: Nodo struct nodo{ tipo_de_dato valor; struct nodo* sgte; } Declaración de un nodo: Vamos a representar$
UNIDAD 8 Tipos de datos dinámicos: Punteros

Asignación dinámica de memoria. Uso de punteros. Inicialización y asignación de punteros. Procedimientos para asignación y liberación de memoria. Tipos de datos recursivos. Listas enlazadas con punteros. Pilas. Colas.

UNIDAD 8 Estructuras Dinámicas de Datos

Estructuras cuyo tamaño (en longitud o en numero de elementos) varia en el tiempo de ejecución.

UNIDAD 8 Lista Enlazada Simple

Cada nodo contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor.

UNIDAD 8 Lista Enlazada Doble

Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor.

UNIDAD 8 Lista Circular Simplemente Enlazada

Una lista enlazada simplemente en la que el último elemento se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular.

UNIDAD 8 Lista Circular Doblemente Enlazada

Una lista doblemente enlazada en la que el ultimo elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular.

UNIDAD 8 Lista Enlazada Simple

UNIDAD 8 Lista Enlazada Simple: Definición

Colección o secuencia de elementos

dispuestos uno detrás de otro, en la que

cada elemento se conecta al siguiente

elemento por un «enlace» o «puntero»

NODO

UNIDAD 8 Lista Enlazada Simple: Nodo

- Contiene la información que queremos almacenar en la lista.

- Es un puntero que apunta al siguiente elemento en la lista.

- Almacena un dato de cualquier tipo.

UNIDAD 8 Lista Enlazada Simple: Nodo

struct nodo{

tipo_de_dato valor;

struct nodo* sgte;

}

Declaración de un nodo:

Vamos a representar un nodo mediante una estructura con dos campos:

Campo valor: Para almacenar el elemento de la lista.

Campo sgte: Puntero que permite el acceso al siguiente elemento de la lista.

UNIDAD 8 Lista Enlazada Simple: Ejemplo

struct nodo{

int valor;

struct nodo* sgte;

};

typedef struct nodo NODO;

Ejemplo: Lista de elementos enteros.

a) La lista tiene elementos:

Necesitamos un puntero que indique el inicio de la lista.

El puntero siguiente del último elemento debe indicar el fin de la lista = NULL.

UNIDAD 8 Lista Enlazada Simple: Ejemplo

struct nodo{

int valor;

struct nodo* sgte;

};

typedef struct nodo NODO;

Ejemplo: Lista de elementos enteros.

b) La lista no tiene elementos:

El inicio no apunta a nadie = NULL.

Operaciones

Agregar un elemento en la lista

Eliminar un elemento de la lista

Cantidad de elementos de la lista

Mostrar lista

Buscar un elemento en la lista

UNIDAD 8 Lista Enlazada Simple: Operaciones

Inicializar lista

Lista vacía?

UNIDAD 8 Lista Enlazada Simple: Inicializar

Deseamos inicializar la lista en vacío. main(){

NODO* ini;

inicializar(&ini);

}

El modulo inicializar tiene un parámetro: inicio que recibe la dirección de la variable ini.

inicio Puntero que apunta a un NODO: NODO* inicio

Que además será modificado: NODO* *inicio

Indica el inicio de la lista

UNIDAD 8 Lista Enlazada Simple: Inicializar

RAM

inicio

ini 101 =*inicio

101

NULL El modulo debe asignar NULL a ini, lo que equivale a hacer *inicio=NULL.

UNIDAD 8 Lista Enlazada Simple: Agregar

Al inicio de la lista. INSERCION

Ordenada

Desordenada

Al final de la lista.

Antes de un elemento.

Después de un elemento.

UNIDAD 8 Agregar al Inicio

Deseamos insertar el elemento llamado elem en la lista enlazada. Como las inserciones se realizaran al inicio de la lista, la variable ini se modificara. main(){

NODO* ini;

scanf(«%i»,&elem);

agregar(&ini, elem);

}

El modulo agregar tiene dos parámetros:

El inicio de la lista, que recibe la dirección de ini y será modificado: NODO* *inicio;

El elemento a insertar: int e;

UNIDAD 8 Agregar al Inicio: Casos

UNIDAD 8 Agregar al inicio en lista vacía

1. Gestionar espacio para almacenar un nuevo nodo.

RAM

inicio

ini 101

101

NULL

=*inicio

nuevo

1101

1101

*nuevo

elem

7

e

7



2. Asignar valores al nuevo nodo.

RAM

inicio

ini 101

101

NULL

=*inicio

nuevo

1101

1101

*nuevo

7 NULL

elem

7

e

7


RAM

inicio

ini 101

101

NULL

=*inicio

nuevo

1101

1101

*nuevo

7 NULL

1101

elem

7

e

7



3. Actualizar el inicio de la lista.

UNIDAD 8 Agregar al inicio en lista no vacía

RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010


nuevo

*nuevo 110

110

RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110



4 100



RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110

4 100



3. Actualizar el inicio de la lista.

110

UNIDAD 8 Lista Enlazada: Agregar al incio



Ordenada

Desordenada




UNIDAD 8 Agregar al Final

Deseamos insertar, al final de la lista, el elemento llamado elem. Es posible que la variable ini sea modificada.

main(){

NODO* ini;


agregar(& ini, elem);

}

El modulo agregar tiene dos parámetros:

El inicio de la lista, que recibe la dirección de ini y puede ser modificado: NODO* *inicio;


UNIDAD 8 Agregar al Final: Casos

UNIDAD 8 Agregar al final en lista no vacía

RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010


nuevo

*nuevo 110

110


RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110



4 NULL


RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110

4 NULL



3. Recorrer la lista hasta llegar al final.

i 100

1010 1000


RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1 1010

3 1000

7

100

1000

1010

nuevo

*nuevo 110

110

4 NULL



3. Recorrer la lista hasta llegar al final.

4. Modificar el final de la lista, para que apunte al nuevo nodo.

i

1000

110

UNIDAD 8 Lista Enlazada: Agregar al Final



Ordenada

Desordenada




UNIDAD 8 Agregar Ordenado

Deseamos insertar el elemento llamado elem en la lista enlazada de manera ordenada. La variable ini podrá ser modificada.

main(){

NODO* ini;


agregar(& ini, elem);

} El modulo agregar tiene dos parámetros:

El inicio de la lista, que recibe la dirección de ini y será modificado: NODO* *inicio;


UNIDAD 8 Agregar Ordenado: Casos

UNIDAD 8 Agregar Ordenado: al final

NULL


NULL

UNIDAD 8 Agregar Ordenado: entre nodos

NULL

RAM

inicio

ini 101

101

100

=*inicio

elem

0

e

0

-1 1010

3 1000

7 NULL

100

1000

1010


nuevo

*nuevo 110

110


RAM

inicio

ini 101

101

100

=*inicio

elem

0

e

0

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110



0


RAM

inicio

ini 101

101

100

=*inicio

elem

0

e

0

-1 1010

3 1000

7 NULL

100

1000

1010

nuevo

*nuevo 110

110

0



3. Recorrer la lista hasta llegar a la posición de inserción.

i 100

1010


ant

NULL 100

RAM

inicio

ini 101

101

100

=*inicio

elem

4

e

4

-1

3 1000

7

100

1000

1010

nuevo

*nuevo 110

110

0



3. Recorrer la lista hasta llegar a la posición de inserción.

4. Establecer el enlace con el nuevo nodo.

i

1010

NULL


ant

100

1010 110

UNIDAD 8 Agregar Ordenado

UNIDAD 8 Lista Enlazada: Mostrar

Deseamos mostrar los elementos de la lista enlazada, por lo que se recorre la lista partiendo del inicio indicado por ini.

main(){

NODO* ini;

mostrar( ini);

}

El modulo mostrar tiene un parámetro:

El inicio de la lista, que recibe la dirección de ini: NODO* inicio;


NULL

i es NULL , fin de la lista !!


RAM

inicio

ini 101

110

-1 1010

3 1000

7 NULL

100

1000

1010

110

4 100 110

1. Ubicarse al inicio de la lista.

i

110


RAM

inicio

ini 101

110

=*inicio

-1 1010

3 1000

7 NULL

100

1000

1010

110

4 100 110


2. Recorrer la lista, mostrando sus elementos, hasta el final.

i 110

100

1010

1000 NULL

Mostrar 4

Mostrar -1

Mostrar 3

Mostrar 7

UNIDAD 8 Lista Enlazada: Eliminar

Deseamos eliminar un elemento llamado elem de la lista enlazada. Es posible que la variable ini sea modificada.

main(){

NODO* ini;


eliminar(& ini, elem);

}

El modulo eliminar tiene dos parámetros:

La dirección del inicio de la lista, que podrá ser modificada: NODO* *inicio;

El elemento a eliminar: int e;

UNIDAD 8 Eliminar: Casos

NULL

UNIDAD 8 Eliminar: Casos

RAM

inicio

ini 101

101

=*inicio

1101

-1 NULL

1101

elem

-1

e

-1


UNIDAD 8 Eliminar: el único elemento NULL

i

ant

1101

NULL

RAM

inicio

ini 101

101

=*inicio

1101

-1 NULL

NULL

elem

-1

e

-1


2. Modificar el inicio.

UNIDAD 8 Eliminar: el único elemento NULL

i

ant

1101

NULL

1101

UNIDAD 8 Eliminar: el primer elemento

RAM

inicio

ini 101

101

100

=*inicio

elem

-1

e

-1

-1 1010

3 1000

7

100

1000

1010


i

100

NULL ant

NULL

UNIDAD 8 Eliminar: el primer elemento

RAM

inicio

ini 101

101

100

=*inicio

elem

-1

e

-1

-1 1010

3 1000

7

100

1000

1010


2. Modificar el inicio.

i

100

NULL ant

NULL

1010

UNIDAD 8 Eliminar: el ultimo elemento

RAM

inicio

ini 101

101

100

=*inicio

elem

7

e

7

-1 1010

3 1000

7

100

1000

1010


i

100

NULL ant

NULL


RAM

inicio

ini 101

101

100

=*inicio

elem

7

e

7

-1 1010

3 1000

7

100

1000

1010


2. Avanzar hasta encontrar el elemento a eliminar.

i

NULL

ant

1010

1000 100

NULL

100

1010


RAM

inicio

ini 101

101

100

=*inicio

elem

7

e

7

-1 1010

3

7

100

1000

1010



3. Modificar el final.

i

NULL

ant

1010

1000

NULL

RAM

inicio

ini 101

101

100

=*inicio

elem

3

e

3

-1 1010

3 1000

7

100

1000

1010


i

100

NULL ant

NULL

UNIDAD 8 Eliminar: un elemento


RAM

inicio

ini 101

101

100

=*inicio

elem

3

e

-1 1010

3 1000

7

100

1000

1010



i

NULL

ant

100

1010 3 100

NULL


RAM

inicio

ini 101

101

100

=*inicio

elem

e

-1

7

100

1000

1010



3. Modificar enlaces.

i

ant

1010

100

1010

3

3

NULL

3 1000

1000 1010

UNIDAD 8 Lista Enlazada: Eliminar

unidad 8 tipos de datos dinámicos: punteros€¦ · unidad 8 lista enlazada simple: nodo struct...

Documents