sdfsqualo
03 de Junio del 2004

Necesito hacer un programa en C++ que implemente una lista doblemente enlazada usando punteros y contenga las funciones para agregar, eliminar, buscar y ordenar elementos.

Consideraciones:
Cada nodo debe ser un registro (struct) y contener una palabra (además de los punteros de enlace).
El sistema debe presentar un menú con las opciones: “1. Agregar” , “2. Eliminar primero”, “3. Eliminar último”, “4. Imprimir lista”, “5. Buscar”, “6. Eliminar por posición”, “7. Ordenar” y “8. Salir”.
El método de ordenamiento puede ser burbuja, selección o quicksort y debe ordenar de menor a mayor fijandose en las letras de las palabras de la lista.
La opción “4. Imprimir lista” debe arrojar a pantalla los elementos de la lista hacia abajo.
La opción “5. Buscar” debe permitir ingresar una palabra a buscar en la lista desde teclado y debe arrojar la posición en la lista partiendo de 1.
La opción “6. Eliminar por posición” debe recibir un número entero con la posición en la lista (partiendo de 1) del elemento a eliminar. Debe verificar existencia del elemento.
Las opciones de eliminación deben considerar desocupar los espacios en memoria.
La opción “1. Agregar” debe recibir una palabra de pantalla y agregarla al final de la lista.
El programa no termina hasta que se elija la opción “Salir” del menú.

noel solw
03 de Junio del 2004

Empeza definiendo una lista doblemente enlazada

struct Node
{
char *str;
Node *next,*anterior;
};

construye la lista, proprcionando datos y trata de verla en la pantalla.
Luego sigue con los otros items, uno por uno.

Una pregunta indiscreta : ya has trabajado con listas simples ?
Si no lo has hecho te propongo que hagas un programa con listas simples antes de largarte con las doblemente enlazadas.
Exito ! ! !

c0de
03 de Junio del 2004

bueno venga, ya que estamos...

void insertarOrdenadoDobleEnlazada(TPListaDobleEnlazada &primero,
char c)
{
/* Esta función inserta un nodo en la lista doblemente enlazada
de forma ordenada*/
// declaración variables
TPListaDobleEnlazada nuevonodo, ptr, ant;
nuevonodo = new ListaDobleEnlazada;
if (nuevonodo == NULL)
{
cout << &#8221;No hay memoria suficiente&#8221; << endl;
}
else
{
nuevonodo->c = c;
nuevonodo->sig = NULL;
nuevonodo->ant = NULL;
if (primero == NULL)
{
/* La lista estaba vacia y nuevonodo se convierte en el
primer y único elemento de ésta */
primero = nuevonodo;
}
else
{
if (nuevonodo->c <= primero->c)
{
/* El elemento a insertar es menor que el primer elemento
de la lista */
nuevonodo->sig = primero;
primero->ant = nuevonodo;
primero = nuevonodo;
}
else
{
ant = primero;
ptr = primero->sig;
while ((ptr != NULL) &&
(nuevonodo->c > ptr->c))
{
ant = ptr;
ptr = ptr->sig;
}
if (ptr == NULL)
{
/* El elemento se inserta al final de la lista */
nuevonodo->ant = ant;
ant->sig = nuevonodo;
}
else
{
/* El elemento se inserta en medio de la lista */
nuevonodo->sig = ptr;
nuevonodo->ant = ant;
ant->sig = nuevonodo;
ptr->ant = nuevonodo;
}
}
}
}
}

void borrarFrenteDobleEnlazada(TPListaDobleEnlazada &primero)
{
// Este procedimiento borra el primer nodo de la lista
// declaración variables
TPListaDobleEnlazada punt;
if (primero != NULL)
{
punt = primero;
primero = primero->sig;
delete punt;
}
}


void borrarOrdenadoDobleEnlazada(TPListaDobleEnlazada &primero,
char c)
{
/* Este procedimiento borra un determinado elemento de
la lista*/
// declaración variables
TPListaDobleEnlazada act,ant;
ant = NULL;
act = primero;
while ((ptr != NULL) && (ptr->c != c))
{
ant = ptr;
ptr = ptr->sig;
}
if (ptr != NULL)
{ /* Se ha encontrado el elemento */
if (ant == NULL)
{ /* El elemento a borrar es el primero de la lista */
primero = primero->sig;
if (primero != NULL) primero->ant = NULL;
}
else if (ptr->sig == NULL)
{ /* El elemento a borrar es el ultimo de la lista */
ant->sig = NULL;
}
else
{ /*El elemento a borrar esta en el medio de la lista */
ant->sig = ptr->sig;
ptr->sig->ant = ant;
}
delete ptr;
}
}

c0de
03 de Junio del 2004

struct ListaDobleEnlazada
{ char c;
ListaDobleEnlazada* sig;
ListaDobleEnlazada* ant;
};

TPListaDobleEnlazada crearListaDobleEnlazada()
{
return NULL;
}

void insertarFrenteDobleEnlazada(TPListaDobleEnlazada &primero,
char c)
{
// Esta función inserta un nodo al principio de la lista
// declaración variables
TPListaDobleEnlazada punt;
punt = new ListaDobleEnlazada;
if (punt == NULL)
{
cout << &#8221;No hay memoria suficiente&#8221; << endl;
}
else
{
punt->c = c;
punt->sig = NULL;
punt->ant = NULL;
if (primero != NULL)
{
punt->sig = primero;
primero->ant = punt;
}
primero = punt;
}
}
typedef ListaDobleEnlazada *TPListaDobleEnlazada;

etc etc...