Machine World | Math World

记录实验过程

【数据结构】有序链表合并(归并)问题的一种解决思路

【背景】

设计一个程序,将两个递增的有序链表合并成一个递减的有序链表,要求结果链表仍使用原来两个链表的存储空间,合并后不允许有重复的数据。

本题取自广西师范大学2018年硕士研究生招生考试试题编程题部分)。

【源码运行环境】

操作系统:Windows 10

编译环境:Dev C++(基于C99标准)

【思路】

在背景题干中,我们知道,初始化有序的链表是递增的。而在我们学习数据结构中,我们是实现过将两个递增的链表合并成一个递增的链表这样的功能。

奈何,题干中的要求并非递增。

于是我们可以换个想法,是否可以综合我们所学的知识:

1、先合并成递增

2、再转置成递减。

由于时间有限,具体实现不赘述,此处给出递增合并单链表的算法;

链表创建即常用操作定义、链表转置的算法可以参照我之前的文章:

1、【数据结构】线性表的C语言实现

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

【伪代码】

void MergeList(LinkList &La, LinkList &Lb, LinkLisk &Lc)
{
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;
    while(pa && pb)
    {
        if(pa->data < pb->data)
        {
            pc->next = data;
            pc = pa;
            pa = pa->next;
        }
        else if(pa->data > pb->data)
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else
        {
            pc->next = pa;
            pc=pa;
            pa=pa->next;
            q=pb->next;
            delete pb;
            pb=q;
        }
    }
    pc->next = pa?pa:pb;
    delete b;
}

【总结】

由于作者最近刚换平台(从Mac OS X -> Windows),基于链表指针的调试涉及到编译环境的调试。复习时间有限,没能够及时地将代码实现,故给出《数据结构习题解析与实验指导》中关于归并递增链表的算法。其余算法已经证实可以在基于Cmake环境下进行实验。等闲下来再讲此算法进行完善。

本题也透露出一种程序设计思想:我们在有限时间内,要针对某项任务编写程序时,可以将需求进行细分,不一定得死磕需求字眼;这也是一种大化小,小化无。分而治之的程序设计思想。

【参考文献】

  • 《大话数据结构》.程杰.清华大学出版社

  • 《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社

  • 广西师范大学2018年硕士研究生招生考试《806/826 数据结构》试题

点赞

发表评论

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