Estructuras de Datos Dinámicas:
Listas
Programación I
Departamento de Informática
Universidad Nacional de San Luis
Argentina
2014
Repaso (1)
•
Nociones Generales
–
–
–
–
Agrupación de valores que por razones lógicas,
se quiere conservar ‘juntos’.
Cómo se incorpora un nuevo elemento a la
estructura.
Cómo se elimina o cambia un elemento que ya
está en la estructura.
Cómo se busca un elemento, que ya está en la
estructura, ya sea para conocerlo o
inspeccionarlo, para eliminarlo de la estructura o
para buscarle un lugar a uno nuevo.
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
2
Repaso (2)
•
•
Estos tres últimos aspectos tienen que ver
con las operaciones que pueden hacerse
sobre la estructura de datos: Poner, Sacar,
Inspeccionar.
Orden, con respecto a las operaciones:
Cronológico, No Cronológico.
–
Cómo se guardan los elementos en la estructura,
es decir en qué orden se encuentran unos con
respecto a los otros. Deben tener algún orden o
estructura.
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
3
Repaso (3)
•
•
•
Cuántos elementos se pueden guardar, capacidad
de almacenamiento de la estructura: Estática /
Dinámica.
Identificar o seleccionar los elementos de la
estructura: sin ambigüedad. Selector de la
estructura, Unívoco. Explícito / Implícito.
Tipo de los datos de los elementos de la estructura.
A este tipo de dato le llamaremos tipo de dato base
de la estructura. Simples / Compuestos.
Homogéneo / Heterogéneo.
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
4
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
5
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
6
Estructuras de Datos Dinámicas:
Listas (3)
Operaciones
–
–
–
–
Inserción
Supresión
Copia
Predicados: isEmpty, isFull.
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
7
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
8
Estructuras de Datos Dinámicas:
Listas: Representación gráfica (4)
Acceso a
la lista
Puntero al
siguiente
vipd
•••
A
nil
•••
Elemento i
Cursor
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
9
Cursor
insert con lista vacía
–
isEmpty = true  isOos = true
Z
–
isEmpty = false  isOos = false
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
10
Cursor
insert con lista NO vacía
– isEmpty = false  isOos = false
•••
G
•••
i
i+1
i
•••
–
P
G
•••
isEmpty = false  isOos = false
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
11
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
12
Cursor
suppress con lista NO vacía
– isEmpty = false  isOos = false
•••
Y
T
•••
i
i+1
•••
T
•••
i
–
isEmpty = false  isOos = false
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
13
Cursor
suppress con lista NO vacía
– isEmpty = false  isOos = false
•••
S
D
n
n-1
•••
–
isEmpty = false  isOos = true
Departamento de Unformática - UNSL
S
n-1
Programación I - Estrucutras Dinámicas
14
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
15
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
16
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) {
reset(&x);
while (!isOos(x) && copy(x) != y) {
forwards(&x);
}
if (!isOos(x))
printf(“%c esta en la lista\n”, y);
else
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
17
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
18
Fin … por suerte ... ¿no? ;-)
Departamento de Unformática - UNSL
Programación I - Estrucutras Dinámicas
19
Descargar

Filminas - Programación I - Universidad Nacional de San Luis