Sortieren einer verketteten Liste in C

Hier ist mein Versuch, zu Sortieren, eine einfach verknüpfte Liste mit QuickSort-Algorithmus. Wenn Sie wissen, dann n Laufzeit wird O(n log n). Überprüfen Sie, ob das hilft.

#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;
}

InformationsquelleAutor user1596193

Schriftlich largest->next Sie überschrieben curr->next. So dass Sie am Ende einen Neustart von oben die ganze Zeit.

Stellen Sie sicher, dass:

1. die Liste bleibt konsistent
2. Ihre Liste iterator konstant bleibt

Aber insgesamt ist dein code scheint zu stark gebrochen, ich glaube, es gibt vielleicht ein paar andere Fehler in deiner sortierlogik.

InformationsquelleAutor Anony-Mousse

//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()'

InformationsquelleAutor Sagar Damle