el puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento
el puntero anterior del elemento actual apunta hacia el nuevo elemento
el puntero fin no cambia
el puntero inicio cambia si la posición elegida es la posición 1
el tamaño se incrementa en una unidad
La función
int ins_antes (dl_Lista * lista, char *dato, int pos){
int i;
dl_Elemento *nuevo_elemento, *actual;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
actual = lista->inicio;
for (i = 1; i < pos; ++i)
actual = actual->siguiente;
nuevo_elemento->siguiente = actual;
nuevo_elemento-> anterior = actual->anterior;
if(actual->anterior == NULL)
lista->inicio = nuevo_elemento;
else
actual->anterior->siguiente = nuevo_elemento;
actual->anterior = nuevo_elemento;
lista->tamaño++;
return 0;
}
5. Inserción después de un elemento de la lista
Modelo de la función:
int ins_después (dl_Lista * lista, char *dato, int pos);
La función devuelve -1 en caso de error, si no devuelve 0. La inserción se efectuará después de cierta posición pasado como argumento a la función. La posición indicada no debe ser el último elemento. En ese caso hay que utilizar la función de inserción al final de la lista. Etapas:
asignación de memoria al nuevo elemento
rellenar el campo de datos del nuevo elemento
Elegir una posición en la lista (la inserción se hará después de la posición elegida)
el puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero siguiente del elemento actual (ver la imagen).
el puntero anterior del nuevo elemento apunta hacia el elemento actual.
el puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo elemento.
el puntero siguiente del elemento actual apunta hacia el nuevo elemento
el puntero inicio no cambia
el puntero fin cambia si la posición elegida es la posición del ultimo elemento (el tamaño de la lista)
el tamaño se incrementa en una unidad
La función
int ins_después (dl_Lista * lista, char *dato, int pos){
int i;
dl_Elemento *nuevo_elemento, *actual;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
actual = lista->inicio;
for (i = 1; i < pos; ++i)
actual = actual->siguiente;
nuevo_elemento->siguiente = actual->siguiente;
nuevo_elemento->anterior = actual;
if(actual->siguiente == NULL)
lista->fin = nuevo_elemento;
else
actual->siguiente->anterior = nuevo_elemento;
actual->siguiente = nuevo_elemento;
lista->tamaño++;
return 0;
}
Eliminación de un elemento de la lista
A continuación el algoritmo para eliminar un elemento de la lista:
uso de un puntero temporal para guardar la dirección de los elementos a eliminar
el elemento a eliminar puede encontrase en cualquier posición en la lista.
En relación a la lista enlazada simple en el que la eliminación solo puede ser hecha después que un elemento ha sido designado, las listas doblemente enlazadas son más flexibles gracias a los 2 punteros que permiten guardar el rastro tanto hacia atrás como hacia delante.
liberar la memoria ocupada por el elemento eliminado
actualizar el tamaño de la lista
Para eliminar un elemento de la lista hay varias situaciones:
Eliminación al inicio de la lista
Eliminación al final de la lista
Eliminación antes de un elemento
Eliminación después de un elemento
5 Eliminación de un elemento
Sin embargo, la eliminación al inicio y al final de la lista doblemente enlazada así como antes o después de un elemento equivale a la eliminación en la posición 0 (cero) o en la posición N (N= numero de elementos de la lista) o en otra parte de la lista. En el caso de listas doblemente enlazadas la eliminación en cualquier posición no presenta ningún problema gracias a los punteros anterior y siguiente, que permiten conservar el enlace entre los elementos de la lista. Razón por la cual solo vamos a crear una función.
si deseamos eliminar el elemento al inicio de la lista elegiremos la posición cero
si deseamos eliminar el elemento al final de la lista elegiremos la posición N (el numero de elementos)
si deseamos eliminar cualquier elemento entonces elegimos su posición en la lista.
Eliminación en la lista
Modelo de la función:
int supp(dl_Lista *lista, int pos);
La función devuelve -1 en caso de error, si no devuelve 0. Podemos distinguir varias situaciones:
eliminación en la posición 1 en una lista con un solo elemento
eliminación en la posición 1 en una lista con varios elementos
eliminación en la ultima posición (el ultimo elemento)
eliminación en otra parte de la lista en cierta posición
La eliminación en una lista vacía no tiene sentido Etapas:
La posición elegida es 1 (el caso de eliminación del 1er elemento de la lista)
el puntero sup_elemento contendrá la dirección del 1er elemento
el puntero inicio contendrá la dirección contenida por el puntero siguiente del 1er elemento que deseamos eliminar (si este puntero vale NULL entonces actualizamos el puntero fin ya que estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior del 2do elemento hacia NULL)
la posición elegida es igual al numero de elementos de la lista
el puntero sup_elemento contendrá la dirección del ultimo elemento
hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que apunta el puntero del ultimo elemento), hacia NULL
actualizamos el puntero fin
la posición elegida es aleatoria en la lista
el puntero sup_elemento contendrá la dirección del elemento a eliminar
el puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección contenida en el puntero siguiente del elemento a eliminar
el puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección contenida en el puntero anterior del elemento a eliminar.
el tamaño de la lista será disminuida en 1 elemento
La función
int supp(dl_Lista *lista, int pos){
int i;
dl_Elemento *sup_elemento,*actual;
if(lista->tamaño == 0)
return -1;
if(pos == 1){ /* eliminación del 1er elemento */
sup_elemento = lista->inicio;
lista->inicio = lista->inicio->siguiente;
if(lista->inicio == NULL)
lista->fin = NULL;
else
lista->inicio->anterior == NULL;
}else if(pos == lista->tamaño){ /* eliminación del último elemento */
sup_elemento = lista->fin;
lista->fin->anterior->siguiente = NULL;
lista->fin = lista->fin->anterior;
}else { /* eliminación en otra parte */
actual = lista->inicio;
for(i=1;i/font>
actual = actual->siguiente;
sup_elemento = actual;
actual->anterior->siguiente = actual->siguiente;
actual->siguiente->anterior = actual->anterior;
}
free(sup_elemento->dato);
free(sup_elemento);
lista->tamaño–;
return 0;
}
Visualización de la lista
Para mostrar la lista entera podemos posicionarnos al inicio
o al final de la lista (el puntero inicio o fin lo permitirá).
Luego utilizando el puntero siguiente o anterior de cada elemento,
la lista es recorrida del 1er al ultimo elemento o del ultimo al 1er elemento.
La condición para detener es dada por el puntero siguiente del
ultimo elemento que vale NULL en el caso de la lectura del inicio hacia el fin
de la lista, o por el puntero anterior del 1er elemento que vale NULL,
en el caso de una lectura del final hacia el inicio de la lista. Las funciones
void affiche(dl_Lista *lista){ /* visualización hacia
adelante */
dl_Elemento *actual;
actual = lista->inicio; /* punto de inicio el 1er elemento
*/
printf("[ ");
while(actual != NULL){
printf("%s ",actual->dato);
actual = actual->siguiente;
}
printf("]n");
}
void mustra_inv(dl_Lista *lista){ /* visualización
hacia atrás */
dl_Elemento *actual;
actual = lista->fin; /* punto de inicio el ultimo elemento
*/
printf("[ ");
while(actual != NULL){
printf("%s : ",actual->dato);
actual = actual->anterior;
}
printf("]n");
}
Destrucción de la lista
Para destruir la lista entera, he utilizado la eliminación
en la posición 1 ya que el tamaño es mayor a cero. La función
void destruir(dl_Lista *lista){
while(lista->tamaño > 0)
sup(lista,1);
}
V. Ejemplo completo
dlista.h
/* ———- dlista.h ———– */
typedef struct dl_ElementooLista{
char *dato;
struct dl_ElementoLista *anterior;
struct dl_ElementoLista *siguiente;
} dl_Elemento;
typedef struct dl_ListaIdentificar{
dl_Elemento *inicio;
dl_Elemento *fin;
int tamaño;
} dl_Lista;
/* inicialización de la liste */
void inicialización (dl_Lista * lista);
dl_Elemento *alloc (dl_Elemento * nuevo_elemento);
/* INSERCION */
int ins_en_lista_vacia (dl_Lista * lista, char *dato);
int ins_inicio_lista(dl_Lista * lista, char *dato);
int ins_fin_lista(dl_Lista * lista, char *dato);
int ins_después (dl_Lista * lista, char *dato, int
pos);
int ins_antes (dl_Lista * lista, char *dato, int pos);
/*ELIMINACION*/
int sup(dl_Lista *liste, int pos);
void muestra (dl_Lista * lista);
/**************************/
void muestra_inv (dl_Lista * lista);
void destruir (dl_Lista * lista);
/* ——– FIN lista.h ——— */
dlista_function.h
/***************************
* dlista_function.h *
***************************/
void inicialización (dl_Lista * lista){
lista->inicio = NULL;
lista->fin = NULL;
lista->tamaño = 0;
}
int inserción_en_lista_vacia (dl_Lista * lista, char
*dato){
dl_Elemento *nuevo_elemento;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->anterior = NULL;
nuevo_elemento->siguiente = NULL;
lista->inicio = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
int ins_inicio_lista(dl_Lista * lista, char *dato){
dl_Elemento *nuevo_elemento;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->anterior = NULL;
nuevo_elemento->siguiente = lista->inicio;
lista->inicio->anterior = nuevo_elemento;
lista->inicio = nuevo_elemento;
lista->tamaño++;
return 0;
}
int ins_fin_lista(dl_Lista * lista, char *dato){
dl_Elemento *nuevo_elemento;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = NULL;
nuevo_elemento->anterior = lista->fin;
lista->fin->siguiente = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
int ins_después (dl_Lista * lista, char *dato, int
pos){
int i;
dl_Elemento *nuevo_elemento, *actual;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
actual = lista->inicio;
for (i = 1; i < pos; i)
actual = actual->siguiente;
nuevo_elemento->siguiente = actual->siguiente;
nuevo_elemento->anterior = actual;
if(actual->siguiente == NULL)
lista->fin = nuevo_elemento;
else
actual->siguiente->anterior = nuevo_elemento;
actual->siguiente = nuevo_elemento;
lista->tamaño++;
return 0;
}
int ins_antes (dl_Lista * lista, char *dato, int pos){
int i;
dl_Elemento *nuevo_elemento, *actual;
if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
actual = lista->inicio;
for (i = 1; i < pos; i)
actual = actual->siguiente;
nuevo_elemento->siguiente = actual;
nuevo_elemento-> anterior = actual->anterior;
if(actual->anterior == NULL)
lista->inicio = nuevo_elemento;
else
actual->anterior->siguiente = nuevo_elemento;
actual->anterior = nuevo_elemento;
lista->tamaño++;
return 0;
}
int sup(dl_Lista *lista, int pos){
int i;
dl_Elemento *sup_elemento,*actual;
if(lista->tamaño == 0)
return -1;
if(pos == 1){ /* eliminación de 1er elemento */
sup_elemento = lista->inicio;
lista->inicio = lista->inicio->siguiente;
if(lista->inicio == NULL)
lista->fin = NULL;
else
lista->inicio->anterior == NULL;
}else if(pos == lista->tamaño){ /* eliminacion del
ultimo elemento */
sup_elemento = lista->fin;
lista->fin->anterior->siguiente = NULL;
lista->fin = lista->fin->anterior;
}else { /* eliminacion en otra parte */
actual = lista->inicio;
for(i=1;igras>i)
actual = actual->siguiente;
sup_elemento = actual;
actual->anterior->siguiente = actual->siguiente;
actual->siguiente->anterior = actual->anterior;
}
free(sup_elemento->dato);
free(sup_elemento);
lista->tamaño–;
return 0;
}
void destruir(dl_Lista *lista){
while(lista->tamaño > 0)
supp(lista,1);
}
dl_Elemento *alloc (dl_Elemento * nuevo_elemento){
if ((nuevo_elemento = (dl_Elemento *) malloc (sizeof (dl_Elemento)))
== NULL)
return NULL;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return NULL;
return nuevo_elemento;
}
int menu (dl_Lista *lista){
int choix;
if (lista->tamaño == 0){
printf ("1. Adición del 1er elementon");
printf ("2. Eliminarn");
} else{
printf ("1. Añadir al inicio de la listan");
printf ("2. Añadir al final de la listan");
printf ("3. Añadir antes de la posición
especificadan");
printf ("4. Añadir después de la posición
especificadan");
printf ("5. Eliminacion en la posicion especificadan");
printf ("6. Destruir la listan");
printf ("7. Eliminarn");
}
printf ("nnElija: ");
scanf ("%d", &elección);
getchar();
if(lista->tamaño == 0 && elección == 2)
elección = 7;
return elección;
}
int supp(dl_Lista *lista, int pos);
void muestra(dl_Lista *lista){
dl_Elemento *actual;
actual = lista->inicio;
printf("[ ");
while(actual != NULL){
printf("%s ",actual->dato);
actual = actual->siguiente;
}
printf("]n");
}
void muestra_inv(dl_Lista *lista){
dl_Elemento *actual;
actual = lista->fin;
while(actual != NULL){
printf("%s : ",actual->dato);
actual = actual->anterior;
}
printf("n");
}
/* ——– FIN dlista_function.h ——— */
dlista.c
/**********************
* dlista.c *
**********************/
#include
#include
#include
#include "dlista.h"
#include "dlista_function.h"
int main (void)
{
int elección = 0,pos;
char *dato;
dato = malloc(50);
dl_Lista *lista;
dl_Elemento *piloto = NULL;
lista = (dl_Lista *) malloc (sizeof(dl_Lista));
inicialización(lista);
while(elección != 7){
elección = menu(lista);
switch(elección){
case 1:
printf("Ingrese un elemento: ");
scanf("%s",dato);
getchar();
if(lista->tamaño == 0)
inserción_en_lista_vacia(lista,dato);
else
ins_inicio_lista(lista, dato);
printf("%d elementos: deb=%s,fin=%s ",
lista->tamaño,lista->inicio->dato,lista->fin->dato);
muestra(lista);
break;
case 2:
printf("Ingrese un elemento: ");
scanf("%s",dato);
getchar();
ins_fin_lista(lista, dato);
printf("%d elementos: deb=%s,fin=%s ",
lista->tamaño,lista->inicio->dato,lista->fin->dato);
muestra(lista);
break;
case 3:
if(lista->tamaño == 1){
printf("Utilizar la inserción al inicio o al
final (Ingrese Menu: 1 ó 2)n");
break;
}
printf("Ingrese un elemento: ");
scanf("%s",dato);
getchar();
do{
printf("Ingrese la posición: ");
scanf("%d",&pos);
}while (pos < 1 || pos > lista->tamaño);
getchar();
ins_antes(liste,dato,pos);
printf("%d elementos: deb=%s fin=%s ",
lista->tamaño,lista->inicio->dato,lista->fin->dato);
muestra(lista);
break;
case 4:
if(lista->tamaño == 1){
Printf("Utilizar la inserción al inicio o al
final (Ingrese Menu: 1 ó 2)n");
break;
}
printf("Ingrese un elemento: ");
scanf("%s",dato);
getchar();
do{
printf("Ingrese la posicion: ");
scanf("%d",&pos);
}while (pos < 1 || pos > lista->tamaño);
getchar();
ins_después(lista,dato,pos);
printf("%d elementos: deb=%s,fin=%s ",
lista->tamaño,lista->inicio->dato,lista->fin->dato);
muestra(lista);
break;
case 5:
do{
printf("Ingrese la posición : ");
scanf("%d",&pos);
}while (pos < 1 || pos > lista->tamaño);
getchar();
supp(lista,pos);
if(lista->tamaño != 0)
printf("%d elementos: deb=%s,fin=%s ",
lista->tamaño,lista->inicio->dato,lista->fin->dato);
else
printf("liste vide : %d elementos",lista->tamaño);
muestra(lista);
break;
case 6:
destruir(lista);
printf("la lista ha sido destruida: %d elementosn",lista->tamaño);
break;
}
}
return 0;
}
/* ——– FIN dlista.c ——— */
Las pilas – Último en entrar, primero en salir (LIFO)
Requisitos
INTRUDUCCION
Definición
La construcción del modelo de un elemento de la
pilaOperaciones sobre las pilas
Inicialización
Inserción de un elemento en la pila
Eliminar un elemento de la pila
Visualización de la pila
Recuperación del dato en la cabeza de la pila
V. Ejemplo completo
pila.h
pila_function.h
pila.c
Requisitos
Los tipos de datos Las estructuras El uso de typedef Los punteros
Las funciones de usuario Las listas simplemente enlazadas Las listas doblemente
enlazadas
I. INTRUDUCCION
El objetivo de este articulo es que el lector comprenda el
empleo de las pilas. Para explicar el algoritmo he elegido utilizar una
lista enlazada simple. Por lo tanto la comprensión de las listas enlazadas
es necesaria.
II. Definición
La pila es una estructura de datos que permite almacenar
datos en el orden LIFO (Last In First Out) en español, último
en entrar, primero en salir). La recuperación de los datos es hecha en
el orden inverso de su inserción. Para la implementación he elegido
una lista enlazada simple, presentada sobre la vertical. Ya que la inserción
es siempre hecha al inicio de la lista, el 1er elemento de la lista será
el ultimo elemento ingresado, por lo tanto estará en la cabeza de la
pila. No he utilizado un puntero fin, como lo hice en el caso de la lista
enlazada simple, ya que el objetivo no es el de tratar una lista enlazada, sino
una pila. Lo interesante es que el ultimo elemento ingresado, será
el 1er elemento recuperado.
III. La construcción del modelo de un elemento de
la pila
Para definir un elemento de la pila será utilizado
el tipo struct. El elemento de la pila contendrá un campo dato
y un puntero siguiente. El puntero siguiente debe ser del
mismo tipo que el elemento, de lo contrario 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 permitir las operaciones sobre la pila, vamos a guardar
ciertos elementos:
el primer elemento
el numero de elementos
El 1er elemento, que se encuentra en la cabeza de la pila,
nos permitirá realizar la operación de recuperación de
los datos situados en la parte superior de la pila. Para ello, será utilizada
otra estructura (no es obligatorio, pueden ser utilizadas variables).
typedef struct ListaUbicación{
Elemento *inicio;
int tamaño;
} Pila;
El puntero inicio contendrá la dirección
del 1er elemento de la lista. La variable tamaño contiene el numero
de elementos. Nota: Esta vez no utilizamos un puntero fin (ver la lista
enlazada simple), no lo necesitamos puesto que únicamente trabajamos
al inicio de la lista. Cualquiera que sea la posición en la lista, el
puntero inicio apunta siempre hacia el 1er elemento, que estará
en la cabeza de la pila. El campo tamaño contendrá el numero
de elementos de la pila, cualquiera que sea la operación efectuada sobre
la pila.
IV. Operaciones sobre las pilas
A. Inicialización
Modelo de la función:
void inicialización (Pila *tas);
Esta operación debe ser hecha antes de cualquier otra
operación sobre la pila. Esta inicializa el puntero inicio con
el puntero NULL, y el tamaño con el valor 0. La función
void inicialización (Pila * tas){
tas->inicio = NULL;
tas->tamaño = 0;
}
B. Inserción de un elemento en la pila
A continuación el algoritmo de inserción y registro
de los elementos:
declaración del elemento a insertar
asignación de la memoria para el nuevo elemento
rellenar el contenido del campo de datos
actualizar el puntero inicio hacia el 1er elemento
(la cabeza de la pila)Actualizar el tamaño de la pila.
Modelo de la función:
int apilar (Pila *tas, char *dato);
La primera imagen muestra el inicio de la inserción,
por lo tanto la lista de tamaño 1 después de la inserción.
La característica de la pila no es muy apreciada con un solo elemento,
ya que es el único a recuperar.
En cambio la 2da imagen nos permite observar el comportamiento
de la pila. Lo que debemos retener es que la inserción siempre se hace
en la parte superior de la pila (al inicio de la lista).
La función
/* apilar (añadir) un elemento en la pila */
int apilar (Pila * tas, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = tas->inicio;
tas->inicio = nuevo_elemento;
tas->tamaño++;
}
C. Eliminar un elemento de la pila
Para eliminar un elemento de la pila, simplemente hay que
eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación
no permite recuperar el dato en la cabeza de la pila, solo eliminarlo. Modelo
de la función:
int desapilar (Pila *tas);
La función devuelve -1 en caso de error, si no devuelve
0. Las etapas:
el puntero sup_elemento contendrá la dirección
del 1er elementoel puntero inicio apuntará hacia el 2do
elemento (después de la eliminación del 1er elemento, el 2do
elemento estará en la cabeza de la pila)el tamaño de la pila disminuirá un
elemento.
La función
int desapilar (Pila * tas){
Elemento *sup_elemento;
if (tas->tamaño == 0)
return -1;
sup_elemento = tas->inicio;
tas->inicio = tas->inicio->siguiente;
free (sup_elemento->dato);
free (sup_elemento);
tas->tamaño–;
return 0;
}
D. Visualización de la pila
Para mostrar la pila entera, es necesario posicionarse al
inicio de la pila (el puntero inicio lo permitirá). Luego, utilizando
el puntero siguiente de cada elemento, la pila es recorrida del 1er hacia
el ultimo elemento. La condición para detenerse es dada por el tamaño
de la pila. La función
/* visualización de la pila */
void muestra (Pila * tas){
Elemento *actual;
int i;
actual = tas->inicio;
for(i=0;itamaño;++i){
printf("tt%sn", actual->dato);
actual = actual->siguiente;
}
}
E. Recuperación del dato en la cabeza de la pila
Para recuperar el dato en la cabeza de la pila sin eliminarlo,
he utilizado una macro. La macro lee los datos en la parte superior de la pila
utilizando el puntero inicio.
#define pila_dato(tas) tas->inicio->dato
V. Ejemplo completo
pila.h
/*********************
* pila.h *
*********************/
typedef struct ElementoLista{
char *dato;
struct ElementoLista *siguiente;
} Elemento;
typedef struct ListaUbicación{
Elemento *inicio;
int tamaño;
} Pila;
/* inicialización */
void inicialización (Pila *tas);
/* APILAR*/
int apilar (Pile *tas, char *dato);
/* DESAPILAR*/
int desapilar (Pila *tas);
/* Visualización del elemento en la cabeza de la pila
(LastInFirstOut) */
#define pila_dato(tas) tas->inicio->dato
/* muestra la pila */
void muestra (Pila *tas);
pila_function.h
/***********************
* pila_function.h *
***********************/
void inicialización (Pila * tas){
tas->inicio = NULL;
tas->tamaño = 0;
}
/* apilar (añadir) un elemento en la pila */
int apilar (Pila * tas, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = tas->inicio;
tas->inicio = nuevo_elemento;
tas->tamaño++;
}
/* desapilar (eliminar un elemento de la pila */
int desapilar (Pila * tas){
Elemento *sup_elemento;
if (tas->tamaño == 0)
return -1;
sup_elemento = tas->inicio;
tas->inicio = tas->inicio->siguiente;
free (sup_elemento->dato);
free (sup_elemento);
tas->tamaño–;
return 0;
}
/* visualización de la pila */
void muestra (Pila * tas){
Elemento *actual;
int i;
actual = tas->inicio;
for(i=0;itamaño;++i){
printf("tt%sn", actual->dato);
actual = actual->siguiente;
}
}
pila.c
/*********************
* pila.c *
*********************/
#include
#include
#include
#include "pila.h"
#include "pila_function.h"
int main ()
{
Pila *tas;
char *nom;
if ((tas = (Pila *) malloc (sizeof (Pila))) == NULL)
return -1;
if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
inicialización (tas);
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
apilar (tas, nom);
printf ("La pila (%de elementos): n",tas->tamaño);
printf("n********** Cabeza de la PILA **********n");
muestra(tas);
printf("__________ Bajo de la PILA __________nn");
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
apilar (tas, nom);
printf ("La pila (%de elementos): n",tas->tamaño);
printf("n********** Cabeza de la PILA **********n");
muestra(tas);
printf("__________ Bajo de la PILA __________nn");
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
apilar (tas, nom);
printf ("La pila (%de elementos): n",tas->tamaño);
printf("n********** Cabeza de la PILA **********n");
muestra(tas);
printf("__________ Bajo de la PILA __________nn");
printf ("nLa ultima entrada (LastInFirstOut) [ %s ]
sera eliminada",
pile_dato(tas));
printf ("nLa ultima entrada es eliminadan");
desapilar (tas); /* eliminación del ultimo elemento
ingresado */
printf ("La pila (%de elementos): n",tas->tamaño);
printf("n********** Cabeza de la PILA **********n");
muestra(tas);
printf("__________ Bajo de la PILA __________nn");
return 0;
}
Las filas – Primero en Entrar, Primero en salir (FIFO)
Requisitos
Introducción
Definición
La construcción del modelo de un elemento de la
filaOperaciones sobre las filas
A. Inicialización
B. Inserción
C. Eliminar un elemento de la fila
D. Visualización de la fila
E. Recuperación del dato al inicio de la fila
V. Ejemplo completo
fila.h
fila_function.h
fila.c
Requisitos
Los tipos de datos Las estructuras El uso de typedef Los punteros
Las funciones de usuario Las listas simplemente enlazadas Las listas doblemente
enlazadas
I. Introducción
El objetivo de este articulo es que el lector comprenda el
empleo de las filas. Para explicar el algoritmo he elegido utilizar una
lista enlazada simple. Por lo que la comprensión de las listas enlazadas
es necesaria.
II. Definición
La fila es una estructura de datos que permite almacenar
datos en el orden FIFO (First In First Out) en español, Primero
en Entrar, Primero en Salir). La recuperación de los datos es hecha en
el orden en que son insertados. Para la implementación he elegido una
lista enlazada simple. La inserción en la fila se hará en el orden
normal, el 1er elemento de la fila será el primer elemento ingresado,
por lo tanto su posición es al inicio de la fila.
III. La construcción del modelo de un elemento de
la fila
Para definir un elemento de la fila será utilizado
el tipo struct. El elemento de la fila contendrá un campo dato
y un puntero siguiente. El puntero siguiente debe ser del
mismo tipo que el elemento, de lo contrario 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 fila, es preferible guardar
ciertos elementos: el primer elemento, el último elemento, el número
de elementos. Para ello, será utilizada otra estructura (no es obligatorio,
pueden ser utilizadas variables).
typedef struct ListaUbicación{
Elemento *inicio;
Elemento *fin;
int tamaño;
} Fila;
IV. Operaciones sobre las filas
A. Inicialización
Modelo de la función:
void initialisation (Fila * serie);
Esta operación debe ser hecha antes de cualquier otra
operación sobre la fila. Esta inicializa el puntero inicio y el
puntero fin con el puntero NULL, y el tamaño con el valor
0. La función
void inicialización (Fila * serie){
serie->inicio = NULL;
serie->fin = NULL;
serie->tamaño = 0;
}
B. Inserción
A continuación el algoritmo de inserción y registro
de los elementos:
declaración del elemento a insertar
asignación de la memoria para el nuevo elemento
rellenar el contenido del campo de datos
actualizar el puntero inicio hacia el 1er elemento
(el inicio de la fila)actualizar el puntero fin (esto nos servirá para
la inserción hacia el final de la fila)actualizar el tamaño de la pila.
Modelo de la función:
int insertar (Fila * serie, Elemento * actual, char *dato);
La primera imagen muestra el inicio de la inserción,
por lo que el tamaño de la lista es 1 después de la inserción.
En la fila, el elemento a recuperar es el primero en entrar.
Por ello, la inserción se hará siempre al final de la fila. Es
el orden normal de la inserción (1ro, 2do, 3ro, etc.)
La función
int insertar (Fila * serie, Elemento * actual, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
if(actual == NULL){
if(serie->tamaño == 0)
serie->fin = nuevo_elemento;
nuevo_elemento->siguiente = serie->inicio;
serie->inicio = nuevo_elemento;
}else {
if(actual->siguiente == NULL)
serie->fin = nuevo_elemento;
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
}
serie->tamaño++;
return 0;
}
C. Eliminar un elemento de la fila
Para eliminar un elemento de la fila, simplemente hay que
eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación
no permite recuperar el dato al inicio de la fila (el primer dato), solo
eliminarlo. Modelo de la función:
int eliminar (Fila * serie);
La función devuelve -1 en caso de error, si no devuelve
0. Las etapas:
el puntero sup_elemento contendrá la dirección
del 1er elementoel puntero inicio apuntará hacia el 2do
elemento (después de la eliminación del 1er elemento, el 2do
elemento estará al inicio de la fila)el tamaño de la fila disminuirá un
elemento.
La función
int eliminar (Fila * serie){
Elemento *sup_elemento;
if (serie->tamaño == 0)
return -1;
sup_elemento = serie->inicio;
serie->inicio = serie->inicio->siguiente;
free (sup_elemento->dato);
free (sup_elemento);
serie->tamaño–;
return 0;
}
D. Visualización de la fila
Para mostrar la fila entera, es necesario posicionarse
al inicio de la fila (el puntero inicio lo permitirá). Luego,
utilizando el puntero siguiente de cada elemento, la fila es recorrida
del 1er hacia el ultimo elemento. La condición para detenerse es dada
por el tamaño de la fila. La función
void muestra(Fila *serie){
Elemento *actual;
int i;
actual = serie->inicio;
for(i=0;itamaño;++i){
printf(" %s ", actual->dato);
actual = actual->siguiente;
}
}
E. Recuperación del dato al inicio de la fila
Para recuperar el dato al inicio de la fila sin eliminarlo,
he utilizado una macro. La macro lee los datos al inicio de la fila utilizando
el puntero inicio.
#define fila_dato(serie) serie->inicio->dato
V. Ejemplo completo
fila.h
/*********************
* fila.h *
*********************/
typedef struct ElementoLista{
char *dato;
struct ElementoLista *siguiente;
} Elemento;
typedef struct ListaUbicación{
Elemento *inicio;
Elemento *fin;
int tamaño;
} Fila;
/* inicialización */
void inicialización (Fila * serie);
/* Insertar*/
int insertar (Fila * serie, Elemento * actual, char *dato);
/* Eliminar*/
int eliminar (Fila * serie);
/* FirstInFirstOut */
#define fila_dato(serie) serie->inicio->dato
/* Muestra la Fila */
void muestra(Fila *serie);
fila_function.h
/***********************
* fila_function.h *
***********************/
void inicialización (Fila * serie){
serie->inicio = NULL;
serie->fin = NULL;
serie->tamaño = 0;
}
/* insertar (añadir) un elemento en la Fila */
int insertar (Fila * serie, Elemento * actual, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
if(actual == NULL){
if(serie->tamaño == 0)
serie->fin = nuevo_elemento;
nuevo_elemento->siguiente = serie->inicio;
serie->inicio = nuevo_elemento;
}else {
if(actual->siguiente == NULL)
serie->fin = nuevo_elemento;
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
}
serie->tamaño;
return 0;
}
/* eliminar (quitar) un elemento de la Fila */
int eliminar (Fila * serie){
Elemento *sup_elemento;
if (serie->tamaño == 0)
return -1;
sup_elemento = serie->inicio;
serie->inicio = serie->inicio->siguiente;
free (sup_elemento->dato);
free (sup_elementoo);
serie->tamaño–;
return 0;
}
/* visualización de la Fila */
void muestra(Fila *serie){
Elemento *actual;
int i;
actual = serie->inicio;
for(i=0;itamaño;++i){
printf(" %s ", actual->dato);
actual = actual->siguiente;
}
}
fila.c
/*********************
* fila.c *
*********************/
#include
#include
#include
#include "fila.h"
#include "fila_function.h"
int main ()
{
Fila *serie;
char *nom;
if ((serie = (Fila *) malloc (sizeof (Fila))) == NULL)
return -1;
if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
inicialización (serie);
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
insertar (serie, serie->fin, nom);
printf ("La fila (%de elementos)n",serie->tamaño);
printf("nInicio de la FILA [ ");
muestra (serie); /*el primero en entrar será mostrado
*/
printf(" ] Fin de la FILAnn");
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
insertar (serie, serie->fin, nom);
printf ("La fila (%de elementos)n",serie->tamaño);
printf("nInicio de la FILA [ ");
muestra (serie); /*el primer elemento será mostrado
*/
printf(" ] Fin de la FILAnn");
printf ("Ingrese una palabra: ");
scanf ("%s", nom);
insertar (serie, serie->fin, nom);
printf ("La fila (%de elementos)n",serie->tamaño);
printf("nInicio de la FILA [ ");
muestra (serie); /*el primero en entrar será mostrado
*/
printf(" ] Fin de la FILAnn");
printf ("nEl primero en entrar (FirstInFirstOut) [
%s ] será eliminado",
fila_dato(serie));
printf ("nEl primer en entrar es eliminadon");
eliminar (serie); /* eliminación del primer elemento
ingresado */
printf ("La fila (%de elementos): n",serie->tamaño);
printf("nInicio de la FILA [ ");
muestra (serie);
printf(" ] Fin de la FILAnn");
return 0;
}
Listas circulares
Requisitos
Introducción
II Definición
La construcción del modelo de un elemento de la
listaOperaciones sobre las listas circulares
A. Inicialización
B. Inserción de un elemento en la lista
Inserción en una lista vacía
Inserción en una lista no vacía
C. Eliminación de un elemento en la lista
1. Eliminación al inicio de la lista
2. Eliminación en una lista con un solo elemento
D. Mostrar la lista
1. Mostrar la lista (del 1er al último elemento)
2. Mostrar la lista sin una condición para detenerse
(indefinidamente )
E. Destrucción de la lista
V. Ejemplo completo
lista_circ.h
lista_circ_function.h
lista_circ.c
Requisitos
Los tipos de datos Las estructuras El uso de typedef Los punteros
La función usuario Las listas enlazadas simples Las listas doblemente
enlazadas
I. Introducción
El objetivo de este artículo es que el lector comprenda
lo que son las listas circulares
II Definición
La lista circular es una especie de lista enlazada simple
o doblemente enlazada, pero que posee una característica adicional para
el desplazamiento dentro de la lista, "ésta no tiene fin"
Para que la lista sea sin fin, el puntero siguiente del último
elemento apuntará hacia el 1er elemento de la lista en lugar de
apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples
o doblemente enlazadas En las listas circulares, nunca se llega a una posición
en la que ya no sea posible desplazarse. Cuando se llegue al último elemento,
el desplazamiento volverá a comenzar desde el primer elemento.
III. La construcción del modelo de un elemento de
la lista
Para definir un elemento de la lista, el tipo struct será
utilizado. El elemento de la lista contendrá un campo dato y un
puntero siguiente. El puntero siguiente debe ser del mismo tipo
que el elemento, en caso contrario no podrá apuntar hacia el elemento.
El puntero siguiente permitirá el acceso hacia el próximo
elemento.
typedef struct ElementoLista {
char *dato;
struct ElementoLista *siguiente;
}Elemento;
Para tener el control de l alista es preferible guardar ciertos
elementos: el primer elemento, el último elemento, el número de
elementos. Para ello, otra estructura será utilizada (no es obligatorio,
pueden ser utilizadas variables)
typedef struct ListaIdentificar {
Elemento *inicio;
Elemento *fin;
int tamaño;
}Lista;
El punter inicio contendrá la dirección
del primer elemento de la lista. El puntero fin contendrá la dirección
del ultimo elemento de la lista. La variable tamaño contiene
el número de elementos. Cualquiera que sea la posición en la lista,
los punteros inicio y fin siempre apuntaran hacia el 1er y el
último elemento respectivamente. El campo tamaño contendrá
el número de elementos de la lista cualquiera sea la operación
efectuada sobre la lista.
IV. Operaciones sobre las listas circulares
A. Inicialización
Modelo de la función
void inicialización (Lista *lista);
Esta operación debe ser hecha antes de cualquier otra
operación sobre la lista. Inicializa el puntero inicio y el puntero
fin con el puntero NULL, y el tamaño con el valor 0. La función:
void inicialización (Lista *lista){
lista->inicio = NULL;
lista->fin = NULL;
tamaño = 0;
}
B. Inserción de un elemento en la lista
A continuación el algoritmo de inserción y registro
de los elementos:
declaración del elemento a insertar
asignación de la memoria para el nuevo elemento
rellenar el contenido del campo de datos
actualizar los punteros hacia el 1er y ultimo elemento
si es necesario.
Caso particular: en una lista con un solo elemento, el
1er elemento es al mismo tiempo el ultimo.Actualizar el tamaño de la lista.
1. Inserción en una lista vacía
Modelo de la función:
int ins_lista_circ_vacia(Lista * lista, char *dato);
La función devuelve -1 en caso de error, si no devuelve
0. Etapas:
asignación de memoria para el nuevo elemento
rellenar el campo de datos del nuevo elemento
el puntero siguiente del nuevo elemento apuntará
hacia si mismo (es la etapa que vuelve a la lista circular)los punteros inicio y fin apuntaran hacia
el nuevo elementoel tamaño es actualizado
La función:
/* inserción en una lista vacía */
int ins_lista_circ_vacia(Lista * lista, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = nuevo_elemento;
lista->inicio = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
2. Inserción en una lista no vacía
Modelo de la función:
int ins_lista_circ(Lista * lista, Elemento *actual, char *dato);
La función devuelve -1 en caso de error, si no devuelve
0. La inserción se efectuara al final de la lista. Etapas:
asignación de memoria para el nuevo elemento
rellenar el campo de datos del nuevo elemento
el puntero siguiente del nuevo elemento apunta
hacia la dirección del primer elemento (conservar la lista circular)el puntero inicio no cambia
el puntero fin apunta hacia el nuevo elemento
el tamaño se incrementa en una unidad
La función:
/* inserción en una lista no vacía */
int ins_lista_circ(Lista * lista, Elemento *actual, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
if(actual != lista->fin)
return -1;
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
C. Eliminación de un elemento en la lista
A continuación el algoritmo de eliminación de
un elemento de la lista:
uso de un puntero temporal para guardar la dirección
de los elementos a eliminarel elemento a eliminar se encuentra después del
elemento actual
Hacer apuntar el puntero siguiente del elemento actual
hacia la dirección del puntero siguiente del elemento a eliminar
liberar la memoria ocupada por el elemento eliminado
actualizar el tamaño de la lista
Para eliminar un elemento de la lista hay varias situaciones:
Eliminación dentro de la lista
Eliminación del último elemento de la lista
1. Eliminación al inicio de la lista
Modelo de la función:
int sup_list_circ(Lista *lista);
La función devuelve -1 en caso de error, si no devuelve
0. Etapas:
el puntero sup_elemento contendrá la dirección
del 1er elementoel puntero inicio apuntara hacia el 2do elemento
el puntero siguiente del ultimo elemento apuntara
hacia el 1er elemento (que era el 2do antes de la eliminación)el tamaño de la lista disminuirá 1 elemento.
La función:
/* eliminación al inicio de la lista */
int sup_lista_circ(Lista * lista){
if (lista->tamaño < 2)
return -1;
Elemento *sup_element;
sup_elemento = lista->inicio;
lista->inicio = lista->inicio->siguiente;
lista->fin->siguiente = lista->inicio;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño–;
return 0;
}
2. Eliminación en una lista con un solo elemento
Modelo de la función:
int sup_list_circ_unica(Lista *lista);
La función devuelve -1 en caso de error, si no devuelve
0. Etapas:
el puntero sup_elemento contendrá la dirección
del elemento (la lista contiene un solo elemento)el puntero inicio apuntara hacia NULL
el puntero fin apuntara hacia NULL
el tamaño de la lista disminuirá un elemento.
La función:
/* eliminación en una lista con un solo elemento*/
int sup_lista_circ_unica(Lista *lista){
if (lista->tamaño != 1)
return -1;
Elemento *sup_elemento;
sup_elemento = lista->inicio;
lista->inicio = NULL;
lista->fin = NULL;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño–;
return 0;
}
D. Mostrar la lista
Para mostrar la lista completa, es necesario posicionarse
al inicio de la lista (el puntero inicio lo permitirá). Luego,
utilizando el puntero siguiente de cada elemento, la lista es recorrida
del 1er al ultimo elemento. En comparación con las listas simples y doblemente
enlazadas, en el que la condición para detenerse esta dada por el puntero
siguiente del ultimo elemento, que vale NULL, para la lista circular,
no hay punto de detención, a menos que elijamos uno. A continuación
dos variantes de visualización:
Mostrar la lista (del 1er al último elemento)
Mostrar la lista sin una condición para detenerse.
1. Mostrar la lista (del 1er al último elemento)
Utilizaremos el tamaño de la lista como la condición
para detenerse. La función:
/* mostrar la lista */
void mostrar (Lista * lista){
Elemento *actual;
actual = lista->inicio;
int i;
for(i=0;itamaño;++i){
printf ("%p – %sn", actual, actual->dato);
actual = actual->siguiente;
}
}
2. Mostrar la lista sin una condición para detenerse
(indefinidamente )
La función:
/* recorrer la lista indefinidamente*/
void mostrar_indefinidamente (Lista * lista){
Elemento *actual;
actual = lista->inicio;
while (1){
printf ("%p – %sn", actual, actual->dato);
actual = actual->siguiente;
}
}
E. Destrucción de la lista
Para destruir la lista completa, he utilizado al eliminación
al inicio de la lista ya que el tamaño es mayor a 1, luego la eliminación
en una lista con un solo elemento. La función:
/* destruir la lista */
void destruir (Lista * lista){
while (lista->tamaño > 0){
if(lista->tamaño > 1)
sup_lista_circ (lista);
else
sup_lista_circ_unica(lista);
}
}
V. Ejemplo completo
lista_circ.h
/* ———- lista_circ.h ———– */
typedef struct ElementoListaCirc {
char *dato;
struct ElementoListaCirc *siguiente;
} Element;
typedef struct ListaIdentificarCirc {
Elemento *inicio;
Elemento *fin;
int tamaño;
} Lista;
/* inicialización de la lista */
void inicialización (Lista * lista);
/* INSERCION */
/* inserción en una lista vacia */
int ins_lista_circ_vacia(Lista * lista, char *dato);
int ins_lista_circ(Lista * lista, Elemento *actual, char *dato);
/* ELIMINACION */
int sup_lista_circ (Lista * lista);
int sup_lista_circ_unica (Lista * lista);
int menu (Lista *lista);
void mostrar (Lista * lista);
void mostrar_infinito (Lista * lista);
void destruir (Lista * lista);
/* ——– FIN lista_circ.h ——— */
lista_circ_function.h
/******************************
* lista_circ_function.h *
******************************/
void inicialización (Lista * lista){
lista->inicio = NULL;
lista->fin = NULL;
lista->tamaño = 0;
}
/* inserción en una lista vacia */
int ins_lista_circ_vacia(Lista * lista, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = nuevo_elemento;
lista->inicio = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño;
return 0;
}
/* inserción en una lista no vacia */
int ins_lista_circ(Lista * lista, Elemento *actual, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
if(actual != lista->fin)
return -1;
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño;
return 0;
}
/* eliminación al inicio de la lista */
int sup_lista_circ(Lista * lista){
if (lista->tamaño < 2)
return -1;
Elemento *sup_elemento;
sup_elemento = lista->inicio;
lista->inicio = lista->inicio->siguiente;
lista->fin->siguiente = lista->inicio;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño–;
return 0;
}
/* eliminación en una lista con un solo elemento*/
int sup_lista_circ_unica(Lista *lista){
if (lista->tamaño != 1)
return -1;
Elemento *sup_elemento;
sup_elemento = lista->inicio;
lista->inicio = NULL;
lista->fin = NULL;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño–;
return 0;
}
/* mostrar la lista */
void mostrar (Lista * lista){
Elemento *actual;
actual = lista->inicio;
int i;
for(i=0;itamaño;++i){
printf ("%p – %sn", actual, actual->dato);
actual = actual->siguiente;
}
}
/* recorrer la lista indefinidamente*/
void mostrar_infinito (Lista * lista){
Elemento *actual;
actual = lista->inicio;
while (1){
printf ("%p – %sn", actual, actual->dato);
actual = actual->siguiente;
}
}
/* destruir la liste */
void destruir (Lista * lista){
while (lista->tamaño > 0){
if(lista->tamaño > 1)
sup_lista_circ (lista);
else
sup_lista_circ_unica(lista);
}
}
int menu (Lista *lista){
int elección; printf("********** MENU **********n");
if (lista->tamaño == 0){
printf ("1. Adicion del 1er elementon");
printf ("2. Quitarn");
}else {
printf ("1. Adición de un elementon");
printf ("2. Eliminación al inicio (la lista debe
tener al menos 2 elementos)n");
printf ("3. Eliminación en una lista con un solo
elementon");
printf ("4. Mostrar lista circularn");
printf ("5. Mostrar lista circular [Ctrl-C] para quitar
el programan");
printf ("6. Destruir la listan");
printf ("7. Quitarn");
}
printf ("nnElegir: ");
scanf ("%d", &elección);
getchar();
if(lista->tamaño == 0 && elección == 2)
elección = 7;
return elección;
}
/* ——– FIN lista_circ_function ——— */
lista_circ.c
/**********************
* lista_circ.c *
**********************/
#include
#include
#include
#include "lista_circ.h"
#include "lista_circ_function.h"
int main (void)
{
char elección;
char *nom;
Lista *lista;
Elemento *actual;
if ((lista = (Lista *) malloc (sizeof (lista))) == NULL)
return -1;
if ((nombre = (char *) malloc (50)) == NULL)
return -1;
actual = NULL;
elección = 'o';
inicialización (lista);
while (elección != 7){
elección = menu (lista);
switch (elección){
case 1:
printf ("Ingrese un elemento: ");
scanf ("%s", nombre);
getchar ();
if(lista->tamaño == 0)
ins_lista_circ_vacia (lista,nombre);
else
ins_lista_circ (lista,lista->fin,nombre);
printf ("%d elements:deb=%s, fin=%sn",
lista->tamaño,
lista->inicio->dato,
lista->fin->dato);
mostrar (lista);
break;
case 2:
if(lista->tamaño < 2)
break;
sup_lista_circ (lista);
if (lista->tamaño != 0)
printf ("%d elements:deb=%s, fin=%sn",
lista->tamaño,
lista->inicio->dato,
lista->fin->dato);
mostrar(lista);
break;
case 3:
if(lista->tamaño != 1)
break;
sup_lista_circ_unica(lista);
printf("La lista está vacian");
break;
case 4:
mostrar(lista);
break;
case 5:
mostrar_infinito(lista);
break;
case 6:
destruir (lista);
printf ("la lista ha sido destruida: %de elementosn",
lista->tamaño);
break;
}
}
return 0;
}
Licencia
Este documento es una compilación de varios artículos.
Los artículos originales fueron escritos por lami20j,
contribuidor de CommentCaMarche:
http://www.commentcamarche.net/faq/7444-liste-simplement-chainee
http://www.commentcamarche.net/faq/7636-liste-doublement-chainee#2-insertion-au-inicio-de-la-liste
http://www.commentcamarche.net/faq/8283-les-piles-en-langage-c#iii-la-construction-du-prototype-d-un-element-de-la-pile
http://www.commentcamarche.net/faq/8282-les-filas-en-langage-c
http://www.commentcamarche.net/faq/8225-listes-circulaires-ring-buffer
Los artículos revisados y traducidos en los cuales
está basado este documento fueron escritos por Carlos-vialfa, contribuidor
de Kioskea.net:
http://es.kioskea.net/faq/2842-la-lista-enlazada-simple
http://es.kioskea.net/faq/2872-listas-doblemente-enlazadas
http://es.kioskea.net/faq/2885-las-pilas-en-lenguaje-c
http://es.kioskea.net/faq/2902-las-filas-en-lenguaje-c
http://es.kioskea.net/faq/2972-las-listas-circulares-ring-buffer
Todos los artículos originales y el presente documento
están puestos a diposición bajo la licencia Creative Commons.
Puede copiar, modificar bajo las condiciones puestas por la licencia, siempre
que esta nota sea visible.
Autor:
Nn
 Página anterior | Volver al principio del trabajo | Página siguiente  |