数据结构A习题课1.

习题课一1.5确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。习题一（第18页）(1)i=1;k=0;do{k=k+10*i;i++;}while(i=n-1)答：划线语句的执行次数为n-1。O(n)(2）i=1;x=0;ik(循环次数)2*ido1121n{2222nx++;i=2*i;2k-1n2kn}while（in）;2kn,klog2n,k=log2n划线语句的执行次数为log2n。O(log2n)(3)for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6。O(n3)niijjk1111(4）x=n;y=0;while(x=(y+1)*(y+1))y++;nk2划线语句的执行次数为。O()nn#includeiostream.h#includeseqlist0.h#includeconio.htemplateclassTvoidInterSection(SeqListT&LA,SeqListT&LB){intm=LB.Length();SeqListTLC(10);Tx;for(inti=1;i=m;i++){LB.Find(i,x);if(LA.Search(x))LC.Insert(LC.Length()+1,x);}coutLC;}2.1利用线性表类LinearList提供的操作，实现两个集合的交和差运算。习题二（第37页）templateclassTvoidDifference(SeqListT&LA,SeqListT&LB){intm=LA.Length();SeqListTLC(10);Tx;for(inti=1;i=m;i++){LA.Find(i,x);if(LB.Search(x)==0)LC.Insert(LC.Length()+1,x);}coutLC;}voidmain(){SeqListintLA(10),LB(10);for(inti=1;i=8;i++)LA.Insert(i,i);for(i=1;i=3;i++)LB.Insert(i,i+3);InterSection(LA,LB);Difference(LA,LB);}2.2(2)在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templateclassTvoidSeqListT::Invert(){Te;for(inti=0;ilength/2;i++){e=elements[i];elements[i]=elements[length-i-1];elements[length-i-1]=e;}}O(n)2.5在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。templateclassTvoidSingleListT::invert(){NodeT*p=first,*q;first=NULL;while(p){q=p-link;p-link=first;first=p;p=q;}}2.7单链表中结点按元素值递增链接，在类SingleList中增加一个成员函数，直接实现删除结点值在a至b之间的结点(ab)。templateclassTvoidSingleListT::DeleteAb(Ta,Tb){NodeT*p=first,*q=first;while(p&&p-datab)if(p-data=a){q=p;p=p-link;}else{q-link=p-link;deletep;p=q-link;}}思考结点a和b有没有删除掉？25791315firsta=5，b=132.8设有单循环链表类CircularList，要求在类CircularList中增加一个成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。//解法1templateclassTvoidMerge(CircularListT&a,CircularListT&b){NodeT*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;}//O(b.length)ab//解法2templateclassTvoidMerge1(CircularListT&a,CircularListT&b){NodeT*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;b.length=0;}//O(1)习题三（第50页）3.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先出栈。同理3）也不能。(1)能。push,pop,push,pop,push,pop,push,pop,push,pop(4)能。push,push,push,push,push,pop,pop,pop,pop,pop3.2设计共享栈。定义一个足够大的栈空间。该空间的两端分别设为两个栈的栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生溢出。栈空，两栈均空：top1=0且top2=n-1栈满：top1=top2-10n-1↑↑↑↑bottom1top1top2bottom23.4写出下列表达式的后缀形式。①/+ab+cd②-^b2**4ac③-*~ac/b^c2④+*+abc/d+ef⑤-*+ab+*cde*ac3.9利用栈可以检查表达式中括号是否配对，试编写算法实现之。//若不匹配，则返回true,否则返回false//解法一boolmatch(chara[],intn){SeqStackchars(n);charc;for(inti=0;in;i++)if(a[i]==‘(’)s.Push(a[i])//判栈满？elseif(a[i]==')')if(!s.Empty())s.Pop();//继续检查elsereturntrue;//不匹配if(!s.Empty())returntrue;//不匹配returnfalse;//匹配}//解法二不用栈，用一个字符数组boolmatch(chara[],intn){charc[n];inttop=-1;for(inti=0;in;i++)if(a[i]==‘(’){top++;s[top]=a[i];}elseif(a[i]==')')if(top-1){s[top]=0;top--;}//继续检查elsereturntrue;//不匹配if(top-1)returntrue;//不匹配returnfalse;//匹配}//解法三不用栈，也不用数组，只用一个计数器top,记录“(”的个数。boolmatch(chara[],intn){inttop=-1;for(inti=0;in;i++)if(a[i]=='(')top++;elseif(a[i]==')')if(top-1)top--;//继续检查elsereturntrue;//不匹配if(top-1)returntrue;//不匹配returnfalse;//匹配}3.10声明并实现链式栈类LinkedStack。templateclassTclassLinkedStack:publicStackT{public:LinkedStack();~LinkedStack();virtualboolIsEmpty()const;virtualboolIsFull()const;virtualboolGetTop(T&x);virtualboolPush(constTx);virtualboolPop();virtualvoidSetNull();private:NodeT*top;};//构造函数templateclassTLinkedStackT::LinkedStack(){top=NULL;}//析构函数templateclassTLinkedStackT::~LinkedStack(){NodeT*q;while(top){q=top-link;deletetop;top=q;}}templateclassTboolLinkedStackT::IsEmpty()const{return!top;}templateclassTboolLinkedStackT::IsFull()const{returnfalse;}templateclassTboolLinkedStackT::GetTop(T&x){if(IsEmpty()){coutEmptystackendl;returnfalse;}x=top-data;returntrue;}templateclassTboolLinkedStackT::Push(constTx){NodeT*q=newNodeT;q-data=x;q-link=top;top=q;returntrue;}templateclassTboolLinkedStackT::Pop(){NodeT*q=top;if(IsEmpty()){coutEmptystackendl;returnfalse;}top=top-link;deleteq;returntrue;}templateclassTvoidLinkedStackT::SetNull(){NodeT*q;while(top){q=top-link;deletetop;top=q;}}4.1给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。习题四（第68页）答：设有三维数组声明为A[n1][n2][n3]，每个元素占m个存储单元，则loc(A[i][j][k])=loc(A[0][0][0])+m*(i*n2*n3+j*n3+k)4.2设三对角矩阵Ann,将其3条对角线上元素按对角线存入二维数组B[3][n]中，使得B[u][v]=A[i][j]。求（1）用i,j表示u,v的下标变换公式；)1)(1()1(2322211211100100000...............00000...0nnnnaaaaaaaaaaa01a12a23a34…a00a11a22a33a44…a10a21a32a43…012012345…u=i-j+1v=j4.3设三对角矩阵Ann,将其3条对角线上元素存入大小为(3n-2)的一维数组B[]中，使得B[k]=A[i][j]。求（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式)3/)1((23/)1(kkjkik=2i+j)1)(1()1(23222