chp2_线性表.ppt

7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接后继结点的语句序列是____________________。 b. 删除P结点的直接前驱结点的语句序列是____________________。 c. 删除P结点的语句序列是____________________。 d. 删除首元结点的语句序列是____________________。 e. 删除尾元结点的语句序列是____________________。 (1) P=P-next; (2) P-next=P; (3) P-next=P-next-next; (4) P=P-next-next; (5) while(P!=NULL) P=P-next; (6) while(Q-next!=NULL) { P=Q; Q=Q-next; } (7) while(P-next!=Q) P=P-next; (8) while(P-next-next!=Q) P=P-next; (9) while(P-next-next!=NULL) P=P-next; (10) Q=P; (11) Q=P-next; (12) P=L; (13) L=L-next; (14) free(Q); a. (11) (3) (14) b. (10) (12) (8) (3)(11) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是_______________________。 b. 在P结点前插入S结点的语句序列是_______________________。 c. 删除P结点的直接后继结点的语句序列是_______________________。 d. 删除P结点的直接前驱结点的语句序列是_______________________。 e. 删除P结点的语句序列是_______________________。 (1) P-next=P-next-next; (2) P-prior=P-prior-prior; (3) P-next=S; (4) P-prior=S; (5) S-next=P; (6) S-prior=P; (7) S-next=P-next; (8) S-prior=P-prior; (9) P-prior-next=P-next; (10) P-prior-next=P; (11) P-next-prior=P; (12) P-next-prior=S; (13) P-prior-next=S; (14) P-next-prior=P-prior; (15) Q=P-next; (16) Q=P-prior; (17) free(P); (18) free(Q); a. (7) (12) (6) (3) b. (8) (13) (5) (4) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 9. 简述以下算法的功能。 (1) Status A(LinkedList L) { //L是无表头结点的单链表 if(L L-next) { Q=L; L=L-next; P=L; while(P-next) P=P-next; P-next=Q; Q-next=NULL; } return OK; } (2) void BB(LNode *s, LNode *q) { p=s; while(p-next!=q) p=p-next; p-next =s; } void AA(LNode *pa, LNode *pb) { //pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); } 【答】(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。 【答】(2) 将单循环链表拆成两个单循环链表。 10. 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。函数原型为： Status InsertOrderList(SqList va,ElemType x)。 【答】 Status InsertOrderList(SqList va,ElemType x