Tema 8b > particularizado para el caso de C
Estructura de datos
Una estructura de datos es una colección de datos organizados de una 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 a tamaño, o que esté desperdiciando la mayor parte de él.
Tipos de estructuras de datos
ED estáticas
- Una vez definidas no pueden variar.
- 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 o disminuye según se va ejecutando el programa y varían las necesidades.
¿Estructuras estáticas?
Inconvenientes de las estructuras estáticas (como un vector):
- Tamaño no puede aumentar ni disminuir. Hay que predecir el tamaño necesario.
- Reorganizar la lista de elementos implica mover muchos elementos. Es costoso.
Si tenemos una lista de elementos ordenados y queremos insertar uno nuevo manteniendo el orden:
- Con un 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 en 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 las 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 a¡ 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 a¡, decimos que a¡ precede o es predecesor de a¡+1 y que a¡ sucede o es el sucesor de a¡-1.
Operaciones sobre una lista
Inicializar
Insertar (al principio, al 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 (una lista en otra)
...
Implementación del tipo de datos Lista
La lista nos la implementamos nosotros, así que lo hacemos como queremos 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 al 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 deba contener un elemento de la lista */
}
struct nodo {
struct info elemento;
struct nodo *siguiente;
}
struct nodo *lista;
Inicializar lista
list=NULL;
list=NULL;
Insertar al principio
Void insertarPrincipio (struct nodo **L, struct info *X){
struct nodo *tmp;
tmp=(struct nodo *) malloc (sizeof(struct nodo));
tmp->elemnto=*X;
tmp->siguiente=*L;
*L=tmp;
}
Yo no he trabajado con punteros (solo copiado la teoría) y si no entiendes punteros, no alcanzas esto, esta dando una larga explicación... y yo me estoy quedando igual. Habrá que insistir en un futuro... No temo volver a preguntar cuando este preparada.
Es obligado hacer dibujo!
Deberes: ¿Como harías para insertar un elemento al final de la lista? ¿Como añadir a una posición cualquiera?
0 comentarios:
Publicar un comentario