《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指 向该结点的后继结点。本题答案为：前驱。

[例7-14] 在一个长度为n的顺序表中删除第i(0≤i≤n一1)个元素，需向前移动 个元素。

解析：需将第i个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。本题答案为：n-i-1。

[例7-15] 在一个具有n个结点的单链表，在 * p结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。

解析：在 * p结点后插入一个新结点 * s的操作是：s—> next＝p—> next；p—>next＝ s；其时间复杂度为0(1)。

在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该 结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。本题答案为：O(1)；O(n)。 三、应用题

(例7-16) 设A是一个线性表(a0，a1，…，ai，…，an-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在ai和ai+1之间 (0≤i≤n-1)的概率为

n?1，则平均每插入一个元素所需要移动的元素个数是多少? n(n?1)/2 解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：

(0?1?2?L?n)n?

n?12若元素插在ai和ai+l之间(0≤i≤n-1)的概率为要移动的元素个数为：

n?i，则平均每插入一个元素所需

n(n?1)/2?i?0n?1(n?i)222n?1222 ???n?(n?1)?L?1???n(n?1)/2n(n?1)3 (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。

解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。

[例7-18] 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么?

解析：应采用链式结构来存储该线性表。采用链式存储结构来存储线性表，在进行插 入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平 均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除 操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。因为指针域的移动 操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。 (例7—19) (1)写出在双向链表中的结点 * p前插入一个结点 *s的语句序列。 (2)写出判断带头结点的双向循环链表L为空表的条件。 解析：(1)s—>prior＝p—>prior；p—>prior — >next＝s；

s—>next＝p；p—>prior＝s；

(2)(L＝＝L—>next)&&(L＝＝L—>prior)

[例7-20] 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表

学习必备 欢迎下载

示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?

解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。

四、算法设计题

(例7-21) 编写一个算法，将一个带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点；

解析：从单链表的一种构造方法——头插法中可以得知，该方法构造的线性表中结点 的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表， 所构造的单链表即为原表的逆转。 具体算法如下：

linklist * reverse(1inklist * h) {

linklist * p，*q，*r； p＝h—>next；

h—>next=NULL； //构造空表 while(p!＝NULL) {

q=p； //拆下结点 p=p—> next；

q—>next=h—>next； //用头插法插入 h—>next=q； }

return h； }

(例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。

解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个 大于等于x的元素之前。应先在表中找到该位置，然后后移该元素，空出一个位置，再将x 插入。

具体算法如下：

insert(sqlist *La，datatype x) //La为指向顺序表的指针 {

int i=0，j；

while(i<= La—>last) //查找插入位置i {

if(x<=La—>data[i])

break； i++； }

for(j=La—>last+1；j>i；j--) //后移所有大于等于x的元素 La—>data[j]=La—>data[j-1]；

La—>data[i]＝x； //将x插入 La—>last++； //表长度加1

学习必备 欢迎下载

}

(例7-23) 用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B表内无重复元素)。 ’

解析：求C＝A∩B，C中元素是A、B中的公共元素。对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。 具体算法如下：

intersection(sqlist A，sqlist B，sqlist * C) {

int i，j，k＝0；

for(i＝0；i<＝A．1ast；i++) { j=0；

while(j<＝B.1ast&& A.dara[i]!＝B.data[j] j++；

if(j<＝B.1ast) //表示A.data[i]在B中 C—>data[k++]＝A.data[i]

}

C—>last=k—l； //修改表长度 }

[例7-24] 编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。 解析：先设一计数器n，初值为0。然后遍历链表中的每个结点，每遇到一个结点都需 要判断其数据域值是否为x，如果是，计数器n加1。遍历完成后计数器n的值就是所求的 结点数。

具体算法如下：

int count(linklist * head, datatype x) {

int n=0； linklist * p； p = head；

while(p ! = NULL) {

if(p—> data = = x) n++; p=p—>next； }

return n； }

(例7-25) 用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C， 并用链表Lc表示(假设A、B内无重复元素)。

解析：根据集合运算规则可知，集合A—B中包含所有属于集合A而不属于集合B的 元素。具体做法是：从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不 在，则将其插入单链表Lc中。

具体算法如下：

linklist * difference(linklist * La, linklist * Lb)

学习必备 欢迎下载

{

linklist *Lc, * pa, *pb, * s, * r； pa= La—>next

Lc = (linklist * ) malloc (sizeof (linklist)) ; r=Lc;

while(pa! = NULL) {

pb=Lb—> next;

while (phb! = NULL & & pb—> data ! = pa—> data) pb= pb—>next； if(pb = = NULL) {

s= (linklist * )malloe(sizeof(linklist)); s—> data= pa—>data； r—>next=s； r—s； }

pa= pa—>next； }

r—>next = NULL； return Lc； }

(例7-26) 已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。 解析：由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。 具体算法如下：

linklist * union(linklist * La, linklist * Lb) {

linklist * pa, * pb, * r； pa = La—> next； pb= Lb—>next；

r=La； //以*La为新表头结点，r为新表尾指针 free(Lb); //释放Lb表头结点 while(pa! =NULL && pb! =NULL) {

if ( pa—> data< pb—> data) {

r=pa;

pa= pa—>next； }

else if(pa—>datadata)