内容发布更新时间 : 2024/12/23 9:19:39星期一 下面是文章的全部内容请认真阅读。

2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){

P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; }

P->next=NULL;

for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i);

解：

精选

2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。 b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S;

(2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P;

(8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P;

解：a. (4) (1)

b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6) 2.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) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是_______________________。 b. 在P结点前插入S结点的语句序列是_______________________。 c. 删除P结点的直接后继结点的语句序列是_______________________。 d. 删除P结点的直接前驱结点的语句序列是_______________________。 e. 删除P结点的语句序列是_______________________。 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P; (6) S->priou=P;

(7) S->next=P->next; (8) S->priou=P->priou;

(9) P->priou->next=P->next; (10) P->priou->next=P; (11) P->next->priou=P; (12) P->next->priou=S; (13) P->priou->next=S;

(14) P->next->priou=P->priou; (15) Q=P->next; (16) Q=P->priou; (17) free(P); (18) free(Q);

解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18)

精选

d. (16) (2) (10) (18) e. (14) (9) (17) 2.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) 将单循环链表拆成两个单循环链表。

2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k) {

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法 else {

for(count=1;count

for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j];

a.length--; }

return OK; } 解：

Status DeleteK(SqList &a,int i,int k) {

//从顺序存储结构的线性表a中删除第i个元素起的k个元素 //注意i的编号从0开始 int j;

if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;

精选

for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k]; a.length=a.length-k; return OK; } 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

解：

Status InsertOrderList(SqList &va,ElemType x) {

//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;

if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,x

解：

Status CompareOrderList(SqList &A,SqList &B) {

int i,k,j;

k=A.length>B.length?A.length:B.length; for(i=0;i

if(A.elem[i]>B.elem[i]) j=1; if(A.elem[i]

if(A.length>k) j=1; if(B.length>k) j=-1;

if(A.length==B.length) j=0; return j; }

2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);

解：

int LocateElem_L(LinkList &L,ElemType x) {

int i=0;

LinkList p=L;

精选