Estructuras de Datos I 

Inicio

Generalidades

Ejercicios

Talleres

Proyecto

Ejercicios "amistosos"

Listas enlazadas

Las estructuras de datos estáticas exigen la reserva de tamaño en memoria antes de compilar el programa, pero se presentan casos en los que la cantidad de memoria necesaria no es fija. La asignación dinámica de memoria reserva un bloque de bytes en memoria para almacenar una estructura durante la ejecución del programa. Así se logra optimizar la utilización de este recurso.

En un programa se pueden implementar estructuras de manejo dinámico de memoria, como listas, pilas y colas. Estas mismas estructuras se pueden utilizar para realizar subrutinas de búsqueda y ordenamiento.

# include "iostream.h"
# include "conio.h"
# define cls clrscr()
// Programita, ejemplo sencillo para crear un lista enlazada

struct nodo {
   int info;
   nodo *sig;  // puntero al siguiente nodo
};
nodo *cab=0, *q;

void main(){
   cls; int tecla;
   cab=new nodo; // creacion del primer nodo
   if (cab==0){
       cout << "Memoria insuficiente!";getch();}
   else{
       q=cab;
       do{
          cls;
          cout <<"Creacion de Nodos..."<<endl<<endl;
          cout<< "Digite un numero : ";
          cin >> q->info;
          q->sig=0;
          cout << "ENTER para continuar, ESC para salir... ";
          tecla=getch();
          if (tecla!=27){
             q->sig=new nodo;
             q=q->sig;}
   }while(tecla!=27);
   }
   cls;
   cout << "Elementos de la lista..."<<endl<<endl;
   q=cab;
   if (q==0)
      cout << "Lista vacia!";
   else{
      while (q!=0){
              cout << q->info << " -> ";
              q=q->sig;
      }
   }
   cout <<"NULL"<<endl;
   cout <<endl<<"Adios, pues!";getch();
}

**************************************

// El siguiente programa ilustra el Software básico de Listas
// <Pingüino Gus>
// 27/08/99

# include "iostream.h"
# include "conio.h"
# include "stdlib.h"
# include "dos.h"
# include "stdio.h"
//#include "marcogmv.h"
#define cls clrscr()

struct tiponodo {
int numero;
struct tiponodo *sig;
};

void captura (struct tiponodo *);
tiponodo * cab = 0;

void marco(int t,int l,int b,int r,int f){
int col=l;
if (f==1){
gotoxy(l,t);printf("É");gotoxy(r,t);printf("»");
gotoxy(l,b);printf("È");gotoxy(r,b);printf("¼");
for (++l;l<r;++l){
gotoxy(l,t);printf("Í");gotoxy(l,b);printf("Í");
}
for (++t;t<b;++t){
gotoxy(col,t);printf("º");gotoxy(r,t);printf("º");
}
}else{
if (f==2){
gotoxy(l,t);printf("Ú");gotoxy(r,t);printf("¿");
gotoxy(l,b);printf("À");gotoxy(r,b);printf("Ù");
for (++l;l<r;++l){
gotoxy(l,t);printf("Ä");gotoxy(l,b);printf("Ä");
}
for (++t;t<b;++t){
gotoxy(col,t);printf("³");gotoxy(r,t);printf("³");
}
}else{
if (f==3){
++r;
for (l;l<r;++l){
gotoxy(l,t);printf("Í");
}
}else{
if (f==4){
++r;
for (l;l<r;++l){
gotoxy(l,t);printf("Ä");
}
}
}
}
}
}

pmenu(){
int c;
textbackground(BLUE);textcolor(WHITE);
cls;
marco(1,1,24,80,1);
gotoxy (21, 5); cout <<" U N I V E R S I D A D DE I B A G U E";
gotoxy (31, 6); cout <<"<CORUNIVERSITARIA>";
gotoxy (27, 8); cout <<"M E N U D E L I S T A S";
marco(10,32,15,49,2);
gotoxy (34,11); cout <<"[1] Adicionar";
gotoxy (34,12); cout <<"[2] Borrar";
gotoxy (34,13); cout <<"[3] Listar";
gotoxy (34,14); cout <<"[4] Ordenar";
gotoxy (29,17); cout <<"Escoja su opcion...? [ ]";
gotoxy (24,19); cout <<"Para terminar pulse la tecla [ESC]";
gotoxy(51,17);c=getch();
return c;
}

struct tiponodo * creanodo(){
struct tiponodo *p;
p=new tiponodo;
if (p==0){
marco(11,20,13,61,1);
gotoxy(22,12);cout <<"Memoria insuficiente... Presione [ESC]";
while (getch() != 27);
exit(1);
}
p->sig=0;
return p;
}

void adicionar(){
struct tiponodo *p;
p=cab;
if (cab==0){
cab=creanodo();
captura(cab);
}else{
while (p->sig != 0)
p=p->sig;
p->sig=creanodo();
captura(p->sig);
}
}

void captura(struct tiponodo *p){
struct tiponodo *q;
int c;
cls;
marco(5,5,20,75,1);
gotoxy(31,5);cout <<" ADICIONAR NUMEROS ";
marco(11,30,13,51,2);
gotoxy(32,12);cout <<"Numero --> [ ]";
do{
gotoxy(44,12);cin >>p->numero;
p->sig=0;
marco(17,20,17,61,4);
gotoxy(20,16);cout <<"[ENTER] = Adicionar Otro, [ESC] = Regresar";
c=getch();
if (c==13){
p->sig=creanodo();
p=p->sig;
gotoxy(44,12);cout <<" ";
}
gotoxy(20,16);cout <<" ";
gotoxy(20,17);cout <<" ";
}
while (c != 27);
}

void listar(){
struct tiponodo *p;
int lin=4,col=10;
p=cab;
cls;
if (cab==0){
marco(11,24,13,56,1);
gotoxy(26,12);cout <<"Lista vacia... Presione [ESC]";
}else{
marco(3,2,21,78,1);
gotoxy(32,3);cout <<" LISTA DE NUMEROS ";
while (p != 0){
++lin;
if (lin>19){
lin=5;col=col+10;
if (col>70)
col=10;
}
gotoxy(col,lin);cout <<p->numero;
p=p->sig;
}
gotoxy (24,23); cout <<"Para Regresar pulse la tecla [ESC]";
}
while (getch() != 27);
}

void borrar(){
struct tiponodo * mem=0, *p;
int num;
p=cab;
cls;
if (cab==0){
marco(11,24,13,56,1);
gotoxy(26,12);cout <<"Lista vacia... Presione [ESC]";
while (getch() != 27);
}else{
marco(5,5,20,75,1);
gotoxy(31,5);cout <<" ELIMINAR NUMEROS ";
marco(11,30,13,51,2);
gotoxy(32,12);cout <<"Numero --> [ ]";
gotoxy(44,12);cin >>num;
while (p->sig != 0){
if (p->numero==num){
if (p==cab)
cab=p->sig;
else
mem->sig=p->sig;
//free(p);
delete p;
return;
}else{
mem=p;
p=p->sig;
}
}
if (p->numero==num){
if (cab==p){
cab=0;
free(p);
}else{
if (p->sig==0){
mem->sig=0;
free(p);
}
}
}else{
cls;
marco(11,17,13,64,1);
gotoxy(19,12);cout <<"N£mero "<<num<<" NO Encontrado... Presione [ESC]";
while (getch() != 27);
}
}
}

void ordenar(){
struct tiponodo *p, *q;
int temp;
p=cab;
cls;
if (cab==0){
marco(11,24,13,56,1);
gotoxy(26,12);cout <<"Lista vacia... Presione [ESC]";
while (getch() != 27);
}else{
marco(11,30,13,50,1);
gotoxy(32,12);cout <<"O R D E N A N D O";
getch(); //delay(1500);
while (p->sig != 0){
q=p->sig;
while (q != 0){
if (p->numero > q->numero){
temp=p->numero;
p->numero=q->numero;
q->numero=temp;
}
q=q->sig;
}
p=p->sig;
}
listar();
}
}

void main(){
int c;
c=pmenu();
while (c != 27){
switch(c){
case '1': adicionar();break;
case '2': borrar();break;
case '3': listar();break;
case '4': ordenar();break;
default : gotoxy(24,21);cout <<"Opcion inv lida... Presione [ESC]";
marco(22,24,22,56,4);
while (getch() != 27);
break;
}
c=pmenu();
}cls;
}

**************************************

Codificar los siguientes programas de computación en Lenguaje C/C++ :

1. Crear una lista lineal enlazada sencilla, cuyos nodos tienen la estructura (Info y Enlace) y diseñar una función que imprima cuántos nodos tiene la lista.

2. Modificar el campo Info del nodo N-ésimo de la lista anterior por un valor dado X.

3. Crear una lista enlazada para guardar el directorio telefónico de los alumnos del curso. Diseñar un menú con las opciones de Adicionar, Insertar, Consultar,  Modificar, Borrar  e Imprimir nodos de la lista.

4. Crear una lista enlazada con los sueldos de N empleados e imprimir la lista en forma descendente.

5. Escribir un programa que lea una cadena, guardando cada caracter en una Pila a medida que se lee y adicionando simultáneamente a una Cola.

6. Almacenar en una Cola la información de los vehículos que llegan a una estación de gasolina: Marca, modelo, año, placa, color, valor pagado por el servicio. a) Cuántos carros marca 'Mazda' fueron atendidos?. b) Porcentaje de vehículos de color azul?. c) Valor promedio recaudado por la estación?.

7. Un Aparta-Hotel tiene 25 habitaciones, de las cuales 14 están ocupadas. Escriba un programa modular (con paso de parámetros) que permita imprimir el número de habitación y el nombre del huésped, correspondiente a los nodos de la lista que representan las habitaciones alquiladas.