数据结构用c++语言描述习题答案01

《数据结构用c++语言描述习题答案01》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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（i=(y+

2、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]=e;}}2．第37页习题(5)在类SingleLis

3、t中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。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)。templatevoidSingleList::DeleteAb(Ta,Tb

4、)//第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中增加一个成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。templatevoidMerge(

5、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(CircularList&a,CircularList&b){Node*p=b.first->link;b.first->data=b.firs

6、t->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,D3)C,A,B,D,E4)E,D,C,B,A答：2）和3）不能。对2）中的E，B，D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。

7、同理3）。2.第50页习题（9）利用栈可以检查表达式中括号是否配对，试编写算法实现之。boolmatch(chara[],intn){inttop=-1;for(inti=0;i-1)top--;elsereturntrue;if(top>-1)returntrue;returnfalse;}3.第50页习题(10)声明并实现链式队列类LinkedQueue。templateclassLinkedStack:publicStack{p

8、ublic:LinkedStack();~LinkedStack();virtu