论坛 › C\C++交流 › 单链表快速排序-编译没问题，运行不了。

learner-ray 发表于 2021-11-1 16:52:48

单链表快速排序-编译没问题，运行不了。

代码如下：从大到小排序。
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-1 17:16:36

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

learner-ray 发表于 2021-11-2 21:57:49

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

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

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

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 发表于 2021-11-3 10:25:03

下面贴一下我改的几个地方
#include<stdio.h>
#include<stdlib.h>

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

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 = (Node *)malloc(sizeof(Node));//这里报错了申请内存应该这样吧
        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 = (Node *)malloc(sizeof(Node));//同上

                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 && move->next != tail)//排序这里要考虑move不能为NULL的情况 否则它就没有->next
        {
                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;
}

learner-ray 发表于 2021-11-3 17:52:41

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;
        int age;
        float score;
        char num;
};

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

查看完整版本: 单链表快速排序-编译没问题，运行不了。