欢迎来到天天文库
浏览记录
ID:48758269
大小:78.00 KB
页数:11页
时间:2020-01-22
《第二章线性表作业参考答案.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第二章线性表作业参考答案作业1.1用顺序表表示集合,设计一个算法实现集合的求差集运算,即C=A-B。算法分析:C中元素为A中所有不属于B的元素。扫描A中元素,若它与B中所有元素均不相同,表示是差集元素,将其放到C中。typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;Voiddiffence(SqlistA,SqlistB,SqlistC){inti,j,k=0;for(i=0;i2、&B.elem[j]!=A.elem[i])j++;if(j==B.length)//表示A.elem[i]不在B中,将其放到C中C.elem[k++]=A.elem[i];}C.length=k;}作业1.2试写一个算法,实现顺序表的就地逆置。typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;算法:statusReverse(SqList&L){//对顺序表实现就地逆序n=L.lengthfor(i=0;i3、[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;}returnOK;}//Reverse作业2.1已知线性表中的数据元素以值递增有序排列,并以单链表作存储结构,试写一个高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结点空间typedefstructLnode{elemtypedata;//数据域structLnode*next;//指针域}Lnode,*linklist;StatusDELmink_maxk(LinkLlist&L,ElemTypemink,Elem4、Typemaxk){p=L->next;q=L;//p指向当前链结点,q指向前一个链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->datanext;}if(!p)retutnERROR;//找不到指定范围的数据elsewhile(p->data<=maxk&&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后,重新建立链接}//DELmink_maxk作业2.2设线性表A=(a1,a2,…,an),B=(b1,b2,…,bm5、),试写一个按下列规则合并A、B为线性表C的算法,即使得C=(a1,b1,a2,b2,…,am,bm,bm+1,…,bn)当m<=n或C=(a1,b1,a2,b2,…,an,bn,an+1,…,am)当m>n线性表A、B和C均为单链表作存储结构,且C表利用A表和B表中的结点空间构表。注意:单链表的长度值m和n均未显式存储。算法:statusCOMBINE(linklistA,linklistB,linklist&C){C=A;a=A->next;b=B->next;If(a==NULL){A->next=B;ReturnOk;}do{p=a->next;q=b->6、next;a->next=b;b->next=p;a=p;b=q;}while(p->next&&q);if(p->next==NULL)a->next=b;}//COMBINE作业3.1假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。算法思路:首先找到s所指链结点的直接前驱结点(即将被删除的链结点,算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址),然后做删除操作。算法:StatusDelS(Linklist&s){r=s;q=s->next/7、/q指向s的下一个结点while(q->next!=s){r=q;q=q->next;}r->next=s;free(q);}//DelS
2、&B.elem[j]!=A.elem[i])j++;if(j==B.length)//表示A.elem[i]不在B中,将其放到C中C.elem[k++]=A.elem[i];}C.length=k;}作业1.2试写一个算法,实现顺序表的就地逆置。typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;算法:statusReverse(SqList&L){//对顺序表实现就地逆序n=L.lengthfor(i=0;i3、[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;}returnOK;}//Reverse作业2.1已知线性表中的数据元素以值递增有序排列,并以单链表作存储结构,试写一个高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结点空间typedefstructLnode{elemtypedata;//数据域structLnode*next;//指针域}Lnode,*linklist;StatusDELmink_maxk(LinkLlist&L,ElemTypemink,Elem4、Typemaxk){p=L->next;q=L;//p指向当前链结点,q指向前一个链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->datanext;}if(!p)retutnERROR;//找不到指定范围的数据elsewhile(p->data<=maxk&&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后,重新建立链接}//DELmink_maxk作业2.2设线性表A=(a1,a2,…,an),B=(b1,b2,…,bm5、),试写一个按下列规则合并A、B为线性表C的算法,即使得C=(a1,b1,a2,b2,…,am,bm,bm+1,…,bn)当m<=n或C=(a1,b1,a2,b2,…,an,bn,an+1,…,am)当m>n线性表A、B和C均为单链表作存储结构,且C表利用A表和B表中的结点空间构表。注意:单链表的长度值m和n均未显式存储。算法:statusCOMBINE(linklistA,linklistB,linklist&C){C=A;a=A->next;b=B->next;If(a==NULL){A->next=B;ReturnOk;}do{p=a->next;q=b->6、next;a->next=b;b->next=p;a=p;b=q;}while(p->next&&q);if(p->next==NULL)a->next=b;}//COMBINE作业3.1假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。算法思路:首先找到s所指链结点的直接前驱结点(即将被删除的链结点,算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址),然后做删除操作。算法:StatusDelS(Linklist&s){r=s;q=s->next/7、/q指向s的下一个结点while(q->next!=s){r=q;q=q->next;}r->next=s;free(q);}//DelS
3、[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;}returnOK;}//Reverse作业2.1已知线性表中的数据元素以值递增有序排列,并以单链表作存储结构,试写一个高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结点空间typedefstructLnode{elemtypedata;//数据域structLnode*next;//指针域}Lnode,*linklist;StatusDELmink_maxk(LinkLlist&L,ElemTypemink,Elem
4、Typemaxk){p=L->next;q=L;//p指向当前链结点,q指向前一个链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->datanext;}if(!p)retutnERROR;//找不到指定范围的数据elsewhile(p->data<=maxk&&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后,重新建立链接}//DELmink_maxk作业2.2设线性表A=(a1,a2,…,an),B=(b1,b2,…,bm
5、),试写一个按下列规则合并A、B为线性表C的算法,即使得C=(a1,b1,a2,b2,…,am,bm,bm+1,…,bn)当m<=n或C=(a1,b1,a2,b2,…,an,bn,an+1,…,am)当m>n线性表A、B和C均为单链表作存储结构,且C表利用A表和B表中的结点空间构表。注意:单链表的长度值m和n均未显式存储。算法:statusCOMBINE(linklistA,linklistB,linklist&C){C=A;a=A->next;b=B->next;If(a==NULL){A->next=B;ReturnOk;}do{p=a->next;q=b->
6、next;a->next=b;b->next=p;a=p;b=q;}while(p->next&&q);if(p->next==NULL)a->next=b;}//COMBINE作业3.1假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。算法思路:首先找到s所指链结点的直接前驱结点(即将被删除的链结点,算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址),然后做删除操作。算法:StatusDelS(Linklist&s){r=s;q=s->next/
7、/q指向s的下一个结点while(q->next!=s){r=q;q=q->next;}r->next=s;free(q);}//DelS
此文档下载收益归作者所有