数据结构1800题（答案全）(13)

(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

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;∥新的前驱

(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的头结点起监视哨作用