数据结构作业系统-答案

◆2.11②设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：voidInsertOrderList(SqList&L,ElemTypex)/*在有序的顺序表L中保序插入数据元素x*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInsertOrderList(SqList&L,ElemTypex)//在有序的顺序表L中保序插入数据元素x{inti=0,j;while(L.elem[i]x&&iL.length)i++;for(j=L.length;ji;j--){L.elem[j]=L.elem[j-1];}L.elem[i]=x;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)，则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则AB；否则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比较）。要求实现下列函数：charCompare(SqListA,SqListB);/*比较顺序表A和B,*//*返回'',若AB;*//*'=',若A=B;*//*'',若AB*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;charCompare(SqListA,SqListB)//比较顺序表A和B,//返回'',若AB;//'=',若A=B;//'',若AB{inti=0;while(A.elem[i]==B.elem[i]&&iA.length&&iB.length)i++;if(i==A.length&&i==B.length)return'=';elseif(A.elem[i]B.elem[i]||i==A.length)return'';elseif(A.elem[i]B.elem[i]||i==B.length)return'';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkListLocate(LinkListL,ElemTypex);//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerhapointingnode'x',//otherwisereturn'NULL'{LinkListp;inti=0;p=L-next;while(p-data!=x&&p!=NULL){i++;p=p-next;}returnp;}2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数：intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{LinkListp;inti=0;p=L-next;while(p!=NULL){i++;p=p-next;}returni;}2.17②试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现下列函数：voidInsert(LinkList&L,inti,ElemTypeb);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInsert(LinkList&L,inti,ElemTypeb){LinkListp,q;intj=2;p=L;while(ji){j++;p=p-next;}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.18②同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。实现下列函数：voidDelete(LinkList&L,inti);单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidDelete(LinkList&L,inti){LinkListp,q;intj=2;p=L;while(ji&&p!=NULL){j++;p=p-next;}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题条件，试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)同时释放被删结点空间，并分析你的算法的时间复杂度。实现下列函数：voidPurge(LinkList&L);单链表类型定义如下：typedefstructLNode{ElemTypedata;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;}}◆2.21③试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。实现下列函数：voidInverse(SqList&L);顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInverse(SqList&L){inti=0,j=0;i=L.length/2;for(j=0;ji;j++){ElemTypee=L.elem[j];L.elem[j]=L.elem[L.length-j-1];L.elem[L.length-j-1]=e;}}◆2.22③试写一算法，对单链表实现就地逆置。实现下列函数：voidInverse(LinkList&L);/*对带头结点的单链表L实现就地逆置*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInverse(LinkList&L)/*对带头结点的单链表L实现就地逆置*/{LinkListp,q,k;q=p=L-next;while(p-next!=NULL){k=q;q=p-next;p-next=q-next;q-next=k;}L-next=q;}2.23③设线性表A=(a1,...,am),B=(b1,...,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1,b1,...,am,bm,bm+1,...,bn)当m≤n时；或者C=(a1,b1,...,an,bn,an+1,...,am)当m＞n时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。实现下列函数：voidMerge(LinkListha,LinkListhb,LinkList&hc)/*依题意，合并带头结点的单链表ha和hb为hc*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*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;else{while(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表*/单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidUnion(LinkList&lc,LinkListla,LinkListlb){LinkListpa=la-next;LinkListpb=lb-next;LinkListpre=NULL;LinkListq,pc;while(pa||pb){if((pa-datapb-data&&pa!=NULL)||pb==NULL){pc=pa;q=pa-next;pa-next=pre;pa=q;}else{pc=pb;q=pb-next;pb-next=pre;pb=q;}pre=pc;printf(%s,done);}lc=la;la-next=pc;//构造新表头/*LinkListpa=la-next;LinkListpb=lb-next;LinkListpc=la;lc=la;while(pa&&pb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-n