Inicio

Temas

Listas Simplemente (LSE) y Doblemente enlazadas (LDE)

Estructuras de Datos en Grafos

Operaciones Insertar, Eliminar y Buscar en LSE

Estos métodos son los mas básicos que podemos crear a partir de la “lógica del puntero”, y la implementación de otros métodos basados en la misma idea queda a gusto (o necesidad) del programador. Por ejemplo, podríamos crear métodos que filtren la lista según una característica de los clientes (como discriminar entre los clientes frecuentes y los no frecuentes), o un método que traspase los datos de los clientes a un archivo de texto para guardarlos, y otro que sea capaz de leer este archivo y llenar una lista con los datos guardados. En fin, hay infinitas posibilidades.

Insertar:

Para añadir un nodo a la lista, primero creamos un nodo, al que llamaremos nodo, que contenga un número por el argumento, al que llamaremos nro. Luego conectamos un nodo con el último nodo de la lista. Para referirnos a éste, creamos un puntero al primer nodo y avanzamos hasta el último.

Ahora que el puntero apunta al último nodo de la lista, haremos que el siguiente nodo al que apunte este último de la lista tome el valor de nuetro nodo a insertar. El proceso para añadir un nodo al principio de la lista es muy parecido e incluso más fácil.

Eliminar:

Para eliminar un nodo X, hay que almacenar en un puntero la ubicación del nodo anterior a este, para luego hacer que apunte al siguiente nodo de X, sacándolo de la lista.

Buscar:

Para buscar un nodo tenemos que recorrer la lista, a traves de un puntero, e ir comparando uno a uno los nodos con el valor de la busqueda y retornar su ubicación de ser encontrado.

Implementación de estas operaciones:

                    
                        #include <iostream>
                        #include <stdlib.h>
                        using namespace std;
                         
                        struct nodo{
                               int nro;        // en este caso es un numero entero
                               struct nodo *sgte;
                        };
                         
                        typedef struct nodo *Tlista;
                         
                        void insertarInicio(Tlista &lista, int valor)
                        {
                            Tlista q;
                            q = new(struct nodo);
                            q->nro = valor;
                            q->sgte = lista;
                            lista  = q;
                        }
                         
                        void insertarFinal(Tlista &lista, int valor)
                        {
                            Tlista t, q = new(struct nodo);
                         
                            q->nro  = valor;
                            q->sgte = NULL;
                         
                            if(lista==NULL)
                            {
                                lista = q;
                            }
                            else
                            {
                                t = lista;
                                while(t->sgte!=NULL)
                                {
                                    t = t->sgte;
                                }
                                t->sgte = q;
                            }
                         
                        }
                         
                        int insertarAntesDespues()
                        {
                            int _op, band;
                            cout<<endl;
                            cout<<"\t 1. Antes de la posicion           "<<endl;
                            cout<<"\t 2. Despues de la posicion         "<<endl;
                         
                            cout<<"\n\t Opcion : "; cin>> _op;
                         
                            if(_op==1)
                                band = -1;
                            else
                                band = 0;
                         
                            return band;
                        }
                         
                        void insertarElemento(Tlista &lista, int valor, int pos)
                        {
                            Tlista q, t;
                            int i;
                            q = new(struct nodo);
                            q->nro = valor;
                         
                            if(pos==1)
                            {
                                q->sgte = lista;
                                lista = q;
                            }
                            else
                            {
                                int x = insertarAntesDespues();
                                t = lista;
                         
                                for(i=1; t!=NULL; i++)
                                {
                                    if(i==pos+x)
                                    {
                                        q->sgte = t->sgte;
                                        t->sgte = q;
                                        return;
                                    }
                                    t = t->sgte;
                                }
                            }
                            cout<<"   Error...Posicion no encontrada..!"<<endl;
                        }
                         
                        void buscarElemento(Tlista lista, int valor)
                        {
                            Tlista q = lista;
                            int i = 1, band = 0;
                         
                            while(q!=NULL)
                            {
                                if(q->nro==valor)
                                {
                                    cout<<endl<<" Encontrada en posicion "<< i <<endl;
                                    band = 1;
                                }
                                q = q->sgte;
                                i++;
                            }
                         
                            if(band==0)
                                cout<<"\n\n Numero no encontrado..!"<< endl;
                        }
                         
                        void reportarLista(Tlista lista)
                        {
                             int i = 0;
                         
                             while(lista != NULL)
                             {
                                  cout <<' '<< i+1 <<") " << lista->nro << endl;
                                  lista = lista->sgte;
                                  i++;
                             }
                        }
                         
                         
                        void eliminarElemento(Tlista &lista, int valor)
                        {
                            Tlista p, ant;
                            p = lista;
                         
                            if(lista!=NULL)
                            {
                                while(p!=NULL)
                                {
                                    if(p->nro==valor)
                                    {
                                        if(p==lista)
                                            lista = lista->sgte;
                                        else
                                            ant->sgte = p->sgte;
                         
                                        delete(p);
                                        return;
                                    }
                                    ant = p;
                                    p = p->sgte;
                                }
                            }
                            else
                                cout<<" Lista vacia..!";
                        }
                         
                        void eliminaRepetidos(Tlista &lista, int valor)
                        {
                            Tlista q, ant;
                            q = lista;
                            ant = lista;
                         
                            while(q!=NULL)
                            {
                                if(q->nro==valor)
                                {
                                    if(q==lista) // primero elemento
                                    {
                                        lista = lista->sgte;
                                        delete(q);
                                        q = lista;
                                    }
                                    else
                                    {
                                        ant->sgte = q->sgte;
                                        delete(q);
                                        q = ant->sgte;
                                    }
                                }
                                else
                                {
                                    ant = q;
                                    q = q->sgte;
                                }
                         
                            }// fin del while
                           
                            cout<<"\n\n Valores eliminados..!"<<endl;
                        }
                         
                        void menu1()
                        {
                            cout<<"\n\t\tLISTA ENLAZADA SIMPLE\n\n";
                            cout<<" 1. INSERTAR AL INICIO               "<<endl;
                            cout<<" 2. INSERTAR AL FINAL                "<<endl;
                            cout<<" 3. INSERTAR EN UNA POSICION         "<<endl;
                            cout<<" 4. REPORTAR LISTA                   "<<endl;
                            cout<<" 5. BUSCAR ELEMENTO                  "<<endl;
                            cout<<" 6. ELIMINAR ELEMENTO 'V'            "<<endl;
                            cout<<" 7. ELIMINAR ELEMENTOS CON VALOR 'V' "<<endl;
                            cout<<" 8. SALIR                            "<<endl;
                         
                            cout<<"\n INGRESE OPCION: ";
                        }
                         
                         
                        /*                        Funcion Principal
                        ---------------------------------------------------------------------*/
                         
                        int main()
                        {
                            Tlista lista = NULL;
                            int op;     // opcion del menu
                            int _dato;  // elemenento a ingresar
                            int pos;    // posicion a insertar
                         
                         
                            system("color 0b");
                         
                            do
                            {
                                menu1();  cin>> op;
                         
                                switch(op)
                                {
                                    case 1:
                         
                                         cout<< "\n NUMERO A INSERTAR: "; cin>> _dato;
                                         insertarInicio(lista, _dato);
                                    break;
                         
                         
                                    case 2:
                         
                                         cout<< "\n NUMERO A INSERTAR: "; cin>> _dato;
                                         insertarFinal(lista, _dato );
                                    break;
                         
                         
                                    case 3:
                         
                                         cout<< "\n NUMERO A INSERTAR: ";cin>> _dato;
                                         cout<< " Posicion : ";       cin>> pos;
                                         insertarElemento(lista, _dato, pos);
                                    break;
                         
                         
                                    case 4:
                         
                                         cout << "\n\n MOSTRANDO LISTA\n\n";
                                         reportarLista(lista);
                                    break;
                         
                         
                                    case 5:
                         
                                         cout<<"\n Valor a buscar: "; cin>> _dato;
                                         buscarElemento(lista, _dato);
                                    break;
                         
                                    case 6:
                         
                                        cout<<"\n Valor a eliminar: "; cin>> _dato;
                         
                                        eliminarElemento(lista, _dato);
                                    break;
                         
                                    case 7:
                         
                                        cout<<"\n Valor repetido a eliminar: "; cin>> _dato;
                         
                                        eliminaRepetidos(lista, _dato);
                                    break;
                         
                                            }
                         
                                cout<<endl<<endl;
                                system("pause");  system("cls");
                         
                            }while(op!=8);
                         
                         
                           system("pause");
                           return 0;
                        }

Links de apoyo

Operaciones sobre una Lista

Listas Enlazadas Simples Lineales en C++

Siguiente tema:

Estructura y diseño de una LDE >>

Algoritmos y Estructura de Datos

Temas

Listas Simplemente (LSE) y Doblemente enlazadas (LDE)

Árboles Binarios

Árboles Binarios Equilibrados

Matrices poco Densas

Tablas Hash

Estructuras de Datos en Grafos

Rutas más cortas

Algortimos sobre Grafos

Árboles multicamino

Operaciones Insertar, Eliminar y Buscar en LSE

Insertar:

Eliminar:

Buscar:

Implementación de estas operaciones: