欢迎来到天天文库
浏览记录
ID:16287645
大小:54.50 KB
页数:8页
时间:2018-08-09
《《数据结构题集》参考答案2 线性表》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第二章线性表◆2.11②设顺序表L中的数据元素递增有序。试写一算法,将x插入到L的适当位置上,并保持该表的有序性。要求实现下列函数:voidInsertOrderList(SqList&L,ElemTypex)/*在有序的顺序表L中保序插入数据元素x*/顺序表类型定义如下:typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInsertOrderList(SqList&L,ElemTypex)//在有序的顺序表L中保序插入数据元素x{intj,i=L.length-1;while(x2、&i>=0)i--;for(j=L.length-1;j>i;j--){L.elem[j+1]=L.elem[j];}L.elem[i+1]=x;L.length++;}◆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'≠空表,或者两者均不为空表,且3、A'的首元小于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,//返回'<',若A4、=',若A=B;//'>',若A>B{inti=0,j=0;while(i5、6、j';}else{i++;j++;}}if(i==j)return'=';elseif(i==A.length)return'<';elsereturn'>';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数:LinkListLocate(LinkListL,ElemType7、x);//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointe8、rhapointingnode'x',//otherwisereturn'NULL'{LinkListP;P=L->next;while(P!=NULL&&P->data!=x){P=P->next;}returnP;}2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数:intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode9、*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{inti=0;LinkListP;P=L->next;while(P!=NULL){P=P->next;i++;}returni;}2.16③已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第i个元素之前。试问此
2、&i>=0)i--;for(j=L.length-1;j>i;j--){L.elem[j+1]=L.elem[j];}L.elem[i+1]=x;L.length++;}◆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'≠空表,或者两者均不为空表,且
3、A'的首元小于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,j=0;while(i5、6、j';}else{i++;j++;}}if(i==j)return'=';elseif(i==A.length)return'<';elsereturn'>';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数:LinkListLocate(LinkListL,ElemType7、x);//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointe8、rhapointingnode'x',//otherwisereturn'NULL'{LinkListP;P=L->next;while(P!=NULL&&P->data!=x){P=P->next;}returnP;}2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数:intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode9、*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{inti=0;LinkListP;P=L->next;while(P!=NULL){P=P->next;i++;}returni;}2.16③已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第i个元素之前。试问此
5、
6、j';}else{i++;j++;}}if(i==j)return'=';elseif(i==A.length)return'<';elsereturn'>';}2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数:LinkListLocate(LinkListL,ElemType
7、x);//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListLocate(LinkList&L,ElemTypex)//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointe
8、rhapointingnode'x',//otherwisereturn'NULL'{LinkListP;P=L->next;while(P!=NULL&&P->data!=x){P=P->next;}returnP;}2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数:intLength(LinkListL);//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'单链表类型定义如下:typedefstructLNode{ElemTypedata;structLNode
9、*next;}LNode,*LinkList;intLength(LinkListL)//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{inti=0;LinkListP;P=L->next;while(P!=NULL){P=P->next;i++;}returni;}2.16③已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第i个元素之前。试问此
此文档下载收益归作者所有