《数据结构作业系统答案》由会员分享，可在线阅读，更多相关《数据结构作业系统答案（33页珍藏版）》请在金锄头文库上搜索。
1、2.11设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：voidInsertOrderList(SqList&L,ElemTypex)/*在有序的顺序表L中保序插入数据元素x*/顺序表类型定义如下：typedefstructElemType*elem;intlength;intlistsize;SqList;voidInsertOrderList(SqList&L,ElemTypex)/在有序的顺序表L中保序插入数据元素xinti=0,j;while(L.elemixⅈj-)L.elemj=L.elemj-1;L.elemi=x
2、;L.length+=1;2.12设A=(a1,am)和B=(b1,bn)均为有序顺序表，A和B分别为A和B中除去最大共同前缀后的子表(例如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),贝V两者中最大的共同前缀为(x,y,y,z),在两表中除去最大共同前缀后的子表分别为A=(x,z)和B=(y,x,x,z)。若A=B=空表，则A=B；若A=空表，而BM空表，或者两者均不为空表，且A的首元小于B的首元，则AvB；否则AB。试写一个比较A和B大小的算法。(注意：在算法中，不要破坏原表A和B，也不一定先求得A和B才进行比较)要求实现下列函数：charCompare(SqL
3、istA,SqListB);/*比较顺序表A和B,*/*返回,若A,若AB*/顺序表类型定义如下：typedefstructElemType*elem;intlength;intlistsize;SqList;charCompare(SqListA,SqListB)/比较顺序表A和B,/返回,若A,若ABinti=0;while(A.elemi=B.elemi&iA.length&iB.length)i+;if(i=A.length&i=B.length)return=;elseif(A.elemiB.elemi|i=A.length)returnB.elemi|i=B.length)retu
4、rn;2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkListLocate(LinkListL,ElemTypex);/Ifxinthelinkedlistwhoseheadnodeispointed/byL,thenreturnpointerpointingnodex,/otherwisereturnNULL单链表类型定义如下：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)/Ifxint
5、helinkedlistwhoseheadnodeispointed/byL,thenreturnpointerhapointingnodex,/otherwisereturnNULLLinkListp;inti=0;p=L-next;while(p-data!=x&p!=NULL)i+;p=p-next;returnp;2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数：intLength(LinkListL);/Returnthelengthofthelinkedlist/whoseheadnodeispointedbyL单链表类型定义如下：typed
6、efstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;intLength(LinkListL)/Returnthelengthofthelinkedlist/whoseheadnodeispointedbyLLinkListp;inti=0;p=L-next;while(p!=NULL)i+;p=p-next;returni;2.17试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现下列函数：voidInsert(LinkList&L,inti
7、,ElemTypeb);单链表类型定义如下typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;voidInsert(LinkList&L,inti,ElemTypeb)LinkListp,q;intj=2;p=L;while(jnext;if(i!=0&i!=1)q=(LinkList)malloc(sizeof(LNode);q-data=b;q-next=p-next;p-next=q;if(i=1)q=(LinkList)malloc(sizeof(LNode);q-data=b;q-next=p;L=q;2.1
8、8同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。实现下列函数：voidDelete(LinkList&L,inti);单链表类型定义如下：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;voidDelete(LinkList&L,inti)LinkListp,q;intj=2;p=L;while(jnext;if(i!=0&i!=1)q=p-next;p-next=q-next;free(q);if(i=1)q=L;L=L-next;free(q);2.20同2.19题条件，试写一高效的算法，
9、删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)同时释放被删结点空间，并分析你的算法的时间复杂度。实现下列函数：voidPurge(LinkList&L);单链表类型定义如下：typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;voidPurge(LinkList&L)LinkListp,q;inti=0;p=L;while(p!=NULL&p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);elsep=p-next
10、;2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,al)。实现下列函数：voidInverse(SqList&L);顺序表类型定义如下：typedefstructElemType*elem;intlength;intlistsize;SqList;voidInverse(SqList&L)inti=0,j=0;i=L.length/2;for(j=0;jnext;while(p-next!=NULL)k=q;q=p-next;p-next=q-next;q-next=k;L-next=q;2.23设线性表A=(al,.,am),
11、B=(bl,.,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1,b1,.,am,bm,bm+1,.,bn)当mWn时；或者C=(a1,b1,.,an,bn,an+1,.,am)当mn时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。实现下列函数：voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依题意，合并带头结点的单链表ha和hb为hc*/单链表类型定义如下：typedefstructLNodeElemTypedata;structLNode*next;LN
12、ode,*LinkList;voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依题意，合并带头结点的单链表ha和hb为hc*/LinkListp,q,k,r;p=ha-next;q=hb-next;if(p=NULL)hc=hb;elseif(q=NULL)hc=ha;elsewhile(p-next!=NULL&q-next!=NULL)k=p-next;r=q-next;p-next=q;p=k;q-next=p;q=r;if(p-next!=NULL)q-next=p-next;p-next=q;hc=ha;2.24假设有两个按元素值递增有序排列的线性表A和B均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。实现下列函数：voidUnion(LinkList&lc,LinkListla,LinkListlb);/*依题意，利用la和lb原表的结点空间构造lc表*/单链表类型定义如下：typedefstructLNodeElemTypedata;struct
