Estructura
de datos
Una estructura de datos es una
colección de datos organizados de determinada manera.
Ejemplo: Entero real, vector
(de…), registro, matriz, fichero (de…), lista, cola, árbol…
Si tengo que trabajar con
varios datos iguales en memoria, a veces un vector se queda demasiado grande, o
demasiado pequeño.
Si yo tengo un fichero de
datos y quiero pasarlo a memoria para trabajar con él, si uso un vector me
puede ocurrir que sea insuficiente en cuanto al tamaño, o que esté
desperdiciando la mayor parte de él.
Tipos de
estructuras de datos
ED Estáticas
- Una vez definidas no pueden cambiar
- El contenido puede variar, pero no la estructura
- Tamaño fijo, ya sea mediante
- Variables estáticas (tamaño fijado en compilación)
- Variables dinámicas (tamaño fijado en ejecución)
ED Dinámicas
- Podemos cambiar la estructura en cualquier momento
- Tamaño aumenta y disminuye según se va ejecutando el programa y varían las necesidades
¿Estructuras
estáticas?
Inconvenientes de las
estructuras estáticas (como vector):
- El tamaño no puede aumentar ni disminuir. Hay que predecir el tamaño exacto.
- Reorganizar la lista de elementos implica mover muchos elementos. Es costoso.
- Si tenemos una lista de elementos ordenados y queremos insertar uno manteniendo el orden:
- Con vector:
- Primero tenemos que disponer de espacio para el nuevo elemento (y puede ser que no tengamos)
- Segundo tenemos que desplazar todos los elementos que están después de él en el orden para mantenerlo.
- Con una EDD:
- Siempre podemos insertar un nuevo elemento (salvo limitación de recursos)
- Podemos insertar cualquier posición, con coste bajo
Tipos de
EDD
Lineales. Que aumentan su
tamaño en una única dimensión:
- Listas
- Pilas
- Colas
No lineales. Que aumentan su
tamaño en varias dimensiones:
- Árboles
- Grafos
Uso de las
EDD
Las EDD no están directamente
soportadas por el lenguaje. Tenemos que programarlas nosotros.
- Definir las estructuras de datos necesarias
- Implementar las funciones y procedimientos que realicen las operaciones sobre estructuras de datos que hemos definido
El tipo de
datos lista
Concepto. Secuencia
finita de cero o más elementos de un tipo determinado.
a1, a2, an (n>=0)
Cada ai es del tipo de los
elementos de la lista.
n: Longitud de la lista
Si n=0 lista vacía
Si n>=1 a1 es el primer
elemento y an es el último elemento.
Dado un elemento ai, decimos
que ai precede o es predecesor de ai+ y que ai sucede o es sucesor de ai-1.
Operaciones
sobre una lista
Inicializar
Insertar (al
principio, final o en una determinada posición)
Eliminar
Recorrer la lista
Tamaño
Recuperar (información
de una posición concreta)
Localizar (posición
a partir de información)
Copiar (de una
lista a otra)
…
Implementación
del tipo de datos lista
La lista nos la implementamos
nosotros, así que lo hacemos como queramos de acuerdo con nuestras necesidades.
Una opción posible es implementarla
como una lista enlazada
Lista
enlazada
Cada elemento de la lista se
almacena en un nodo, que es una estructura.
Los nodos se identifican por
su posición, que es una dirección de memoria, a la que algo apuntará.
Los nodos contienen un
elemento de la lista y la posición del siguiente nodo.
El nodo que contiene el último
elemento de la lista tiene NULL en el campo “siguiente nodo”.
La lista es un puntero al
primer elemento
Definición
de la lista
struct info {
/* Rellenar con toda la
información que contenga un elemento de la lista
}
struct nodo {
struct info elemento;
struct nodo *siguiente;
}
struct nodo lista*
Inicializar lista
lista=NULL;
Insertar
el principio
void insertarPrincipio (struct nodo **L, struct info *X) {
struct nodo *tmp;
tmp=(struct nodo *)
malloc (sizeof(struct nodo));
tmp->elemento=*X;
tmp->siguiente=*L;
}
Insertar al final de la lista
void insertarFin (struct nodo **L, struct info *x){
struct nodo *tmp;
struct nodo *aux;
tmp=(struct nodo
*)malloc(sizeof(struct nodo));
tmp->siguiente=NULL;
if(*L==NULL) /* Lista
vacía */
*L=tmp;
else { /* Lista con
información */
aux=*L;
while
(aux->siguiente !=NULL)
aux=aux->siguiente;
aux->siguiente=tmp;
}
}
Insertar en posición concreta
(tras nodo determinado apuntado por p)
void insertarPos (struct nodo **L, struct nodo *p, struct info *x) {
struct nodo *tmp;
tmp=(struct nodo
*)malloc (sizeof(struct nodo));
tmp->elemento=*x;
if (L==NULL){ /* Lista
vacía */
tmp->siguiente=NULL;
*L=tmp;
}
else {
tmp->siguiente=p->siguiente;
p->siguiente=tmp;
}
}
Eliminar el elemento apuntado por
p
void eliminar (struct nodo **L, struct nodo *p) {
struct nodo *tmp;
if (*L==p) /* Eliminar
el primer elemento */
*L=p->siguiente;
else {
tmp=*L;
while (tmp->siguiente!=p)
tmp=tmp->siguiente;
/* tmp apunta al anterior */
tmp->siguiente=p->siguiente;
}
free(p);
}
Calcular el tamaño de una lista
Mi solución:
int tamagno (struct nodo **L) {
struct nodo *tmp;
int contador=1;
tmp=*L;
if (*tmp==NULL)
return 0;
else {
while (tmp->siguiente!=NULL) {
contador++
}
}
return contador;
}
Solución del profesor:
int tamagno (struct nodo **L) {
int n;
struct nodo *tmp;
tmp=*L;
n=0;
while (tmp!=NULL) {
n++;
tmp=tmp->siguiente;
}
return (n);
}
Comentario sobre tamagno
Las EDD nos las creamos
nosotros y podemos decidir implementarlas de muy diversas formas.
Si se va a utilizar de forma
intensiva la función tamagno, se puede modificar la implementación para hacer
que esta función sea más eficiente (ya que tener que recorrer cada vez que es
llamada todos los elementos no resulta especialmente eficiente).
Podríamos, por ejemplo,
guardar explícitamente información sobre el número de elementos, de tal manera
que la lista en vez de ser un único puntero al primer elemento, sería un struct
que tendría el número de elementos además del puntero al primer elemento.
En caso de optar por esta
implementación, tendríamos que asegurarnos que esa información se actualiza
adecuadamente cada vez que se inserta o borra un elemento, en las
correspondientes funciones.
Localizar (el primer elemento de
la lista, que tiene un campo entero igual a uno fijado)
struct nodo *localizar(struct nodo**L, int x) {
struct nodo *tmp;
tmp=*L;
while ((tmp!=NULL)
&& ((tmp->elemento).campo_x!=x))
tmp=tmp->siguiente;
return tmp;
}
C realiza una evualuación
cortocircuitada. Es decir, si en el anterior while, por ejemplo, no se cumple
la primera condición, no continúa examinando la segunda.
De otro modo, el anterior código
reventaría porque si fuera NULL intentaría leer el siguiente elemento pasado
NULL, dando un fallo de segmentación.
Ejemplo de utilización
main() {
struct info c;
struct nodo *Lista;
struct nodo *p;
Lista=NULL;
c.campo_x=5;
insertarPrincipio(&Lista,
&c);
c.campo_x=12;
insertarFin(&Lista,
&c);
/* Ver contenido */
p=Lista;
while (p!=NULL){
printf(“%d”,(p->elemento).campo_x);
p=p->siguiente;
}
p=Lista; /* Apunta a “5”
*/
p=p->siguiente; /*
Apunta a “12” */
c.campo_x=56;
/* Voy a insertar tras “12”
*/
insertarPos(&Lista,
p, &c);
p=Lista; /* Apunta a 5
*/
p=p->siguiente; /*
Apunta a 12 */;
/* Voy a eliminar “12”
*/
eliminar(&Lista, p);
}
Listas ordenadas
Listas ordenadas
Si necesitamos una lista
ordenada tenemos dos alternativas:
è Manejar una lista genérica y ordenarla
cuando haga falta (usando algoritmos similares que para ordenar vectores). Se
puede ofrecer una operación de ordenación.
è Mantener una lista ordenada siempre.
Modificaciones necesarias:
·
Insertar.
Ya no hay que indicar la posición. La función deberá encargarse de insertar en
la posición adecuada.
·
Localizar.
Podemos detener la búsqueda cuando encontremos un elemento mayor que el que
buscamos.
Para llevar a cabo lo
anterior, hay que tener en cuenta que mecanismo vamos a utilizar.
Ejemplo de aplicación de las listas
Almacenar un polinomio. En este caso podría ser útil una lista de
estructura del siguiente tipo:
struct info {
int exponente;
float coeficiente;
}
0 comentarios:
Publicar un comentario