2)while(p!=null & p->data<X)p=p->next f(p==null|lp->data>x) return(nu11);∥查找失败 (p) (3)while! =null & p->data)X)p=p->next if(p=nul1|p>data<X) return(ml1):∥查找失败 else return(p);∥查找成功 15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中(pa中与pb中不 同结点删除),pa是结果链表的头指针。链表中结点值与从前逆序。S1记结果链表中结点个 数(即pa与pb中相等的元素个数)。S2记原pa链表中删除的结点个数 16.设q:=p.1link;则 q. rlink: =p. rlink: p. rlink. llink: =g: p. llink: =g. llink g. llink. rlink: = p: p. rlink: =q q. llink: =p 17.(1)前两个语句改为 p llink. rlink<- p. rlink: p. rlink. llink<- p. llink; (2)后三个语句序列应改为 q. rlink<-p. rlink;∥以下三句的顺序不能变 p. rlink. llink<- q p. rlink<-g: 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)fl↑.data<f2↑.data (C)f2↑.data<fl↑.data D)f3↑.data<fl↑.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->n (4)r=r->next;或r=q->next;∥后移指针,再将新结点插入到适当位置 算法设计题 1.[题目分析]因为两链表已按元素值递增次序排列,将其合并时,均从第一个结点起 进行比较,将小的链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减 次序排列。故在合并的同时,将链表结点逆置(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; 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．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起 进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减 次序排列。故在合并的同时，将链表结点逆置