[已解决]单链表快速排序-编译没问题，运行不了。

learner-ray

代码如下：从大到小排序。
void QuickSort(struct Node *head, struct Node *tail) //传递参数为链表的头指针和尾指针。
{
        struct Node *key;         //快速排序中的参考变量
        struct Node *move;         //用来遍历链表的移动指针变量。
        struct Node *save = NULL;         //因为比参考变量大的要往前插入，因此用save来保存move->next地址。
       
        if (head->next == tail || head->next->next == tail)         //设置递归终止条件。
        {
                return;
        }
       
        key = head->next;         //        初始化
        move = head->next;        //        初始化
       
        while (move->next != tail)        //当move指向倒数第二个结点，move->next指向最后一个有效结点的时候遍历了一遍，循环终止。
        {
                if ((move->next->data.score) > (key->data.score))         //判断条件按照分数大小来排序。
                {
                        save = move->next;         //因为要把move->next往前插入，所以先保存它的地址。
                        move->next = move->next->next;        //将原来move的下一个链表设置为move->next的下一个。（因为move->next要往前插入了）
                        save->next = head->next;        //将save插入为首结点。
                        head->next = save;                  //将save插入为首结点。
                }
                move = move->next;        //move往后移一位。
        }
        QuickSort(head, key);         //进行递归。
        QuickSort(key, tail);        //递归。
}

最佳答案

月排行榜 / 总排行榜

lei1996

2021-11-3 10:25:03

下面贴一下我改的几个地方

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. struct Student
   
5. {
   
6.         char name[20];
   
7.         int age;
   
8.         float score;
   
9.         char num[20];
   
10. };
    
11. 
    
12. struct Node
    
13. {
    
14.         struct Student data;
    
15. 
    
16.         struct Node *next;
    
17. };
    
18. 
    
19. struct Node *CreatLink(void);
    
20. void InitLink(struct Node *head);
    
21. void QuickSort(struct Node *head, struct Node *tail);
    
22. void OutputLink(struct Node *head);
    
23. 
    
24. int main(void)
    
25. {
    
26.         struct Node *head = CreatLink();
    
27.         InitLink(head);
    
28.         QuickSort(head, NULL);
    
29. 
    
30.         printf("排序后的结果如下：\n");
    
31.         OutputLink(head);
    
32. 
    
33.         return 0;
    
34. }
    
35. 
    
36. struct Node *CreatLink(void)
    
37. {
    
38.         struct Node *head = (Node *)malloc(sizeof(Node));//这里报错了  申请内存应该这样吧
    
39.         int i = 0;
    
40.         int cnt = 0;
    
41.         struct Node *move = head;
    
42.         move->next = NULL;
    
43. 
    
44.         printf("请输入学生的数量：");
    
45.         scanf("%d", &cnt);
    
46.         getchar();
    
47. 
    
48.         for (i = 1; i <= cnt; i++)
    
49.         {
    
50.                 struct Node *fresh = (Node *)malloc(sizeof(Node));//同上
    
51. 
    
52.                 move->next = fresh;
    
53.                 fresh->next = NULL;
    
54.                 move = fresh;
    
55.         }
    
56.         return head;
    
57. }
    
58. 
    
59. void InitLink(struct Node *head)
    
60. {
    
61.         int i = 1;
    
62.         struct Node *move = head->next;
    
63. 
    
64.         while (move != NULL)
    
65.         {
    
66.                 printf("请输入第%d个学生的名字：", i);
    
67.                 scanf("%s", move->data.name);
    
68.                 getchar();
    
69. 
    
70.                 printf("请输入第%d个学生的年龄：", i);
    
71.                 scanf("%d", &(move->data.age));
    
72.                 getchar();
    
73. 
    
74.                 printf("请输入第%d个学生的分数：", i);
    
75.                 scanf("%f", &(move->data.score));
    
76.                 getchar();
    
77. 
    
78.                 printf("请输入第%d个学生的学号：", i);
    
79.                 scanf("%s", move->data.num);
    
80.                 getchar();
    
81. 
    
82.                 move = move->next;
    
83.                 i++;
    
84.         }
    
85.         return;
    
86. }
    
87. 
    
88. void QuickSort(struct Node *head, struct Node *tail)
    
89. {
    
90.         struct Node *key;
    
91.         struct Node *move;
    
92.         struct Node *save = NULL;
    
93. 
    
94.         if (head->next == tail || head->next->next == tail)
    
95.         {
    
96.                 return;
    
97.         }
    
98. 
    
99.         key = head->next;
    
100.         move = head->next;
     
101. 
     
102.         while (move && move->next != tail)  //排序这里要考虑  move不能为NULL的情况 否则它就没有->next
     
103.         {
     
104.                 if ((move->next->data.score) > (key->data.score))
     
105.                 {
     
106.                         save = move->next;
     
107.                         move->next = move->next->next;
     
108.                         save->next = head->next;
     
109.                         head->next = save;
     
110.                 }
     
111.                 move = move->next;
     
112.         }
     
113.         QuickSort(head, key);
     
114.         QuickSort(key, tail);
     
115. }
     
116. 
     
117. void OutputLink(struct Node *head)
     
118. {
     
119.         struct Node *move = head->next;
     
120.         int i = 1;
     
121. 
     
122.         while (move != NULL)
     
123.         {
     
124.                 printf("第%d位学生信息为\n", i);
     
125.                 printf("姓名：%s; 年龄：%d; 分数：%.2f; 学号：%s\n", move->data.name, move->data.age, move->data.score, move->data.num);
     
126. 
     
127.                 i++;
     
128.                 move = move->next;
     
129.         }
     
130.         return;
     
131. }

复制代码

跳转到最佳答案楼层

lei1996

可以贴一下你的所有代码吗

learner-ray

lei1996 发表于 2021-11-1 17:16
可以贴一下你的所有代码吗

下面是我的所有代码，麻烦您看看
#include<stdio.h>
#include<stdlib.h>

struct Student
{
        char name[20];
        int age;
        float score;
        char num[20];
};

struct Node
{
        struct Student data;
       
        struct Node *next;
};

struct Node *CreatLink(void);
void InitLink(struct Node *head);
void QuickSort(struct Node *head, struct Node *tail);
void OutputLink(struct Node *head);

int main(void)
{
        struct Node *head = CreatLink();
        InitLink(head);
        QuickSort(head, NULL);
       
        printf("排序后的结果如下：\n");
        OutputLink(head);
       
        return 0;
}

struct Node *CreatLink(void)
{
        struct Node *head = malloc(sizeof *head);
        int i = 0;
        int cnt = 0;
        struct Node *move = head;
        move->next = NULL;
       
        printf("请输入学生的数量：");
        scanf("%d", &cnt);
        getchar();
       
        for(i = 1; i <= cnt; i++)
        {
                struct Node *fresh = malloc(sizeof *fresh);
               
                move->next = fresh;
                fresh->next = NULL;
                move = fresh;
        }
        return head;
}

void InitLink(struct Node *head)
{
        int i = 1;
        struct Node *move = head->next;
       
        while (move != NULL)
        {
                printf("请输入第%d个学生的名字：", i);
                scanf("%s", move->data.name);
                getchar();
               
                printf("请输入第%d个学生的年龄：", i);
                scanf("%d", &(move->data.age));
                getchar();
               
                printf("请输入第%d个学生的分数：", i);
                scanf("%f", &(move->data.score));
                getchar();
               
                printf("请输入第%d个学生的学号：", i);
                scanf("%s", move->data.num);
                getchar();
               
                move = move->next;
                i++;
        }
        return;
}

void QuickSort(struct Node *head, struct Node *tail)
{
        struct Node *key;
        struct Node *move;
        struct Node *save = NULL;
       
        if (head->next == tail || head->next->next == tail)
        {
                return;
        }
       
        key = head->next;
        move = head->next;
       
        while (move->next != tail)
        {
                if ((move->next->data.score) > (key->data.score))
                {
                        save = move->next;
                        move->next = move->next->next;
                        save->next = head->next;
                        head->next = save;
                }
                move = move->next;
        }
        QuickSort(head, key);
        QuickSort(key, tail);
}

void OutputLink(struct Node *head)
{
        struct Node *move = head->next;
        int i = 1;
       
        while (move != NULL)
        {
                printf("第%d位学生信息为\n", i);
                printf("姓名：%s; 年龄：%d; 分数：%.2f; 学号：%s\n", move->data.name, move->data.age, move->data.score, move->data.num);
               
                i++;
                move = move->next;
        }
        return;
}

lei1996

下面贴一下我改的几个地方

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. struct Student
   
5. {
   
6.         char name[20];
   
7.         int age;
   
8.         float score;
   
9.         char num[20];
   
10. };
    
11. 
    
12. struct Node
    
13. {
    
14.         struct Student data;
    
15. 
    
16.         struct Node *next;
    
17. };
    
18. 
    
19. struct Node *CreatLink(void);
    
20. void InitLink(struct Node *head);
    
21. void QuickSort(struct Node *head, struct Node *tail);
    
22. void OutputLink(struct Node *head);
    
23. 
    
24. int main(void)
    
25. {
    
26.         struct Node *head = CreatLink();
    
27.         InitLink(head);
    
28.         QuickSort(head, NULL);
    
29. 
    
30.         printf("排序后的结果如下：\n");
    
31.         OutputLink(head);
    
32. 
    
33.         return 0;
    
34. }
    
35. 
    
36. struct Node *CreatLink(void)
    
37. {
    
38.         struct Node *head = (Node *)malloc(sizeof(Node));//这里报错了  申请内存应该这样吧
    
39.         int i = 0;
    
40.         int cnt = 0;
    
41.         struct Node *move = head;
    
42.         move->next = NULL;
    
43. 
    
44.         printf("请输入学生的数量：");
    
45.         scanf("%d", &cnt);
    
46.         getchar();
    
47. 
    
48.         for (i = 1; i <= cnt; i++)
    
49.         {
    
50.                 struct Node *fresh = (Node *)malloc(sizeof(Node));//同上
    
51. 
    
52.                 move->next = fresh;
    
53.                 fresh->next = NULL;
    
54.                 move = fresh;
    
55.         }
    
56.         return head;
    
57. }
    
58. 
    
59. void InitLink(struct Node *head)
    
60. {
    
61.         int i = 1;
    
62.         struct Node *move = head->next;
    
63. 
    
64.         while (move != NULL)
    
65.         {
    
66.                 printf("请输入第%d个学生的名字：", i);
    
67.                 scanf("%s", move->data.name);
    
68.                 getchar();
    
69. 
    
70.                 printf("请输入第%d个学生的年龄：", i);
    
71.                 scanf("%d", &(move->data.age));
    
72.                 getchar();
    
73. 
    
74.                 printf("请输入第%d个学生的分数：", i);
    
75.                 scanf("%f", &(move->data.score));
    
76.                 getchar();
    
77. 
    
78.                 printf("请输入第%d个学生的学号：", i);
    
79.                 scanf("%s", move->data.num);
    
80.                 getchar();
    
81. 
    
82.                 move = move->next;
    
83.                 i++;
    
84.         }
    
85.         return;
    
86. }
    
87. 
    
88. void QuickSort(struct Node *head, struct Node *tail)
    
89. {
    
90.         struct Node *key;
    
91.         struct Node *move;
    
92.         struct Node *save = NULL;
    
93. 
    
94.         if (head->next == tail || head->next->next == tail)
    
95.         {
    
96.                 return;
    
97.         }
    
98. 
    
99.         key = head->next;
    
100.         move = head->next;
     
101. 
     
102.         while (move && move->next != tail)  //排序这里要考虑  move不能为NULL的情况 否则它就没有->next
     
103.         {
     
104.                 if ((move->next->data.score) > (key->data.score))
     
105.                 {
     
106.                         save = move->next;
     
107.                         move->next = move->next->next;
     
108.                         save->next = head->next;
     
109.                         head->next = save;
     
110.                 }
     
111.                 move = move->next;
     
112.         }
     
113.         QuickSort(head, key);
     
114.         QuickSort(key, tail);
     
115. }
     
116. 
     
117. void OutputLink(struct Node *head)
     
118. {
     
119.         struct Node *move = head->next;
     
120.         int i = 1;
     
121. 
     
122.         while (move != NULL)
     
123.         {
     
124.                 printf("第%d位学生信息为\n", i);
     
125.                 printf("姓名：%s; 年龄：%d; 分数：%.2f; 学号：%s\n", move->data.name, move->data.age, move->data.score, move->data.num);
     
126. 
     
127.                 i++;
     
128.                 move = move->next;
     
129.         }
     
130.         return;
     
131. }

复制代码

learner-ray

lei1996 发表于 2021-11-3 10:25
下面贴一下我改的几个地方

1、那个申请内存的因为malloc函数返回类型是void型指针，所以不加类型转换也不会报错，加的话应该加（struct Node *) 我用的DEV C++编译的，如果不加struct会报错，但不加也可以。
2、while (move && move->next != tail)  //排序这里要考虑  move不能为NULL的情况 否则它就没有->next
这里的话因为我是按照顺序往后比的，所以应该是move->next先到NULL，而且刚开始做了head->next->next !=NULL的判断。
3、我刚刚发现了自己的逻辑上的问题， if ((move->next->data.score) > (key->data.score))如果执行了这里面的代码，move->next已经往后移了，我用的也是move->next和key作比较，不是move。如果执行了它还要执行move = move->next; 那此时move所在的地方没有和key比较，会漏掉数据。因此把那句move = move->next用else括起来就对了。
下面是改后的代码（只改动了一处）非常感谢您的讨论，不然也找不到自己的问题。谢谢~
#include<stdio.h>
#include<stdlib.h>

struct Student
{
        char name[20];
        int age;
        float score;
        char num[20];
};

struct Node
{
        struct Student data;
       
        struct Node *next;
};

struct Node *CreatLink(void);
void InitLink(struct Node *head);
void QuickSort(struct Node *head, struct Node *tail);
void OutputLink(struct Node *head);

int main(void)
{
        struct Node *head = CreatLink();
        InitLink(head);
        QuickSort(head, NULL);
       
        printf("排序后的结果如下：\n");
        OutputLink(head);
       
        return 0;
}

struct Node *CreatLink(void)
{
        struct Node *head = malloc(sizeof *head);
        int i = 0;
        int cnt = 0;
        struct Node *move = head;
        move->next = NULL;
       
        printf("请输入学生的数量：");
        scanf("%d", &cnt);
        getchar();
       
        for(i = 1; i <= cnt; i++)
        {
                struct Node *fresh = malloc(sizeof *fresh);
               
                move->next = fresh;
                fresh->next = NULL;
                move = fresh;
        }
        return head;
}

void InitLink(struct Node *head)
{
        int i = 1;
        struct Node *move = head->next;
       
        while (move != NULL)
        {
                printf("请输入第%d个学生的名字：", i);
                scanf("%s", move->data.name);
                getchar();
               
                printf("请输入第%d个学生的年龄：", i);
                scanf("%d", &(move->data.age));
                getchar();
               
                printf("请输入第%d个学生的分数：", i);
                scanf("%f", &(move->data.score));
                getchar();
               
                printf("请输入第%d个学生的学号：", i);
                scanf("%s", move->data.num);
                getchar();
               
                move = move->next;
                i++;
        }
        return;
}

void QuickSort(struct Node *head, struct Node *tail)
{
        struct Node *key;
        struct Node *move;
        struct Node *save = NULL;
       
        if (head->next == tail || head->next->next == tail)
        {
                return;
        }
       
        key = head->next;
        move = head->next;
       
        while (move->next != tail)
        {
                if ((move->next->data.score) > (key->data.score))
                {
                        save = move->next;
                        move->next = move->next->next;
                        save->next = head->next;
                        head->next = save;
                }
                else        //只改动这一处。
                {
                        move = move->next;
                }
        }
        QuickSort(head, key);
        QuickSort(key, tail);
}

void OutputLink(struct Node *head)
{
        struct Node *move = head->next;
        int i = 1;
       
        while (move != NULL)
        {
                printf("第%d位学生信息为\n", i);
                printf("姓名：%s; 年龄：%d; 分数：%.2f; 学号：%s\n", move->data.name, move->data.age, move->data.score, move->data.num);
               
                i++;
                move = move->next;
        }
        return;
}