将当前结点作为头结点后的第一元素结点插入 31.(1)L=L->next;∥暂存后继 待逆置结点 (3)L=p ∥头指针仍为L 32.(1)p. next(>po (2)r: = p.next p, -r (2)NIL (3)x<head.data (4)p. data<x (5)p: =p. next (6)p. data>=x:(7)r (9)r (10NIL (11)NIL 34.(1)pa!=ha ∥或pa->exp!=-1 (2)pa->exp==0 ∥若指数为0,即本项为常数项 (3)q->next=pa->next∥删常数项 ∥取下一元素 pa->coef冰 p ∥指数项减1 (7)pa ∥前驱后移,或q>next 取下一元素 ∥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!=nul)∥两均未空时循环 (2)A-> element==B-> element∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针 (4)A!=null ∥将A表剩余部分放入结果表中 (5)last->link=null ∥置链表尾 四 应用题 1.(1)选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的 影响,插入、删 除时间复杂度为0(1)。 (2)选顺序存储结构。顺序表可以随机存取,时间复杂度为0(1)。 2.链式存储结构一般说克服了顺序存储结构的三个弱点。首先,插入、删除不需移动 元素,只修改指针,时间复杂度为0(1);其次,不需要预先分配空间,可根据需要动态申 请空间:其三,表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销,当空 间不允许时,就不能克服顺序存储的缺点。(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）。 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为 O（1）。 2．链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动 元素，只修改指针，时间复杂度为 O(1)；其次，不需要预先分配空间，可根据需要动态申 请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空 间不允许时，就不能克服顺序存储的缺点