• Author / Uploaded
• Anny Haley

Citation preview

Investigar sobre los siguientes conceptos: 1) Colas con prioridades. Una cola de prioridades es un ​tipo de dato abstracto​ similar a una ​cola​ en la que los elementos tienen adicionalmente, una prioridad asignada. En una cola de prioridades un elemento con mayor prioridad será desencolado antes que un elemento de menor prioridad. Si dos elementos tienen la misma prioridad, se desencolaran siguiendo el orden de cola. 2) Declaración e inserción de elementos en colas de prioridad.

● Estructura de los nodos de la cola ● Estructura de la cola ● Crear Nodo Encolar carácter con prioridad -----------------------------------------------------------------------void encolar( struct cola &q, char valor, int priori ) { struct nodo *aux = crearNodo(valor, priori); aux->sgte = NULL; if( q.delante == NULL) q.delante = aux; // encola el primero elemento else (q.atras)->sgte = aux; q.atras = aux;

// puntero que siempre apunta al último elemento

} Insertar caracteres en una cola -----------------------------------------------------------------------void insertar( struct cola &q, char c, int pr ) { /* Encolando caracteres */ encolar( q, c, pr ); }

3) Concepto de listas enlazadas.

Una lista enlazada o estructura ligada, es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y ligas a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura. Las listas enlazadas son estructuras dinámicas que se utilizan para almacenar datos que están cambiando constantemente. A diferencia de los vectores, las estructuras dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de añadir o eliminar información. Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean contiguas; para almacenar la información contienen elementos llamados nodos. Estos nodos poseen dos campos uno para almacenar la información o valor del elemento y otro para el enlace que determina la posición del siguiente elemento o nodo de la lista.

4) Clasificación de las listas enlazadas Listas simples enlazadas básica: Tiene un enlace por nodo, este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo. Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo. Lista doblemente enlazada Lista de dos vías.- Cada nodo tiene dos enlaces 1.- Uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo. 2.- Otro que apunta al nodo siguiente o apunta al valor NULL si es el último nodo Lista enlazadas circulares El primer y último nodo está unido. Podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Vistas como listas sin comienzo ni fin, usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado. Una lista enlazada circular que contiene tres valores enteros. Listas enlazadas circulares simples. Cada nodo tiene un enlace “El siguiente nodo del último apunta al primero” Como es una lista enlazada simple, los

nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Permite rápidas inserciones al principio y también permite accesos al primer nodo desde el puntero de último nodo. Lista enlazada doblemente circular. Cada nodo tiene dos enlaces “Enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo apunta al primero”. Las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin.

5) Tipo de datos abstracto en una lista. Las listas constituyen una estructura exible en particular, porque pueden crecer y acortarse según se requiera; los elementos son accesibles y se pueden insertar y suprimir en cualquier posición de la lista. I. .as listas también pueden concatenarse entre sl o dividirse en sublistas; se presentan de manera rutinaria en aplicaciones como recuperación de información, traducción de lenguajes de programación y simulación. Las técnicas de administración de memoria del tipo de las que se analizan en el capítulo l2 hacen uso extensivo de técnicas de procesamiento de listas. En esta sección se presentarán algunas operaciones básicas con listas, y en el resto del capitulo se presentarán estructuras de datos para representar listas que manejan con e- ciencia varios subconjuntos de estas operaciones.

6) Cómo se accede a los datos de una lista. Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un índice sino mediante un puntero. En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista. Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.

7) Construcción de una lista Para establecer un elemento de la lista, será utilizado el tipo struct. El elemento de la lista tendrá un campo dato y un puntero siguiente. El puntero siguiente tiene que ser del mismo tipo que el elemento, si no, no podrá

apuntar hacia el elemento. El puntero siguiente permitirá el acceso al próximo elemento. typedef struct ElementoLista { char *dato; struct ElementoLista *siguiente; }Elemento; Para tener el control de la lista es preferible guardar determinados elementos: el primer elemento, el último elemento, el número de elementos. Para ello será empleado otra estructura (no es obligatorio, pueden ser utilizadas variables). typedef struct ListaIdentificar { Elemento *inicio; Elemento *fin; int tamaño; }Lista; El puntero inicio tendrá la dirección del primer elemento de la lista. El puntero fin albergará la dirección del último elemento de la lista. La variable tamaño contiene el número de elementos. Cualquiera sea la posición en la lista, los punteros inicio y fin apuntan siempre al primer y último elemento. El campo tamaño contendrá al número de elementos de la lista cualquiera sea la operación efectuada sobre la lista. 8) Como puedo insertar datos en una lista. Inserción de un elemento en la lista A continuación el algoritmo de inserción y el registro de los elementos: declaración del elemento que se va a insertar, asignación de la memoria para el nuevo elemento, llena el contenido del campo de datos, actualización de los punteros hacia el primer y último elemento si es necesario. Caso particular: en una lista con un único elemento, el primero es al mismo tiempo el último. Actualizar el tamaño de la lista

Para añadir un elemento a la lista se presentan varios casos: la inserción en una lista vacía, la inserción al inicio de la lista, la inserción al final de la lista y la inserción en otra parte de la lista. Inserción en una lista vacía Ejemplo de la función: int ins_en_lista_vacia (Lista *lista, char *dato);

9) Búsquedas en listas enlazadas Visualización de la lista Para mostrar la lista entera hay que posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego usando el puntero siguiente de cada elemento la lista es recorrida del primero al último elemento. La condición para detener es proporcionada por el puntero siguiente del último elemento que vale NULL. void visualización (Lista * lista) { Element *actual; actual = lista->inicio; while (actual != NULL){ printf ("%p - %s\n", actual, actual->dato); actual = actual->siguiente; } }

10)Cómo recorrer una lista circular Si la lista no está vacía disponemos un puntero en el primer nodo y utilizamos un do/while para recorrer la lista. La condición del do/while es que se repita mientras el puntero reco sea distinto a raiz (es decir que no haya dado toda la vuelta a la lista).