在C中对链表进行排序。

I'm trying to sort a linked list by finding the largest value, deleting it from its position, and then inserting it at the top of the list.

我试图通过查找最大的值来对链表进行排序，从它的位置删除它，然后将它插入到链表的顶部。

The difficulty I'm running into is the actual deleting and inserting at the top. The issue seems to be in the if condition in the while loop contained within the sortList function, but I'm not sure how to fix it.

我遇到的困难是在顶部实际的删除和插入。问题似乎在sortList函数中包含的while循环中的if条件中，但我不确定如何修复它。

Any help would be appreciated.

如有任何帮助，我们将不胜感激。

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

6 个解决方案

#1

There is issues in the sortList function.

sortList函数中存在一些问题。

This function only put some large nodes in the beginning of the list. It is not soting all the list. you can you a sort algorithm to sort the file : quicksort/ bubblesort/... i put a code doing a sort in the end of this answer.

这个函数只在列表的开头放置一些大的节点。这并不是全部。您可以使用排序算法对文件进行排序:quicksort/ bubblesort/…我在这个答案后面放了一个排序的代码。

here is a code doing the sort of the list :

下面是执行列表的代码:

//it is replacing largest node with first one then doing the same operation with sublist (list-first element)

//它用第一个节点替换最大的节点，然后用子列表(list-first元素)执行相同的操作

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

#2

Here is my attempt to sort a singly linked list using QuickSort algorithm. If you know n then run time will be O(n log n). Check if this helps.

下面是我尝试使用快速排序算法对一个链表进行排序。如果你知道n，那么运行时间将是O(n log n)。

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

#3

This should really help you. It's a very nice post.

这对你很有帮助。这是一个非常好的帖子。

#4

By writing to largest->next you overwrote curr->next. So you end up restarting from the top all the time.

通过写到最大的->下一个你重写了curr->下一个。所以你最终从顶部重新开始。

Make sure that:

确保:

1. the list remains consistent
2. 清单保持一致
3. your list iterator remains consistent
4. 列表迭代器保持一致

But overall, your code seems to be heavily broken, I believe there might be a couple other errors in your sorting logic.

但总的来说，您的代码似乎严重损坏，我认为您的排序逻辑可能还有其他一些错误。

#5

The following are some of the problems which exist in your sorting logic:

以下是您的排序逻辑中存在的一些问题:

1. You are setting the prev pointer to curr in the beginning of the loop itself which is incorrect. By doing this, you are making the current pointer and the previous node pointer as same which makes it impossible to delete the node.
2. 您正在将prev指针设置为在循环开始时curr，这是不正确的。通过这样做，您将使当前指针和以前的节点指针相同，从而不可能删除节点。
3. You should assign the largest pointer also to top whereby it facilitates the possibility of setting the largest->next to real top node.
4. 您还应该将最大指针赋给top，以便在真正的top节点旁边设置最大的->。

The code can modified like below (Just a pointer, you need to check for other issues yourself):

代码可以修改如下(只是一个指针，您需要自己检查其他问题):

while(curr != NULL)
{

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

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

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