COMO CREAR LISTAS SIMPLES CON PUNTEROS
Enviado por MCPOOL92 • 25 de Septiembre de 2018 • Documentos de Investigación • 2.211 Palabras (9 Páginas) • 163 Visitas
ALGORITMOS Y ESTRUCTURA DE DATOS
LISTAS SIMPLES CON PUNTEROS
DEFINICION:
Las Listas Simples son un tipo de estructuras de datos que se caracterizan porque cada uno de sus elementos apunta o direcciona al siguiente, por lo cual también se le conoce con el nombre de listas Enlazadas.
GRAFICAMENTE:
[pic 1]
DEFINICION DE LA LISTA SIMPLE
struct Elemento
{
int dato;
Elemento *sig;
};
Elemento *p;
p = new Elemento;
p ->sig = NULL;
EXPLICACION
La estructura definida contiene un miembro que es un puntero a un objeto del mismo tipo. Esto permitirá a un elemento creado referenciar a su sucesor.
- La instrucción: Elemento *p, declara un puntero p a un objeto de tipo Elemento.
- La instrucción: p = new Elemento, crea (asigna memoria para) un objeto de tipo Elemento, genera un puntero (dirección de memoria) que referencia este nuevo objeto y asigna esta dirección a la variable p.
- La instrucción: p ->sig = NULL, asigna al miembro sig del objeto apuntado por p el valor NULL, indicando así que después de este elemento no hay otro.
- El valor NULL, dirección nula, nos permite crear estructuras finitas.
- Una declaración como p = NULL, indica una lista vacía.
REFERENCIAS DE OBJETOS POR MÁS DE UN PUNTERO
Un objeto se puede referenciar por mas de un puntero y también un objeto de un de
Terminado tipo puede copiarse en otro objeto del mismo tipo.
Ejemplo:
#include
#include
void (*_new_handler)(void);
void error_new(void);
struct elemento
{
int dato;
elemento *sig;
};
main()
{
elemento *p, *q, *r;
_new_handler = error_new; // error_new() sera invocada si ocurre un error al ejecutar new
// Creacion de dos objetos de tipo elemento apuntados por p y q respectivamente
p = new elemento;
q = new elemento;
p ->dato = 5;
// Copiar el objeto apuntado por p en el objeto apuntado por q.
*q = *p;
// r apunta al mismo objeto que q
r = q;
// Escribir 10
cout<
}
void error_new(void)
{
cerr<<"Error: insuficiente espacio de memoria"<
exit(1);
}
OPERACIONES BASICAS
Las operaciones basicas que desarrollaremos con listas, son:
- Inserción de un elemento en la lista
- Borrado de un elemento de la lista
- Recorrido de una lista
- Busqueda de un elemento en la lista
Desarrollaremos cada una de estas operaciones tomando como referencia la siguiente definición de la lista:
struct elemento
{
int dato;
elemento *sig;
};
elemento *p, *q;
INSERCION DE UN ELEMENTO AL INICIO DE LA LISTA
En primer lugar crearemos un elemento y después reasignaremos los punteros, de la siguiente manera:
q = new elemento;
q -> dato = n; // Asignación de valores
q -> sig = p; // Reasignación de punteros
p = q;
-Tener en cuenta que el orden para estas operaciones es fundamental
-A continuación presentamos el programa que sirve para crear una lista simple partiendo de una lista vacia:
elemento *p, *q;
int n;
cout<<”Introducir datos… Finalizar con ^Z ”<
p = NULL;
cout<<”dato : “;
while(cin>>n)
{
q = new elemento;
q -> dato = n;
q -> sig = p;
p = q;
cout<<”dato: “;
}
INSERCION DE UN ELEMENTO EN GENERAL
La inserción de un elemento en la lista, a continuación de otro elemento apuntado por p, es de la forma siguiente:
q = new elemento;
q -> dato = x; // Valor ingresado
q -> sig = p -> sig;
p -> sig = q;
GRAFICAMENTE:
[pic 2]
La inserción de un elemento en la lista antes de otro elemento apuntado por p, se hae insertando un nuevo elemento detrás del elemento apuntado por p, intercambiando previamente los valores del nuevo elemento y del elemento apuntado por p.
q = new elemento;
*q = *p;
p -> dato = x; // Valor insertado
p -> sig = q;
[pic 3]
BORRAR UN ELEMENTO DE LA LISTA
Para borrar el sucesor de un elemento apuntado por p, las operaciones a realizar son:
q = p -> sig;
p -> sig = q -> sig;
delete q;
[pic 4]
Para borrar un elemento apuntado por p, las operaciones a realizar, son:
q = p -> sig;
*p = *q;
delete q;
[pic 5]
EJEMPLO
#include
class Elem
{
private:
int dato;
Elem *sig;
Elem(int d=0, Elem *s = NULL)
...