数据结构作业系统-答案

《数据结构作业系统-答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、◆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]

2、)i++;for(j=L.length;j>i;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'的首

3、元小于B'的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比较）。要求实现下列函数：charCompare(SqListA,SqListB);/*比较顺序表A和B,*//*返回'<',若A',若A>B*/顺序表类型定义如下：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;charCompare(SqListA,SqListB)//比较顺序表A和B,//返回'<',若A

4、=',若A=B;//'>',若A>B{inti=0;while(A.elem[i]==B.elem[i]&&i

5、

6、i==A.length)return'<';elseif(A.elem[i]>B.elem[i]

7、

8、i==B.length)return'>';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkListLocate(Link

9、ListL,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

10、',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'单链表类型定义如下：typedefstr

11、uctLNode{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)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现