设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 单链表快速排序-编译没问题，运行不了。
返回列表 发新帖
查看: 1169|回复: 4

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

[复制链接]
learner-ray
发表于 2021-11-1 16:52:48 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
代码如下：从大到小排序。
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
下面贴一下我改的几个地方
#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 = (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;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

lei1996
发表于 2021-11-1 17:16:36 | 显示全部楼层
可以贴一下你的所有代码吗
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

learner-ray
 楼主| 发表于 2021-11-2 21:57:49 | 显示全部楼层
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;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

lei1996
发表于 2021-11-3 10:25:03 | 显示全部楼层    本楼为最佳答案   
下面贴一下我改的几个地方
#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 = (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;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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[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;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-10 12:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表