线性表习题课

1、12021年年10月月17日日 删除顺序表a中第i个元素起的k个元素 Status DeleteK(SqList &a,int i,int k) if(i1|ka.length) return FALSE; for(count=0;i+count-1va.listsize) return ERROR; va.length+; for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; 32021年年10月月17日日 在带头结点的链表上实现在带头结点的链表上实现locate操作操作 LNode

2、* Locate(LinkList L,int x) for(p=L-next;p&p-data!=x;p=p-next); return p;42021年年10月月17日日 将将ha和和hb两条链表连接起来两条链表连接起来,带头节点带头节点 void ListConcat(LinkList ha,LinkList hb,LinkList &hc) hc=ha;p=ha; while(p-next) p=p-next; p-next=hb-next; free(hb);52021年年10月月17日日在无头结点链表中第i个元素前插入节点b Status Insert(LinkList &L,in

3、t i,int b) p=L;q=(LinkList*)malloc(sizeof(LNode); q-data=b; if(i=1) q-next=p;L=q; else while(-i1) p=p-next; q-next=p-next;p-next=q; 62021年年10月月17日日删除无头结点链表中第i个元素 Status Delete(LinkList &L,int i) if(i=1) L=L-next; else p=L; while(-i1) p=p-next; p-next=p-next-next; 72021年年10月月17日日删除递增链表中大于mink小于maxk的节

4、点Status Delete_Between(Linklist &L,int mink,int maxk) p=L; while(p&p-next-datanext; if(p-next) q=p-next; while(q-datanext; p-next=q; 8 实现顺序表的转置 void reverse(SqList &A) for(i=1,j=A.length;ij;i+,j-) A.elemiA.elemj;2021年年10月月17日日9 实现链表转置（要求利用原空间，l2） void LinkList_reverse(Linklist &L) p=L-next;q=p-next;

5、s=q-next; p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; q-next=p;s-next=q;L-next=s;2021年年10月月17日日102021年年10月月17日日void merge(LinkList &A,LinkList &B,LinkList &C) p=A-next;q=B-next;C=A; while(p&q) s=p-next;p-next=q; if(s) t=q-next;q-next=s; p=s;q=t; 11 把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间 void r

6、everse_merge(LinkList &A,LinkList &B,LinkList &C)/ pa=A-next;pb=B-next;pre=NULL; while(pa|pb) if(pa-datadata|!pb) pc=pa;q=pa-next;pa-next=pre;pa=q; else pc=pb;q=pb-next;pb-next=pre;pb=q; / pre=pc; C=A;A-next=pc; /reverse_merge2021年年10月月17日日12 求递增排列的顺序表A和B的元素交集并存入C中(递增) 假设A，B结束的条件为：A.elemn=B.elemn=0;

7、 void SqList_Intersect(SqList A,SqList B,SqList &C) i=1;j=1;k=0; while(A.elemi&B.elemj) if(A.elemiB.elemj) j+; if(A.elemi=B.elemj) C.elem+k=A.elemi; i+;j+; 2021年年10月月17日日13 求递增排列的链表A和B的元素交集并存入C中(递增) void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)/ p=A-next;q=B-next; pc=(LNode*)malloc(size

8、of(LNode); C=pc; while(p&q) if(p-datadata) p=p-next; else if(p-dataq-data) q=q-next; else s=(LNode*)malloc(sizeof(LNode); s-data=p-data; pc-next=s;pc=s; p=p-next;q=q-next; 2021年年10月月17日日14A,B,C三个顺序表，要求删除A中同时出现在B,C的元素 A，B，C中的元素可能出现重复中的元素可能出现重复 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)

9、 i=0;j=0;k=0;m=0; while(iA.length&jB.length& kC.length) if(B.elemjC.elemk) k+; else same=B.elemj; while(B.elemj=same) j+; while(C.elemk=same) k+; while(iA.length&A.elemisame) A.elemm+=A.elemi+; while(iA.length&A.elemi=same) i+; /while while(inext;q=C-next;r=A-next; while(p&q&r) if(p-datadata) p=p-ne

10、xt; else if(p-dataq-data) q=q-next; else u=p-data; while(r-next-datanext; if(r-next-data=u) s=r-next; while(s-data=u) t=s;s=s-next;free(t); /while r-next=s; /if while(p-data=u) p=p-next; while(q-data=u) q=q-next; 2021年年10月月17日日可以改进可以改进16 删除单循环链表中结点s的直接前驱（无头结点、头指针） Status Delete_Pre(CiLNode *s) p=s;

11、while(p-next-next!=s) p=p-next; p-next=s; return OK;2021年年10月月17日日17 完成双向循环链表结点的pre域(本来pre为NULL) Status DuLNode_Pre(DuLinkList &L) for(p=L;!p-next-pre;p=p-next) p-next-pre=p; return OK;2021年年10月月17日日18 把单链表L的元素按类型分为三个循环链表. Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C) s=L-next; A

12、=(CiList*)malloc(sizeof(CiLNode);p=A; B=(CiList*)malloc(sizeof(CiLNode);q=B; C=(CiList*)malloc(sizeof(CiLNode);r=C; while(s) if(isalphabet(s-data) p-next=s;p=s; else if(isdigit(s-data) q-next=s;q=s; else r-next=s;r=s; s=s-next; /while p-next=A;q-next=B;r-next=C; 2021年年10月月17日日19 按1,3,5,.4,2的顺序重排双向循环链表L中的所有结点(有头节点) void OEReform(DuLinkedList &L) p=L.next; while(p-next!=L&p-next-next!=L) p-next=p-next-next