双链表的初始化 [关于线性链表基本操作技巧]
时间：2018-12-24 03:32:45 来源：雅意学习网 本文已影响 人 
摘要： 笔者从事《数据结构》专业基础课教学4年的时间，通过教学实践和项目实践，以及计算机专业考研辅导等各种方式和途径，总结了学生在学习中的一些比较常见的问题。由于线性结构是数据结构学科中最基本最常用的结构，所以针对线性结构的各种算法和应用，笔者简单地总结了其中的一部分技巧性的方法。
关键词： 线性表 数据结构 基本操作 技巧
线性表是我们在数据结构的学习中碰到的第一个数据结构，其重要性不言而喻。学习线性表的重点是掌握顺序表和单链表上实现的各种基本算法和相关的时间性能及空间性能的分析，难点就是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
就逻辑结构而言线性表非常简单，是有限数据元素的顺序序列，对于存储结构我们初学者一般也只研究顺序存储和链式存储两种。即便如此，仍然有很多学生对线性表的综合应用题目无从下手，这种现象甚至在许多学生考研过程中经常出现。问题的关键是学生只把线形表的各个知识点作为一个独立的题目看待，没有将它们联系看待，此外在解决较为复杂的题目时不知道和简单的基础知识点作联系。
例如关于线形链表（通常以单链表为例）的插入操作，已知单链表L，在第i个元素的前面插入一个新的元素e；一般程序实现如下：
单链表的这种基本插入算法，在数据结构的各种教材中都有描述，而且都是将其当作对单链表操作的第一个算法来学习。其寓意在于借助简单算法解决较为复杂的算法。其中最为典型的就是利用插入算法完成构造单链表算法，经典的构造算法有“首插法”和“尾插法”。我们先来认识一下首插法。首插法简单地理解就是通过在单链表的首部插入新节点完成单链表的构造任务。在数据结构中单链表一般指的就是带头节点的单链表，所以单链表的首部就是指头节点后面的位置，算法的关键就成了如何始终在头节点的后面插入新节点。问题分析完了大家就可以起笔描述算法了。
首先对算法分析可知，建立单链表的过程是一个动态生成的过程。即从“空表”的初始状态起，依次建立。在该算法中核心语句为P->next=L->next；L->next=P。在头节点的后面插入，不难发现这和前面的在单链表第i个位置之前插入新元素算法的核心语句几乎等同，所以我们可以认为是插入基本操作解决了建立单链表问题。同样如果我们继续探索首插法就会发现，由首插法建立的单链表元素输入顺序和最终在单链表里的位置刚好逆置！这就是在考研中经常出现的题目，比如已知某某线性链表，编写算法将该链表逆置；或者已知线性链表节点值非递减有序，编写算法完成该链表的非递增有序排列……看来只要我们细心观察分析，就能从很多简单问题中得到解决复杂问题的突破口。
通过上面对“首插法”的分析，我们可能会得到一些相关的启示。下面再通过对“尾插法”分析加深大家的理解。尾插法直观地理解就是不断地在单链表的尾部插入新节点，完成单链表的建立。同上面同样的题目：建立具有n个节点的单链表L，条件是利用尾插法。算法描述如下：
前面的算法实现和首插法完全相同，关键是下面的核心语句体现在链表尾部插入。假设仍让使用上一种算法的语句：P->next=L->next；L->next=P，先插入第一个节点。因为插入第一个节点的时候，该节点既是第一个节点又是最后一个节点（既是首部又是尾部），所以看不出两种算法的差别。再结合画图分析插入第二个节点。在第一个节点的尾部插入，这时第二个节点就成了链表的尾部；同样，插入第三个节点在第二个节点的尾部，结果第三个节点就成了尾部，将这种方法继续下去就是尾插法。从插入的过程分析可以知道链表的尾部比较关键，所以需要定义一个Lnode型的结构体指针r始终指向尾部节点。原来的链表为空，可以令r=L，即指向头节点，我们的目标就转化成了每次把新节点P插入到r所指节点的尾部，则就有插入语句序列：P->next=r->next；r->next=P，这两个命令在教材中是我们学习过的基本插入语句。但是最后的细节一定要注意到，为了保证r始终指向尾部，则应该r=r->next；或者r=P，都可以实现。我们的程序描述就完整了：
对尾插法的算法分析后，我们知道利用这种方法建立的单链表，元素的输入次序和元素在单链表中的次序一致，利用这种特点我们也可以技巧性地处理一些问题，比如：“已知两个线性链表La和Lb，元素均是递增排列，编写算法完成这两个单链表的合并，并且合并以后的单链表保持元素的递增特点；算法要求利用原来单链表中的节点存放归并后的单链表。”这个算法的关键在于合并后保持递增性，也就是跟合并前单链表的特性保持一致。根据这个提示我们可以分析一下：假设合并以后的单链表是Lc，Lc初始状态为空链表，即只有头节点，为了节约空间我们假借链表La的头节点为Lc的头节点，即Lc=La；下面的工作就是解决如何将La和Lb中的节点插入到Lc中去；假设La中的元素分别为（a ，a ，a ……a ）且a next，q=La->next；从第一个节点开始出发，将p和q所指的节点进行比较，if（p->datadata），则将La中的节点p插入Lc中，否则插入Lb中的节点q，这时在Lc中的第一个节点值就是最小的，我们就在最小的节点后面插入第二小的，在第二小的节点后面插入第三小的……不断地在Lc的尾部插入满足条件的节点，这在本质上刚好使用了我们上面讲过的“尾插法”建立单链表Lc，剩余的工作就是把算法赋予代码了：
除此之外，通过对线性链表的简单问题仔细分析和掌握，我们就可以攻克许多关于线性表甚至是非线性结构的较复杂问题。所以平时学习课本基础知识的时候，不能只停留在知识的表面，应该充分理解，遇到复杂问题时我们不要恐惧，要学会跟基本的知识联系，以基本的理论方法解决掉复杂的问题；同时我们还不难发现，在算法实现时考虑问题的全面性也非常重要；就像刚才合并算法中，虽然找出了算法的核心，但是当出了那个核心循环体，还要考虑到哪个链表中有节点剩余，这样的情况时常会出现。综合来看，按照上面所讲的这种技巧性的思考方式，即在理解基础知识之上进行发散思考，学生不但找到了许多复杂问题的解决途径，同时也让自己有了小小的成就感，学习更有兴趣和信心了。这种技巧不仅在解决线性链表的各种问题中适用，在数据结构的其他方面同样适用，只要平时多观察、多思考、多练习，大家就可以找到更多更巧妙的方法。
参考文献：
［１］严蔚敏.数据结构（C语言版）.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”189,
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
