LISTA ENLAZADA SIMPLE. La lista enlazada básica es la lista enlazada simple la cual tiene un...

LISTA ENLAZADA SIMPLE

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

He aquí tenemos un ejemplo de una lista enlazada simple:

DECLARACIÓN DE PROTOTIPOS

#include<alloc.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>

DECLARAMOS LA ESTRUCTURA

typedef struct nodo{int dato;struct nodo * siguiente;}tipoNodo;

RESERVAMOS EL ESPACIO DE MEMORIA

tipoNodo *nuevo_elemento();

OPERACIONES QUE VAMOS A AREALIZAR

void crear();void insertar();void insertar_inicio();void insertar_ordenado();void insertar_final();void presentar();void modificar();void buscar();void ordenar();void ordenar_ascendente();void ordenar_descendente();void eliminar();void eliminar_cabeza();

FUNCIÓN PARA EL CUADRO

void cuadro(int x1,int y1, int x2, int y2, char simb);

NUESTRA CABEZA

tipoNodo *cab;

tipoNodo *nuevo_elemento(){tipoNodo *nodo1;nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));if(!nodo1)cout<<“No se ha reservado memoria para el nuevo “;return nodo1;}

void  main(){clrscr();crear();clrscr();char opc=’ ‘;

do{

clrscr();cuadro(1,10,35,56,’²’);gotoxy(13,3);cout<<“->[ LISTAS ENLAZADAS ]<-\n”;gotoxy(12,6);cout<<”    MENU PRINCIPAL\n”;gotoxy(12,9); cout<<” [1]:  INSERTAR\n”;gotoxy(12,12);cout<<” [2]:  MODIFICAR\n”;gotoxy(12,15);cout<<” [3]:  BUSCAR\n”;gotoxy(12,17);cout<<” [4]:  ORDENAR\n”;gotoxy(12,19);cout<<” [5]:  ELIMINAR\n”;gotoxy(12,21);cout<<” [6]:  PRESENTAR\n”;gotoxy(12,24);cout<<” [7]:  SALIR DEL MENU\n”;

gotoxy(12,27);cout<<” Elegir una Opci¢n [ ]”;gotoxy(32,27);cin>>opc;

switch(opc){case’1′:clrscr();insertar();getch();break;case’2′:clrscr();modificar();getch();break;case’3′:clrscr();buscar();getch();break;case’4′:clrscr();ordenar();getch();break;case’5′:clrscr();eliminar();getch();break;

case’6′:clrscr();presentar();getch();break;

}

}while(opc!=’7′);

getch();

}

CREANDO LA CABEZA

void crear(){clrscr();cab=nuevo_elemento();gotoxy(20,20);cout<<“Ingrese valor de cabeza :\t”;cin>>cab->dato;cab->siguiente=NULL;getch();

}

MENU DE INSERTAR

void insertar(){clrscr();char opc=’ ‘;

do{

clrscr();cuadro(1,10,35,56,’²’);gotoxy(13,3);cout<<“->[ LISTAS ENLAZADAS ]<-\n”;gotoxy(12,6);cout<<”    MENU PRINCIPAL\n”;gotoxy(12,9); cout<<” [1]:  INSERTAR AL INICIO\n”;gotoxy(12,12);cout<<” [2]:  insertar AL FINAL\n”;gotoxy(12,15);cout<<” [3]:  INSERTAR ORDENADO\n”;gotoxy(12,18);cout<<” [4]:  REGRESAR\n”;

gotoxy(12,21);cout<<” Elegir una Opci¢n [ ]”;gotoxy(32,21);cin>>opc;

switch(opc){case’1′:clrscr();insertar_inicio();getch();break;case’2′:clrscr();insertar_final();getch();break;case’3′:clrscr();insertar_ordenado();getch();break;

}

}while(opc!=’4′);

getch();

}

INSERATAR AL INICIO

void insertar_inicio(){clrscr();

nodo *pAuxElem;nodo *recorre;pAuxElem=(tipoNodo*) malloc(sizeof(tipoNodo));while(recorre->siguiente!=NULL){recorre=recorre->siguiente;}

int n;gotoxy(20,20);cout<<“INGRESE VALOR  :\t”;cin>>n;pAuxElem->dato=n;pAuxElem->siguiente=cab;cab=pAuxElem;}

INSERTAR AL FINAL

void insertar_final(){clrscr();nodo *elem;elem=nuevo_elemento();clrscr();gotoxy(20,20);cout<<“INGRESE VALOR  :\t”;cin>>elem->dato;nodo *recorrer;recorrer=cab;while(recorrer->siguiente!=NULL)recorrer=recorrer->siguiente;recorrer->siguiente=elem;elem->siguiente=NULL;getch();}

INSERTAR ORDENADO

void insertar_ordenado(){clrscr();nodo *pAuxElem;nodo *post;nodo *recorre;pAuxElem=(tipoNodo*) malloc(sizeof(tipoNodo));post=(tipoNodo*) malloc(sizeof(tipoNodo));int n;gotoxy(20,20);cout<<“INGRESE VALOR  :\t”;cin>>n;

if(n<cab->dato){

post=cab->siguiente;while((pAuxElem->dato>post->dato)&&(post->siguiente!=NULL)){post=post->siguiente;}

if(post->siguiente!=NULL){pAuxElem->siguiente=cab;cab=pAuxElem;}else{pAuxElem->siguiente=NULL;post->siguiente=pAuxElem;}

}else{while(recorre->siguiente!=NULL){recorre=recorre->siguiente;}pAuxElem->dato=n;pAuxElem->siguiente=cab;cab=pAuxElem;}

PARA MODIFICAR

void modificar(){clrscr();nodo *elem;nodo *ele;gotoxy(10,25);cout<<“ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;gotoxy(10,26);cout<<“º                          º\n”;gotoxy(10,27);cout<<“ºMODIFICAR NUMERO DE LISTA º\n”;gotoxy(10,28);cout<<“º                          º\n”;gotoxy(10,29);cout<<“ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;gotoxy(20,20);cout<<“INGRESE EL VALOR A MODIFICAR :\t”;cin>>elem->dato;nodo *recorrer;recorrer=cab;

while(recorrer!=NULL){

if(recorrer->dato==elem->dato){clrscr();gotoxy(20,20);cout<<“INGRESE VALOR  :\t”;cin>>ele->dato;

recorrer->dato=ele->dato;}recorrer=recorrer->siguiente;

}getch();}

PARA BUSCAR

void buscar(){clrscr();nodo *elem;

gotoxy(10,25);cout<<“ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;gotoxy(10,26);cout<<“º                           º\n”;gotoxy(10,27);cout<<“ºBUSCADOR DE NUMERO DE LISTAº\n”;gotoxy(10,28);cout<<“º                           º\n”;gotoxy(10,29);cout<<“ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;gotoxy(20,20);cout<<“INGRESE EL VALOR A BUSCAR :\t”;cin>>elem->dato;nodo *recorrer;recorrer=cab;while(recorrer!=NULL){

if(recorrer->dato==elem->dato){clrscr();gotoxy(20,20);cout<<elem->dato<<“:\t”;cout<<“ESTE ELEMENTO SI EXISTE”;recorrer->dato=elem->dato;}

recorrer=recorrer->siguiente;

}

getch();}

ORDENAR

void ordenar(){clrscr();char opc=’ ‘;

do{

clrscr();cuadro(1,10,25,56,’²’);gotoxy(13,3);cout<<“->[ ORDENAR  LAS LISTAS ENLAZADAS ]<-\n”;gotoxy(12,6);cout<<”    MENU PRINCIPAL\n”;gotoxy(12,9); cout<<” [1]:  ORDENAR ASCENDENTE\n”;gotoxy(12,12);cout<<” [2]:  ORDENAR DESCENDENTE\n”;gotoxy(12,15);cout<<” [3]:  REGRESAR\n”;

gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]”;gotoxy(32,17);cin>>opc;

switch(opc){case’1′:clrscr();ordenar_ascendente();getch();break;case’2′:clrscr();ordenar_descendente();getch();break;

}

}while(opc!=’3′);

getch();

}

void ordenar_ascendente(){nodo* aux;nodo* temp;int vaux;aux=(tipoNodo *)malloc(sizeof(tipoNodo));temp=(tipoNodo *)malloc(sizeof(tipoNodo));aux=cab;

while (aux!=NULL){temp=aux;while(temp->siguiente!=NULL){temp=temp->siguiente;if(aux->dato>temp->dato){vaux=aux->dato;aux->dato=temp->dato;temp->dato=vaux;}}aux=aux->siguiente;}}

void ordenar_descendente(){nodo* aux;nodo* temp;int vaux;aux=(tipoNodo *)malloc(sizeof(tipoNodo));temp=(tipoNodo *)malloc(sizeof(tipoNodo));aux=cab;

while (aux!=NULL){temp=aux;while(temp->siguiente!=NULL){temp=temp->siguiente;if(aux->dato<temp->dato){vaux=aux->dato;aux->dato=temp->dato;temp->dato=vaux;}}aux=aux->siguiente;}}

ELIMINAR

void eliminar(){presentar();nodo *eliminar;//    nodo *recorrer;nodo *asigna;gotoxy(10,25);cout<<“ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;gotoxy(10,26);cout<<“º                          º\n”;gotoxy(10,27);cout<<“ºINSERTAR NUMERO A ELIMINARº\n”;gotoxy(10,28);cout<<“º                          º\n”;gotoxy(10,29);cout<<“ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;gotoxy(10,31);cout<<“Ingrese el n—mero a eliminar\t”;cin>>eliminar->dato;

//    recorrer=cab;if (eliminar->dato==cab->dato){

eliminar_cabeza();}else{nodo *anterior=cab;nodo * aux=cab->siguiente;

while((aux!=NULL)&&(aux->dato!=eliminar->dato)){anterior=aux;aux=aux->siguiente;}if(aux!=NULL){anterior->siguiente=aux->siguiente;aux->siguiente=NULL;free(aux);

}else{gotoxy(10,33);cout<<“NO SE ENCUENTRA”;}}

}

ELIMINAR CABEZA

void eliminar_cabeza(){nodo *aux;aux=cab;cab=cab->siguiente;aux->siguiente=NULL;free(aux);}

PRESENTAR LA LISTA

void presentar(){clrscr();int f=10;nodo *recorrer;recorrer=cab;gotoxy(20,f);while(recorrer!=NULL){gotoxy(20,f);cout<<recorrer->dato;cout<<“\n\n”;

recorrer=recorrer->siguiente;f=f+2;}getch();}

PRESENTAR LOS BORDES DE UN CUADRO

void cuadro(int x1,int y1, int x2, int y2, char simb){for (int i1=y1;i1<=y2;i1++){gotoxy(i1,x1);cout<<simb;gotoxy(i1,x2);cout<<simb;}for (int i2=x1;i2<=x2;i2++){gotoxy(y1,i2);cout<<simb;gotoxy(y2,i2);cout<<simb;}}