logo标签列表

在C语言中对链表进行排序

csortinglinked-listsingly-linked-list
5
我正在尝试通过查找最大值，从其位置删除它，然后将其插入列表顶部来对链表进行排序。
我遇到的困难在于实际的删除和插入操作。问题似乎出现在sortList函数内部的while循环中的if条件语句中，但我不知道该如何解决它。
任何帮助都将不胜感激。
#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;
}
2
有许多关于在C中对链表进行排序的问题，其中许多问题都列在页面右侧的相关问题中。您是否查看过它们，以确定它们是否与您的问题相关？ - Jonathan Leffler
5个回答
1

sortList函数存在问题。

该函数仅将一些大节点放在列表开头。它没有对整个列表进行排序。您可以使用排序算法对文件进行排序：快速排序/冒泡排序/...我在答案末尾放置了一个进行排序的代码。

以下是对列表进行排序的代码：

//它将最大节点替换为第一个节点，然后对子列表（列表-第一个元素）执行相同的操作

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;
}
1
请修正您的代码（在您的答案中，prev 总是指向尾部），您必须添加一个新的指针 largest_prev，并在以下情况将其设置为 prev：if(curr->num > largest->num)，然后使用它代替 prev（largest_prev->next = list）。 - TOC
@TOC：已完成。更易读的代码可以使用一个搜索最大元素的函数和一个交换节点的函数。 - Hicham
这个算法在你有像524361这样的列表时无法工作。 - user1511417
1
这是我尝试使用快速排序算法对单向链表进行排序的结果。如果您知道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;
}
0

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

  1. 您在循环开始时将prev指针设置为curr，这是不正确的。通过这样做，您使当前指针和前一个节点指针相同，这使得删除节点变得不可能。
  2. 您应该将最大指针也分配给top，从而方便将largest->next设置为真正的顶部节点。

代码可以像下面这样修改（只是一个指针，您需要自己检查其他问题）：

while(curr != NULL)
{

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

    }
    prev = curr;
    curr = curr->next;
}
还存在一个指针问题，curr 一直指向 top：largest 指向的节点与 curr 指向的相同。你将 largest->next 放到 top 上，然后 curr->next 指向 top。当你写 curr = curr->next 时，实际上是将 top 放入了 curr 中（因为在此时 largest = curr）。所以你会无限地从 top 开始重新开始。 - Hicham
0
// 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()'
0
通过写入largest->next，您覆盖了curr->next。因此，您每次都会从顶部重新开始。
确保：
  1. 列表保持一致
  2. 您的列表迭代器保持一致
但总体而言，您的代码似乎存在严重问题，我相信您的排序逻辑中可能还有其他几个错误。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接