List As

LISTAS

En Ciencias de la Computación, una lista es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Los nodos de una lista enlazada no ocupan posiciones contiguas en memoria. EL tamaño de la estructura puede aumentar y disminuir durante la ejecución del programa. Si la lista está vacía, comienzo es NULL. La lista se considera llena cuando no existe espacio disponible para crear una variable dinámica de tipo nodo. No todos los lenguajes de programación permiten la implementación de las listas enlazadas dinámicas.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Independientemente del tipo de lista que estamos utilizando, tendría una serie de funciones que hay que realizar sobre la misma: Crear un nodo (reservar memoria y guardar información). Insertar un nodo (enlazarlo). Borrar un nodo (quitar enlaces y liberar memoria). Recorrer la lista. Buscar un elemento en la lista. Para cada tipo de lista hay que realizar cada una de estas funciones

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

ESTRUCTURA DE LISTAS • Una estructura de datos Lista es una secuencia conectada de nodos, cada uno de los cuales contiene algún dato. • Hay un nodo al comienzo llamado la cabeza o frente (head o front). • Hay un nodo de término llamado la cola o atrás (tail o back). • Una Lista sólo puede ser recorrida en secuencia, usualmente hacia atrás o adelante. • Hay varias formas de implementar una lista, como se muestra a continuación.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Una Lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior.

Una lista enlazada puede representarse de la forma

info

comienzo

primer nodo

sig

info

sig

segundo nodo

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

info

último nodo

sig

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones. El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Como cualquier estructura de datos, una lista enlazada nos servirá para almacenar datos. Las operaciones sobre una lista enlazada más importantes son: Recorrido. Búsqueda sobre lista enlazada ordenada y sobre lista enlazada desordenada. Control del espacio disponible en memoria: desbordamiento y subdesbordamiento. Inserción: Lista vacía Por el principio Por el medio Por el final Borrado: Primer nodo de la lista Cualquier nodo Último nodo.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Cuando se construye una lista enlazada, se enfrenta a la elección de si almacenar los datos de la lista directamente en los nodos enlazados de la lista, llamado almacenamiento interno, o almacenamiento externo. El almacenamiento interno tiene la ventaja de hacer accesos a los datos más eficientes, requiriendo menos almacenamiento global, teniendo mejor referencia de localidad, y simplifica la gestión de memoria para la lista

El almacenamiento externo, por otro lado, tiene la ventaja de ser más genérico, en la misma estructura de datos y código máquina puede ser usado para una lista enlazada, no importa cual sea su tamaño o los datos.

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

Listas en C/C++ con arreglos una primera implementación de listas usando arreglos, cada elemento del arreglo debe ser un elemento compuesto. Cada elemento debe contener una parte para la información y otra parte para apuntar al elemento siguiente: #include En el programa anterior, en las líneas ( 1) #define numNodes 500 (2) a (5) se crea un nuevo tipo de dato, el tipo nodo. Cada nodo tiene dos partes, su parte de ( 2) struct nodeType{ información y su parte de apuntador al siguiente. ( 3) int info; Como solamente tenemos 500 nodos (declarados ( 4) int next; en la línea (1), el tipo de datos siguiente es entero ( 5) }; y hemos decidido almacenar números enteros solamente. ( 6) struct nodeType node[numNodes]; En la línea (6) se ha declarado una variable global de tipo arreglo de estructura de int main (int argc, char * const argv[]) { nodos, es decir, se ha creado un arreglo de 500 nodos. std::cout << "\EL GRUPO ESTA INTEGRADO POR:!\n"; std::cout <<"\NIEVES KARLA!\n"; std::cout <<"\VIERA URIAN!\n"; std::cout <<"\SUAREZ RENY!\n"; std::cout <<" \ AULA 06S5IST B!\n";

return 0; }

clic

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN

AUTORES: NIEVES KARLA,SUAREZ RENY ,VIERA URIAN