• Categories
• Datos
• Programación de computadoras
• Informática
• Tecnología
• Datos informáticos

Citation preview

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FÍSICAS Y MATEMÁTICAS ESCUELA DE INFORMÁTICA

ORGANIZACIÓN DE ARCHIVOS “LISTAS ENLAZADAS”

AUTORES: Alfaro Alonso Elvis Príncipe Orbegozo Luis Rodríguez Cosavalente Jham

Trujillo - Perú 2011

1

Manipulación de archivos con listas enlazadas Recordando: Listas Enlazadas Una lista es una estructura de datos que nos permite agrupar elementos de una manera organizada. Las listas están compuestas por nodos, estos nodos tienen un dato o valor y un puntero a otro(s) nodo(s). Una lista enlazada tiene un conjunto de nodos, los cuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior. Ejemplo: 9-> 5-> 3-> 8-> 1-> NULL

Gráficamente:

Obviamente, internamente no existen las palabras nodo, dato, dirección y siguiente, es solo una representación. Como una lista es una estructura de datos dinámica, el tamaño de la misma puede cambiar durante la ejecución del programa. Definición Lista Simple - Dinámica Es una secuencia de 0 o más elementos de un tipo de dato determinado, formando un grupo unidos por una ligadura entre los diferentes elementos (llamados ahora Nodos); esto da lugar a la existencia de dos sub-elementos en el Nodo que son: dato (elemento dato) y ligadura (referencia), usando dinámicamente la memoria.

2

La lista consta de una colección de nodos situados en la memoria dinámica conectados entre sí. Cada Nodo Cada nodo se compone de un dato y una referencia al siguiente nodo de la lista. El último nodo de la lista contiene una referencia siguiente NULL.

¿Cómo aplicar Listas Enlazadas en Archivos?

Archivo desordenado

Reporte deseado: listado en orden por nombre

3

Para reportar ordenadamente se debe:

La solución anterior tiene un defecto, si el archivo es grande, la complejidad computacional aumenta:

NRS →∞ n=NRS

4

Aplicamos Lista enlazada:

Recordando como ingresamos elementos en Listas Enlazadas: a) Ingresamos al final de la Lista

b) Ingresamos al inicio de la Lista

5

c) Ingresamos en un cualquier lugar de la Lista

Pensando en archivos insertamos registros: I(P), I(K), I(B), I(M). I(P):

I(B):

I(K):

I(M):

6

En un archivo se pueden tener varias Listas:  Que ordenan por Nombre  Que ordenan por Apellido  Que ordenan Descendentemente Ejemplo:

Ejemplo de implementación de archivos con listas enlazadas:

7

Implementación en lenguaje C++: #include #include #include #include #include using namespace std; struct encabezado{ int PR; int NRS; }e; struct registro{ int NR; char nom[10]; int edad; int SR; }r,a,s; void escribir(){ system("cls"); char nomarch[10]; int fd,rpta=1,le,lr,x,band,pos; le=sizeof(struct encabezado); lr=sizeof(struct registro); cout