數(shù)據(jù)結(jié)構(gòu)實用教程第二版答案-徐孝凱

第一章緒習(xí)題一1.有以下幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對應(yīng)的圖形表示〔當出現(xiàn)多個關(guān)系時，對每個關(guān)系畫出相應(yīng)的結(jié)構(gòu)圖〕，并指出它們分別屬于何種結(jié)構(gòu)。⑴A=(K,R)其中K={a1,a2,a3...,an}R={}⑵B=(K,R)其中K={a,b,c,d,e,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}⑶C=(K,R)其中K={a,b,c,d,f,g,h}R={r}r={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}⑷D=(K,R)其中K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}⑸E=(K,R)其中K={48,25,64,57,82,36,75,43}R={r1,r2,r3}r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>}解：⑴是集合結(jié)構(gòu)；⑵是線性結(jié)構(gòu)；⑶⑷是樹型結(jié)構(gòu)；⑸散列結(jié)構(gòu)。只作為參考。2.設(shè)計二次多項式ax2+bx+c的一種抽象數(shù)據(jù)類型，假定起名為QIAdratic,該類型的數(shù)據(jù)局部分為三個系數(shù)項a、b和c，操作局部為：(請寫出下面每一個操作的具體實現(xiàn))。⑴初始化數(shù)據(jù)成員ab和c(假定用記錄類型Quadratie定義成員)，每個數(shù)據(jù)成員的默認值為0。QuadraticInitQuadratic(floataa=0,floatbb=0,floatcc=0);解：QuadraticInitQuadratic(floataa,floatbb,floatcc){Quadraticq;q.a=aa;q.b=bb;q.c=cc;returnq;}⑵做兩個多項式加法,即使對應(yīng)的系數(shù)相加,并返回相加的結(jié)果。QuadraticAdd(Quadraticq1,Quadraticq2);解：QuadraticAdd(Quadraticq1,Quadraticq2);{Quadraticq;q.a=q1.a+q2.a;q.b=q1.b+q2.b;q.c=q1.c+q2.c;returnq;}⑶根據(jù)給定x的值計算多項式的值。floatEval(Quadraticq,floatx);解：floatEval(Quadraticq,floatx){return(q.a*x*x+q.b*x+q.c);}⑷計算方程ax2+bx+c=0的兩個實數(shù)根，對于有實根、無實根和不是實根方程(即a==0)這三種情況要返回不同的整數(shù)值，以便于工作調(diào)用函數(shù)做不同的處理。intRoot(Quadraticq,float&r1,float&r2);解：intRoot(Quadraticq,float&r1,float&r2){if(q.a==0)return-1;floatx=q.b*q.b-4*q.a*q.c;if(x>=0){r1=(float)(-q.b+sqrt(x))/(2*q.a);r2=(float)(-q.b-sqrt(x))/(2*q.a);return1;}elsereturn0;}⑸按照ax**2+bx+c的格式(x2用x**2表示)輸出二次多項式，在輸出時要注意去掉系數(shù)為0的項，并且當b和c的值為負時，其前不能出現(xiàn)加號。voidPrint(Quadraticq)解：voidPrint(Quadraticq){if(q.a)cout<<q.a<<"x**2";if(q.b)if(q.b>0)cout<<"+"<<q.b<<"x";elsecout<<q.b<<"x";if(q.c)if(q.c>0)cout<<"+"<<q.c;elsecout<<q.c;cout<<end1;}3.用c++函數(shù)描述以下每一個算法，并分別求出它們的時間復(fù)雜度。⑴比擬同一簡單類型的兩個數(shù)據(jù)x1和x2的大小，對于x1>x2,x1=x2和x1<x2這三種不同情況分別返回'>''='和'<'字符。假定簡單類型用SimpleType表示，它可通過typedef語句定義為任一簡單類型。解：charcompare(SimpleTypex1,SimpleTypex2){if(x1>x2)return'>';elseif(x1==x2)return'=';elsereturn'<';}其時間復(fù)雜度為O(1)⑵將一個字符串中的所有字符按相反方的次序重新放置。解：voidReverse(char*p){intn=strlen(p);for(inti=0;i<n/2;i++){charch;ch=p[i]p[i]=p[n-i-1];p[n-i-1]=ch;}}其時間復(fù)雜度為O(n)⑶求一維double型數(shù)組a[n]中的所有元素之乘積。解：doubleproduct(doublea[],intn){doublep=1;for(inti=0;i<n;i++)p*=a[i];returnp;}其時間復(fù)雜度為O(n)⑷計算Σni=0xi/i+1的值。解：doubleAccumulate(doublex,intn){doublep=1,s=1;for(inti=1;i<=n;i++){p*=x;s+=p/(i+1);}returns;}其時間復(fù)雜度為O(n)⑸假定一維數(shù)組a[n]中的每個元素值均在[0，200]區(qū)間內(nèi)，分別統(tǒng)計出落在[0，20),[20,50),[50,80),[80,130),[130,200]等各區(qū)間的元素個數(shù)。解：intCount(inta[],intn,intc[5])//用數(shù)組c[5]保存統(tǒng)計結(jié)果{intd[5]={20,50,80,130,201};//用來保存各統(tǒng)計區(qū)間的上限inti,j;for(i=0;i<5;i++)c[i]=0;//給數(shù)組c[5]中的每個元素賦初值0for(i=0;i<n;i++){if(a[i]<0||a[i]>200)return0;//返回數(shù)值0表示數(shù)組中數(shù)據(jù)有錯，統(tǒng)計失敗for(j=0;j<5;j++)//查找a[i]所在區(qū)間if(a[i]<d[j])break;c[j]++;//使統(tǒng)計相應(yīng)區(qū)間的元素增1}return1;//返回數(shù)值1表示統(tǒng)計成功}其時間復(fù)雜度為O(n)⑹從二維整型數(shù)組a[m][n]中查找出最大元素所在的行、列下標。解：voidfind(inta[M][N],intm,intn,int&Lin,int&Col)//M和N為全局常量，應(yīng)滿足M>=n和N>=n的條件，Lin和Col為引用//形參，它是對應(yīng)實參的別名，其值由實參帶回{Lin=0;Col=0;for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(a[i][j]>a[Lin][Col]){Lin=i;Col=j;}}其時間復(fù)雜度為O(m*n)4.指出以下各算法的功能并求出其時間復(fù)雜度。⑴intprime(intn){inti=2;intx=(int)sqrt(n);while(i<=x){if(n%i==0)break;i++;}if(i>x)return1;elsereturn0;}解：判斷n是否是一個素數(shù)，假設(shè)是那么返回數(shù)值1，否那么返回0。該算法的時間復(fù)雜度為O(n1/2)。⑵intsum1(intn){intp=1,s=0;for(inti=1;i<=n;i++){p*=i;s+=p;}returns;}解：計算Σi!(上標為n，下標為i=1)的值，其時間的復(fù)雜度為O(n)。⑶intsum2(intn){ints=0;for(inti=1;i<=n;i++){intp=1;for(intj=1;j<=i;j++)p*=j;s+=p;}returns;}解：計算Σi!的值，時間復(fù)雜度為O(n2)⑷intfun(intn){inti=1,s=1;while(s<n)s+=++i;returni;}解：求出滿足不等式1+2+3...+i≥n的最小i值，其時間復(fù)雜度為O(n1/2)。⑸voidUseFile(ifstream&inp,intc[10])//假定inp所對應(yīng)的文件中保存有n個整數(shù){for(inti=0;i<10;i++)c[i]=0;intx;while(inp>>x){i=x%10;c[i]++;}}解：利用數(shù)組c[10]中的每個元素c[i]對應(yīng)統(tǒng)計出inp所聯(lián)系的整數(shù)文件中個位值同為i的整數(shù)個數(shù)，時間復(fù)雜度為O(n)⑹voidmtable(intn){for(inti=1;i<=n;i++){for(intj=i;j<=n;j++)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j<<"";cout<<end1;}}解：打印出一個具有n行的乘法表，第i行(1≤i≤n)中有n-i+1個乘法項，每個乘法項為i與j(i≤j≤n)的乘積，時間復(fù)雜度為O(n2)。⑺voidcmatrix(inta[M][N],intd)//M和N為全局整型常量{for(inti=0;i<M;i++)for(intj=0;j<N;j++)a[i][j]*=d;}解：使數(shù)組a[M][N]中的每一個元素均詳細以d的值，時間復(fù)雜度為O(M*N)⑻voidmatrimult(inta[M][N],intb[N][L],intc[M][L])//{inti,j,k;for(i=0;i<M;i++)for(j=0;j<L;j++)c[i][j]=0;for(i=0;i<M;i++)for(j=0;j<L;j++)for(k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];}解：矩陣相乘，即a[M][N]×b[N][L]→c[M][L]，時間復(fù)雜度為O(M×N×L)。5.題目略⑴解：voidInitSet(Set&s){for(inti=1;i<=SETSIZE;i++)s.m[i]=0;}⑵解：voidInitSet(Set&s,inta[],intn){fot(inti=0;i<n;i++)s.m[a[i]]=1;}⑶解：Setoperator+(Sets1,Sets2){Sets;InitSet(s);for(inti=1;i<=SETSIZE;i++)if((s1.m[i]==1)||s2.m[i]===1))s.m[i]=1;returns;}⑷解：Setoperator*(Sets1,Sets2){Sets;InitSet(s);for(inti=1;i<=SETSIZE;i++)if((s1.m[i]==1)&&(s2.m[i]==1))s.m[i]=1;returns;⑸解：Booleanoperator＾(intelt,Sets){if(s.m[elt]==1)returnTrue;elsereturnFalse;}⑹解：voidInisert(Set&s,intn){s.m[n]=1;}⑺解：voidDelete(Set&s,intn){s.m[n]=0;}⑻解：ostream&operator<<(ostream&ostr,Set&s){ostr<<'{'for(inti=1;i<=SETSIZE;i++)if(s.m[i]==1)ostr<<i<<',';ostr<<'}'<<end1;returnostr;}第二章線性表習(xí)題二1.⑴解：(79,62,34,57,26,48)⑵解：(26,34,48,57,62,79)⑶解：(48,56,57,62,79,34)⑷解：(56,57,79,34)⑸解：(26,34,39,48,57,62)2.解：為了排版方便，假定采用以下輸出格式表示單鏈接表的示意圖；每個括號內(nèi)的數(shù)據(jù)表示一個元素結(jié)點，其中第一個數(shù)據(jù)為元素值，第二個數(shù)據(jù)為后繼結(jié)點的指針，第一個元素結(jié)點前的數(shù)值為表頭指針。⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0))⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0))⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0))⒋(8(56,4),(57,7),(79,5),(34,0))3.對于List類型的線性表,編寫出以下每個算法。⑴從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，假設(shè)線性表為空那么顯示出錯信息并退出運行。解：ElemTypeDMValue(List&L)//從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置//由最后一個元素填補,假設(shè)線性表為空那么顯示出錯信息并退出運行{if(ListEmpty(L)){cerr<<"ListisEmpty!"<<end1;exit(1);}ElemTypex;x=L.list[0];intk=0;for(inti=1;i<L.size;i++){ElemTypey=L.list[i];if(y<x){x=y;k=i;}}L.list[k]=L.list[L.size-1];L.size--;returnx;}⑵從線性表中刪除第i個元素并由函數(shù)返回。解：intDeletel(List&L,inti)//從線性表中刪除第i個元素并由函數(shù)返回{if(i<1||i>L.size){cerr<<"Indexisoutrange!"<<end1;exit(1);}ElemTypex;x=L.list[i-1];for(intj=i-1;j<L.size-1;j++)L.list[j]=L.list[j+1];L.size--;returnx;}⑶向線性表中第i個元素位置插入一個元素。解：voidInser1(List&L,inti,ElemTypex)//向線性表中第i個元素位置插入一個元素{if(i<1||i>L.size+1){cerr<<"Indexisoutrange!"<<end1;exit(1);}if(L.size==MaxSize){cerr<<"Listoverflow!"<<end1;exit(1);}for(intj=L.size-1;j>i-1;j--)L.list[j+1]=L.list[j];L.list[i-1]=x;L.size++;}⑷從線性表中刪除具有給定值x的所有元素。解：voidDelete2(List&L,ElemTypex)//從線性表中刪除具有給定值x的所有元素{inti=0;while(i<L.size)if(L.list[i]==x){for(intj=i+1;j<L.sizr;j++)L.list[j-1]=L.list[j];L.size--;}elsei++;}⑸從線性表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：voidDelete3(List&L,ElemTypes,ElemTypet)//從線性表中刪除其值在給定值s和t之間的所有元素{inti=0;while(i<L.size)if((L.list[i]>=s)&&(L.list[i]<=t)){for(intj=i+1;j<L.size;j++)L.list[j-i]=L.list[j];L.size--;}elsei++;}⑹從有序表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。解：voidDelete4(List&L,ElemTypes,ElemTypet)//從有序表中刪除其值在給定值s和t之間的所有元素{inti=0;while(i<L.size)//從有序表L中查找出大于等于s的第一個元素if(L.list[i]<s)i++;elsebreak;if(i<L.size){While((i+j<L.size)&&(L.list[i+j]<=t))j++;//求出s和t之間元素的個數(shù)for(intk=i+j;k<L.size;k++)L.list[k-j]=L.list[k];L.size-=j;}}⑺將兩個有序表合并成一個新的有序表并由變量返回。解：voidMerge(List&L1,List&L2,List&L3)//將兩個有序表合并成一個新的有序表并由變量返回{if(L1.size+L2.size>MaxSize){cerr<<"Listoverflow!"<<end1;exit(1);}inti=0,j=0,k=0;while((i<L1.size)&&(j<L2.size)){if(L1.list[i]<=L2.list[j]){//將L1中的元素賦給LL.list[k]=L1.list[i];i++;}else{//將L2中的元素賦給LL.list[k]=L2.list[j];j++;}k++;}while(i<L1.size){//將L1中剩余的元素賦給LL.list[k]=L1.list[i];i++;k++;}while(j<L2.size){//將L2中剩余的元素賦給LL.list[k]=L2.list[j];j++;k++;}L.size=k;}⑻從線性表中刪除所有其值重復(fù)的元素，使其所有元素的值均不同，如對于線性表(2,8,9,2,5,5,6,8,7,2)，那么執(zhí)行此算法后變?yōu)?2,8,9,5,6,7)。解：voidDelete5(List&L)//從線性表中刪除所有其值重復(fù)的元素,使其所有元素的值均不同{inti=0;while(i<L.size){intj=i+1;while(j<L.size){//刪除重復(fù)值為L.list[i]的所有元素if(L.list[j]==L.list[i]){for(intk=j+1;k<L.size;k++)L.list[k-1]=L.list[k];L.size--;}elsej++;}i++;}}4.對于結(jié)點類型為LNode的單鏈接表,編寫出以下每個算法。⑴將一個單鏈接表按逆序鏈接,即假設(shè)原單鏈表中存儲元素的次序為a1,a2,...,an,那么逆序鏈接后變?yōu)閍n,an-1,...a1。解：voidContrary(LNode*&HL)//將一個單多辦實事有按逆序鏈接{LNode*p=HL;//p指向待逆序的第一個結(jié)點，初始指向原表頭結(jié)點HL=NULL;//HL仍為逆序后的表頭指針，祿始值為空while(p!=NULL){//把原單鏈表中的結(jié)點依次進行逆序鏈接LNode*q=p;//q指向待處理的結(jié)點p=p->next;//p指向下一個待逆序的結(jié)點//將q結(jié)點插入到已陳序單鏈表的表頭q->next=HL;HL=q;}}⑵刪除單鏈表中的第i個結(jié)點。解：voidDelete1(LNode*&HL,inti)//刪除單鏈表中的第i個結(jié)點{if(i<1||HL==NULL){cerr<<"Indexisoutrange!"<<end1;exit(1);}LNode*ap,*cp;ap=NULL;cp=HL;//cp指向當前結(jié)點，ap指向其前驅(qū)結(jié)點intj=1;while(cp!=NULL)if(j==i)break;//cp結(jié)點即為第i個結(jié)點else{//繼續(xù)向后尋找ap=cp;cp=cp->next;j++;}if(cp==NULL){cerr<<"Indexisoutrange!"<<end1;exit(1);}if(ap==NULL)HL=HL->next;elseap->next=cp->next;deletecp;}⑶從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，假設(shè)單鏈表為空，那么顯示出錯信息并停止運行。解：ElemTypeMaxValue(LNode*HL)//從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回{if(HL==NULL){cerr<<"Linkedlistisempty!"<<end1;exit(1);}ElemTypemax=HL->data;LNode*p=HL->next;while(p!=NULL){if(max<p->data)max=p->data;p=p->next;}returnmax;}⑷統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。解：intCount(LNode*HL,ElemTypex)//統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù){intn=0;while(HL!=NULL){if(HL->data==x)n++;HL=HL->next;}returnn;}⑸根據(jù)一維數(shù)組a[n]建立一個單鏈表，使單鏈表中元素的次序與a[n]中元素的次序相同，并使該算法的時間復(fù)雜度為O(n)。解：voidCreate(LNode*&HL,ElemTypea[],intn)//根據(jù)一維數(shù)組a[n]建立一個單鏈表{InitList(HL);for(inti=n-1;i>=0;i--)InsertFront(HL,a[i];}⑹將一個單鏈表重新鏈接成有序單鏈表。解：voidOrderList(LNode*&HL)//將一個單鏈表重新鏈接成有序單鏈表{LNode*p=HL;//p指向待處理的第一個結(jié)點，初始指向原表頭結(jié)點HL=NULL;//HL仍為待建立的有序表的表頭指針，祿始值為空while(p!=NULL){//把原單鏈表中的結(jié)點依次進行有序鏈接LNode*q=p;//q指向待處理的結(jié)點p=p->next;//p指向下一個待處理的結(jié)點LNode*ap=NULL,*cp=HL;//cp指向有序表中待比擬的結(jié)點，ap指向其前驅(qū)結(jié)點while(cp!=NULL){//為插入q結(jié)點尋找插入位置if(q->data<cp->data)break;else{ap=cp;cp=cp->next;}}//將q結(jié)點插入到ap和cpxfhkoppujq->next=cp;if(ap==NULL)HL=q;elseap->next=q;}}⑺將兩個有序單鏈表合并成一個有序單鏈表，合并后使原有單鏈表為空。解：LNode*Mergel(LNode*&p1,LNode*&p2)//將兩個有序單鏈表合并成一個有序單鏈表{LNodea;//a結(jié)點作為結(jié)果的有序單鏈表的表頭附加結(jié)點，這樣便于處理，處理//結(jié)束后返回a結(jié)點的鐨針域的值LNode*p=&a;//p指向結(jié)果的有序單鏈表的表尾結(jié)點p->next=NULL;//初始指向表頭附加結(jié)點while((p1!=NULL)&&(p2!=NULL)){//處理兩個表非空的情況if(p1->data<p2->data){p->next=p1;p1=p1->next;}else{p->next=p2;p2=p2->;}p=p->next;}if(p1!=NULL)p->next=p1;if(p2!=NULL)p->next=p2;p1=p2=NULL;returna.next;}⑻根據(jù)兩個有序單鏈表生成一個新的有序單鏈表，原有單鏈表保持不變。如假定兩個有序單鏈表中的元素為(2,8,10,20)和(3,8,9,15,16)，那么生成的新單鏈表中的元素為(2,3,8,8,9,10,15,16,20)。解：LNode*Merge2(LNode*p1,LNode*p2)//根據(jù)兩個有序單鏈表生成一個新的有序單鏈表{LNodea;//用a作為新的有序單鏈表的表頭附加結(jié)點LNode*p=&a;//p指向結(jié)果有序單鏈表的表尾結(jié)點p->next=NULL;//初始指向表頭附加結(jié)點while((p1!=NULL&&(p2!=NULL)){//處理兩個表非空時的情況LNode*newptr=newLNode;if(p1->data<p2->data){//由p1->data建立新結(jié)點，然后p1指針后移newptr->data=p1->data;p1=p1->next;}else{//由p2->data建立新結(jié)點，然后p2指針后移newptr->data=p2->data;p2=p2->next;}//將newptr結(jié)點插入到結(jié)果的有序表的表尾p->next=newptr;p=newptr;}while(p1!=NULL){//繼續(xù)處理p1單鏈表中剩余的結(jié)點LNode*newptr=newLNode;newptr->data=p1->data;p1=p1->next;p->next=newptr;p=newptr;}while(p2!=NULL){//繼續(xù)處理p2單鏈表中剩余的結(jié)點LNode*newptr=newLNode;newptr->data=p2->data;p2=p2->next;p->next=newptr;p=newptr;}p->next=NULL;returna.next;}⑼根據(jù)一個元素類型為整型的單鏈表生成兩個單鏈表，使得第一個單鏈表中包含原單鏈表中所有元素值為奇數(shù)的結(jié)點，使得第二個單鏈表中包含原單鏈表中所有元素值為偶數(shù)的結(jié)點。原有單鏈表保持不變。解：voidSeparate(LNode*HL,LNode*&p1,LNode*&p2)//根據(jù)一個單鏈表HL按條件拆分生成兩個單鏈表p1和p2{LNodea,b;//a和b結(jié)點分別作為p1和p2單鏈表的表頭附加結(jié)點LNode*t1=&a,*t2=&b;//t1和t2分別作為指向p1和p2單鏈表的//表尾結(jié)點，初始指向表頭附加結(jié)點Lnode*p=HL;while(p!=NULL){//每循環(huán)一次產(chǎn)生一個新結(jié)點，并把它參加到p1或p2單鏈表//的未尾LNode*newptr=newLNode;if(p->data%2==1){newptr->data=p->data;t1->next=newptr;t1=newptr;}else{newptr->data=p->data;t2->next=newptr;t2=newptr;}p=p->next;}t1->next=t2->next=NULL;p1=a.next;p2=b.next;//把指向兩個單鏈表的表頭結(jié)點的指針分別賦給//p1和p2返回}6.編寫一個算法，使用表頭附加結(jié)點的循環(huán)單鏈表解決約瑟夫(Josephus)問題。其問題是：設(shè)有n個人圍坐在一張圓桌周圍，現(xiàn)從某個人開始從1報數(shù)，數(shù)到m的人出列(即離開坐位，不參加以后的報數(shù))，接著從出列的下一個人開始重新從1報數(shù)，數(shù)到m的人又出列，如此下去直到所有人都出列為止，試求出它們的出列次序。假設(shè)，當n=8、m=4時，假設(shè)從第一個人(假定每個人的編號依次為1,2...,n)開始報數(shù)，那么得到的出列次序為:4,8,5,2,1,3,7,6。此算法要求以n、m和s(假定從第s個人開始第一次報數(shù))作為值參。解：voidJosephus(intn,intm,ints)//使用帶表頭附加結(jié)點的循環(huán)單鏈表解決約瑟夫問題{//生成表頭附加結(jié)點，此時循環(huán)單鏈表為空LNode*HL=newLNode;HL->next=HL;inti;//生成含有n個結(jié)點、結(jié)點依次為1,2,...n的帶表頭結(jié)點的循環(huán)單鏈表for(i=n;i>=1;i--){//生成新的結(jié)點LNode*newptr=newLNode;newptr->data=i;//把新的結(jié)點插入到表頭newptr->next=HL->next;HL->next=newptr;}//從表頭開始順序查找出第s個結(jié)點，對應(yīng)第一個開始報數(shù)的人LNode*ap=HL,*cp=HL->next;for(i=1;i<s;i++){//ap和cp指針后移一個位置ap=cp;cp=cp->next;//假設(shè)cp指向了表頭附加結(jié)點，那么仍需后移ap和cp指針，使之指向表頭結(jié)點if(cp==HL){ap=HL;cp=HL->next;}}//依次使n-1個人出列for(i=1;i<n;i++){//順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的結(jié)點for(intj=1;j<m;j++){ap=cp;cp=cp->next;if(cp==HL){ap=HL;cp=HL->next;}}//輸出cp結(jié)點的值，即出列的人cout<<cp->data<<"";//從單鏈表中刪除cp結(jié)點ap->next=cp->next;deletecp;//使cp指向被刪除結(jié)點的后繼結(jié)點cp=ap->next;//假設(shè)cp指向了表頭附加結(jié)點，那么后移ap和cp指針if(cp==HL){ap=HL;cp=HL->next;}}//使最后一個人出列cout<<HL->next->data<<end1;//刪除表頭結(jié)點和表頭附加結(jié)點deleteHL->next;deleteHL;}7.對于在線性表抽象數(shù)據(jù)類型中定義的每一個操作，寫出結(jié)點類型為LNode的帶頭附加結(jié)點的循環(huán)單鏈表上實現(xiàn)的對應(yīng)算法。⑴初始化單鏈表解：voidInitList(LNode*HL){HL->next=HL;//將單鏈表置空}⑵刪除單鏈表中的所有結(jié)點，使之成為一個空表voidClearList(LNode*HL){LNode*cp,*np;cp=HL->next;//將指向第一個結(jié)點的指針賦給cpwhile(cp!=HL)//遍歷單鏈表，向系統(tǒng)交回每一個結(jié)點。{np=cp->next;//保存下一個結(jié)點的指針。deletecp;//刪除當前結(jié)點。cp=np;//使下一個結(jié)點成為當前結(jié)點。}HL->next=HL;//置單鏈表為空}⑶得到單鏈表的長度intListSize(LNode*HL){LNode*p=HL->next;inti=0;while(p!=HL){i++;p=p->next;}returni;}⑷檢查單鏈表是否為空intListEmpty(LNode*hl){return(HL->next==HL);}⑸得到單鏈表中第pos個結(jié)點中的元素ElemTypeGetElem(LNode*HL,intpos){if(pos<1){cerr<<"posisoutrange!"<<end1;exit(1);}LNode*p=HL->next;inti=0;while(p!=HL){i++;if(i==pos)break;p=p->next;}if(p!=HL)returnp->data;else{cerr<<"posisoutrange!"<<end1;exit(1);}}⑹遍歷單鏈表voidTraverseList(LNode*HL){LNode*p=HL->next;while(p!=HL){cout<<p->data<<"";p=p->next;}cout<<end1;}⑺從單鏈表查找具有給定值的第一個元素intFind(LNode*HL,ElemType&item){LNode*p=HL->next;while(p!=HL)if(p->data==item){item=p->data;return1;}elsep=p->next;return0;}⑻更新單鏈表中具有給定值的第一個元素intUpdata(LNode*HL,constElemType&item){LNode*p=HL->next;while(p!=HL)//查找元素if(p->data==item)break;elsep=p->next;if(p==HL)return0;else{//更新元素p->data=item;return1;}}⑼向單鏈表的未尾插入一個元素voidInsertRear(LNode*HL,constElemType&item){LNode*newptr;newptr=newLNode;newptr->data=item;//把新元素賦給動態(tài)結(jié)點*newptr的值域。LNode*p=HL;while(p->next!=HL)//從表頭開始遍歷到最后一個結(jié)點為止。p=p->next;newptr->next=HL;p->next=newptr;//把新結(jié)點鏈接到表尾。}⑽向單鏈表的表頭插入一個元素voidInsertFront(LNode*HL,constElemType&item){LNode*newptr;newptr=newLNode;newptr->data=item;newptr->next=HL->next;HL->next=newptr;}(11)向單鏈表中插入一個元素voidInsert(LNode*HL,constElemType&item){LNode*newptr;newptr=newLNode;newptr->data=item;LNode*ap,*cp;ap=HL;cp=HL->next;while(cp!=HL)if(item<cp->data)break;else{ap=cp;cp=cp->next;}newptr->next=cp;ap->next=newptr;}(12)從單鏈表中刪除表頭元素ElemTypeDeleteFront(LNode*HL){if(HL->next==HL){cerr<<"Deleteingfromanemptylist!"<<end1;exit(1);}LNode*p=HL->next;HL->next=p->next;ElemTypetemp=p->data;deletep;returntemp;}(13)從單鏈表中刪除等于給定值的第一個元素intDelete(LNode*HL,constElemType&item){LNode*ap=HL,*cp=HL->next;while(cp!=HL)if(cp->data==item)break;else{ap=cp;cp=cp->next;}if(cp==HL){cerr<<"Deletedelementisnotexitst!"<<end1;return0;}else{ap->next=cp->next;deletecp;return1;}}(14)利用單鏈表進行數(shù)據(jù)排序voidLinkSort(ElemTypea[],intn){LNode*head=newLNode;InitList(head);inti;for(i=0;i<n;i++)Insert(head.a[i]);LNode*p=head->next;i=0;while(p!=head){a[i++]=p->data;p=p->next;}ClearList(head);deletehead;}*8.對于結(jié)點類型為DNode的雙向鏈表，編寫出以下每一個算法。⑴向雙向鏈表的未尾插入一個值為x的結(jié)點。解：voidInsertRear(DNode*&DL,ElemTypex){//建立值為x的結(jié)點DNode*newptr=newDNode;newptr->data=x;newptr->left=newptr->right=newptr;//當鏈表為空時完成插入if(DL==NULL){DL=newptr;return;}//當鏈表不為空時完成插入DNode*p=DL->left;newptr->right=p->right;DL->left=newptr;newptr->left=p;p->right=newptr;}⑵向雙向循環(huán)表的第i個結(jié)點位置插入一個值為x的結(jié)點。解：voidInsert(DNode*&DL,inti,ElemTypex){//i值越界，退出執(zhí)行if(i<=0){cerr<<"iisoutrange!"<<end1;exit(1);}//建立值為x的新結(jié)點DNode*newptr=newDNode;newptr->data=x;newptr->left=newptr->right=newptr;//當鏈表為空同時i等于1時進行插入，i不為1那么退出if(DL==NULL)if(i==1){DL=newptr;return;}else{out<<"iisrange!"<<end1;exit(1);}//實現(xiàn)i等于1時的插入if(i==1){newptr->right=DL;newptr->left=DL->left;DL->left->right=newptr;DL->left=newptr;DL=newptr;return;}//查找第i個結(jié)點intk=1;DNode*p=DL->right;while(p!=DL){k++;if(k==i)break;p=p->right;}//i值越界，退出執(zhí)行if(i>k+1){cerr<<"iisoutrange!"<<end1;exit(1);}//把newptr結(jié)點插入到p結(jié)點之前newptr->right=p;newptr->left=p->left;p->left->right=newptr;p->left=newptr;return;}⑶從雙向循環(huán)鏈表中刪除值為x的結(jié)點。解：boolDelete(DNode*&DL,ElemTypex){if(DL==NULL)return0;//當表頭結(jié)點為x時那么刪除之DNode*p=DL;if(DL->data==x){DL=DL->right;p->left->right=DL;DL->left=p->left;deletep;return1;}//查找值為x的結(jié)點p=p->right;while(p!=DL){if(p->data==x)break;elsep=p->right;}//不存在值為x的結(jié)點那么返回0if(p==DL)return0;//刪除值為x的結(jié)點p->left->right=p->right;p->right->left=p->left;deletep;return1;}9.假定有一種帶頭附加結(jié)點的鏈表，每個結(jié)點含三個域：data、next和range，其中data為整型值域，next和range均為指針域，現(xiàn)在所有結(jié)點已經(jīng)由next域鏈接起來，試編一算法，利用range域把所有結(jié)點按照其值從小到大的順序鏈接起來，當然由此域鏈接得到的單鏈表的表頭指針保存在表頭附加結(jié)點的range域中。解：voidOrderList(SLNode*SL)//假定SLNode類型為按題目要求所定義的結(jié)點類型，SL為指向表頭附加結(jié)點的指針{SL->range=NULL;for(SLNode*p=SL->next;p!=NULL;p=p->next){//每循環(huán)一次把p所指向的結(jié)點按序插入到以range域鏈接的有序表中SLNode*ap,*cp;//為p結(jié)點尋找適宜的插入位置ap=SL;cp=ap->range;while(cp!=NULL)if(p->data<cp->data)break;else{ap=cp;cp=cp->range;}//插入位置在ap和cp之間，把結(jié)點插入其中p->range=cp;ap->range=p;}}10.編一程序，實現(xiàn)以下功能：⒈按照9題對結(jié)點的要求生成一個具有10個整數(shù)元素結(jié)點的帶表頭附加結(jié)點的根據(jù)next域鏈接的鏈表，元素值由隨機函數(shù)產(chǎn)生；⒉按照next域鏈接的次序輸出鏈表中每個結(jié)點的值；⒊調(diào)用按第9題要求編寫的操作算法；⒋按照range域鏈接的次序輸出鏈表中每個結(jié)點的值。解：//lx2-7.cpp#include<isotream.h>#include<stdlib.h>typedefintElemType;//規(guī)定元素類型為整型structSLNode//定義單鏈表結(jié)點{ElemTypedata;SLNode*next;SLNode*range;};voidOrderList(SLNode*SL){SL->range=NULL;for(SLNode*p=SL->next;p!=NULL;p=p->next){SLNode*ap,*cp;//為p結(jié)點尋找適宜的插入位置ap=SL;cp=ap->range;while(cp!=NULL)if(p->data<cp->data)break;else{ap=cp;cp=cp->range;}//插入位置在ap和cp之間，把p結(jié)點插入其中p->range=cp;ap->range=p;}}voidmain(){//按next域鏈接生成具有10個整數(shù)元素結(jié)點的鏈表SLNode*a=newSLNode;a->next=NULL;inti;SLNode*p;for(i=0;i<10;i++){p=newSLNode;p->data=range()%30;//假定產(chǎn)生30以內(nèi)的隨機整數(shù)p->next=a->next;a->next=p;}//按next域鏈接的次序輸出單鏈表for(p=a->next;p!=NULL;p=p->next)cout<<p->data<<"";cout<<end1;//調(diào)用按第9題要求編寫的操作算法orderList(a);//按range域鏈接的次序輸出單鏈表for(p=a->range;p!=NULL;p=p->range)cout<<p->data<<"";cout<<end1;}稀疏距陣和廣義表1.一個稀疏矩陣如以下圖所示:0400000000-3001800000000050000-7000200006000圖3-1具有6行×7列的一個稀疏矩陣⑴寫出它的三元組線性表；解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6))⑵給出它的順序存儲表示；解：下標12345678...MaxTermsrow(行號)12234556col(列號)24714264val(元素值)4-3185-726⑶給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示；解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))⑷給出對它進行快速轉(zhuǎn)置時,num向量中各分量的值；⑸給出對它進行快速轉(zhuǎn)置前和轉(zhuǎn)置后,pot向量中各分量的值。解：Col1234567Num[col]1203011pot[col](前)1244778pot[col](后)24477892.采用順序存儲方式實現(xiàn)稀疏矩陣M1和M2相加的運算，運算結(jié)果由變量M返回。解：voidAdd(SMatrix&M1,SMatrix&M2,SMatrix&M)//采用順序存儲方式實現(xiàn)稀疏矩陣M1和M2相加的運算，運算結(jié)果由變量M返回{InitMatrix(M);//假設(shè)兩個矩陣尺寸不同，那么給出錯誤信息并停止運行if((M1.m!=M2.m)||(M1.n!=M2.n)){cerr<<"towmatrixmeasurenentsaredifferent!"<<end1;exit(1);}M.m=M1.m;M.n=M1.n;//假設(shè)兩個矩陣均為零矩陣，那么無須計算if(M1.t==0)&&(M2.t==0))return;inti=1,j=1;//用i，j分別指示M1.smtM2.sm數(shù)組中待比擬元素的下標,初值均//為1intk=1;//用k指示M.sm數(shù)組中待寫入元素的下標，初值為1while((i<=M1.t)&&(j<=M2.t)){//把行號較小元素寫入到結(jié)果矩陣中,假設(shè)行號相同進行列號的比擬,使列號//較小的元素寫入到結(jié)果矩陣中,假設(shè)行、列號均相等，那么當相應(yīng)元素的//和不為0時才把這個和寫入到結(jié)果矩陣中if(M1.sm[i].row<M2.sm[j].row){M.sm[k]=M1.sm[i];i++;k++;}elseif(M1.sm[i].row>M2.sm[j].row){M.sm[k]=M2.sm[j];j++;k++;}else{if(M1.sm[i].col<M2.sm[j].col){M.sm[k]=M1.sm[i];i++;k++;}elseif(M1.sm[i].col>M2.sm[i].col{M.sm[k]=M2.sm[j];j++;k++;}else{//此時相應(yīng)元素的行列號必然相等if(M.sm[i].val+M2.sm[j].val!=0){M.sm[k].row=M1.sm[i].row;M.sm[k].col=M1.sm[i].col;M.sm[k].val=M1.sm[i].val+M2.sm[j].val;k++;}i++;j++;}}}while(i<=M1.t){//把M1中的剩余元素寫入到結(jié)果矩陣M中M.sm[k]=M1.sm[i];i++;k++;}while(j<=M2.t){//把M2中的剩余元素寫入到結(jié)果矩陣M中M.sm[k]=M2.sm[j];j++;k++;}M.t=k-1;//把寫入到結(jié)果矩陣M中元素的個數(shù)賦給M中保存元素個數(shù)的//變量域return;}3.畫出以下每個廣義表的帶表頭附加結(jié)點的鏈接存儲結(jié)構(gòu)圖并分別計算出它們的長度和深度。⑴A=(())⑵B=(a,b,c)⑶C=(a,(b,(c)))⑷D=((a,b),(c,d))⑸E=(a,(b,(c,d)),(e))⑹F=((a,(b,(),c),((d)),e)))解：每題的長度和深度如下表示。題號123456長度132231深度2132344.編寫一個建立廣義表鏈接存儲結(jié)構(gòu)的算法，假定廣義表由字符串值提供。解：voidCreate(GLNode*&GL,char*a)//根據(jù)在字符串a(chǎn)中保存的廣義表生成其對應(yīng)的存儲結(jié)構(gòu){staticinti=0;//定義靜態(tài)變量i指示a中待處理的字符串位置，每處理一//個字符后i值增1if(a[i]=='\0')return;//當字符串處理結(jié)束后返回if(a[i]=='#'){GL=NULL;i++;}elseif(a[i]=='('){GL=newGLNode;GL->tag=True;i++;Create(GL->sublist,a);}if(GL=newGLNode;GL->tag=False;GL->data=a[i];i++;}else{GL=newGLNode;GL->tag=False;GL->data=a[i];i++;}if(GL==NULL)//此時的a[i]必然為')'字符i++;elseif(a[i]==','){i++;Create(GL->next,a);}elseif((a[i]==')')||(a[i]==',')){i++;GL->next=NULL;}}5.編寫一個廣義表中查找元素字等于給定值的算法，假設(shè)查找成功那么返回數(shù)值1，否那么返回數(shù)值0。解：intFind(GLNode*GL,charch)//從廣義表GL中查找單元素字符等于ch的算法，假設(shè)查找成功，那么返回數(shù)值1，//否那么返回數(shù)值0{while(GL!=NULL){if(GL->tag==0){//處理單元素結(jié)點if(GL->data==ch)return1;//查找成功返回1elseGL=GL->next;//否那么繼續(xù)向后查找}else{//處理子表結(jié)點intx=Find(GL->sublist,ch);//向子表中繼續(xù)查找if(x)//假設(shè)在子表中查找成功那么返回1，否那么繼續(xù)向后查找return1;elseGL=GL->next;}}return0；//當查找到表為空時返回0}棧和隊列.習(xí)題四1.假定有四個元素A、B、C、D，按所列次序進棧，試寫出所有可能的出棧列，注意，每一個元素進棧后都允許出棧，如ACDB就是一種出棧序列。解：ABCDABDCACBDADCBBACDBADCBCADBCDABDCACBADCDBADCBA2.在一個數(shù)組空間stack[StackMaxSize]中可以同時存放兩個順序棧，棧底分別在數(shù)組的兩端，當?shù)谝粋€棧的棧頂指針top1等于-1時那么棧1為空，當?shù)诙€棧的棧頂指針top2等于StackMaxSize時棧2為空。兩個棧均向中間增長，當向棧1插入元素時，使top1增1得到新的棧頂位置，當向棧2插入元素時，那么使top2減1才能夠得到新的棧頂位置。當top1等于top2-1或者top2等于top1+1時，存儲空間用完，無法再向任一棧插入元素。用于雙棧操作的順序存儲類型可定義為：structBothstack{ElemTypestack[stackMaxSize];inttop1,top2;};雙棧操作的抽象數(shù)據(jù)類型可定義為：DATBSTACKisData:采用順序結(jié)構(gòu)存儲的雙棧，其存儲類型為Bothstackoperations:voidInitStack(Bothstack&BS,intk);//初始化棧。當k=1或2時對應(yīng)置棧1或棧2為空，k=3時置兩個格均為空voidClearstack(BothStack&BS,intk)//去除棧。當k=1或2時對應(yīng)棧1或棧2被去除，k=3時兩個棧均被去除intStackEmpty(BothStack&BS,intk)//判斷棧是否為空。當k=1或2時判斷對應(yīng)的棧1或棧是否為空，k=3時//判斷兩個棧是否同時為空。假設(shè)判斷結(jié)果為空那么返回1，否那么返回0ElemTypePeek(BothStack&BS,intk)//取棧頂元素。當k=1或2時對應(yīng)返回棧1或棧2的棧頂元素voidPush(BothStack&Bs,intk,constElemType&item)//進棧。當k=1或2時對應(yīng)向棧1或棧2的頂端壓入元素itemEndBSTACK1.試寫出上述抽象數(shù)據(jù)類型中每一種操作的算法。解：voidInitStack(BothStack&BS,intk){if(k==1)BS.top1=-1;elseif(k==2)BS.top2=StackMaxSize;elseif(k==3){BS.top1=-1;BS.top2=StackMaxSize;}}voidClearStack(BothStack&BS,intk){//函數(shù)體同上}intStackEmpty(BothStack&BS,intk){if(k==1)returnBS.top1==-1;elseif(k==2)returnBS.top2==StackMaxSize;elseif(k==3)return(BS.top1==-1)&&(BS,top2==StackMaxSize);else{cerr<<"k的值不正確!"';exit(1);}}ElemTypepeek(BothStack&BS,intk){if(k==1){if(BS.top1==-1){cerr<<"Stack1isempty!"<<end1;exit(1);}returnBS,stack(bs,top1);}elseif(k==2){if(BS.top2==StackMaxSize){cerr<<"Stack2isempty!"<<end1;exit(1);}returnBS,stack[BS,top2];}else{cerr<<"k的值不正確!";exit(1);}}voidpush(BothStack&BS,intk,constElemType&item){if(BS.top1==BS.top2-1){cerr<<"Stackoverflow!"<<end1;exit(1);}if(k==1){BS.top1++;Bs.stack[BS.top1]=item;}elseif(k==2){BS.top1--;BS.stack[BS.top2]=item;}}ElemTypepop(BothStack&BS,intk]{if(k==1){if(BS.top==-1){cerr<<"Stack1isempty!"<<end1;exit(1);}BS.top--;returnBS,stack[BS.top1+1];}elseif(k==2){if(BS.top==StackMaxSize){cerr<<"Stack2isempty!"<<end1;exit(1);}BS.top2++;returnBS.stack[BS,top2-1];}else{cerr<<"k的值不正確!";exit(1);}}2.假定上述所有操作的算法已存于頭文件"bstack.h"中，試編寫一個程序，讓計算機隨機產(chǎn)生出100以內(nèi)的20個正整數(shù)并輸出，同時把它們中的偶數(shù)依次存入到第一個棧中，奇數(shù)依次存入到第二個棧中，接著按照存入每個棧中元素的次序分別輸出每個棧中的所有元素(此操作不改變棧的狀態(tài))，然后按照后進先出的原那么輸出每個棧中的所有元素。解：#include<iostream.h>#include<stdlib.h>constintStackMaxSize=50;typedefintElemType;structBothStack{ElemTypestack[StackMaxSize];inttop1,top2;};#include"bstack.h"voidmain(){BothStacka;InitStack(a,3);//初始化兩個棧inti,j,k;//計算機產(chǎn)生20個隨機數(shù)并輸出，同時按奇偶數(shù)不同分別放入不同的棧中for(i=0;i<20;i++){j=rand()%100;cout<<j<<"";if(j%2==0)push(a,1,j);elsepush(a,2,j);}cout<<end1;//按照存入棧1中元素的次序輸出棧1中的所有元素cout<<"棧1：";for(i=0;i<=a.top1;i++)cout<<a.stack[i]<<"";cout<<end1;//按照存入棧2中元素的次序輸出棧2中的所有元素cout<<"棧2：";for(i=StackMaxSize-1;i>=a.top2;i--)cout<<a.stack[i]<<"";cout<<end1;//按照后進先出的原那么輸出每個棧中的所有元素for(k=1;k<=2;k++){if(k==1)cout<<"棧1：";elsecout<<"棧2：";while(!StackEmpty(a,k))cout<<Pop(a,k)<<"";cout<<end1;}}該程序輸入并運行后將得到如下結(jié)果(由于機器系統(tǒng)和C++版本不同，你得到的結(jié)果可能與此不同)：416734069247858625458127619195422736棧1：34024785862644236棧2：416769545812761919527棧1：36426462587824034棧2：2795916127814556967413.設(shè)用第二章定義的類型為AlinkList的一維數(shù)組MS[MaxSize]建立三個鏈接堆棧，其中前三個元素的next域用來存儲三個棧頂指針，從下標為3的元素起作為空閑元素提供應(yīng)三個棧共同使用，試編寫一個算法把從鍵盤上輸入的n個整數(shù)按照以下條件分別進入不同的棧：⑴假設(shè)輸入的整數(shù)x小于60，那么進第一個棧；⑵假設(shè)輸入的整數(shù)x大于等于60同時小于100，那么進第二個棧；⑶假設(shè)輸入的整數(shù)大于100，那么進第三個棧。解：voidMoreStack(ALinkListMS,intn)//把從鍵盤上輸入的n個整數(shù)按不同條件分別進入到三個不同的鏈接棧中{if(n>MaxSize-3){cerr<<"存儲空間缺乏!";exit(1);}inti,x,av;for(i=0;i<3;i++)MS[i].next=0//置空棧，即給三個棧頂指針賦0av=3;//av指向可利用元素的下標，賦初值為3cout<<"輸入"<<n<<"個整數(shù)："<<end1;for(i=0;i<n;i++){//從鍵盤讀入一個整數(shù)并把它賦給av元素的值域cin>>x;MS[av].data=x;//按條件把av元素壓入不同的棧，即鏈接到相應(yīng)棧的棧頂if(x<60){Ms[av].next=MS[0].next;MS[0].next=av;}elseif(x>=60&&x<=100){MS[av].next=MS[1].next;MS[1].next=av;}else{MS[av].next=MS[2].next;MS[2].next=av;}//使av指向下一個可利用元素av++;}}4.編寫一個程序，首先調(diào)用上題算法，然后分別打印出每個棧中的內(nèi)容。解：#include<iostream.h>#include<stdlib.h>constintMaxSize=50;//要至少定義為比輸入的整數(shù)個數(shù)大3typedefintElemType;structALNode{ElemTypedata;intnext;};typedefALNodeALinkList[MaxSize];voidMoreStack(ALinkListMS,intn){//函數(shù)體在此省略}voidmain(){ALinkLista;intn;cout<<"從鍵盤輸入的整數(shù)個數(shù)(1～47):";cin>>n;MoreStack(a,n);for(inti=0;i<3;i++){//依次將每個棧中的元素全部出棧并打印出來intj=a[i].next;while(j!=0){cout<<a[j].data<<"";j=a[j].next;}cout<<end1;}}一次輸入和運行結(jié)果如下：從鍵盤上輸入的整數(shù)個數(shù)為(1～47)：12輸入12個整數(shù)：3864971207833452148825143602545333860887897641432141205.一個中綴算術(shù)表達式為：3+4/(25-(6+15))*8@⑴寫出對應(yīng)的后綴算術(shù)表達式。解：3425615+-/8*+@⑵畫出在轉(zhuǎn)換成后綴表達式的過程中運算符棧的變化。解：略6.一個后綴算術(shù)表達式為：248+3*4107-*/@⑴寫出對應(yīng)的中綴算術(shù)表達式。解：(24+8)*3/(4*(10-7))⑵畫出在進行后綴算術(shù)表達式求值的過程中數(shù)值棧的變化。解：略7.為了計算表達式的值：把棧Stack類型定義為帶模板的類型，該類型中包含順序存儲的棧和對棧的每一種基本操作的實現(xiàn)。解：把進行后綴表達式求值的Compute算法改寫為使用Stack類的算法。解：把進行中綴表達式轉(zhuǎn)換為后綴表達式的Change算法改寫為使用Stack類的算法。解：寫出計算C(n,k)的遞歸算法。解：利用二維數(shù)組寫出計算C(n,k)的非遞歸算法。解：分析遞歸算法和非遞歸算法的時間復(fù)雜度和空間復(fù)雜度。解：template<classElemType>classStack{ElemTypestack[StackMaxSize];inttop;public:voidInitStack()//初始化棧對象，即把它置為空{(diào)top=-1;}voidClassStack()//去除棧對象中的所有元素，使之成為一個空棧{top=-1;}intStackEmpty()//判斷棧對象是否為空，假設(shè)是那么返回1，否那么返回0{returntop==-1;}ElemTypepeek()//返回棧對象的棧頂元素，但不移動棧頂指針{if(top==-1){cerr<<"Stackisempty!"<<end1;exit(1);}returnstack[top];}voidpush(constElemType&item)//元素item進棧，即插入到棧頂if(top==StackMaxSize-1){cerr<<"Stackoverflow!"<<end1;exit(1);}top++;stack[top]=item;}ElemTypePop()//刪除棧頂元素并返回之{if(top==-1){cerr<<"Stackisempty!"<<end1;exit(1);}ElemTypetemp=stack[top];top--;returntemp;}}floatCompute(char*str){Stack<float>s;//定義元素類型為float的棧S.InitStack();istrstreamins(str);charch;floatx;ins>>ch;while(ch!='@'){//掃描每一個字符并進行相應(yīng)處理switch(ch){cass'+':X=S.Pop()+S.Pop();break;cass'-':X=S.Pop();X=S.Pop()-X;break;cass'*':X=S.Pop()*S.Pop();break;cass'/':X=S.Pop();if(X!=0.0)X=S.Pop()/X;else{cerr<<"Divideby0!"<<end1;exit(1);}break;ins.putback(ch);ins<<X;}S.Push(X);ins>>ch;}if(!S.StackEmpty()){x=s.Pop();if(!S.StackEmpty())returnX;else{cerr<<"expressionerror!"<<end1;exit(1);}}else{cerr<<"Stackisempty!"<<end1;exit(1);}}voidChange(char*s1,char*s2){Stack<char>R;//定義元素類型為char的棧R.InitStack();R.push('@');inti,j;i=0;j=0;charch=s1[i];while(ch='@'){if(ch=='')ch=s1[++i];elseif(ch=='('){R.Push(ch);ch=s1[++i];}elseif(ch==')'){while(R.peek()!='(')s2[j++]=R.Pop();R.Pop();ch=s1[++i];}elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/'){charw=R.peek();while(precedence(w)>=Precedence(ch){s2[j++]=w;R.Pop();w=R.Peek();}R.Push(ch);ch=s1[++i];}else{while(isdigit(ch)||ch=='.'){s2[j++]=ch;ch=s1[++i];}s2[j++]='';}}ch=R.Pop();while(ch!='@'){s2[j++]=ch;ch=R.Pop();}s2[j++]='@';s2[j++]='\0';}8.編寫把十進制正整數(shù)轉(zhuǎn)換為十六進制數(shù)輸出的算法。解：voidTransform(longnum)//把一個正整數(shù)num轉(zhuǎn)為一個十六進制數(shù)輸出{Stacka;InitStack(a);while(num!=0){intk=num%16;Push(a,k);num/=16;}while(!StackEmpty(a)){intX=Pop(a);if(x<10)cout<<x;else{switch(x){cass10:cout<<'A';break;cass11:cout<<'B';break;cass12:cout<<'C';break;cass13:cout<<'D';break;cass14:cout<<'