1、習題解答3.設n為正整數，分析下列各程序段中加下劃線的語句的執行次數。(1) for (int i = 1; i <= n; i+)for (int j = 1; j <= n; j+) cij = 0.0;for (int k = 1; k <= n; k+)(2) x = 0; y = 0;for (int i = 1; i <= n; i+)for (int j = 1; j <= i; j+) for (int k = 1; k <= j; k+) x = x + y; int i = 1, j = 1;while (i<=n &&am

2、p; j<=n) i = i + 1; j = j + i;(4) int i =1; dofor (int j = 1; j <= n; j+) i = i + j；while(i<100 + n);解出滿足上述不等式的 k值，即為語句i = i + 1的程序步數?！窘獯稹?1)n nnIf 13 二 ni =1 j =1 k £(2)n i jnin1=E Ej八i A j £ k Ti £ j占i £3*2'、-2 丿 2 y1 n(n 1)(2 n 1)1 n(n 1) ,"T-n(n 1)(n 2)_ 262

3、2 _6(3)i =1時，i =2，j =j + i = 1+ 2 =2 + 1，i = 2時,i = 3，j = j +i =(2 +1 ) +3 = 3 + 1+ 2i = 3時,i = 4，j = j +i =(3 +1 + 2)+ 4 = 4+ 1 + 2 + 3i = 4時,i = 5，j = j +i =(4 +1 + 2+ 3 ) + 5=5 + 1 + 2 +3 + 4i = k時,i = k +1，j=j+ i =(k +1 ) + ( 1 +2 + 3 + 4 +j=kk1 !亠一 i<ni#k 1k k 1Lk23k3 .n22(4) for語句每執行一次，語句i=

4、i+j將執行n次，而i的值會增加呵 12因此，當for語句執行k次后，i的值將變為2故最終for語句的執行次數k為滿足1 kn(n 1) _100 n2的最小整數k，語句i = i + j 的程序步數為n*k。4.試編寫一個函數計算 n!*2 n的值，結果存放于數組 AarraySize的第n個數組元素中，0 < n < arraySize。若設計算機中允許的整數的最大值為maxInt，則當n>arraySize 或者對于k某一個k (0< k < n)，使得k!*2 > maxInt 時，應按出錯處理。可有如下三種不同的出錯處理方式：(1) 用printf

5、顯示錯誤信息及exit(1)語句來終止執行并報告錯誤；(2) 用返回整數函數值 0, 1來實現算法，以區別是正常返回還是錯誤返回；(3) 在函數的參數表設置一個引用型的整型變量來區別是正常返回還是某種錯誤返回。 試討論這三種方法各自的優缺點，并以你認為是最好的方式實現它?！窘獯稹?i nclude <stdio.h>const int arraySize = 100;const int MaxI nt = 0x7fffffff;int calc( int T , int n ) int i, value = 1;T0=1;if ( n != 0 ) int edge = MaxI

6、nt / n / 2;for ( i = 1; i < n; i+ ) value *= i*2;Ti = value;if ( value > edge ) retur n 0;value *= n * 2;Tn = value;n” ,n,Tn);return 1;void main ( ) int AarraySize;int i;for ( i = 0; i < arraySize; i+ )if ( !calc ( A, i ) ) prin tf("failed at %d .n", i );break;/* 順序表結構的定義為簡化起見，表元素

7、我們使用整型數據 typedef struct /*int dataMAXSIZE; /*int len gth;/*listtype;5.設有一個線性表(a 0, a數據元素從dataO處開始存儲-typedef 的使用*/注意數據域*/表長*/數組元素位置。請編寫一個函數將這個線性表原地逆置,*/a n-2, a n-i)存放在一個一維數組AarraySize 中的前n個即將數組的前n個原址內容置換為(an-1, a n-2,a 1, a 0)。最后分析此算法的時間復雜度及空間復雜度。 【解答】void in verse (listtype * A) int tmp;int n= A-&g

8、t;le ngth;for( int i = 0; i <= ( n-1 ) / 2; i+ )=tmp;tmp = A->datai; A->datai= A->data n-i-1; A->data n-i-1時間復雜度：需進行 n/2次循環，因此時間復雜度為0(n);空間復雜度：使用一個整形輔助存儲單元tmp，因此空間復雜度為0(1)。6順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下，對有127個元素的順序表進行插入，平均需要移動多少個元素？刪除一個元素，又平均需要移動多少個元素？【解答】若設順序表中已有 n個元素。又設插入或刪除表中各個

9、元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能在已有 n個表項范圍內刪除，所以每個元素位置刪除的概率為1/n。插入時平均移動元素個數 AMN(Averagy Movi ng Number ) 為AMN(n (n - 1)亠 亠 10) =n63 .52刪除時平均移動元素個數1AMN(n -in i gAMN為-1) =1(n -1) (n - 2)川汕1 0) J (n "1)n n7. 利用順序表的操作，實現以下的函數。并分析你所編制的函數的時間復雜度，并分析與(3)的時間復雜度出現差異的原因

10、。(1) 從順序表中刪除具有給定值x的所有元素。(2) 從順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。(3) 從有序順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。(4) 將兩個有序順序表la,lb 合并成一個新的有序順序表lc。(5) 從順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。【解答】(1) 從順序表中刪除具有給定值x的所有元素。void DelValue(listtype * L, i nt x )int i = 0, j;while ( i < L->length )/*循環，尋找具有值x的元素并刪除它*/if (L->

11、;datai = x ) /*刪除具有值x的元素，后續元素前移*/for (j = i;j < L->le ngth_1; j+ ) L->dataj = L->dataj+1;L-length-;/* 表長減 1*/else i+;(2) 實現刪除其值在給定值s與t之間(要求s小于t)的所有元素的函數如下:void DelValue_s_to_t (listtype *L,int s, i nt t)int i,j;if ( L->le ngth = 0 | s >= t ) printf( "List is empty or parameter

12、s are illegal!n” ); exit(1); i = 0;while ( i < L->length)/*循環，尋找具有值x的元素并刪除它*/if (L->datai>=s &&L->datai<= t)/*刪除滿足條件的元素，后續元素前移*/for ( j = i; j < L->le ngth_1; j+ ) L->dataj = L->dataj+1;L->length-;/* 表長減 1*/else i+;(3) 實現從有序順序表中刪除其值在給定值 void DelValue_s_to_t_1

13、 (listtype *L,i nt s int t)int i,j,k;if ( L->le ngth = 0 | s >= t ) printf(" List is emptyfor (i = 0; i < L->le ngth; i+ )if ( L->datai >= s ) break;if ( i < L->le ngth ) for (j = 1; i + j < L->le ngth; j+ )/* if (L->datai+j > t ) break;for (k = i+j; k < L

14、->length; k+ ) /* L->datak-j = L->datak;L->le ngth-= j;s與t之間的所有元素的函數如下:n”); exit(1); /*循環，尋找值 > s的第一個元素*/*退出循環時,i指向該元素*/循環，尋找值> t的第一個元素*/*退出循環時，i+j 指向該元素*/ 刪除滿足條件的元素，后續元素前移*/*表長減j*/(4) 實現將兩個有序順序表合并成一個新的有序順序表的函數如下：listtype * Merge(listtype *LA,listtype *LB )/*合并有序順序表LA與LB成為一個新的有序順序表

15、并由函數返回listtype *LC;int value1,value2;int i,j,k;ini tiatelist(LC);if (LA->length + LB->length > MAXSIZE) printf("表上溢 /n ” ; exit(1);i = 0, j = 0, k = 0;value1 = LA->datai;value2 = LB->dataj;while (i < LA->le ngth && j < LB->le ngth ) /*循環，兩兩比較，小者存入結果表*/if (valu

16、e1 <= value2)LC->datak = value1; i+; value仁LA->datai;else LC->datak = value2; j+; value2=LB->dataj;k+;while( i < LA->length)/*當LA表未檢測完，繼續向結果表傳送*/LC->datak = value1; i+; k+; value1 = LA->datai;while( j < LB->length)/*當LB表未檢測完，繼續向結果表傳送*/LC->datak = value2; j+; k+; v

17、alue2 = LB->dataj;LC->le ngth = k;return LC;(5) 實現從表中刪除所有其值重復的元素的函數如下:void DelDouble(listtype *L)int i,j,k;int tmp;if(L->le ngth = 0 )printf("表空 n” ； exit(1); /*循環檢測*/*對于每一個i,重復檢測一遍后續元素*/*如果相等，刪除此結點，后續元素前移 */i=0;while ( i < L->le ngth ) j = i + 1;tmp = L->datai;while( j < L

18、->length ) if( tmp = L->dataj) for( k = j+1; k < L->length; k+ ) L->datak-1 = L->datak;L->le ngth-;/*表最后元素位置減1*/else j+;/*檢測完L->datai,檢測下一個*/i+；8. 線性表可用順序表或鏈表存儲。試問：(1) 兩種存儲表示各有哪些主要優缺點 ？(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用哪種存儲表示？為什么？(3) 若表的總數基本穩定， 且很少進行插入和

19、刪除， 但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示？為什么？【解答】(1) 順序存儲表示是將數據元素存放于一個連續的存儲空間中，實現順序存取或(按下標)直接存取。它的存儲效率高，存取速度快。但它的空間大小一經定義，在程序整個運行期間不會發生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態分配和釋放，且只要存儲器中還有空間，就不會產生存儲溢出的問題。 同時在插入和刪除時不需要保持數據元素原來的物理順序， 只需要保持原來的邏輯順序，因此不必移動數據，只需修改它們的鏈接指針

20、，修改效率較高。但存取表中的數據元素時，只能循鏈順序訪問，因此存取效率不高。(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用鏈接存儲表示。如果采用順序存儲表示， 必須在一個連續的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程序運行過程中，有的表占用的空間增長得快， 有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。這個處理過程極其繁瑣和低效。如果

21、采用鏈接存儲表示， 一個表的存儲空間可以連續，可以不連續。表的增長通過動態存儲分配解決，只要存儲器未滿，就不會有表溢出的問題； 表的收縮可以通過動態存儲釋放實現， 釋放的空間還可以在以后動態分配給其他的存儲申請要求，非常靈活方便。對于n個表(包括表的總數可能變化)共存的情形，處理十分簡便和快捷。所以選用鏈接存儲表示較好。(3) 應采用順序存儲表示。 因為順序存儲表示的存取速度快， 但修改效率低。若表的總 數基本穩定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素， 這時采用順序 存儲表示較好。.為簡化起見，表元素我們使用整型數據*/數據域：整型*/指針域*/* 鏈表結構的定義 此鏈表帶

22、頭結點typedef struct myno de int data;/*struct mynode *n ext; /* no de, li nklisttype;9. 試寫出計算線性鏈表長度的算法。int lengthsl(linklisttype *L)lin klisttype * p;int len;/* p 指向鏈表L的頭結點*/if(L = NULL)return 1; p = L_>n ext;len = 0;while(p != NULL) len+; p = p_>n ext;return len;10. 設有一個表頭指針為 h的單鏈表。試設計一個算法，通過遍歷

23、一趟鏈表，將鏈表中所有 結點的鏈接方向逆轉，如下圖所示。要求逆轉結果鏈表的表頭指針 h指向原鏈表的最后一個 結點。表未初始化，或為空表*/p = L_>n ext;pre = L;while( p != NULL ) n ext = p->n ext; p_>next = pre; pre = p , p=n ext;L-> next-next = NULL; L_>next = pre;【解答】void LinkListInverse(linklisttype *L)lin klisttype *p, *pre, * next;if(L = NULL | L-&

24、gt; next = NULL ) return; /*/*循環修改鏈表中所有結點的后繼指針的指向*/*取當前結點的后繼指針*/*當前結點的后繼改為指向其原來的前驅*/*指針后移*/*原第一個結點改為最后一個結點*/*鏈表的頭結點指向原最后一個結點*/11. 設有一線性鏈表，其結點值均為整數。試將該線性鏈表分解為兩個線性鏈表，其中一鏈 表中的結點值均為負整數，而另一鏈表中結點的值均為正整數，并刪除結點值為零的結點。【解答】void Li nkListDispose(li nklisttype * L,li nklisttype * LA,li nklisttype * LB)/*將鏈表L分解為

25、LA、LB兩個鏈表，其中LA中結點值均為正，LB中結點值均為負， 并刪除結點值為零的結點，最后釋放L的頭結點。*/lin klisttype *p , *pt , *pa, * pb;LA = in itiatesl();pa = LA;LB = in itiatesl();pb = LB;If(L = NULL | L->n ext = NUUL) return;p = L_>n ext;while(p != NULL)if(p->data > 0)pa->next = p;pa = p; p = p_>n ext;elseif(p->data &l

26、t; 0) pb->next = p; pb = p;p = p_>n ext;elsept = p_>n ext;free(p); p = pt;pa-> next = NULL;pb-> next = NULL;free(L);/*指向LA中的最后一個結點*/*指向LB中的最后一個結點*/*L為空指針或L為空表*/*p指向鏈表L的第一個結點*/*遍歷鏈表L*/*將p鏈入鏈表LA的pa后*/*將p鏈入鏈表LB的pb后*/*刪除值為0的結點*/*記錄當前結點的后繼，以便刪除當前結點*/12. 設ha和hb分別是兩個帶表頭結點的非遞減有序單鏈表的表頭指針，試設計一個

27、算法將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲空間。表中允許有重復的數據。【解答】void linklistMerge(linklisttype *LA,linklisttype *LB )/*合并有序鏈表LA與LB,結果存入LA中，并釋放LB的頭結點*/lin klisttype *pa, *pb , *pre ,*p n;if(LA = NULL | LB = NULL |) return; if(LA-> next = NULL)LA->n ext = LB->n ext;free(LB);retru n

28、;if(LB-> next = NULL)return;pa = LA->n ext, pb = LB->n ext ,pre=LA; while (pa != NULL && pb != NULL) if(pa->data > pb->n ext) pre->next = pb;pn = pb->n ext;pb->next = pa; pb = pn;pre = pre->n extelsepa = pa->n ext; pre = pre->n ext;if(pb != NULL)pre->n

29、ext = pb;free(LB);/*LA為空表，則直接將 LB鏈入LA即可*/*LB為空表，則直接返回即可 */*循環，兩兩比較，小者存入結果表*/*將pb鏈入LA,然后pb指針后移*/*pa指針后移*/*將pb剩余結點鏈入LA*/13. 設ha和hb分別是兩個帶表頭結點的非遞減有序單鏈表的表頭指針，試設計一個算法將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲空間。表中允許有重復的數據?！窘獯稹縇in klisttype * lin klistMergenverse(li nklisttype *LA,li nklisttype

30、 *LB )/*合并有序鏈表LA與LB,結果存入LC中，并釋放LA、LB的頭結點，函數返回LC*/lin klisttype *pa，*pb，*p;if(LA = NULL | LB = NULL |) return; LC = ini tiatesl();pa = LA->n ext，pb = LB->n ext;while (pa != NULL && pb != NULL) if(pa->data > pb->n ext) p = pa->n ext;pa->next = LC->n ext;LC->n ext = p

31、a; pa = p;else/*循環，兩兩比較，大者存入LC*/*將pa鏈為LC的第一個結點*/*將pa鏈為LC的第一個結點*/p = pb->n ext;pb->next = LC->n ext; LC->n ext = pb;pb = p；while(pa != NULL) p = pa->n ext;pa->n ext = LC->n ext;LC->next = pa; pa = p;while(pb != NULL) p = pb->n ext; pb->n ext = LC->n ext;LC->next =

32、pb; pb = p;free(LA);free(LB);/*將pa剩余結點鏈入LC*/*將pb剩余結點鏈入LC*/14.在一個循環鏈表中尋找值為x的結點，并將該結點移到第一個結點之前?！窘獯稹吭O此循環鏈表為單鏈表，則其類型定義與一般單鏈表相同typedef struct mynode cyclelisttype;void search_movefirst(cyclelisttype *CL, int x)cyclelisttype * p , *pre;if(CL = NULL) retur n;p = CL->n ext;pre = CL;while(p != CL)/*查找x，注意

33、與普通單鏈表在判斷是否到表尾上的不同*/if(p->data = x)break;elsepre = p; p = p->n ext;if(p != CL)per->n ext = p->n ext; p->next = CL->n ext; CL->next = p;/*查找成功*/*在原來位置刪除p*/*p插入到CL后*/16.鐵路進行列車調度時，常把站臺設計成棧式結構的站臺，如 右圖所示。試問：(1) 設有編號為123,4,5,6的六輛列車，順序開入棧式結構的站臺，則可能的出棧序列有多少種？(2) 若進站的六輛列車順序如上所述 ,那么是否能夠得到

34、 435612, 325641, 154623 和 135426的出站序列，如果不能，說明為什么不能；如果能，說明如何得到(即寫出”進棧” 或"出棧”的序列)?！窘獯稹?1) 可能的不同出棧序列有 1/(61) C1® 132 種。(2) 不能得到435612和154623這樣的出棧序列。因為若在 4, 3, 5, 6 之后再將1,2 出棧，則1, 2必須一直在棧中，此時 1先進棧，2后進棧，2應壓在1上面，不可能1先于 2出棧。154623也是這種情況。出棧序列 325641和135426可以得到。17. 試證明：若借助?？捎奢斎胄蛄?1, 2, 3,n得到一個輸出序列

35、p1, p2, p3,pn (它 是輸入序列的某一種排列)，則在輸出序列中不可能出現以下情況，即存在 i < j <k ，使 得Pj < P k < pi。(提示：用反證法)【解答】因為借助棧由輸入序列 1,2, 3,n，可得到輸出序列 P1, p 2, p 3,p n，如果存在下標i, j, k ，滿足i< j < k ，那么在輸出序列中，可能出現如下5種情況： i進棧，i出棧，j進棧，j出棧，k進棧，k出棧。此時具有最小值的排在最前面p位置，具有中間值的排在其后pj位置，具有最大值的排在 pk位置，有pi < p j < p k,不可能出現p

36、j < p k < p i的情形； i進棧，i出棧，j進棧，k進棧，k出棧，j出棧。此時具有最小值的排在最前面p位置，具有最大值的排在 pj位置，具有中間值的排在最后pk位置，有pi < pk< pj ,不可能出現pj < p k < p i的情形； i進棧，j進棧，j出棧，i出棧，k進棧，k出棧。此時具有中間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < p i < p k,不可能出現pj < p k < p i的情形； i進棧，j進棧，j出棧，k進棧，k出棧，i出棧。此時具有中間值的排在最前面pi位置，具有最大值

37、的排在其后pj位置，具有最小值的排在 pk位置，有pk < p i < p j,也不可能出現pj < p k < p i的情形； i進棧，j進棧，k進棧，k出棧，j出棧，i出棧。此時具有最大值的排在最前面pi位置，具有中間值的排在其后口位置，具有最小值的排在 pk位置，有pk < p j < p i,也 不可能出現pj < P k < p i的情形;18. 將編號為0和1的兩個棧存放于一個數組空間Vm中，棧底分別處于數組的兩端。當第0號棧的棧頂指針top0等于-1時該棧為空，當第1號棧的棧頂指針top1等于m時該棧 為空。兩個棧均從兩端向中間增長

38、。當向第 0號棧插入一個新元素時，使top0增1得到新的棧頂位置，當向第1號棧插入一個新元素時，使top1減1得到新的棧頂位置。當top0+1= top1時或top0 = top1-1 時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結構的類定義，并實現判?？?、判棧滿、插入、刪 除算法。【解答】,"叭 le.9i rr.-. i.r.-. r.-i rr.oi“11 'M »! ! !»!I I叭!'tt ttbot0top0top1bot1雙棧的類型定義如下：typedef structint top0,t

39、op1;elemtype dataMAXSIZE; DoubleStack;判?？読nt DoubleStackEmpty(DoubleStack * DS,i nt StackNo)/*DS :指向雙棧的指針，StackNo:0或1,指定要判斷的是第0棧，還是第一棧if(StackNo=0)return(DS->top0 < 0);elseretru n(DS->top1 >= MAXSIZE);判棧滿int DoubleStackFull(DoubleStack * DS) return(DS->top1-DS->top0=1);入棧int PopDou

40、bleStack(DoubleStack * DS, int StackNo,elemtype x)/*將數據元素x插入到棧StackNo中*/if(DoubleStackFull(DS) return(FALSE);/*棧滿溢出 */if(StackNo=0)/* 對第 0 棧插入 */DS->top0+; DS->datatop0=x;else/*對第1棧插入*/DS->top1-;DS->datatop1=x; return(TRUE);刪除算法elemtype PushDoubleStack(DoubleStack * DS,i nt StackNo)/*從St

41、ackNo棧中刪除并返回一個元素，若?？?，則返回 NULL*/ if(DoubleStackEmpty(DS,StackNo) return(NULL);if(StackNo=0)/* 對0號棧進行操作*/DS->top0-; return(DS->dataDS->top0+1);elseDS->top1+; return(DS->dataDS->top1-1);19.改寫順序棧的進棧成員函數 Push(x)，要求當棧滿時執行一個 stackFull()操作進行棧滿處理。其功能是：動態創建一個比原來的棧數組大二倍的新數組，代替原來的棧數組，原 來棧數組中的元

42、素占據新數組的前MaxSize位置?！窘獯稹縱oid push(stack * S,elemtype x) if(StackEmpty(S) stackFull(S);/ 棧滿，做溢出處理S->top +;S->dataS->top = x;/ 進棧 void stackFull(stack *S)elemtype *temp;創建體積大二倍的數組/傳送原數組的數據/刪去原數組/數組最大體積增長二倍/新數組成為棧的數組空間temp=calloc(3*MAXSIZE,sizeof(elemtype); / for ( int i = 0; i <= S->top;

43、i+ )tempi = S->datai;free(S->data);MAXSIZE *= 3;S->data = temp;20.根據教案中給出的優先級，回答以下問題：(1) 在表達式求值的過程中，如果表達式e含有n個運算符和分界符，問操作數棧(NS)中最多可存入多少個元素？(2) 如果表達式e含有n個運算符，且括號嵌套的最大深度為 6層，問棧中最多可存入 多少個元素？【解答】(1) 如果表達式e含有n個運算符和分界符，則可能的運算對象有 n+1個。因此在利用后綴表達式求值時所用到的運算對象棧中最多可存入n+1個元素。(2) 同上。21.表達式的中綴表示為 a * x -

44、b / xA2，試利用棧將它改為后綴表示ax * bx2A/ -。寫出轉換過程中棧的變化。(A表示乘方運算)【解答】若設當前掃描到的運算符ch的優先級為icp(ch)，該運算符進棧后的優先級為isp(ch)，則可規定各個算術運算符的優先級如下表所示。運算符ch的icp(ch)小于isp(stack)時，則位于棧頂的運算符退棧并輸出。從表中可知， icp( “(”)最高，但當“(”進棧后，isp( “(”)變得極低。其它運算符進入棧中后優先數 都升1,這樣可體現在中綴表達式中相同優先級的運算符自左向右計算的要求。運算符優先 數相等的情況只出現在括號配對“)”或棧底的“；”號與輸入流最后的“；”號

45、配對時。前 者將連續退出位于棧頂的運算符，直到遇到“(”為止。然后將“(”退棧以對消括號，后者將結束算法。步序掃 描 項項類型動作棧的 變化輸出0''進棧,讀下一付號51a操作數直接輸出,讀下一付號5A2*操作符isp ('；讀下一付號')< icp ( ' * '),進棧， *5A3x操作數直接輸出,讀下一付號 *5a x4-操作符isp ( ' * ') >輸出icp ('-'),退棧5a x *isp ('；讀下一付號')< icp ('-'),進棧，a x

46、*5b操作數直接輸出,讀下一付號a x * b6/操作符isp ('-') <下一符號icp ( '/'),進棧，讀;-/a x * b7x操作數直接輸出,讀下一付號;-/a x * b x8A操作符isp ( ' / ') <下一符號icp ( 'A'),進棧，讀;-/Aa x * b x92操作數直接輸出,讀下一付號;-/Aa x * b x 2105操作符isp ( ' f 出')> icp (''),退棧輸;-/a x * b x 2Aisp ( ' / '

47、) >icp (''),退棧a x * b x 2A/輸出isp ( ' - ' ) > icp (''), 退棧；a x * b x 2A/輸出-結束22. 設循環隊列的容量為70 (序號從1到70),經過一系列入隊和退隊運算后，有：(1) front=15 ， rear=46 ；(2) front=45 ， rear=10問在上述兩種情況下，循環隊列中各有多少個元素？【解答】(1) 隊列中元素的個數為 (MAXSIZE+rear-fro nt) %MAXSIZE = (70+46-15)%70=31(2) 隊列中元素的個數為 (MAXSIZE+rear-fro nt) %MAXSIZE = (70+10-45)%70=3523. 設用鏈表表示一個雙端隊列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結構的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿的條件。設此隊