Ordenar una lista vinculada en C

Question

Estoy tratando de ordenar una lista vinculada buscando el valor más grande, eliminándolo de su posición y luego insertándolo en la parte superior de la lista.

La dificultad que me estoy encontrando es la eliminación real y la inserción en la parte superior. El problema parece estar en la condición if en el ciclo while contenido en la función sortList, pero no estoy seguro de cómo solucionarlo.

Cualquier ayuda sería apreciada.

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node{ 
    int num; 
    struct node *next; 
} Node, *NodePtr; 

void printList(NodePtr np); 
NodePtr makeList(void); 
NodePtr makeNode(int n); 
NodePtr sortList(NodePtr list); 

int main(void) { 
    NodePtr list; 
    printf("Enter numbers for the list (0 to end)\n"); 
    list = makeList(); 
    printList(list); 
    list = sortList(list); 
    printList(list); 
    return 0; 
} 

NodePtr makeList(void) { 
    NodePtr makeNode(int), np, top, last; 
    int n; 
    top = NULL; 
    if(scanf("%d", &n) != 1)n = 0; 
    while(n != 0) { 
     np = makeNode(n); 
     if(top == NULL)top = np; 
     else last->next = np; 
     last = np; 
     if(scanf("%d", &n)!=1)n=0; 
    } 
    return top; 
} 


void printList(NodePtr np) { 
    while(np != NULL) { 
     printf("%d\n", np->num); 
     np = np->next; 
    } 
} 

NodePtr makeNode(int n) { 
    NodePtr np = (NodePtr)malloc(sizeof(Node)); 
    np->num = n; 
    np->next = NULL; 
    return np; 
} 

NodePtr sortList(NodePtr list) { 
    NodePtr top = list; 
    NodePtr curr = NULL; 
    NodePtr largest; 
    NodePtr prev; 
    prev = NULL; 
    curr = top; 
    largest = top; 

    while(curr != NULL) { 
     prev = curr; 
     if(curr->num > largest->num) { 
      largest = curr; 
      prev->next = curr->next; 
      largest->next = top; 
     } 
     curr = curr->next; 
    } 
    if(prev == NULL) { 
     largest->next = top; 
     return largest; 
    } 
    return largest; 
} 

Answer 1

This realmente debería ayudarle. Es una publicación muy agradable.

Answer 2

Al escribir al largest->next sobrescribió curr->next. Así que terminas reiniciando desde arriba todo el tiempo.

Asegúrese de que:

1. la lista permanece constante
2. su lista de iterador permanece constante

Pero en general, el código parece estar fuertemente roto, creo que podría haber un par otros errores en su lógica de clasificación.

Answer 3

Los siguientes son algunos de los problemas que existen en la lógica de la clasificación:

1. se está ajustando el puntero anterior a curr en el inicio de la misma bucle que es incorrecto. Al hacer esto, está haciendo que el puntero actual y el puntero del nodo anterior sean los mismos, lo que hace que sea imposible eliminar el nodo.
2. Debe asignar el puntero más grande también a la parte superior, lo que facilita la posibilidad de establecer el mayor -> al lado del nodo superior real.

El código puede modificarse, como a continuación (Sólo un puntero, es necesario comprobar si hay otras cuestiones a sí mismo):

while(curr != NULL) 
{ 

    if(curr->num > largest->num) 
    { 
     largest = curr; 
     prev->next = curr->next; 
     largest->next = top; 
     top = largest; 

    } 
    prev = curr; 
    curr = curr->next; 
} 

Answer 4

Hay problemas en la función sortList.

Esta función solo pone algunos nodos grandes al principio de la lista. No está ocupando toda la lista. puedes ordenar un algoritmo para ordenar el archivo: quicksort/bubblesort/... puse un código haciendo una especie al final de esta respuesta.

aquí es un código que hace la clasificación de la lista:

// que está reemplazando el nodo más grande con el primero uno y luego hacer la misma operación con la sub-lista (lista-elementos primero)

NodePtr sortList(NodePtr list) 
{ 

// 
if(list == null || list->next == null) 
    return list; // the list is sorted. 

//replace largest node with the first : 

//1- find largest node : 
NodePtr curr, largest,largestPrev; 
curr = list; 
largest = list; 
prev = list; 
largestPrev = list; 
while(curr != NULL) { 
     if(curr->num > largest->num) { 
      largestPrev = prev; 
      largest = curr; 
     } 
     prev = curr; 
     curr = curr->next; 

    } 
//largest node is in largest. 

//2- switching firt node and largest node : 
NodePtr tmp; 
if(largest != list) 
{ 
    largestPrev->next = list; 
    tmp = list->next; 
    list->next = largest->next; 
    largest->next = tmp; 
} 

// now largest is the first node of the list. 

// calling the function again with the sub list : 
//   list minus its first node : 
largest->next = sortList(largest->next); 


return largest; 
} 

Answer 5

Aquí es mi intento de ordenar una lista individualmente vinculada utilizando el algoritmo QuickSort. Si conoce n, el tiempo de ejecución será O (n log n). Verifica si esto ayuda.

#include "malloc.h" 

typedef struct node { 
    struct node *next; 
    int val; 
} node; 

bool insert_node(struct node **head, int val) 
{ 
    struct node *elem; 
    elem = (struct node *)malloc(sizeof(struct node)); 
    if (!elem) 
     return false; 
    elem->val = val; 
    elem->next = *head; 
    *head = elem; 
    return true; 
} 

int get_lval(struct node *head, int l) 
{ 
    while(head && l) { 
     head = head->next; 
     l--; 
    } 
    if (head != NULL) 
     return head->val; 
    else 
     return -1; 
} 

void swap(struct node *head, int i, int j) 
{ 
    struct node *tmp = head; 
    int tmpival; 
    int tmpjval; 
    int ti = i; 
    while(tmp && i) { 
     i--; 
     tmp = tmp->next; 
    } 
    tmpival = tmp->val; 
    tmp = head; 
    while(tmp && j) { 
     j--; 
     tmp = tmp->next; 
    } 
    tmpjval = tmp->val; 
    tmp->val = tmpival; 
    tmp = head; 
    i = ti; 
    while(tmp && i) { 
     i--; 
     tmp = tmp->next; 
    } 
    tmp->val = tmpjval; 
} 


struct node *Quick_Sort_List(struct node *head, int l, int r) 
{ 
    int i, j; 
    int jval; 
    int pivot; 
    i = l + 1; 
    if (l + 1 < r) { 
     pivot = get_lval(head, l); 
     printf("Pivot = %d\n", pivot); 
     for (j = l + 1; j <= r; j++) { 
      jval = get_lval(head, j); 
      if (jval < pivot && jval != -1) { 
       swap(head, i, j); 
       i++; 
      } 
     } 
     swap(head, i - 1, l); 
     Quick_Sort_List(head, l, i); 
     Quick_Sort_List(head, i, r); 
    } 
    return head; 
} 

struct node *Sort_linkedlist(struct node *head) 
{ 
    struct node *tmp = head; 
    // Using Quick sort. 
    int n = 0; 

    while (tmp) { 
     n++; 
     tmp = tmp->next; 
    } 
    printf("n = %d\n", n); 
    head = Quick_Sort_List(head, 0, n); 
    return head; 
} 

void print_list(struct node *head) 
{ 
    while(head) { 
     printf("%d->", head->val); 
     head = head->next; 
    } 
    printf("\n"); 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    struct node *head = NULL; 
    struct node *shead = NULL; 

    insert_node(&head, 10); 
    insert_node(&head, 12); 
    insert_node(&head, 9); 
    insert_node(&head, 11); 
    insert_node(&head, 7); 
    insert_node(&head, 1); 
    insert_node(&head, 3); 
    insert_node(&head, 8); 
    insert_node(&head, 5); 
    insert_node(&head, 2); 
    insert_node(&head, 4); 
    insert_node(&head, 6); 
    print_list(head); 

    shead = Sort_linkedlist(head); 
    print_list(shead); 

    return 0; 
} 

Answer 6

// Program to sort a single linked list in ascending order 
// (without exchanging data in the nodes) 
/************************************************************************** 

There are two methods of sorting presented here(At a time,we can use any of 
these two functions to sort our single linked list.) - 

1. Function 'void Sort()' - This function uses selection sort method(I 
          think). 
    In this function,a node whose data is the smallest in the list is made 
    as 'head' node(i.e. starting node of the list) by scanning the whole list 
    once.Then from the remaining list,again a node with the smallest data is 
    found out whose address is kept in the 'next' field of previous node(head 
    node).This process continues to sort the whole list. 
2. Function 'void Sort_method2()' - This function uses insertion sort 
            method(I think). 
    In this function,starting from second node in the list, all previous node 
    data(starting from 'head' node) are compared with current reference node 
    (which is initially second node in the list).If 'data' field of current 
    reference node is smaller than that of any of its previous nodes,then 
    suitable changes in the 'next' field of corresponding nodes are made.If 
    data in the current reference node is smaller than that in the 'head' node, 
    then the current reference node is made as 'head' node. 

    *********************************************************************/ 

#include<stdio.h> 
#include<conio.h> 
#include<alloc.h> 
#include<stdlib.h> 

struct node 
{ 
int data; 
struct node *next; 
}; 

struct node *head,*head1; 

void Create_node(int data); 
void display(); 
void Sort(); 
void Sort_method2(); 


void main() 
{ 
int choice,d; 
clrscr(); 
while(1) 
{ 
    printf("\n 1.Create new node"); 
    printf("\n 2.Sort in ascending order"); 
    printf("\n 3.Exit"); 
    printf("\nEnter your choice : "); 
    scanf("%d",&choice); 

    switch(choice) 
    { 
    case 1: printf("\nEnter data :"); 
      scanf("%d",&d); 
      Create_node(d); 
      break; 
    case 2: Sort();  // At a time,we can use any of these two 
      //Sort_method2(); // functions to sort our single linked list. 
      break; 
    case 3: exit(0); 
    default:exit(0); 
    } 
    } // end of while(1) 
} // end of main() 

//-------------------------------------------- 
void Create_node(int d) 
{ 
    struct node *newnode,*temp; 
    newnode = (struct node *)malloc(sizeof(struct node)); 
    newnode -> data = d; 
    newnode -> next = NULL; 
    if(head == NULL) 
    head = newnode; 
    else 
    { 
     temp = head; 
     while(temp -> next != NULL) 
     temp = temp -> next; 

     temp -> next = newnode; 
    } // end of 'else' 
} // end of 'Create_node(int d)' 

//--------------------------------------------- 
void display() // Print linked list contents 
{ 
    struct node *temp; 
    printf("\nList contents are :\n"); 
    temp = head; 
    while(temp != NULL) 
    { 
    printf(" Data = %d Address = %u\n",temp->data,temp); 
    temp = temp->next; 
    } 
    printf("\n"); 
} 
//-------------------------------------------- 
void Sort() 
{ 
    struct node *t,*t1,*t2,*t3; 
    t1 = head; 
    head1 = head; 
    if(head == NULL) 
    printf("\nThe linked list is empty!"); 
    else 
    { 
    while((t2 = t1 -> next) != NULL) 
    { 
     while(t2 != NULL) 
     { 
     t3 = t2 -> next; 
     if(t1 -> data > t2 -> data) 
     { 
      t2 -> next = t1; 
      for(t = t1; t -> next != t2;t = t -> next); 

      t -> next = t3; 
      t1 = t2;  // t1 = Node with smaller data 
      t2 = t3;  // t2 = Node to be compared with t1 
     } // end of 'if' 
     else 
     { 
      // t1 = t1;  // That is,no change in t1. 
      t2 = t3; 
     } 
     } // end of ' while(t2 != NULL)' 

     if(head == head1) // We want this action only for first pass of 
     {     // outer while() loop.Only initially, head = head1. 
     head = t1; 
     head1 = t1 -> next; 
     } // end of 'if(head == head1)' 
     else 
     { 
     for(t = head;t -> next != head1; t = t -> next); 

     t -> next = t1; 
     head1 = t1 -> next; 
     } // end of 'else' 

     t1 = t1 -> next; 
    } // end of 'while((t2 = t1 -> next) != NULL)' 

    display(); // Display the list. 
    } // end of 'else' of 'if(head == NULL)' 
} // end of 'Sort()' 

//-------------------------------------------- 
void Sort_method2() 
{ 
struct node *t,*t1,*t2,*tt; 
if(head == NULL) 
    printf("\nThe linked list is empty!"); 
else 
{ 
    t1 = head -> next; 
    while(t1 != NULL)       // This is i-loop(outer loop). 
    { 
    t2 = t1 -> next; 
    for(t = head; t != t1; t = t -> next) // This is j-loop(inner loop). 
    { 
     if(t1->data < t->data) 
     { 
     t1 -> next = t; 
     for(tt=head; tt->next != t1; tt=tt->next); //end of for loop in 'if' 

     tt -> next = t2; 
     if(t == head) 
      head = t1; // There is only one statement in this 'if'. 
     else // i.e.,'if(t != head)' 
     { 
      for(tt=head; tt->next != t; tt=tt->next); 

      tt -> next = t1; 
     } 
     break; 
     } // end of 'if' 
    } // end of outer 'for' loop 
    t1 = t2; 
    }  // end of 'while' 

    display(); // Display the list. 
}  // end of 'else' of 'if(head == NULL)' 
}   // end of 'Sort_method2()'