1.2 链式存储结构的存储结构和实现

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：线性表的顺序存储结构具有3个弱点：其一，在做插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述3个弱点，试讨论之。
　　● 习题2：说明在线性表的链式存储结构中，头指针与头节点之间的根本区别；头节点与首元节点的关系。
　　● 习题3：设链表节点的类型为：

　　函数merge(int *a,int *b)的功能是将两个升序链表 a 和 b 合并成一个升序链表。试将以下程序补充完整。

　　● 习题4：函数DelA_insB(LinkedList La,LinkedList Lb,int key1,int key2,int len)的功能是：将线性表A中关键码为key1的节点开始的len个节点，按原顺序移至线性表B中关键码为key2的节点之前，若移动成功，则返回0；否则返回1。线性表的存储结构为带头节点的单链表，La为表A的头指针，Lb为表B的头指针。单链表节点的类型定义为：

　　试将以下程序填写完整。

　　● 习题5：有一个带头节点的单链表L，其头指针为head，编写算法将链表L逆置。
　　● 习题6：已知两个表中元素为整型的带头节点的单链表LA和LB，其数据元素递增有序，且其存储的数据元素各不相同，设计算法将LA和LB中的数据元素都存储到LC中，并且LC中的数据元素仍然递增有序，比如：
　　LA=(1,3,5,7,9)，LB=(2,4,6,8,10)，
　　那么：LC=(1,2,3,4,5,6,7,8,9,10)
　　已有带头节点的空链表LC，要求不新增存储空间，并且时间复杂度为O(m+n)，其中m和n分别为LA和LB中数据元素的个数。
　　● 习题7：在一个递增有序的线性表L中，有数值相同的元素存在。若存储方式为带头节点单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(1,2,2,2,3,4,4,4,5,7)将变为(1,2,3,4,5,7)，分析算法的时间复杂度。
　　● 习题8：假设在算法描述语言中引入指针的二元运算“异或”（用 表示），若a和b为指针，则a b的运算结果仍旧为指针类型，且：
　　a (a b)=(a a) b=b
　　(a b) b=a (b b)=a
　　则可以利用一个指针域来实现双向链表。每个节点的两个域data域和link域，link域存放该节点前驱与后续节点指针（不存在时为NULL）的异或。若设指针h指向链表中的第一个节点，e指向链表中的最后一个节点，则可以实现从前向后或从后向前遍历此双向链表。编写一个算法从前向后输出该链表中各个元素的值。
　　2．综合应用题答案与分析
　　若无明确说明，综合应用题中涉及的线性表的链式存储结构，其中单链表的数据结构为：

　　双向链表的数据结构为：

　　习题1分析：
　　链式存储结构一般来说克服了顺序存储结构的3个弱点。首先，链式存储结构在进行插入和删除操作时不需要移动元素，只需要修改指针即可，其时间复杂度为O(1)；其次，链式存储结构不需要预先分配空间，可根据需要动态申请空间；再次，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，所以当内存空间不允许时，就不能克服顺序存储的缺点。
　　习题2分析：
　　在线性表的链式存储结构中，头指针即链表的指针，若链表有头节点，则链表的头指针即为指向头节点的指针，头指针具有标识作用。
　　头节点是为了操作的统一、方便而设立的，一般来说，头节点放在第一元素节点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度或用做监视哨等）。有头节点后，对在第一元素节点前插入节点和删除第一节点，其操作与对其他节点的操作统一了。而且无论链表是否为空，头指针均不为空。
　　首元节点也就是第一元素节点，它是头节点后边的第一个节点。
　　习题3分析：
　　此函数功能是将两个升序链表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。最后一个语句将合成的链表首指针作为函数返回值。
　　习题4分析：
　　本题是在链表插入和删除单个节点的基础上进行扩展，一次性插入多个节点和删除多个节点，其原理和插入、删除一个节点一致。首先在A链表中查找键值为key1的节点，使用了下列循环：

　　因此，当找到键值为key1的节点时，p指向该节点，prep指向p的前驱。然后再看在p的后面是否有len个节点，使用了下列语句：

　　显然，首先把q指向p，k为计数器，所以该循环的结束条件有两个：一是p的后面没有len个节点，这时q为空，所以（2）空应填写q = q->next，使q的指针往后移动；二是p的后面有len个节点，这时k=len。因此，（1）空应填写k < len。
　　根据上面的语句，如果p的后面有len个节点，则q指向第len个节点。如图1-2所示（虚线表示省略了中间若干个节点）。

　　同样的道理，在表B中查找键值为key2的节点，使用了下列循环：

　　首先，s指向第一个节点，然后进行循环，循环的结束条件也是两个，要么s为空（这时说明从头到尾都没有找到键值为key2的节点），要么找到了，s指向该节点，pres指向s的前驱。但是，如果第一个节点的键值就是key2，根据循环条件，循环中的语句不执行，则pres没有值，所以（3）空应该填写pres = Lb，使pres始终指向s的前驱，如图1-3所示（虚线表示省略了中间若干个节点）。

　　剩下的事情就是把p到q的连续len个节点从A表中删除，在B表中插入，如图1-4所示。

　　程序中使用的语句如下：

　　要把p到q的连续len个节点从A表中删除，就要把p的前驱（prep）的next指向q的next，因此，（4）空应填写prep->next。然后把q的next指向B表中s，把s的前驱（pres）的next指向p。所以，（5）空应填写s。