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就是无表头结点得单链表
}
p=s;
while(p->next!=q) p=p->next; p->next =s; if(L && L->next) { }
return OK;
Q=L;
L=L->next;
P=L;
while(P->next) P=P->next; P->next=Q;
Q->next=NULL;
(2) void BB(LNode *s, LNode *q) {
}
void AA(LNode *pa, LNode *pb) { }
解：(1) 如果L得长度不小于2，将L得首元结点变成尾元结点。
//pa与pb分别指向单循环链表中得两个结点 BB(pa,pb); BB(pb,pa);
(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 } 解： Status DeleteK(SqList &a,int i,int k) { } 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 va、elem[i]=va、elem[i-1]; va、elem[i]=x; //从顺序存储结构得线性表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; } //删除第一个元素 for(j=a、length;j>=i+1;j--) a、elem[j-i]=a、elem[j]; a、length--; return OK; } 2、12 设 va、length++; return OK; A??a1,?,am?与B??b1,?,bn?均为顺序表，A?与B?分别为A与B中除去最大共同前 A??B??空表，则A?B；若A?=空表，而B??空表，或者两者均不为空表，且A?得首元小于B?得首元，则A?B；否则A?B。试写一个比较A，B大小得算法。枭鴇羈鋯饲巅勵。 缀后得子表。若 解： Status CompareOrderList(SqList &A,SqList &B) { } 2、13 试写一算法在带头结点得单链表结构上实现线性表操作Locate(L,x); 解： int LocateElem_L(LinkList &L,ElemType x) { } 2、14 试写一算法在带头结点得单链表结构上实现线性表操作Length(L)。 解： //返回单链表得长度 int ListLength_L(LinkList &L) { int i=0; LinkList p=L; if(p) p=p-next; while(p){ p=p->next; int i=0; LinkList p=L; while(p&&p->data!=x){ } if(!p) return 0; else return i; p=p->next; i++; int i,k,j; k=A、length>B、length?A、length:B、length; for(i=0;i if(A、length>k) j=1; if(B、length>k) j=-1; if(A、length==B、length) j=0; return j; if(A、elem[i]>B、elem[i]) j=1; if(A、elem[i] } } i++; return i; 2、15 已知指针ha与hb分别指向两个单链表得头结点，并且已知两个链表得长度分别为m与n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后得链表得头结点，并要求算法以尽可能短得时间完成连接运算。请分析您得算法得时间复杂度。练锺媽诽穑妩脶。 解： void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)販錠粮鵝绢誚滦。 { } 2、16 已知指针la与lb分别指向两个无头结点单链表中得首元结点。下列算法就是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法就是否正确？若有错，请改正之。垒瓊編织卢矿炉。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)緶钦緗臏診攪腻。 { } 解： if(i<0||j<0||len<0) return INFEASIBLE; p=la; q=p; while(k<=len){ q=q->next; s=lb; k=1; while(k s=s->next; k++; } q->next=s->next; k++; } k=1; p=p->next; k++; } while(k while(pa->next&&pb->next){ } if(!pa->next){ } else{ } hc=ha; while(pa->next) pa=pa->next; pa->next=hb->next; hc=hb; while(pb->next) pb=pb->next; pb->next=ha->next; pa=pa->next; pb=pb->next;