Machine World | Math World

记录实验过程

【数据结构】单向链表的反转/倒置的一种实现方法

【背景】

单向链表由于其存储灵活,所有的元素位置是通过额外开辟的指针作为指向的,于是在复习过程中,不由得想象一下如何将链表进行反转。

参考网上的教程,大多是用改变指针的指向进行实现,当然也有利用递归栈的特殊性质进行实现,考虑到复习时间不足,本文对其中一种实现方法进行分析,并给出源码实现。

【源码运行环境】

操作系统:MAC OS X 10.13.4

编译环境:CLion (C++ 14) cmake

【分析】

现假定针对这样一个结构构成的链表进行分析:

《【数据结构】单向链表的反转/倒置的一种实现方法》

首先,在上图基础上做辅助指针准备工作。

为了保存链表上下文(中间状态)

本文设置了四块指针:

  1. head —> 保存链表头结点 

  2. cur   —> 保存前驱节点(游标)

  3. top   —> 保存待反转节点(游标)

  4. first  —> 保存元素首节点

设置后的指针结构如下:

《【数据结构】单向链表的反转/倒置的一种实现方法》

本文采用一种元素前插倒转法进行链表倒置。

算法描述如下:

  1. 将元素上下文用first首指针保存;

  2. 将链表头节点用head指针保存;

  3. 现阶段链表划分为两个子集s1(反转后状态),s2(未反转状态);

  4. 其中cur是指向s1集合中的尾元素,top指向的是s2集合中的首元素

  5. 将头结点(head-next)指向在s2集合中的首元素(top指向的元素);

  6. 利用前驱指针cur-next指向s2集合中的次元素(top->next);

  7. 将s2集合中的首元素指向(top->next)first元素首部(first);

  8. 将top指针后移(top = cur->next);

  9. 判断top指针是否为空;

  10. case 1: top为空 结束反转

  11. case2 : top不为空重复1-9步骤

算法数学描述:

起始:

s1 = {}

s2 ={S1,S2,S3,S4,…Sn}

第一次:

s1 = {S1}

s2 = {S2,S3,S3,S4,…,Sn}

第二次:

s1 = {S2,S1}

s3 = {S3,S4,S5}

第n次:

s1 = {Sn,…,S3,S2,S1}

s3 = {}

算法图解如下:

第一步步骤如下:

《【数据结构】单向链表的反转/倒置的一种实现方法》

第一步完成时:各指针状态

《【数据结构】单向链表的反转/倒置的一种实现方法》

简化后(第二次开始状态):

《【数据结构】单向链表的反转/倒置的一种实现方法》

第二次步骤:

《【数据结构】单向链表的反转/倒置的一种实现方法》

简化后(第三次起始)指针上下文如下:

《【数据结构】单向链表的反转/倒置的一种实现方法》

当top指向NULL节点时,此时循环结束,反转完成。

【算法源码实现】

本源码基于前文的单链表实现。

核心代码如下:

Status LinkListReverse(Link *L)
{
    if(LinkListEmpty(*L))
    {
        return OVERFLOW;
    }
    Link head = *L;
    Link cur = head->next;
    Link top = cur->next;
    Link first = NULL;
    while(top != NULL)
    {
        first = head->next;
        head->next = top;
        cur->next = top->next;
        top->next = first;
        top = cur->next;
    }
    return TRUE;
}

【总结】

本文介绍了一种实现单向链表反转的方法并给出了实现,但是反转的算法还有很多值得改善的地方,也有不同的算法可以实现同样的功能。(递归法、后插反转法等)。算法的学习道路还很深,希望自己能够借此机会锻炼自己的计算机思维能力。(共勉)。

【参考文献】

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注