鱼C论坛

 找回密码
 立即注册
查看: 74|回复: 3

能不能用qsort对链表排序

[复制链接]
发表于 7 天前 | 显示全部楼层 |阅读模式

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

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

x
链表是用指针连接起来的, 不知道qsort能不能正确处理这种数据结构.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 7 天前 | 显示全部楼层
哈哈,这个问题就像问“我能不能用榨汁机做炸鸡”一样,虽然听起来都跟吃的有关,但其实用错了工具哦!

链表和数组就好比面条和意大利面,它们虽然都是面,但处理方式大不相同。`qsort` 是为数组设计的,就像那意大利面的叉子,而链表呢,更像一盘经典的中式面条,需要用筷子来对付。

`qsort` 期待的是一个可以随机访问的数组,但链表是顺序访问的数据结构,正因为如此,`qsort` 对链表束手无策。我们需要用适合链表的排序算法,比如插入排序(插茄子版好像更接地气一点)、归并排序等。

如果你硬要让 `qsort` 去排链表,那估计它得抗议:“这个活儿真不是我的菜!”

所以,老铁,选择合适的工具来解决问题,比如下面用归并排序给链表排个序:
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
struct ListNode {
    int val;
    struct ListNode *next;
};

// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 切割链表的中点
struct ListNode* getMid(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 归并排序链表
struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) return head;

    struct ListNode *mid = getMid(head);
    struct ListNode *right = mid->next;
    mid->next = NULL;

    struct ListNode *left = sortList(head);
    right = sortList(right);

    return merge(left, right);
}

// 这里是测试代码,你可以创建自己的链表并调用上面的函数进行排序。
int main() {
    // 创建一个链表 4->2->1->3
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 4; n1->next = n2;
    n2->val = 2; n2->next = n3;
    n3->val = 1; n3->next = n4;
    n4->val = 3; n4->next = NULL;

    struct ListNode* sortedList = sortList(n1);

    // 打印排序后的链表
    struct ListNode* current = sortedList;
    while (current) {
        printf("%d ", current->val);
        current = current->next;
    }

    // 释放内存
    free(n1);
    free(n2);
    free(n3);
    free(n4);

    return 0;
}

看看,程序是不是整齐很多?记住啦,工具用对了,事半功倍!
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 7 天前 | 显示全部楼层
先转数组再用 qsort 再转链表即可
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 6 天前 | 显示全部楼层
zhangjinxuan 发表于 2024-7-10 21:12
先转数组再用 qsort 再转链表即可

好主意
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-7-17 03:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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