南邮数据结构A习题2参考答案

部分答案(2).2在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templateclassTvoidSeqListT::Invert(){Te;for(inti=1;i=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2.3templateclassTboolSeqListT::Insert2(inti,Tx){if(i-1||in-1){coutOutofboundsendl;returnfalse;}if(n==maxLength){T*elem=newT[2*maxLength];maxLength=maxLength*2;for(intj=0;j=i;j++)elem[j]=elements[j];elem[i+1]=x;for(j=i+1;jn;j++)elem[j+1]=elements[j];n++;delete[]elements;elements=elem;returntrue;}for(intj=n-1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}算法的时间复杂度为O(n)2.4templateclassTboolSeqListT::Del(Tx){if(!n){coutUnderFlowendl;returnfalse;}for(inti=0;in;i++){if(elements[i]==x){for(intj=i+1;jn;j++)elements[j-1]=elements[j];n--;returntrue;}}returnfalse;}算法的时间复杂度为O(n)2.6templateclassTvoidSingleListT::Invert(){NodeT*p=first,*q;first=NULL;while(p){q=p-link;p-link=first;first=p;p=q;}}算法的时间复杂度为O(n)2.7templateclassTboolSingleListT::Del(constT&x){if(!n){coutUnderFlow!!!endl;returnfalse;}NodeT*p=first,*q;if((first-data)==x){first=first-link;deletep;n--;returntrue;}while(p&&p-data!=x){q=p;p=p-link;}if(p){q-link=p-link;delete(p);n--;returntrue;}returnfalse;}算法的时间复杂度为O(n)