欢迎来到天天文库
浏览记录
ID:1299560
大小:3.87 MB
页数:21页
时间:2017-11-09
《数据结构(陈惠南主编第二版)习题答案1-9章 【全】》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第一章绪论1.(第18页,第(5)题)确定下列各程序段的程序步,确定划线语句的执行次数,计算它们的渐近时间复杂度。(1)i=1;k=0;do{k=k+10*i;i++;}while(i<=n-1)划线语句的执行次数为n-1。(2)i=1;x=0;do{x++;i=2*i;}while(i2、0;while(x>=(y+1)*(y+1))y++;划线语句的执行次数为ëÖnû。第二章线性表1.第37页习题(2).2在类LinearList中增加一个成员函数,将顺序表逆置,实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templatevoidSeqList::Invert(){Te;for(inti=1;i<=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i3、]=e;}}2.第37页习题(5)在类SingleList中增加一个成员函数,将单链表逆置运算,直接实现该函数并分析其时间复杂度。templatevoidSingleList::invert(){Node*p=first,*q;first=NULL;while(p){q=p->link;p->link=first;first=p;p=q;}}3.(第37页,第7题)单链表中结点按元素值递增链接,在类SingleList中增加一个成员函数,直接实现删除结点值在a至b之间的结点(a£b)。templat4、evoidSingleList::DeleteAb(Ta,Tb)//第37页,习题(7){Node*p=first,*q=first;while(p&&p->datadata<=a){q=p;p=p->link;}elseif(q==first){q=p->link;deletep;p=first=q;}else{q->link=p->link;deletep;p=q->link;}}}4.(第37页,第8题)在类CircularList中增加一个成员函数,在不增加新结点的情况下5、,直接实现两个链表合并为一个链表的算法,并分析其时间复杂度。templatevoidMerge(CircularList&a,CircularList&b){Node*p=b.first;while(p->link!=b.first)p=p->link;p->link=a.first->link;a.first->link=b.first->link;b.first->link=b.first;b.length=0;}templatevoidMerge1(CircularLis6、t&a,CircularList&b){Node*p=b.first->link;b.first->data=b.first->link->data;b.first->link=a.first->link;a.first->link=p->link;p->link=p;b.first=p;}第一章栈与队列1.第50页习题(1)设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。1)A,B,C,D,E2)A,C,E,B,D7、3)C,A,B,D,E4)E,D,C,B,A答:2)和3)不能。对2)中的E,B,D而言,E最先出栈,则表明,此时B和D均在栈中,由于,B先于D进栈,所以应有D先出栈。同理3)。2.第50页习题(9)利用栈可以检查表达式中括号是否配对,试编写算法实现之。boolmatch(chara[],intn){inttop=-1;for(inti=0;i-1)top--;elsereturntrue;if(top>-1)returntru8、e;returnfalse;}3.第50页习题(10)声明并实现链式队列类LinkedQueue。templateclassLinkedStack:publicStack{public:LinkedStack();~LinkedStack();virtu
2、0;while(x>=(y+1)*(y+1))y++;划线语句的执行次数为ëÖnû。第二章线性表1.第37页习题(2).2在类LinearList中增加一个成员函数,将顺序表逆置,实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templatevoidSeqList::Invert(){Te;for(inti=1;i<=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i
3、]=e;}}2.第37页习题(5)在类SingleList中增加一个成员函数,将单链表逆置运算,直接实现该函数并分析其时间复杂度。templatevoidSingleList::invert(){Node*p=first,*q;first=NULL;while(p){q=p->link;p->link=first;first=p;p=q;}}3.(第37页,第7题)单链表中结点按元素值递增链接,在类SingleList中增加一个成员函数,直接实现删除结点值在a至b之间的结点(a£b)。templat
4、evoidSingleList::DeleteAb(Ta,Tb)//第37页,习题(7){Node*p=first,*q=first;while(p&&p->datadata<=a){q=p;p=p->link;}elseif(q==first){q=p->link;deletep;p=first=q;}else{q->link=p->link;deletep;p=q->link;}}}4.(第37页,第8题)在类CircularList中增加一个成员函数,在不增加新结点的情况下
5、,直接实现两个链表合并为一个链表的算法,并分析其时间复杂度。templatevoidMerge(CircularList&a,CircularList&b){Node*p=b.first;while(p->link!=b.first)p=p->link;p->link=a.first->link;a.first->link=b.first->link;b.first->link=b.first;b.length=0;}templatevoidMerge1(CircularLis
6、t&a,CircularList&b){Node*p=b.first->link;b.first->data=b.first->link->data;b.first->link=a.first->link;a.first->link=p->link;p->link=p;b.first=p;}第一章栈与队列1.第50页习题(1)设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。1)A,B,C,D,E2)A,C,E,B,D
7、3)C,A,B,D,E4)E,D,C,B,A答:2)和3)不能。对2)中的E,B,D而言,E最先出栈,则表明,此时B和D均在栈中,由于,B先于D进栈,所以应有D先出栈。同理3)。2.第50页习题(9)利用栈可以检查表达式中括号是否配对,试编写算法实现之。boolmatch(chara[],intn){inttop=-1;for(inti=0;i-1)top--;elsereturntrue;if(top>-1)returntru
8、e;returnfalse;}3.第50页习题(10)声明并实现链式队列类LinkedQueue。templateclassLinkedStack:publicStack{public:LinkedStack();~LinkedStack();virtu
此文档下载收益归作者所有