1.3 章真题解析

　　例题21
　　线性表的顺序存储结构具有三个弱点：其一，在做插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
　　例题21分析
　　链式存储结构克服了顺序存储结构的三个弱点：首先，链式存储结构在进行插入和删除操作时不需移动元素，只需要修改指针即可，其时间复杂度为O(1)；其次，链式存储结构不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。
　　例题22
　　设链表结点的类型为：
　　
　　函数merge(int *a，int *b)的功能是将两个升序链表 a 和 b 合并成一个升序链表。试将以下程序补充完整。
　　
　　例题22分析
　　此函数功能是将两个升序链表a，b合并。合并两个链表一般有两种方法：一是把两个链表合成一个新的链表，二是把一个链表插入另一个链表中。此函数采用的是第二种方法。这一点从函数中的“*h=a”和“return h”可以看出。还有一点值得注意，在for循环体中用到了一个变量q，q用于记录当前结点p的上一个结点。q的引入能让我们更方便地对链表进行操作，是链表操作的一个常用技巧。
　　程序中的for循环用于为链表b的当前结点查找合适的插入位置。if判断条件“p==h”，当a链表为NULL，或a链表的第一个元素大于b链表的第一个元素时成立。此时，b链表第一个元素应当成为a链表的首元素。所以，（1）空应填写“h = b”。当if判断条件“p == h”不成立时，b链表当前元素应插入的位置为q结点之后，p结点之前。所以，（2）空应填写“q->next = b”。
　　当程序运行到（3）空时，b已经不是原来的b了（因为前面执行了“b = b->next”），而q指向了原来的b，所以，（3）空应填写“q->next = p”。最后一个语句将合成的链表首指针作为函数返回值。
　　例题23
　　已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
　　（1）描述算法的基本设计思想。
　　（2）描述算法的详细实现步骤。
　　（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或Java语言实现），关键之处请给出简要注释。[2009年试题42]
　　例题23分析
　　（1）算法的基本思想如下：从头至尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。
　　（2）详细的实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点，如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少个结点，当i>k时，指针p随着每次的遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。
　　（3）算法描述如下：
　　
　　例题24
　　带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集A∪B。要求该并集中的元素仍保持递增有序，且要利用A和B的原有结点空间。
　　例题24分析
　　算法描述如下：
　　
　　例题25
　　试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
　　例题25分析
　　本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删除结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以，算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。算法描述如下：
　　
　　例题26
　　设头指针为head，并设带头结点的单链表中的数据元素递增有序，编写算法将数据元素x插入到适当位置上，要求插入后保持单链表数据元素的递增有序。
　　例题26分析
　　从链表的首结点开始，逐个比较每个结点的合适位置，申请新结点，当data小于等于x时，进行下一个结点的比较；否则，就找到了插入结点的合适位置，把新结点插入；当比较到最后一个结点时，如果data小于等于x，则把新结点插入到单链表的表尾。算法描述如下：