第2章线性表 德例。下面是张个时刻的乘客表。试为该系统写出一个当任一乘客要订聚时修致乘客表的法。 1Li65 2 Chan 4 9 3 W ang 5 7 4 Bao 02 5 M ai 1 3 6 Dong 8 1 7Xi30 8 Deng 9 6 Cuang 2 8 【北方交通大 (17分) 的有 针为的 有 头点的循环向链 表 结点除有前驱指 daa（数据) 和next(后继指 使此 表中结点保持 (递)的 结点的最月 序排 以便使繁访间的结点总是靠近 同时最近 访问的结点挂在频用 该运算为函数过 返回找到结点的地址 类型为指针型。 1 给定生成 ad为头指针，结点的结构为日atn xdat为整型元素 t为指针，试写 安递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。（偠求不允许使用数组作辅助空间）【华中理 34.已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编 写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所 有无用结点。限定算法的时间复杂度为0(m+n+p),其中m、n和p分别为三个表的长度。【清华大学1995一(15分)】 h.bjing.com/u/knoyan/docum en t/aoyan/hiti/s2.htm 1/7)10-4-1511
第2章 线性表 链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。 序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8 【北方交通大学 2000 六 （17分）】 32．设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指 针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元 素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度 相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过 程，返回找到结点的地址，类型为指针型。【清华大学 1997 二 （10分）】 33．给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出 算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)【华中理 工大学 2000 八、2 （13分）】 34．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编 写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所 有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。【清华大学 1995 一 （15分）】 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 17／17 页）2010-4-15 11:00:46
第2章线性衣 第2章线性表 ,选择题 1.A 5.D 6D 10.RC 111T 112T 113E 1.4B1.5C 12B 3.C h4C 5.C 6.A 7.A 18.A 19.D 21B 22D 23C 24.B 25R D6A 27D 。判断题 5.×6.×.×8.×9.×0.×1.×2.× 13.×4√5.x6.√ 部分案解释如下 头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。 4.两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。 7.集合中元素无逻辑关系。 元素无前驱，最后 一个元素无后 线性表是逻辑结构，可以顺序存储，也可链式存储 填空题 1. 2.(n-1)/2 3.py->nextpx->next:px->nex=py 4n-t1 5.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链 表指针不变。 6.0),0)7.单链表，多重链表，（动态）链表，静态链表 8.f>nextp->next:f>prior=p:p->next>prior=f;p->nextf: 指r 物理相邻指针12.42 14.u ->next:p->nextu->next:free(u):15.L->next>nex=L 16.p->next=null 17.L>next=L&&L>priE=L 18.s>nextp->nextp->nexts: 88Nba6e AND pa.data>=pb".data (1)pre=pb:(2)pa<>N I AN D pb<>N IL AND pb".data>=pa".data (3)pa=pa".next:pb=pb->next: (4)pb=pre".nextpre=pbpa=pa".next:(5)IF pa=N IL TH EN retum (true)ELSE retum (fake) [注]：本题是在链表上求模式匹配问题。非递归算法中用指针指向主串中开始结点（初始时为第一元素结点）。若主串与子串 对应数 L 作指 pa和pb后移 ,主串工作指针从D的下一结点开始（这时pe又指向新的开始结点），子串工作 开始， “直 条件失败。若pa为空 成功，返回ue,否则，返回。 (=N I)TH EN r'.next=P g.ik°.data<>ma B:r=r'.Iink C:q'.lnk D:q".lnk E:r.lnk F:r'.Ink G :r=s (r=r'.Ink)H:r=r'.Ink I:q'.lnk=s'.Ink 院 1)h2)0 3)关广1 (4)p T .next 5)X1 动t∥工作指针后移 地后生的商是s (6)s".bft=p: 25.0)X=L.hst∥L.hst为元素个数 ∥有值不相等的元素 e和∥元素前彩 0 拉上链，前指向后继 新 前 ,biionzo0 ora0/月amuO2h年（第1/2H页）20104-511010
第2章 线性表 第2章 线性表 一．选择题 1.A 2.B 3.C 4.A 5.D 6.D 7.D 8.C 9.B 10.B,C 11.1I 11.2I 11.3E 11.4B 11.5C 12.B 13.C 14.C 15.C 16.A 17.A 18.A 19.D 20.C 21.B 22.D 23.C 24.B 25.B 26.A 27.D 二．判断题 1. × 2.√ 3. √ 4.× 5.× 6. × 7. × 8.× 9.× 10.× 11.× 12.× 13. × 14. √ 15.× 16. √ 部分答案解释如下。 1、 头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。 4．两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。 7．集合中元素无逻辑关系。 9．非空线性表第一个元素无前驱，最后一个元素无后继。 13．线性表是逻辑结构，可以顺序存储，也可链式存储。 三．填空题 1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py 4 ．n-i+1 5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链 表指针不变。 6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表 8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; 9．p^.prior s^.prior^.next 10． 指针 11．物理上相邻 指针 12．4 2 13．从任一结点出发都可访问到链表中每一个元素。 14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null 17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s; 19．(1) IF pa=NIL THEN return(true); (2) pb<>NIL AND pa^.data>=pb^.data (3) return(inclusion(pa,pb)); (4) pb:=pb^.next; (5) return(false); 非递归算法： (1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next; (4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE return(false); [注]：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串 对应数据相等，两串工作指针pa和pb后移；否则，主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作 指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。 20．A．VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(带头结点) 21．（1）new(h);∥生成头结点，以便于操作。 （2）r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p; 22．A: r^.link^.data<>max AND q^.link^.data<>max B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link G: r:=s（或r:= r^.link） H: r:=r^.link I: q^.link:=s^.link 23．(1)la (2)0 (3)j<i-1 (4)p↑.next (5)i<1 24.(1)head^.left:=s ∥head的前驱指针指向插入结点 (2)j:=1; (3)p:=p^.right ∥工作指针后移 (4)s^.left:=p (5)p^.right^.left:=s; ∥p后继的前驱是s (6)s^.left:=p; 25.(1)i<=L.last ∥L.last 为元素个数 (2)j:=j+1 ∥有值不相等的元素 (3)L.elem[j]:=L.elem[i] ∥元素前移 (4)L.last:=j ∥元素个数 26.(A)p^.link:=q;∥拉上链，前驱指向后继 (B)p:=q;∥新的前驱 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 1／24 页）2010-4-15 11:01:08
第2章线性表 (C)phk=head:∥形成循环链表 0)三0：计数器. 记被结点 )a=p.k∥记下被刑结点 )D.mk=a“.k∥删除结点 刀0相的佛根小值的前驱， 作指 个结占信是小 k骑 （即删除一结点) 28.0①)ke x:∥头结点这时起监视哨作用 广6eg=n“∥斗结占起监规哨作用 ③)q->pe>nex卡q->next:q->nexr>preq->pe;∥先将q结点从链表上摘下 p .pre;p ore->next=q ,qF0 值 将新建 点前) .Key= 的 ，取不同于a链表中其它数据域的值 表指针后移 30.C部分：1)p上u1 ∥链表未到尾就一直作 2)g 川将当前结占作为头结占后的第一元素结占插入 3L.)儿=L->next∥暂存后继 (2)q=L; 指 (3)p'.next=do: (4)=p:(5)p=r 33.) N I 3)x<head .data (4) .data<x 8)E (1)pa=ha (2)n exn==0 若指数为0，即本项为常数项 3)a->nex巨na>next∥l常数项 (4)q->next ∥取下一元素 (5)=pa>coepp exp 6) 贝减 p ∥前 >next >next 工作指针p的前 、是作指 ∥r记最大值的前驱 (④)q=p: ∥或q=q”,next (⑤)r,next=q^.next∥或rnext=r,next.next别最大值结点 36.()L->nexnu 链表，然后将原链表结点逐个插入到有序表中 9=nul 由的 这时q是工作指针 (5->nexEp 是。的前驱，u是下个待插入结点的指针。 37.程序(a)PA SCAL部分编者略) 程序(b)C部分 )(A=nu&&B=nuD∥两均未空时循环 相等元素不作结果元素 那表指 部分放入结果表中 (5)hst /置链表尾 四、应用题 (1)选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、别 除时间复杂度为0(1)。 p/.bjliong.com /au/kaoya/docu m/aoym /lamn/ia2h)010-4-15 11108
第2章 线性表 (C)p^.link:=head;∥形成循环链表 (D)j:=0; ∥计数器，记被删结点 (E)q:=p^.link∥记下被删结点 (F)p^.link=q^.link ∥删除结点 27. (1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;∥q指向最小值结点，s是工作指针 (3)s:=s^.link∥工作指针后移 (4)head:=head^.next;∥第一个结点值最小； (5)p^link:=q^.link;∥跨过被删结点（即删除一结点） 28．(1) l^.key:=x;∥头结点l这时起监视哨作用 (2) l^.freq:=p^.freq ∥头结点起监视哨作用 (3) q->pre->next=q->next; q->next->pre=q->pre; ∥先将q结点从链表上摘下 q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥结点q插入结点p前 (4) q^.freq=0 ∥链表中无值为x的结点，将新建结点插入到链表最后（头结点前）。 29．(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值 (2)b^.key:=p^.key∥b的头结点起监视哨作用 (3)p:=p^.next∥找到a,b表中共同字母，a表指针后移 (4)0(m*n) 30. C 部分：(1)p!=null ∥链表未到尾就一直作 (2)q ∥将当前结点作为头结点后的第一元素结点插入 31. (1)L=L->next; ∥暂存后继 (2)q=L; ∥待逆置结点 (3)L=p; ∥头指针仍为L 32. (1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0; (4) q0:= p; (5) p:=r 33. (1)r (2)NIL (3)x<head^.data (4)p^.data<x (5)p:=p^.next (6)p^.data>=x; (7)r (8)p (9)r (10)NIL (11)NIL 34．(1)pa!=ha ∥或pa->exp!=-1 (2)pa->exp==0 ∥若指数为0，即本项为常数项 (3)q->next=pa->next ∥删常数项 (4)q->next ∥取下一元素 (5)=pa->coef*pa->exp (6)- ∥指数项减1 (7)pa ∥前驱后移,或q->next (8)pa->next ∥取下一元素 35．(1)q:=p; ∥q是工作指针p的前驱 (2)p^.data>m ∥p是工作指针 (3)r:=q; ∥r 记最大值的前驱， (4)q:=p; ∥或q:=q^.next; (5)r^.next:=q^.next; ∥或r^.next:=r^.next^.next 删最大值结点 36．(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null ∥当链表尚未到尾，p为工作指针 (3)q!=null ∥查p结点在链表中的插入位置，这时q是工作指针。 (4)p->next=r->next ∥将p结点链入链表中 (5)r->next=p ∥r是q的前驱，u是下个待插入结点的指针。 37．程序（a） PASCAL部分(编者略） 程序（b） C部分 (1)(A!=null && B!=null) ∥两均未空时循环 (2)A->element==B->element ∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针 (4)A!=null ∥将A 表剩余部分放入结果表中 (5)last->link=null ∥置链表尾 四、 应用题 1．（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删 除时间复杂度为O（1）。 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 2／24 页）2010-4-15 11:01:08
第2章线性表 2) 结构 顺序表可以随机存取 时间复杂度为0 1) 其次 开销当间不许时，不能点字存储的占 3。采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和 别除操作不需要移动元素。 ,线性表枝 队列串 顺序存储结构和链式存储结构。 TYPE 线性表可能达到的最大长度 RRAYIm axen]0FEm Type: 链式存储结构的定义是： link list 5顺序映射时，5+1的物理位置相邻：链表表示时与a+1的物理位置不要求相邻。 6。在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用 头指针冠以 表的名子。 头结点是为了操作的统一 方便而设立的，放在第 元素结点之前，其数据域一般无意义（当然有些情 放链表的 ”对在第 和 对其它结 点的操作 个结点。 将 变为两个域：pe和 8,收0是元秦个 ext,其值域均为0.m axsize。初始化时，头结点（下标为0的元素）其nex域值为l,其pe域值为r (2)stalist[stalist[p].pre].pre: (3)stalist[p].next: 9.在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中 每个结点。 在双链表中求驱和后继都容易 当前结点 摘下，并将其指针城。然后从第素结开始结高到最后 丽到弟 点，回 后到最后结点， 可以功何到任何 个结古 该法的功能是判断链 是是非递有序， 若是则返回“ue”:否则返回“e“。pe指向当前结点，p指向p的后 >next:free(a) 18:设单链表的头结点的头指针为ead,且pr=henad: while(pre >next=p)pre=pre >next: s>nexEp;pre- 点， 作指针p初始化为p=H>next Dm查找失败 2)whienull&data )n=p -)m n==nuⅡ川n->da>X)etum (uD:∥杏找失败 ele retum (p): 3)while(p=null&&p->dataX)p= if(p==nul Ip-dat retm (nu:∥查找失败 15,本程序段功能是将 a链表中(pa中与pb中不同结点除) a是结果链表的头指针。链表 中结点值与从前 相等的元 个数 S2记 a链表中除的结点个数 盘水k:p, .Ink .rlink=p:p .rink=q: a.Ilink=p 17.1)前两个语句改为： p.llnk .rlink<-p .rlink h/w.biion20omaM0 n月a02h（第3/2页）2010-4-5110108
第2章 线性表 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。 2．链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)； 其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间 开销，当空间不允许时，就不能克服顺序存储的缺点。 3．采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和 删除操作不需要移动元素。 4．线性表 栈 队列 串 顺序存储结构和链式存储结构。 顺序存储结构的定义是： CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD elem:ARRAY[1.maxlen] OF ElemType; last:0.maxlen; END; 链式存储结构的定义是： TYPE pointer=↑nodetype; nodetype=RECORD data:ElemType; next:pointer; END; linklisttp=pointer; 5.顺序映射时，ai 与ai+1的物理位置相邻；链表表示时ai 与ai+1的物理位置不要求相邻。 6．在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用 头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情 况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结 点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。 7．见上题6。 8．(1)将next域变为两个域: pre和next，其值域均为0.maxsize。初始化时，头结点（下标为0的元素）其next域值为1，其pre域值为n （设n是元素个数，且n<maxsize） (2) stalist[stalist[p].pre].pre; (3) stalist[p].next; 9. 在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中 每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 10．本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一 个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 11．该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false“。pre指向当前结点，p指向pre的后 继。 12．q=p->next; p->next=q->next; free(q); 13. 设单链表的头结点的头指针为head,且pre=head； while(pre->next!=p) pre=pre->next; s->next=p; pre->next=s; 14.设单链表带头结点，工作指针p初始化为p=H->next; (1) while(p!=null && p->data!=X) p=p->next; if(p= =null) return(null);∥查找失败 else return(p);∥查找成功 (2) while(p!=null && p->data<X ) p=p->next; if(p==null || p->data>X) return(null);∥查找失败 else return(p); (3) while(p!=null && p->data>X) p=p->next; if(p==null || p->data<X) return(null); ∥查找失败 else return(p); ∥查找成功 15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中（pa中与pb中不同结点删除），pa是结果链表的头指针。链表 中结点值与从前逆序。S1记结果链表中结点个数（即pa与pb中相等的元素个数）。S2记原pa链表中删除的结点个数。 16．设 q:=p^.llink; 则 q^.rlink:=p^.rlink; p^.rlink^.llink:=q; p^.llink:=q^.llink; q^.llink^.rlink:=p; p^.rlink:=q; q^.llink:=p 17.(1)前两个语句改为： p.llink^.rlink<- p^.rlink; http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 3／24 页）2010-4-15 11:01:08
第2章线性表 p.rk.ik<-p.k: ②)后三个语句序列应改为 qmk<-p^mk:∥以下三句的顺序不能变 p".rlnk".Ilink<-q: p .rlnk<-q; 作用白 其 嵌套有过程 ubp 是将 前驱构造为循环链表 的前指在链表中】 并非构浩的低环链表中)构浩为衙环裤表 当之 两次调用将L循环链表分解为两个。第一个循环链表包含从P到b的前驱，L中除刚构造的a到pb前驱外的结点形成第二个循 环链表 19.在指针p所指结点前插入结点s的语句如下： a<沉并且5P>nex卡p2 )n<-n,k或2=2↑k 21.1)本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向 循环链表。 2)I)r>p1=q->por:∥将q结点摘下，以便插入到适当位置。 2p〉next>p西=q∥(2)(3)将q结点插入 ④r>nex或=g>next/后移指针，再将新结点插入到适当位置 算法设计颗 [愿目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链 表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 L inkedL istU n ion inkedL ist h,b) a,b 带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次 DD- ∥a作 Ena>next ∥将Da的后继结点暂存于Tr Da->next=h>next∥将Da结点链于结果表中，同时逆置 h->next-pa: a-r ∥恢复pa为当前待比较结点 nex七∥将h的后继结占新存 pb->nex卡hr)next∥将pb结点链于结果表中，同时逆置 h->next=pb ob=r:∥恢复Db为当前待比较结点。 whpa=nuD∥将h表的剩余部 h ob->nexth->next:h->next=pb:pb=r:) [算法讨论]上面两链表均不为空的表达式也可简写为wh正pk&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆 置。也可先合并完 ,冉作链表逆置。后者不 如前者优化。算法中最后两个W语句，不可能执行两个，只能二者取一，即哪个表 尚未到尾， 将具 逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 (1) 其它思 同之处在于 数据相同的结 “是链表无头结点，为处理方便 ,给加上头结点，处理结束再删除之：二是 链表中 三是 表不能被 即将b的结点合并到结果链表时，要生成新结点。 ht年ww.biliong.com fza/k n月am02h每（第4/24页）2010-4-15110108
第2章 线性表 p^.rlink^.llink<- p^.llink; (2)后三个语句序列应改为： q^.rlink<- p^.rlink;∥以下三句的顺序不能变 p^.rlink^.llink<- q; p^.rlink<- q; 18．mp是一个过程，其内嵌套有过程subp。 subp(s,q)的作用是构造从s到q的循环链表。 subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。 subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环链表中）构造为循环链表。 总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循 环链表。 19．在指针p所指结点前插入结点s的语句如下： s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s; 20．(A) f1<>NIL并且f2<>NIL (B) f1↑.data < f2↑.data (C) f2↑.data<f1↑.data (D) f3↑.data<f1↑.data (E) f1<- f1↑.link 或f2=f2↑.link; 21. 1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向 循环链表。 2）(1)r->prior=q->prior;∥将q结点摘下，以便插入到适当位置。 (2)p->next->prior=q;∥（2）（3）将q结点插入 (3)p->next=q; (4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。 五、 算法设计题 1．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链 表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList la,lb) ∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次 序排列的单链表。 { pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针 la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; ∥将pa 的后继结点暂存于r。 pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; ∥恢复pa为当前待比较结点。 } else {r=pb->next;∥ 将pb 的后继结点暂存于r。 pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; ∥恢复pb为当前待比较结点。 } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }∥算法Union结束。 ［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆 置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表 尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 与本题类似的其它题解答如下： （１）［问题分析］与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是 数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。 LinkedList Union(LinkedList ha, hb) http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 4／24 页）2010-4-15 11:01:08