C语言链表常用方法的讲解
本文最后更新于 481 天前,其中的信息可能已经有所发展或是发生改变。

本篇文章是对于 上一篇 文章的补充与说明。

其实链表真的是一种挺简单的数据结构,非常的清楚,也很好用,在这里向大家安利一个在知乎上发现的比较好的学习数据结构与算法的网站:http://zh.visualgo.net 里面有比较详细的讲解,就我自己的体验还行,但是要提醒大家的就是这里面的快排讲解写的是错的,不要信啦,我自己看了好久,才发现讲解不能自圆其说·········

实现链表的过程中,比较难得几个点有:

  • 链表的创建与初始化
  • 链表的反序
  • 链表的排序

其实细心的同学会发现这都集中在对于链表有写操作的基础上,我在开始的时候,没有很清楚的概念,于是犯了错,但是在过程中总结出来一个经验:

如果需要对传入参数修改,请传入原值的二级指针

为什么这么说呢?大家可以看一下我在Stack Overflow上提的:How to set struct pointer to NULL with function 这个问题,相信如果看完了解答大家会有一个比较清楚的理解,关键在于,如果传入的一级指针,在没有返回值的情况下,就不能对原链表的头进行赋值,所以便不能对其更改。

当然,另外一种的解决方式便是:

node* func(node* list){
    ...
}

list = func(node);

再返回指针的情况下,调用者对其重新赋值,这样也是可以的。不过用Python习惯,更喜欢前一种方式。

正是因为如此,有新的同学会观察到,我对于链表的这个实现中,所有涉及写操作的全部都要传入头指针的地址。

在这里对链表逆序的操作是这样的:

  1. 创建三个node* 型变量:
    node* previousNode;
    node* currentNode;
    node* nextNode;
  2. 这三个值分别保存上一个节点,当前结点,下一节点,并在对列表遍历的过程中,不断地把当前结点的指针重新指向上一节点
  3. 对于第一个传入的头指针,将其下一节点赋值为NULL
  4. 重要的是:一定要在对下一节点赋值完成之后,在进行上面的操作! 我开始就是因为没有这样,导致下一节点形成野指针,这就非常的难以寻找错误了
  5. 当链表遍历到最后一个时,退出循环

这样便能实现链表的逆序,我觉得也是比较省空间和时间的一种方式。

对于链表的排序,我采取了投机取巧的方式,因为有将链表导出为数组的接口,而我开始初始化链表时传入一个数组进行的,我便采取了用空间换时间的方式(这里空间复杂度是O(n),平均时间复杂度是O(nlogn))这是因为采取了快排的方式对于数组排序。

为什么不直接对链表排序呢?

大家可以观察一下我链表的swap函数:

void swapTwo(node** headNode, int fIndex, int sIndex){
    if (*headNode == NULL) return;
    if (fIndex == sIndex) return;
    int maxIndex = max(fIndex, sIndex);
    int minIndex = ((maxIndex == fIndex) ? sIndex : fIndex);
    int length = getLength(*headNode);
    if (maxIndex >= length || minIndex < 0) return;
    node* currentNode = *headNode;
    node* minNode;
    node* maxNode;
    int currentIndex = 0;
    while (currentIndex < minIndex){
        currentNode = currentNode -> next;
        currentIndex++;
    }
    int minIndexValue = currentNode -> data;
    minNode = currentNode;
    while (currentIndex < maxIndex){
        currentNode = currentNode -> next;
        currentIndex++;
    }
    int maxIndexValue = currentNode -> data;
    maxNode = currentNode;
    minNode -> data = maxIndexValue;
    maxNode -> data = minIndexValue;
}

每次找到被操作节点都需要遍历链表,最坏的情况下(即为链表全部逆序)我可能会得到O(n!)的时间复杂度,这是不可接受的。

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇