Título: ordenar una lista enlazada c++ por insercion ayuda Publicado por: abelhecks en 13 Agosto 2022, 21:59 pm 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; } } } Título: Re: ordenar una lista enlazada c++ por insercion ayuda Publicado por: dario01dr en 14 Agosto 2022, 03:16 am Hola, C++ ya tiene listas implementadas.
Si sabes un poco de ingles lee esto: https://cplusplus.com/reference/forward_list/forward_list/ (https://cplusplus.com/reference/forward_list/forward_list/) Te ayudara. Saludos |