計算機軟件技術(shù)基礎(chǔ)-習題一解答

計算機軟件技術(shù)基礎(chǔ)-習題一解答線性結(jié)構(gòu) 習題解答第8頁共16頁習題解答3.設(shè)n為正整數(shù),分析下列各程序段中加下劃線的語句的執(zhí)行次數(shù)。(1) for(inti=1;i<=n;i++) for(intj=1;j<=n;j++){ c[i][j]=0.0; for(intk=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2) x=0;y=0; for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) for(intk=1;k<=j;k++) x=x+y;(3) inti=1,j=1; while(i<=n&&j<=n){ i=i+1;j=j+i; }(4)* inti=1; do{ for(intj=1;j<=n;j++) i=i+j; }while(i<100+n);【解答】 (1) (2) (3)i=1時，i=2，j=j+i=1+2=2+1，i=2時，i=3，j=j+i=(2+1)+3=3+1+2，i=3時，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4時，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，…… intA[arraySize]; inti; for(i=0;i<arraySize;i++) if(!calc(A,i)){ printf("failedat%d.\n",i); break; }}/*順序表結(jié)構(gòu)的定義.為簡化起見，表元素我們使用整型數(shù)據(jù)數(shù)據(jù)元素從data[0]處開始存儲*/typedefstruct /*注意typedef的使用*/{ intdata[MAXSIZE];/*數(shù)據(jù)域*/ intlength;/*表長*/}listtype;5.設(shè)有一個線性表(a0,a1,…,an-2,an-1)存放在一個一維數(shù)組A[arraySize]中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為(an-1,an-2,…,a1,a0)。最后分析此算法的時間復雜度及空間復雜度?！窘獯稹?voidinverse(listtype*A){ inttmp; intn=A->length; for(inti=0;i<=(n-1)/2;i++){ tmp=A->data[i];A->data[i]=A->data[n-i-1];A->data[n-i-1]=tmp; } }時間復雜度：需進行n/2次循環(huán)，因此時間復雜度為O(n)；空間復雜度：使用一個整形輔助存儲單元tmp，因此空間復雜度為O(1)。6.順序表的插入和刪除要求仍然保持各個元素原來的次序。設(shè)在等概率情形下,對有127個元素的順序表進行插入,平均需要移動多少個元素?刪除一個元素,又平均需要移動多少個元素?【解答】 若設(shè)順序表中已有n個元素。又設(shè)插入或刪除表中各個元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能在已有n個表項范圍內(nèi)刪除，所以每個元素位置刪除的概率為1/n。插入時平均移動元素個數(shù)AMN(AveragyMovingNumber)為 刪除時平均移動元素個數(shù)AMN為 7.利用順序表的操作，實現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時間復雜度，并分析(2)與(3)的時間復雜度出現(xiàn)差異的原因。 (1)從順序表中刪除具有給定值x的所有元素。 (2)從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。 (3)從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。 (4)將兩個有序順序表la,lb合并成一個新的有序順序表lc。 (5)從順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同?！窘獯稹?(1)從順序表中刪除具有給定值x的所有元素。voidDelValue(listtype*L,intx){inti=0,j; while(i<L->length) /*循環(huán),尋找具有值x的元素并刪除它*/if(L->data[i]==x){ /*刪除具有值x的元素,后續(xù)元素前移*/for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];L-length--; /*表長減1*/} elsei++;} (2)實現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：voidDelValue_s_to_t(listtype*L,ints,intt){ inti,j;if(L->length==0||s>=t){ printf(“Listisemptyorparametersareillegal!\n”);exit(1);} i=0; while(i<L->length) /*循環(huán),尋找具有值x的元素并刪除它*/if(L->data[i]>=s&&L->data[i]<=t){/*刪除滿足條件的元素,后續(xù)元素前移*/for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];L->length--; /*表長減1*/ } elsei++;} (3)實現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下：voidDelValue_s_to_t_1(listtype*L,intsintt){ inti,j,k;if(L->length==0||s>=t){ printf(“Listisemptyorparametersareillegal!\n”);exit(1);}for(i=0;i<L->length;i++) /*循環(huán),尋找值≥s的第一個元素*/if(L->data[i]>=s)break; /*退出循環(huán)時,i指向該元素*/if(i<L->length){for(j=1;i+j<L->length;j++)/*循環(huán),尋找值>t的第一個元素*/if(L->data[i+j]>t)break; /*退出循環(huán)時,i+j指向該元素*/ for(k=i+j;k<L->length;k++)/*刪除滿足條件的元素,后續(xù)元素前移*/L->data[k-j]=L->data[k]; L->length-=j; /*表長減j*/}} (4)實現(xiàn)將兩個有序順序表合并成一個新的有序順序表的函數(shù)如下：listtype*Merge(listtype*LA,listtype*LB){/*合并有序順序表LA與LB成為一個新的有序順序表并由函數(shù)返回 listtype*LC; intvalue1,value2; inti,j,k; initiatelist(LC);if(LA->length+LB->length>MAXSIZE){printf(“表上溢/n”;exit(1);} i=0,j=0,k=0; value1=LA->data[i]; value2=LB->data[j];while(i<LA->length&&j<LB->length){/*循環(huán),兩兩比較,小者存入結(jié)果表*/if(value1<=value2){ LC->data[k]=value1;i++;value1=LA->data[i];} else{LC->data[k]=value2;j++;value2=LB->data[j];}k++;}while(i<LA->length){ /*當LA表未檢測完,繼續(xù)向結(jié)果表傳送*/LC->data[k]=value1;i++;k++;value1=LA->data[i];} while(j<LB->length){ /*當LB表未檢測完,繼續(xù)向結(jié)果表傳送*/LC->data[k]=value2;j++;k++;value2=LB->data[j];} LC->length=k;returnLC;} (5)實現(xiàn)從表中刪除所有其值重復的元素的函數(shù)如下：voidDelDouble(listtype*L){inti,j,k;inttmp;if(L->length==0){printf(“表空\n”;exit(1);} i=0;while(i<L->length){ /*循環(huán)檢測*/j=i+1;tmp=L->data[i];while(j<L->length){ /*對于每一個i,重復檢測一遍后續(xù)元素*/if(tmp==L->data[j]){ /*如果相等,刪除此結(jié)點，后續(xù)元素前移*/ for(k=j+1;k<L->length;k++)L->data[k-1]=L->data[k];L->length--; /*表最后元素位置減1*/}elsej++;} i++; /*檢測完L->data[i],檢測下一個*/}}8.線性表可用順序表或鏈表存儲。試問： (1)兩種存儲表示各有哪些主要優(yōu)缺點? (2)如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應選用哪種存儲表示？為什么？ (3)若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示？為什么？【解答】(1)順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間中，實現(xiàn)順序存取或(按下標)直接存取。它的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不需要保持數(shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。(2)如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應選用鏈接存儲表示。如果采用順序存儲表示，必須在一個連續(xù)的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程序運行過程中，有的表占用的空間增長得快，有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。這個處理過程極其繁瑣和低效。如果采用鏈接存儲表示，一個表的存儲空間可以連續(xù)，可以不連續(xù)。表的增長通過動態(tài)存儲分配解決，只要存儲器未滿，就不會有表溢出的問題；表的收縮可以通過動態(tài)存儲釋放實現(xiàn)，釋放的空間還可以在以后動態(tài)分配給其他的存儲申請要求，非常靈活方便。對于n個表(包括表的總數(shù)可能變化)共存的情形，處理十分簡便和快捷。所以選用鏈接存儲表示較好。 (3)應采用順序存儲表示。因為順序存儲表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序存儲表示較好。

/*鏈表結(jié)構(gòu)的定義.為簡化起見，表元素我們使用整型數(shù)據(jù)此鏈表帶頭結(jié)點*/typedefstructmynode{ intdata;/*數(shù)據(jù)域：整型*/ structmynode*next;/*指針域*/}node,linklisttype;9.試寫出計算線性鏈表長度的算法。intlengthsl(linklisttype*L){ linklisttype*p; intlen; if(L==NULL){return–1;} p=L->next; /*p指向鏈表L的頭結(jié)點*/ len=0; while(p!=NULL){ len++; p=p->next;}returnlen;}10.設(shè)有一個表頭指針為h的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個結(jié)點?！窘獯稹縱oidLinkListInverse(linklisttype*L){ linklisttype*p,*pre,*next;if(L==NULL||L->next==NULL)return;/*表未初始化，或為空表*/ p=L->next;pre=L; while(p!=NULL){ /*循環(huán)修改鏈表中所有結(jié)點的后繼指針的指向*/ next=p->next; /*取當前結(jié)點的后繼指針*/ p->next=pre; /*當前結(jié)點的后繼改為指向其原來的前驅(qū)*/ pre=p,p=next; /*指針后移*/}L->next->next=NULL; /*原第一個結(jié)點改為最后一個結(jié)點*/L->next=pre; /*鏈表的頭結(jié)點指向原最后一個結(jié)點*/}11.設(shè)有一線性鏈表，其結(jié)點值均為整數(shù)。試將該線性鏈表分解為兩個線性鏈表，其中一鏈表中的結(jié)點值均為負整數(shù)，而另一鏈表中結(jié)點的值均為正整數(shù)，并刪除結(jié)點值為零的結(jié)點?！窘獯稹縱oidLinkListDispose(linklisttype*L,linklisttype*LA,linklisttype*LB){/*將鏈表L分解為LA、LB兩個鏈表，其中LA中結(jié)點值均為正，LB中結(jié)點值均為負，并刪除結(jié)點值為零的結(jié)點,最后釋放L的頭結(jié)點。*/ linklisttype*p,*pt,*pa,*pb;LA=initiatesl();pa=LA; /*指向LA中的最后一個結(jié)點*/LB=initiatesl();pb=LB; /*指向LB中的最后一個結(jié)點*/If(L==NULL||L->next==NUUL)return; /*L為空指針或L為空表*/p=L->next; /*p指向鏈表L的第一個結(jié)點*/while(p!=NULL) /*遍歷鏈表L*/ if(p->data>0){ /*將p鏈入鏈表LA的pa后*/ pa->next=p; pa=p; p=p->next;}elseif(p->data<0){ /*將p鏈入鏈表LB的pb后*/ pb->next=p; pb=p; p=p->next;}else{ /*刪除值為0的結(jié)點*/ pt=p->next; /*記錄當前結(jié)點的后繼，以便刪除當前結(jié)點*/ free(p); p=pt;} pa->next=NULL; pb->next=NULL; free(L);}12．設(shè)ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針,試設(shè)計一個算法,將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)?！窘獯稹縱oidlinklistMerge(linklisttype*LA,linklisttype*LB){/*合并有序鏈表LA與LB,結(jié)果存入LA中，并釋放LB的頭結(jié)點*/ linklisttype*pa,*pb,*pre,*pn; if(LA==NULL||LB==NULL||)return; if(LA->next==NULL){ /*LA為空表，則直接將LB鏈入LA即可*/ LA->next=LB->next; free(LB); retrun;}if(LB->next==NULL) return; /*LB為空表，則直接返回即可*/pa=LA->next,pb=LB->next,pre=LA;while(pa!=NULL&&pb!=NULL) /*循環(huán),兩兩比較,小者存入結(jié)果表*/if(pa->data>pb->next){ /*將pb鏈入LA，然后pb指針后移*/ pre->next=pb;pn=pb->next;pb->next=pa;pb=pn;pre=pre->next} else{ /*pa指針后移*/ pa=pa->next; pre=pre->next; } if(pb!=NULL) /*將pb剩余結(jié)點鏈入LA*/ pre->next=pb; free(LB);}13．設(shè)ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針,試設(shè)計一個算法,將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)?！窘獯稹縇inklisttype*linklistMerge_inverse(linklisttype*LA,linklisttype*LB){/*合并有序鏈表LA與LB,結(jié)果存入LC中，并釋放LA、LB的頭結(jié)點,函數(shù)返回LC*/ linklisttype*pa,*pb,*p; if(LA==NULL||LB==NULL||)return;LC=initiatesl();pa=LA->next,pb=LB->next;while(pa!=NULL&&pb!=NULL) /*循環(huán),兩兩比較,大者存入LC*/if(pa->data>pb->next){ /*將pa鏈為LC的第一個結(jié)點*/p=pa->next;pa->next=LC->next;LC->next=pa;pa=p;} else{ /*將pa鏈為LC的第一個結(jié)點*/p=pb->next;pb->next=LC->next;LC->next=pb;pb=p; } while(pa!=NULL){ /*將pa剩余結(jié)點鏈入LC*/p=pa->next;pa->next=LC->next;LC->next=pa;pa=p; } while(pb!=NULL){ /*將pb剩余結(jié)點鏈入LC*/p=pb->next;pb->next=LC->next;LC->next=pb;pb=p; } free(LA); free(LB);}14.在一個循環(huán)鏈表中尋找值為x的結(jié)點，并將該結(jié)點移到第一個結(jié)點之前?！窘獯稹吭O(shè)此循環(huán)鏈表為單鏈表，則其類型定義與一般單鏈表相同typedefstructmynodecyclelisttype;voidsearch_movefirst(cyclelisttype*CL,intx){ cyclelisttype*p,*pre; if(CL==NULL)return; p=CL->next; pre=CL; while(p!=CL)/*查找x，注意與普通單鏈表在判斷是否到表尾上的不同*/ if(p->data==x) break; else{ pre=p; p=p->next; }if(p!=CL){ /*查找成功*/ per->next=p->next; /*在原來位置刪除p*/ p->next=CL->next; /*p插入到CL后*/ CL->next=p;}16.鐵路進行列車調(diào)度時,常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，如右圖所示。試問： (1)設(shè)有編號為1,2,3,4,5,6的六輛列車,順序開入棧式結(jié)構(gòu)的站臺,則可能的出棧序列有多少種? (2)若進站的六輛列車順序如上所述,那么是否能夠得到435612,325641,154623和135426的出站序列,如果不能,說明為什么不能;如果能,說明如何得到(即寫出"進棧"或"出棧"的序列)。【解答】 (1)可能的不同出棧序列有種。 (2)不能得到435612和154623這樣的出棧序列。因為若在4,3,5,6之后再將1,2出棧，則1,2必須一直在棧中，此時1先進棧，2后進棧，2應壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。3562244441111111133232325325325632564325641534412222611131351354135421354213542617.試證明：若借助棧可由輸入序列1,2,3,…,n得到一個輸出序列p1,p2,p3,…,pn(它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i<j<k，使得pj<pk<pi。(提示：用反證法)【解答】 因為借助棧由輸入序列1,2,3,…,n，可得到輸出序列p1,p2,p3,…,pn，如果存在下標i,j,k，滿足i<j<k，那么在輸出序列中，可能出現(xiàn)如下5種情況：①i進棧，i出棧，j進棧，j出棧，k進棧，k出棧。此時具有最小值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最大值的排在pk位置，有pi<pj<pk,不可能出現(xiàn)pj<pk<pi的情形；②i進棧，i出棧，j進棧，k進棧，k出棧，j出棧。此時具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中間值的排在最后pk位置，有pi<pk<pj,不可能出現(xiàn)pj<pk<pi的情形；③i進棧，j進棧，j出棧，i出棧，k進棧，k出棧。此時具有中間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj<pi<pk,不可能出現(xiàn)pj<pk<pi的情形；④i進棧，j進棧，j出棧，k進棧，k出棧，i出棧。此時具有中間值的排在最前面pi位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk<pi<pj,也不可能出現(xiàn)pj<pk<pi的情形；⑤i進棧，j進棧，k進棧，k出棧，j出棧，i出棧。此時具有最大值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最小值的排在pk位置，有pk<pj<pi,也不可能出現(xiàn)pj<pk<pi的情形；18.將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。當向第0號棧插入一個新元素時，使top[0]增1得到新的棧頂位置，當向第1號棧插入一個新元素時，使top[1]減1得到新的棧頂位置。當top[0]+1==top[1]時或top[0]==top[1]-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(DoubleStack)結(jié)構(gòu)的類定義，并實現(xiàn)判?？?、判棧滿、插入、刪除算法?！窘獯稹縝ot[0]top[0]top[1]bot[1]bot[0]top[0]top[1]bot[1] 雙棧的類型定義如下：typedefstruct{ inttop0,top1; elemtypedata[MAXSIZE];}DoubleStack;判?？読ntDoubleStackEmpty(DoubleStack*DS,intStackNo){/*DS：指向雙棧的指針，StackNo:0或1，指定要判斷的是第0棧，還是第一棧 if(StackNo==0) return(DS->top0<0); else retrun(DS->top1>=MAXSIZE);}判棧滿intDoubleStackFull(DoubleStack*DS){ return(DS->top1-DS->top0==1);}入棧intPopDoubleStack(DoubleStack*DS,intStackNo,elemtypex){/*將數(shù)據(jù)元素x插入到棧StackNo中*/ if(DoubleStackFull(DS))return(FALSE);/*棧滿溢出*/ if(StackNo==0){/*對第0棧插入*/ DS->top0++; DS->data[top0]=x; } else{/*對第1棧插入*/ DS->top1--; DS->data[top1]=x; } return(TRUE);}刪除算法elemtypePushDoubleStack(DoubleStack*DS,intStackNo){/*從StackNo棧中刪除并返回一個元素，若棧空，則返回NULL*/ if(DoubleStackEmpty(DS,StackNo))return(NULL); if(StackNo==0){/*對0號棧進行操作*/ DS->top0--; return(DS->data[DS->top0+1]); } else{ DS->top1++; return(DS->data[DS->top1-1]);}}19.改寫順序棧的進棧成員函數(shù)Push(x)，要求當棧滿時執(zhí)行一個stackFull()操作進行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置?！窘獯稹縱oidpush(stack*S,elemtypex){if(StackEmpty(S))stackFull(S); //棧滿，做溢出處理 S->top++; S->data[S->top]=x; //進棧}voidstackFull(stack*S){elemtype*temp;temp=calloc(3*MAXSIZE,sizeof(elemtype));//創(chuàng)建體積大二倍的數(shù)組 for(inti=0;i<=S->top;i++) //傳送原數(shù)組的數(shù)據(jù)temp[i]=S->data[i]; free(S->data); //刪去原數(shù)組 MAXSIZE*=3; //數(shù)組最大體積增長二倍 S->data=temp; //新數(shù)組成為棧的數(shù)組空間}20.根據(jù)教案中給出的優(yōu)先級，回答以下問題： (1)在表達式求值的過程中，如果表達式e含有n個運算符和分界符，問操作數(shù)棧(NS)中最多可存入多少個元素？ (2)如果表達式e含有n個運算符，且括號嵌套的最大深度為6層，問棧中最多可存入多少個元素？【解答】(1)如果表達式e含有n個運算符和分界符，則可能的運算對象有n+1個。因此在利用后綴表達式求值時所用到的運算對象棧中最多可存入n+1個元素。(2)同上。21.表達式的中綴表示為a*x-b/x^2，試利用棧將它改為后綴表示ax*bx2^/-。寫出轉(zhuǎn)換過程中棧的變化。(^表示乘方運算)【解答】若設(shè)當前掃描到的運算符ch的優(yōu)先級為icp(ch)，該運算符進棧后的優(yōu)先級為isp(ch)，則可規(guī)定各個算術(shù)運算符的優(yōu)先級如下表所示。運算符;(^*,/,%+,-)isp017538icp086421 isp也叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)，icp也叫做棧外(incomingpriority)優(yōu)先數(shù)。當剛掃描到的運算符ch的icp(ch)大于isp(stack)時，則ch進棧；當剛掃描到的運算符ch的icp(ch)小于isp(stack)時，則位于棧頂?shù)倪\算符退棧并輸出。從表中可知，icp(“(”)最高，但當“(”進棧后，isp(“(”)變得極低。其它運算符進入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達式中相同優(yōu)先級的運算符自左向右計算的要求。運算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對“)”或棧底的“;”號與輸入流最后的“;”號配對時。前者將連續(xù)退出位于棧頂?shù)倪\算符，直到遇到“(”為止。然后將“(”退棧以對消括號，后者將結(jié)束算法。步序掃描項項類型動作棧的變化輸出0';'進棧,讀下一符號;1a操作數(shù)直接輸出,讀下一符號;A2*操作符isp(';')<icp('*'),進棧,讀下一符號;*A3x操作數(shù)直接輸出,讀下一符號;*ax4-操作符isp('*')>icp('-'),退棧輸出;ax*isp(';')<icp('-'),進棧,讀下一符號;-ax*5b操作數(shù)直接輸出,讀下一符號;-ax*b6/操作符isp('-')<icp('/'),進棧,讀下一符號;-/ax*b7x操作數(shù)直接輸出,讀下一符號;-/ax*bx8^操作符isp('/')<icp('^'),進棧,讀下一符號;-/^ax*bx92操作數(shù)直接輸出,讀下一符號;-/^ax*bx210;操作符isp('↑')>icp(';'),退棧輸出;-/ax*bx2^isp('/')>icp(';'),退棧輸出;-ax*bx2^/isp('-')>icp(';'),退棧輸出;ax*bx2^/-結(jié)束22.設(shè)循環(huán)隊列的容量為70（序號從1到70），經(jīng)過一系列入隊和退隊運算后，有：（1）front=15，rear=46；（2）front=45，rear=10問在上述兩種情況下，循環(huán)隊列中各有多少個元素？【解答】隊列中元素的個數(shù)為(MAXSIZE+rear-front)%MAXSIZE=(70+46-15)%70=31隊列中元素的個數(shù)為(MAXSIZE+rear-front)%MAXSIZE=(70+10-45)%70=3523.設(shè)用鏈表表示一個雙端隊列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿的條件