PDF de programación - Estructuras de Datos Dinámicas: Listas - Teoría: Programación I

Estructuras de Datos Dinámicas:

Listas

Teoría: Programación I

http://proguno.unsl.edu.ar

[email protected]

Listas

• Capacidad: dinámica
• Orden: no cronológico. El orden puede ser

definido por el programador. Ej. Orden
alfabético, orden numérico, etc…

• Implementaciones:

– Listas estáticas
– Listas dinámica

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

2

Estructuras de Datos Dinámicas:

Listas (1)

• Capacidad: dinámica, crece y disminuye con las

inserciones y supresiones

• Orden: No tiene orden cronológico de

inserción o supresión.
Secuencia.

•

–

unidireccional, 1º  último

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

3

Estructuras de Datos Dinámicas:

Listas (2)

• Elementos de una lista unidireccional o

secuencia, llamados nodos, constan de dos
partes:
•

Variable de Información Propiamente Dicha
(VIPD)
puntero al elemento (nodo) siguiente en la
lista.
último elemento, el puntero no apunta a un
elemento y se dice que su valor es nil

•

•

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

4

Estructuras de Datos Dinámicas:

Listas (3)

Operaciones sobre la lista

– Inserción
– Supresión
– Copia
– Predicados: isEmpty, isFull

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

5

Estructuras de Datos Dinámicas:

Listas (4)

• Selector de la lista: implícito  cursor

• Operaciones sobre el cursor de la lista

– Ir al primero: reset
– Avanzar: forwards
– Predicado:

Fuera de la estructura (cursor = nil): isOos

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

6

Estructuras de Datos Dinámicas:
Listas: Representación gráfica (4)

Acceso a
la lista

vipd

Puntero al
siguiente

nil

• • •

A

• • •

Elemento i

Cursor

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

7

Cursor

insert con lista vacía

– isEmpty = true  isOos = true

– isEmpty = false  isOos = false

Z

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

8

Cursor

insert con lista NO vacía

– isEmpty = false  isOos = false

• • •

G

• • •

i

i

i + 1

• • •

P

G

• • •

– isEmpty = false  isOos = false

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

9

Cursor

insert con lista NO vacía

– isEmpty = false  isOos = true

• • •

7

• • •

• • •

7

• • •

4

– isEmpty = false  isOos = false

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

10

Cursor

suppress con lista NO vacía

– isEmpty = false  isOos = false

• • •
i

Y

T

• • •

i + 1

• • •
i

T

• • •

– isEmpty = false  isOos = false

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

11

Cursor
suppress con lista NO vacía

– isEmpty = false  isOos = false

• • •

S

D

n

n - 1

– isEmpty = false  isOos = true

• • •

S

n - 1

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

12

Cursor
suppress con lista NO vacía

– isEmpty = false  isOos = false

R

– isEmpty = true  isOos = true

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

13

Tipo de Datos Abstracto (TDA) (1)

Ejemplo de uso (1)

#include “list_of_int.h”
...
/**** Imprime lista de enteros ****/
void printListaInt (list_of_int x) {

reset(&x);
while (!isOos(x)) {

printf("%d ", copy(x));
forwards(&x);

}
printf("\n");

} /* fin de printListaInt */

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas y TDA

14

Tipo de Datos Abstracto (TDA) (2)

Ejemplo de uso (2)

#include “list_of_char.h”
...
/* ***** Buscar en lista de char ***** */
void buscaListaChar(list_of_char x, char y) {

forwards(&x);

reset(&x);
while (!isOos(x) && copy(x) != y) {
}
if (!isOos(x))
else

printf(“%c esta en la lista\n”, y);
printf(“%c NO esta en la lista\n“, y);

} /* fin de buscaListaChar */

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas y TDA

15

Tipo de Datos Abstracto (TDA) (3)

Ejemplo de uso (3)

#include “list_of_int.h”
...
/* ****** Copiar lista de int ****** */
void copiaListaInt (lista_of_int *x,
lista_of_int y) {

reset(&y);
while (!isOos(y)) {
insert(x, copy(y));
forwards(&y);

}

} /* fin de copiaListaInt */

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas y TDA

16

¿Pensemos?

• ¿Es posible implementar una Pila dinámica?
• ¿Y una Fila?
• ¿Cómo implemento la lista en forma

dinámica? Memoria?

¿Cómo?

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámicas

17

Programación I
Datos Recursivos

http://proguno.unsl.edu.ar

[email protected]

Definiciones recursivas

Repaso

• La definición de un concepto es recursiva si

el concepto es definido en términos de sí
mismo.

• En una definición recursiva, en general,

distinguimos dos partes:
– Caso(s) base o elemental(es).
– Definición recursiva o caso general.

19

Recursividad en Computación

Repaso

• Se encuentra presente en:

–Definiciones recursivas de módulos.
–Definiciones recursivas de datos.

20

Definiciones Recursivas de Datos

• Ejemplo 1: Definición recursiva de una lista

elemento seguido de una Lista (Caso General)

Lista

Lista vacía (Caso base)

21

Definiciones Recursivas de Datos

• Ejemplo 2: Definición recursiva de un árbol

binario

Árbol derecho + Árbol izquierdo (Caso Gral.)

Árbol

Árbol vacío (Caso base)

22

Datos Recursivos en C

• Diversas estructuras de datos pueden ser

implementadas por medio de datos recursivos.

• En esta materia:

– Listas
– Pilas
– Colas

23

Datos Recursivos en C

• Se pueden implementar en C por medio de
structs que se autoreferencian por medio de
campos de tipo puntero.

24

Datos Recursivos en C - LISTAS
struct nodo{
char vipd;
struct nodo *siguiente;
};
• Cada struct nodo es un registro con dos
campos (vipd y siguiente), que tiene la
siguiente pinta:

‘A’

vipd

siguiente

25

Datos Recursivos en C -LISTAS
struct nodo{
char vipd;
struct nodo *siguiente;
};
• Podemos también representar gráficamente un
struct nodo de la forma que estamos más
habituados:

siguiente

26

‘A’

vipd

Datos Recursivos en C -LISTAS

struct nodo{
char vipd;
struct nodo *next;
}
typedef struct nodo Nodo;
typedef Nodo * list_of_char;
list_of_char lis = NULL;/*lista vacia*/

lis

27

Datos Recursivos en C -LISTAS
 ¿Nos basta con definir el tipo list_of_char como
Nodo *?
 Sí y no

• Si, porque es una posible representación para una lista.
– No, porque queremos implementar las listas
unidireccionales tal como lo hemos venido
haciendo, es decir, necesitaremos mantener
información no solo sobre el acceso a la lista sino
también sobre sus cursores.

28

Implementación de un TDA para

Listas Unidireccionales
– 1) Definir el tipo de dato para soportar las listas.
– 2) Definir las funciones típicas para operar con las listas y

a partir de las cuales podremos definir nuevas funciones:

– init
– isEmpty
– isFull
– reset
– forward
– isOos
– copy
– insert
– suppress

29

Implementación de un TDA para

Listas Unidireccionales

• 1) Definición del tipo de dato

– Para soportar una lista unidireccional tal como lo
hemos venido haciendo necesitaremos mantener
información sobre:
• Acceso a la lista
• Cursor de la lista
• Cursor auxiliar

30

Implementación de un TDA para

Listas Unidireccionales

struct nodo{

tipoBase vipd;
struct nodo *next;

};
typedef struct nodo Nodo;
typedef struct {

Acá vendrá el tipo de
los elementos de la

lista

Nodo *acc;
Nodo *cur;
Nodo *aux; /* cursor auxiliar */

/* acceso a la lista */
/* cursor de la lista */

} List_of_char;

31

Implementación de un TDA para
Listas Unidireccionales de char
struct nodo{
char vipd;
struct nodo *next;

tipo List_of_char para

En este caso estamos definiendo el

};
typedef struct nodo Nodo;
typedef struct {

soportar listas de caracteres, pero

podrían ser listas de cualquier
tipo simple o estructurado, por
ejemplo fechas, como se ve en la

próxima transparencia.

Nodo *acc;
Nodo *cur;
Nodo *aux; /* cursor auxiliar */

/* acceso a la lista */
/* cursor de la lista */

} List_of_char;

32

Implementación de un TDA para
Listas Unidireccionales de Fecha
#include Fecha.h /* TDA Fecha */
struct nodo{
Fecha vipd;
struct nodo *next;

En este caso estamos

definiendo el tipo

ListaDeFechas para
soportar listas cuyo tipo base
es el tipo Fecha, definido en el

};
typedef struct nodo Nodo;
typedef struct {

TDA Fecha

Nodo *acc;
Nodo *cur;
Nodo *aux; /* cursor auxiliar */

/* acceso a la lista */
/* cursor de la lista */

} ListaDeFechas;

33

Implementación de un TDA para
Listas Unidireccionales de char

• 2) Definición de las operaciones del TDA:

– init
– reset
– forwards
– isOos
– copy
– insert
– suppress
– isEmpty
– isFull

34

Implementación de un TDA para
Listas Unidireccionales de char

Inicialización de la lista (en vacío)
void init(list_of_char *l){
(*l).acc = NULL;
(*l).cur = NULL;
(*l).aux = NULL;

}

acc

cur

aux

35

Implementación de un TDA para
Listas Unidireccionales de Fecha
Inserción de una fecha en la posición apuntada por el cursor

void insert(list_of_char *l, char c);

nuevo elemento a insertar (un caracter, en este caso):

• Necesitaremos, entre otras cosas, pedir espacio al compilador para el
•malloc(n) /* asigna n bytes de memoria y devuelve el
puntero a la dirección del lugar asignado, sino retorna NULL.
*/

• ¿Cuántos bytes pedimos?

•sizeof(Tipo) /* devuelve el tamaño en bytes ocupado
por un objeto de datos de tipo T. */

36

Implementación de un TDA para
Listas Unidireccionales de Fecha

Supresión de la fecha corriente (apuntada por el cursor)

void suppress(list_of_char *l);

• Necesitaremos, entre otras cosas, devolver el espacio liberado:

•free(vble-ptr);
Devuelve al sistema los bytes apuntados por vble-ptr.

37

Fin … por suerte ... ¿no? ;-)

Departamento de Unformática - UNSL

Programación I - Estrucutras Dinámic