(Listas enlazadas en Turbo C)
¿Cómo definir una lista
enlazada en lenguaje C?
Función
que manejan la asignación dinámica de memoria.
Las listas constituyen una
estructura flexible en particular, porque pueden crecer y acortarse según lo
requiera; los elementos son accesibles y pueden insertar y suprimir en
cualquier posición de la lista.
Las listas enlazadas a
diferencia de los vectores (arrays o arreglos), su tamaño se define en tiempo
de ejecución.
A continuación les presento un cuadro con las diferencias más destacadas entre listas enlazadas y vectores:
Vectores |
Listas enlazadas |
·
En un tipo de almacenamiento estático. ·
El tamaño se determina en tiempo de compilación. ·
El almacenamiento es contiguo. |
·
Es un tipo de almacenamiento dinámico. ·
El tamaño se determina en tiempo de ejecución. |
Una lista enlazada gráficamente se representa de la siguiente manera:
Cada cuadro que está dividido en dos se lo denomina nodo. Los datos en un nodo se guarda de la siguiente manera:
NOTA: una lista enlazada está compuesta por nodos, y estos nodos a su vez de dos áreas: ·
Área de datos: En esta área se guarda los datos que se desee almacenar,
esta área puede tener más de un campo. ·
Un área donde guarda la dirección al siguiente elemento, por lo general
es un puntero de estructura. |
Para definir una lista enlazada en lenguaje C se utiliza la palabra clave
struct.
Esta palabra clave tiene otras utilidades, quiero decir, que aparte de
crear listas enlazadas, también se crea lo que se llama tipos de datos
definidos por el usuario. (Supuestamente ya el manejo de estructura lo doy por
sabido).
Para crear un nodo generalmente se utiliza el siguiente código:
int n // guarda un número entero.
struct nodo_lista *sig; // Guarda la dirección del siguiente nodo
};
A partir de aquí vamos a crear una lista enlazada para números entero. Ya tenemos la estructura que vamos a usar.
Si vemos el razonamiento de esta estructura, vemos que tiene dos campos, una campo donde guarda los datos y otro donde guarda la dirección del siguiente elemento.
Como ves, *sig es un puntero a estructura, una lista enlazada se maneja con punteros (ya doy por sabido el manejo de punteros).
En Turbo C, existen dos
funciones que manejan las listas enlazadas, se denominan malloc() y free().
Estas dos funciones se encuentran en el archivo de cabecera STDLIB.H que se lo
llama mediante un #include<stdlib.h> al comienzo de un programa.
Malloc(): Esta
función lo que hace es asignar memoria, es decir, piede memoria cuando la
necesita. Esta función devuelve un puntero que contiene la dirección de la
nueva porción de memoria asignada.
Por ejemplo malloc en
una lista enlazada se utiliza de la siguiente manera:
Supongamos que pido memoria al sistema,
y la dirección de esa porción de memoria la guardo en un puntero llamado p,
el uso sería de la siguiente manera:
struct nodo_lista *p;
p=(struct nodo_lista *)malloc(sizeof(struct nodo_lista);
Como verás utilice una
palabra reservada llamada sizeof, para que tengas una idea, esto quiere decir
tamaño de. Sizeof devuelve un tamaño en bytes, en este caso está devolviendo el
tamaño de bytes de la estructura.
En este cado, p
tiene la dirección del nuevo nodo. La función malloc se utiliza generalmente en
la función insertar (más adelante desarrollaré el código de esta función),
porque cada vez que quiero agregar un dato, tengo que pedir memoria.
La función free() es
lo contrario de malloc(), esta función devuelve memoria al sistema. Es
necesario cuando se termina de usar la porción de memoria, hay que devolversela
al sistema. Esta función se utiliza generalmente para borrar datos de una
lista.
Podría no devolver la
memoria al sistema cuando la termino de usar, pero pensá que cuando elimino un
dato, esa porción de memoria queda inaccesible, por lo que sería un desperdicio
tener una porción de memoria que no se pueda utilizar.
Basta ya de palabras
y comencemos a armar un pequeño programa donde vamos a guardar una lista de
números entero donde no sepamos cuantos número va a contener esta lista. Aquí
se incluye el desarrollo de las funciones insertar, eliminar, mostrar y busacar
en una lista enlazada.
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
struct
nodo_lista {
int n;
struct nodo_lista *sig;
};
struct
nodo_lista *primero=NULL;
void
insertar(int num) {
struct nodo_lista *p, *q;
p=(struct nodo_lista *)malloc(sizeof(struct
nodo_lista));
p->n=num;
p->sig=NULL;
if(primero == NULL)
primero=p;
else {
q=primero;
while(q->sig != NULL)
q=q->sig;
q->sig=p;
}
}
void
mostrar() {
struct nodo_lista *p;
p=primro;
while((p != NULL) && (primero != NULL))
{
printf(%d, p->n);
p=p->sig;
}
}
struct
nodo_lista *buscar(int num) {
struct nodo_lista *p, *q;
p=primero;
while((p != NULL) && (primero != NULL))
{
if(num == p->n)
q=p->sig;
else printf(Número no encontrado);
p=p->sig;
}
if(p->sig == NULL) && (p->n ==
num)
q=p->sig;
return q;
}
void
eliminar(int pos) {
struct nodo_lista *p, *q;
int c;
if(pos == 1)
{
q=primero;
primero=primero->sig;
free(primero);
}
else {
c=1;
q=NULL;
p=primero;
while((q->sig != NULL) && (c < pos))
{
q=p;
p=p->sig;
c++;
}
if(c == pos)
{
q->sig = p->sig;
free(p);
}
}
void
main() {
int n;
scanf(%d, &n);
while(n != 0)
{
insrtar(n);
scanf(%d, &n);
}
clrscr();
mostrar();
scanf(%d, &n);
eliminar(n);
clrscr();
mostrar();
}
Como verás, al principio del programa, declaré la estructura para la lista y puse un puntero llamado primero en nulo (NULL). En lenguaje C la palabre NULL en este caso indica el fin de la lista. Puse primero en NULL, porque se supone que al principio la lista no existe. El último nodo de la lista, el campo siguiente vale NULL.
La palabra NULL en lenguaje
C tiene varias utilidades, pero no voy a entrar en detalles.
En la función insertar usé
dos punteros p y q, el puntero p lo que hace es guardar la dirección del
nuevo nodo, mientras que q me permite recorrer la lista. En algún momento
puse q->sig=p, en esta linea me permite enlazar el nuevo nodo a la lista.
Confeccionar
un programa que permita generar una lista de empleados con los siguientes
datos:
-
Identificación de empleado (entero de 1 a n)
-
Apellido y nombre(string[30])
-
Saldo por mes.
Este
programa debe estar escrito por las siguiente funciones:
a)
Una función insertar, para ingresar los empleados.
b)
Una función buscar, que busque por identificación de empleado, e imprima
por pantalla el Apellido y nombre y el sueldo que gana.
Le recomiendo que lo arme directamente en la computadora. Aunque si le
sirve para guiarse se puede utilizar un diagrama de flujo y luego codificarlo.
Suerte.
Yo creo que con esto ya les
doy una base de lo que es asignación dinámica de memoria. Cualquier pregunta
que tengan, en esta página hay una sección de preguntas y respuestas, podés
dejar tu pregunta allí.
Autor: Leonardo Diego Zulli
Estudiante de Tecnico en programación.
Bibliografía:
Para poder expresar una definición lo más posible clara he consultado un
libro:
ESTRUCTURA DE DATOS Y ALGORITMOS de ALFRED V. AHO, JHON E. HOPCROFT y JEFFREY D. ULLMAN
El Resto del Apunte, he aportado el conocimiento que logré conseguir
hasta ahora sobre el tema.
Programa de ejemplo comprimido en un zip, trabajado en Turbo C.