hola quiero poder ordenar una lista enlazada por insercion pero solo me cambia un parametro de los 4 que tengo en el nodo
#include <iostream>
using namespace std;
struct Nodo
{
int numeroC;
string nombnre;
string direccion;
float saldo;
Nodo* sig;
};
void insertar(Nodo *&, int, string, string,float);
void mostrarLista(Nodo *);
void eliminarElemento(Nodo*&, int);
//Devuelve el último nodo de la lista.
Nodo* getTail(Nodo* cur) {
while (cur != NULL && cur->sig != NULL) {
cur = cur->sig;
}
return cur;
}
//Particiona la lista tomando el último elemento como pivote
Nodo* Partition(Nodo* head, Nodo* end, Nodo** newhead, Nodo** newend) {
Nodo* pivot = end;
Nodo* prev = NULL, * cur = head, * tail = pivot;
// Durante la partición, tanto el encabezado como el final de la lista
// podría cambiar cuál se actualiza en newHead y
// newEnd variables
while (cur != pivot) {
if (cur->numeroC > pivot->numeroC) {
// Primer nodo que tiene un valor menor que el
// pivote - se convierte en el newHead
if ((*newhead) == NULL)
(*newhead) = cur;
prev = cur;
cur = cur->sig;
}
else {// Si el nodo cur es mayor que el pivote
if (prev)
prev->sig = cur->sig;
Nodo* tmp = cur->sig;
cur->sig = NULL;
tail->sig = cur;
tail = cur;
cur = tmp;
}
}
// Si los datos pivote son el elemento más pequeño en el
// lista actual, el pivote se convierte en la cabeza
if ((*newhead) == NULL)
(*newhead) = pivot;
// Actualizar newEnd al último nodo actual
(*newend) = tail;
// Devolver el nodo pivote
return pivot;
}
// aquí la ordenación ocurre sin incluir el nodo final
Nodo* quickSortRecur(Nodo* head, Nodo* end) {
// condición básica
if (!head || head == end)
return head;
Nodo* newhead = NULL, * newend = NULL;
// Particionar la lista, newHead y newEnd serán
// actualizado por la función de partición
Nodo* pivot = Partition(head, end, &newhead, &newend);
// Si el pivote es el elemento más pequeño, no es necesario recurrir
// para la parte izquierda.
if (newhead != pivot) {
// Establecer el nodo antes del nodo pivote como NULL
Nodo* tmp = newhead;
while (tmp->sig != pivot)
tmp = tmp->sig;
tmp->sig = NULL;
// Repetir para la lista antes del pivote
newhead = quickSortRecur(newhead, tmp);
// Cambia el siguiente del último nodo de la mitad izquierda a
// pivote
tmp = getTail(newhead);
tmp->sig = pivot;
}
// Repetir para la lista después del elemento pivote
pivot->sig = quickSortRecur(pivot->sig, newend);
return newhead;
}
// La función principal para ordenar rápidamente.
// función recursiva quickSortRecur()
void quikShort(Nodo** headRef) {
(*headRef) = quickSortRecur(*headRef, getTail(*headRef));
return;
}
void ordenarinser(Nodo *&lista){
Nodo* actual;
actual = lista;
int cont = 1,cursor,aux,k;
while (actual != NULL) {
cursor = cont;
cout << "\ncursor: " << cursor << " ";
aux = actual->numeroC;
cout << "\naux: " << aux << " ";
k = cursor - 1;
cout << "\nk: " << k << " ";
Nodo *anterior = lista;
for (int f = 0; f < k - 1; f++) {
anterior = anterior->sig;
}
cout << "\n anterior: " << anterior << " ";
while (k >= 0 && aux < anterior->numeroC) {
anterior->sig->numeroC = anterior->numeroC;
Nodo* temp = lista;
for (int j = 0; j < k - 2; j++) {
temp = temp->sig;
}
cout << "\ntemp: " << temp->numeroC;
anterior = temp;
k--;
}
cout << "\n--" << aux << endl;
Nodo* temp2 = lista;
for (int h = 0; h < k; h++) {
temp2 = temp2->sig;
}
temp2->numeroC = aux;
actual = actual->sig;
cont++;
}
cout << "\nlista ordenada...." << endl;
}
int main()
{
Nodo* lista = NULL;
int opc=0,nuc;
string nom, di;
float sald;
do {
cout << "1. insertar....." << endl;
cout << "2. mostrar....." << endl;
cout << "3. elimnar...." << endl;
cout << "4. Ordenamiento por quickSSort" << endl;
cout << "5. ordenamiento por insercion" << endl;
cout << "6. salir" << endl;
cout << "dijite una opcion.. ";
cin >> opc;
switch (opc)
{
case 1:
cout << "Dijite sue numero de cuenta" << endl;
cin >> nuc;
cout << "Dijite su Nombre" << endl;
cin >> nom;
cout << "Dijite su direccion" << endl;
cin >> di;
cout << "Dijite su saldo" << endl;
cin >> sald;
insertar(lista, nuc, nom, di, sald);
break;
case 2:
mostrarLista(lista);
break;
case 3:
cout << "Dijite el numero de cuenta..."<<endl;
cin >> nuc;
eliminarElemento(lista, nuc);
break;
case 4:
cout << "Ordenamiento por quickSort" << endl;
quikShort(&lista);
/*cout << "lista ordenada..." << endl;
mostrarLista(lista);*/
break;
case 5:
cout << "ordenamiento por insercion" << endl;
ordenarinser(lista);
break;
default:
break;
}
} while (opc != 6);
return 0;
}
void insertar(Nodo*& lista, int n, string nom, string di, float daldo) {
Nodo* nuevo_nodo = new Nodo();
nuevo_nodo->numeroC = n;
nuevo_nodo->nombnre = nom;
nuevo_nodo->direccion = di;
nuevo_nodo->saldo = daldo;
Nodo* aux1 = lista;
Nodo* aux2=NULL;
if (lista == aux1) {
lista = nuevo_nodo;
}
else {
aux2->sig = nuevo_nodo;
}
nuevo_nodo->sig = aux1;
cout << "cuenta creada " << n << " insertado"<<endl;
}
void mostrarLista(Nodo* lista) {
Nodo* actual = new Nodo();
actual = lista;
while (actual != NULL) {
cout << actual->numeroC << " - ";
cout << actual->nombnre << " - ";
cout << actual->direccion<< " - ";
cout << actual->saldo << " - "<<endl;
actual = actual->sig;
}
}
void eliminarElemento(Nodo*& lista, int n) {
if (lista != NULL) {
Nodo* axu_borrar;
Nodo* anterior = NULL;
axu_borrar = lista;
while ((axu_borrar != NULL) && (axu_borrar->numeroC != n)) {
anterior = axu_borrar;
axu_borrar = axu_borrar->sig;
}
if (axu_borrar == NULL) {
cout << "Elemento no encontrado"<<endl;
}
else if (anterior == NULL) {
lista = lista->sig;
delete axu_borrar;
cout << "Elemento borrado" << endl;
}
else {
anterior->sig = axu_borrar->sig;
delete axu_borrar;
cout << "Elemento borrado" << endl;
}
}
}