c-我应该怎么做才能让链表中的最后一个节点参与冒泡排序

Question

我已经编写了一个链表程序，应该编写一个冒泡排序函数，但最后一个节点似乎没有参与冒泡排序。我想这是因为指针移动到NULL并拒绝最后一个结点的数据。你能给我一个用其他方式对链接列表进行排序的方法吗？这也会有帮助。

我的代码是：

#include<stdio.h>
#include<stdlib.h>
typedef struct node_type{
int data;
struct node_type *next;
}node;
typedef node *list;
list head;
void traverse()
{
list temp;
temp=head;
printf("nThe Data is: n");
while(temp!=NULL)
{
printf("%dn",temp->data);
temp=temp->next;
}
printf("nn");
}
void sort_list()
{
list new,ptr;
int temp;
for(new=head;new->next!=NULL;new=new->next)
{
for(ptr=new->next;ptr->next!=NULL;ptr=ptr->next)
{
if(new->data > ptr->data)
{
temp=new->data;
new->data=ptr->data;
ptr->data=temp;
}  
}
}
traverse();
}
void main()
{
list temp,new;
head=NULL;
int n;
char ch;
temp=(list) malloc(sizeof(node));
printf("nGive data: ");
scanf("%d",&temp->data);
head=temp;
printf("n");
printf("Enter more data(y/n): ");
scanf("n%c",&ch);
while(ch=='y')
{
new=(list) malloc(sizeof(node));
printf("Give data: ");
scanf("%d",&new->data);
temp->next=new;
temp=new;
printf("nEnter more data(y/n): ");
scanf("n%c",&ch);
}
temp->next=NULL;
traverse(head);
printf("nnDo you want to sort the Link-List(y/n): ");
scanf("n%c",&ch);
if(ch=='y')
{ 
sort_list();
}
}

输入：2 3 1 5 4

输出：1 2 3 5 4

Answer 1

由于for循环中的条件ptr->next!=NULL，sort_list()的内部循环在排序过程中不考虑最后一个节点。你应该用NULL:检查它ptr

for(ptr = new->next; ptr != NULL; ptr = ptr->next)
^^^^

Answer 2

有几件事需要解决。

• 主函数需要返回值int，而不是void
• 有一些对traverse的调用将head作为参数传递，这将导致错误。将traverse函数更新为除了list参数之外，或者修复这些调用

• sort_list函数的内部for循环条件应在ptr == NULL即时结束

  for(ptr=new->next; ptr != NULL; ptr=ptr->next)
  

函数可能更具防御性，如果head恰好是NULL，则当评估new->next != NULL时，第一个for循环将导致分段故障。您可以在函数的开头使用if语句来防止这种情况的发生。

• 最后一件事是，由于正在使用malloc，请确保释放内存。您需要遍历列表并释放每个节点