線性結(jié)構(gòu)習(xí)題解答習(xí)題解答3.設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語(yǔ)句的執(zhí)行次數(shù)。(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+) cij = cij + aik * bkj; (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;(3)int i = 1, j = 1; while (i<=n && j<=n) i = i + 1; j = j + i; (4)*int i =1; do for (int j = 1; j <= n; j+) i = i + j; while(i<100 + n);【解答】(1) (2) (3)i = 1時(shí)，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2時(shí)，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3時(shí)，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4時(shí)，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，i = k時(shí)，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + + k )，解出滿足上述不等式的k值，即為語(yǔ)句i = i + 1的程序步數(shù)。 (4) for語(yǔ)句每執(zhí)行一次，語(yǔ)句i=i+j將執(zhí)行n次，而i的值會(huì)增加因此，當(dāng)for語(yǔ)句執(zhí)行k次后，i的值將變?yōu)楣首罱Kfor語(yǔ)句的執(zhí)行次數(shù)k為滿足的最小整數(shù)k，語(yǔ)句i = i + j的程序步數(shù)為n*k。4.試編寫(xiě)一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組AarraySize的第n個(gè)數(shù)組元素中，0 £ n £ arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)n>arraySize或者對(duì)于某一個(gè)k (0 £ k £ n)，使得k!*2k > maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式：(1) 用printf顯示錯(cuò)誤信息及exit(1)語(yǔ)句來(lái)終止執(zhí)行并報(bào)告錯(cuò)誤；(2) 用返回整數(shù)函數(shù)值0, 1來(lái)實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來(lái)區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它?！窘獯稹?include <stdio.h>const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T , int n ) int i, value = 1;T0=1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i < n; i+ ) value *= i*2;Ti = value;if ( value > edge ) return 0;value *= n * 2;Tn = value;printf("A %d = %dn”,n,Tn);return 1;void main ( ) int AarraySize;int i;for ( i = 0; i < arraySize; i+ )if ( !calc ( A, i ) ) printf("failed at %d .n", i );break;/*-順序表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-數(shù)據(jù)元素從data0處開(kāi)始存儲(chǔ)-*/typedef struct /*注意typedef的使用*/ int dataMAXSIZE; /*數(shù)據(jù)域*/int length; /*表長(zhǎng)*/listtype;5.設(shè)有一個(gè)線性表 (a0, a1, , an-2, an-1) 存放在一個(gè)一維數(shù)組AarraySize中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫(xiě)一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為 (an-1, an-2, , a1, a0)。最后分析此算法的時(shí)間復(fù)雜度及空間復(fù)雜度?！窘獯稹縱oid inverse (listtype * A) int tmp;int n= A->length;for( int i = 0; i <= ( n-1 ) / 2; i+ )tmp = A->datai; A->datai = A->datan-i-1; A->datan-i-1 = tmp;時(shí)間復(fù)雜度：需進(jìn)行n/2次循環(huán)，因此時(shí)間復(fù)雜度為O(n)；空間復(fù)雜度：使用一個(gè)整形輔助存儲(chǔ)單元tmp，因此空間復(fù)雜度為O(1)。6.順序表的插入和刪除要求仍然保持各個(gè)元素原來(lái)的次序。設(shè)在等概率情形下, 對(duì)有127個(gè)元素的順序表進(jìn)行插入, 平均需要移動(dòng)多少個(gè)元素? 刪除一個(gè)元素, 又平均需要移動(dòng)多少個(gè)元素?【解答】若設(shè)順序表中已有n個(gè)元素。又設(shè)插入或刪除表中各個(gè)元素的概率相等，則在插入時(shí)因有n+1個(gè)插入位置(可以在表中最后一個(gè)表項(xiàng)后面追加)，每個(gè)元素位置插入的概率為1/(n+1)，但在刪除時(shí)只能在已有n個(gè)表項(xiàng)范圍內(nèi)刪除，所以每個(gè)元素位置刪除的概率為1/n。插入時(shí)平均移動(dòng)元素個(gè)數(shù)AMN(Averagy Moving Number )為刪除時(shí)平均移動(dòng)元素個(gè)數(shù)AMN為 7.利用順序表的操作，實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時(shí)間復(fù)雜度，并分析(2)與(3)的時(shí)間復(fù)雜度出現(xiàn)差異的原因。(1) 從順序表中刪除具有給定值x的所有元素。(2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。(3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。(4) 將兩個(gè)有序順序表la,lb合并成一個(gè)新的有序順序表lc。(5) 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同?！窘獯稹?1) 從順序表中刪除具有給定值x的所有元素。void DelValue(listtype * L, int x )int i = 0, j;while ( i < L->length )/*循環(huán), 尋找具有值x的元素并刪除它*/if (L->datai = x ) /*刪除具有值x的元素, 后續(xù)元素前移*/for (j = i;j < L->length-1; j+ ) L->dataj = L->dataj+1;L-length-; /*表長(zhǎng)減1*/else i+;(2) 實(shí)現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：void DelValue_s_to_t (listtype *L,int s, int t)int i,j;if ( L->length = 0 | s >= t ) printf(“List is empty or parameters are illegal!n”); exit(1); i = 0;while ( i < L->length)/*循環(huán), 尋找具有值x的元素并刪除它*/if (L->datai>=s &&L->datai<= t)/*刪除滿足條件的元素, 后續(xù)元素前移*/for ( j = i; j < L->length-1; j+ ) L->dataj = L->dataj+1;L->length-; /*表長(zhǎng)減1*/else i+;(3) 實(shí)現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下：void DelValue_s_to_t_1 (listtype *L,int s int t)int i,j,k;if ( L->length = 0 | s >= t ) printf(“List is empty or parameters are illegal!n”); exit(1); for (i = 0; i < L->length; i+ ) /*循環(huán), 尋找值 s 的第一個(gè)元素*/if ( L->datai >= s ) break; /*退出循環(huán)時(shí), i指向該元素*/if ( i < L->length ) for (j = 1; i + j < L->length; j+ )/*循環(huán), 尋找值 > t 的第一個(gè)元素*/if (L->datai+j > t ) break;/*退出循環(huán)時(shí), i+j指向該元素*/ for (k = i+j; k < L->length; k+ ) /*刪除滿足條件的元素, 后續(xù)元素前移*/L->datak-j = L->datak; L->length-= j; /*表長(zhǎng)減j*/(4) 實(shí)現(xiàn)將兩個(gè)有序順序表合并成一個(gè)新的有序順序表的函數(shù)如下：listtype * Merge(listtype *LA,listtype *LB )/*合并有序順序表LA與LB成為一個(gè)新的有序順序表并由函數(shù)返回listtype *LC;int value1,value2;int i,j,k;initiatelist(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->length && j < LB->length ) /*循環(huán), 兩兩比較, 小者存入結(jié)果表*/if (value1 <= value2)LC->datak = value1; i+; value1=LA->datai; else LC->datak = value2; j+; value2=LB->dataj;k+; while( i < LA->length)/*當(dāng)LA表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/LC->datak = value1; i+; k+; value1 = LA->datai; while( j < LB->length)/*當(dāng)LB表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/LC->datak = value2; j+; k+; value2 = LB->dataj;LC->length = k;return LC;(5) 實(shí)現(xiàn)從表中刪除所有其值重復(fù)的元素的函數(shù)如下：void DelDouble(listtype *L)int i,j,k;int tmp;if(L->length = 0 ) printf(“表空n”; exit(1); i=0;while ( i < L->length ) /*循環(huán)檢測(cè)*/j = i + 1; tmp = L->datai;while( j < L->length ) /*對(duì)于每一個(gè)i, 重復(fù)檢測(cè)一遍后續(xù)元素*/if( tmp = L->dataj) /*如果相等,刪除此結(jié)點(diǎn)，后續(xù)元素前移*/ for( k = j+1; k < L->length; k+ ) L->datak-1 = L->datak;L->length-; /*表最后元素位置減1*/else j+; i+;/*檢測(cè)完L->datai, 檢測(cè)下一個(gè)*/8.線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用哪種存儲(chǔ)表示？為什么？(3) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？【解答】(1) 順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)連續(xù)的存儲(chǔ)空間中，實(shí)現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問(wèn)題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問(wèn)，因此存取效率不高。(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用鏈接存儲(chǔ)表示。如果采用順序存儲(chǔ)表示，必須在一個(gè)連續(xù)的可用空間中為這n個(gè)表分配空間。初始時(shí)因不知道哪個(gè)表增長(zhǎng)得快，必須平均分配空間。在程序運(yùn)行過(guò)程中，有的表占用的空間增長(zhǎng)得快，有的表占用的空間增長(zhǎng)得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進(jìn)行元素的插入時(shí)就必須成片地移動(dòng)其他的表的空間，以空出位置進(jìn)行插入；在元素刪除時(shí)，為填補(bǔ)空白，也可能移動(dòng)許多元素。這個(gè)處理過(guò)程極其繁瑣和低效。如果采用鏈接存儲(chǔ)表示，一個(gè)表的存儲(chǔ)空間可以連續(xù)，可以不連續(xù)。表的增長(zhǎng)通過(guò)動(dòng)態(tài)存儲(chǔ)分配解決，只要存儲(chǔ)器未滿，就不會(huì)有表溢出的問(wèn)題；表的收縮可以通過(guò)動(dòng)態(tài)存儲(chǔ)釋放實(shí)現(xiàn)，釋放的空間還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請(qǐng)要求，非常靈活方便。對(duì)于n個(gè)表(包括表的總數(shù)可能變化)共存的情形，處理十分簡(jiǎn)便和快捷。所以選用鏈接存儲(chǔ)表示較好。(3) 應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。/*-鏈表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-此鏈表帶頭結(jié)點(diǎn)-*/typedef struct mynodeint data; /*數(shù)據(jù)域：整型*/struct mynode *next; /*指針域*/ node, linklisttype;9.試寫(xiě)出計(jì)算線性鏈表長(zhǎng)度的算法。int lengthsl(linklisttype *L)linklisttype * p;int len;if(L = NULL)return 1;p = L->next;/* p指向鏈表L的頭結(jié)點(diǎn)*/len = 0;while(p != NULL)len+;p = p->next;return len;10.設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)?！窘獯稹縱oid LinkListInverse(linklisttype *L)linklisttype *p, *pre, *next;if(L = NULL | L->next = NULL ) return; /*表未初始化，或?yàn)榭毡?/ p = L->next;pre = L;while( p != NULL ) /*循環(huán)修改鏈表中所有結(jié)點(diǎn)的后繼指針的指向*/next = p->next;/*取當(dāng)前結(jié)點(diǎn)的后繼指針*/p->next = pre;/*當(dāng)前結(jié)點(diǎn)的后繼改為指向其原來(lái)的前驅(qū)*/pre = p , p=next;/*指針后移*/L->next->next = NULL;/*原第一個(gè)結(jié)點(diǎn)改為最后一個(gè)結(jié)點(diǎn)*/L->next = pre;/*鏈表的頭結(jié)點(diǎn)指向原最后一個(gè)結(jié)點(diǎn)*/11.設(shè)有一線性鏈表，其結(jié)點(diǎn)值均為整數(shù)。試將該線性鏈表分解為兩個(gè)線性鏈表，其中一鏈表中的結(jié)點(diǎn)值均為負(fù)整數(shù)，而另一鏈表中結(jié)點(diǎn)的值均為正整數(shù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn)?！窘獯稹縱oid LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB)/*將鏈表L分解為L(zhǎng)A、LB兩個(gè)鏈表，其中LA中結(jié)點(diǎn)值均為正，LB中結(jié)點(diǎn)值均為負(fù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn),最后釋放L的頭結(jié)點(diǎn)。*/linklisttype *p , *pt , *pa, * pb;LA = initiatesl();pa = LA;/*指向LA中的最后一個(gè)結(jié)點(diǎn)*/LB = initiatesl();pb = LB;/*指向LB中的最后一個(gè)結(jié)點(diǎn)*/If(L = NULL | L->next = NUUL) return;/*L為空指針或L為空表*/p = L->next;/*p指向鏈表L的第一個(gè)結(jié)點(diǎn)*/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é)點(diǎn)*/pt = p->next;/*記錄當(dāng)前結(jié)點(diǎn)的后繼，以便刪除當(dāng)前結(jié)點(diǎn)*/free(p);p = pt;pa->next = NULL;pb->next = NULL;free(L);12設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)?！窘獯稹縱oid linklistMerge(linklisttype *LA,linklisttype *LB )/*合并有序鏈表LA與LB,結(jié)果存入LA中，并釋放LB的頭結(jié)點(diǎn) */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é)點(diǎn)鏈入LA*/pre->next = pb;free(LB);13設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)?！窘獯稹縇inklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB )/*合并有序鏈表LA與LB,結(jié)果存入LC中，并釋放LA、LB的頭結(jié)點(diǎn) ,函數(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鏈為L(zhǎng)C的第一個(gè)結(jié)點(diǎn)*/p = pa->next;pa->next = LC->next;LC->next = pa;pa = p; else/*將pa鏈為L(zhǎng)C的第一個(gè)結(jié)點(diǎn)*/p = pb->next;pb->next = LC->next;LC->next = pb;pb = p;while(pa != NULL)/*將pa剩余結(jié)點(diǎn)鏈入LC*/p = pa->next;pa->next = LC->next;LC->next = pa;pa = p;while(pb != NULL)/*將pb剩余結(jié)點(diǎn)鏈入LC*/p = pb->next;pb->next = LC->next;LC->next = pb;pb = p;free(LA);free(LB);14.在一個(gè)循環(huán)鏈表中尋找值為x的結(jié)點(diǎn)，并將該結(jié)點(diǎn)移到第一個(gè)結(jié)點(diǎn)之前?！窘獯稹吭O(shè)此循環(huán)鏈表為單鏈表，則其類型定義與一般單鏈表相同typedef struct mynode cyclelisttype;void search_movefirst(cyclelisttype *CL, int x)cyclelisttype * p , *pre;if(CL = NULL) return;p = CL->next;pre = CL;while(p != CL)/*查找x，注意與普通單鏈表在判斷是否到表尾上的不同*/if(p->data = x)break;elsepre = p;p = p->next;if(p != CL)/*查找成功*/per->next = p->next;/*在原來(lái)位置刪除p*/p->next = CL->next;/*p插入到CL后*/CL->next = p;16.鐵路進(jìn)行列車(chē)調(diào)度時(shí), 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問(wèn)：(1) 設(shè)有編號(hào)為1,2,3,4,5,6的六輛列車(chē), 順序開(kāi)入棧式結(jié)構(gòu)的站臺(tái), 則可能的出棧序列有多少種?(2) 若進(jìn)站的六輛列車(chē)順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說(shuō)明為什么不能; 如果能, 說(shuō)明如何得到(即寫(xiě)出"進(jìn)棧"或"出棧"的序列)?！窘獯稹?1) 可能的不同出棧序列有 種。(2) 不能得到435612和154623這樣的出棧序列。因?yàn)槿粼?, 3, 5, 6之后再將1, 2出棧，則1, 2必須一直在棧中，此時(shí)1先進(jìn)棧，2后進(jìn)棧，2應(yīng)壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 13542617.試證明：若借助?？捎奢斎胄蛄?, 2, 3, , n得到一個(gè)輸出序列p1, p2, p3, , pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)【解答】因?yàn)榻柚鷹Ｓ奢斎胄蛄?, 2, 3, , n，可得到輸出序列p1, p2, p3, , pn ，如果存在下標(biāo)i, j, k，滿足i < j < k，那么在輸出序列中，可能出現(xiàn)如下5種情況： i進(jìn)棧，i出棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧。此時(shí)具有最小值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，i出棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧。此時(shí)具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中間值的排在最后pk位置，有pi < pk < pj , 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，j出棧，i出棧，k進(jìn)棧，k出棧。此時(shí)具有中間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧，i出棧。此時(shí)具有中間值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧，i出棧。此時(shí)具有最大值的排在最前面pi 位置，具有中間值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出現(xiàn)pj < pk < pi的情形；18.將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top0等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top1等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top0增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top1減1得到新的棧頂位置。當(dāng)top0+1 = top1時(shí)或top0 = top1-1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類定義，并實(shí)現(xiàn)判?？?、判棧滿、插入、刪除算法?！窘獯稹縝ot0 top0 top1 bot1雙棧的類型定義如下：typedef structint top0,top1;elemtype dataMAXSIZE;DoubleStack;判?？読nt DoubleStackEmpty(DoubleStack * DS,int StackNo)/*DS：指向雙棧的指針，StackNo:0或1，指定要判斷的是第0棧，還是第一棧if(StackNo=0)return(DS->top0 < 0);elseretrun(DS->top1 >= MAXSIZE);判棧滿int DoubleStackFull(DoubleStack * DS)return(DS->top1-DS->top0=1);入棧int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x)/*將數(shù)據(jù)元素x插入到棧StackNo中*/if(DoubleStackFull(DS) return(FALSE);/*棧滿溢出*/if(StackNo=0)/*對(duì)第0棧插入*/DS->top0+;DS->datatop0=x;else/*對(duì)第1棧插入*/DS->top1-;DS->datatop1=x;return(TRUE);刪除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo)/*從StackNo棧中刪除并返回一個(gè)元素，若?？?，則返回NULL*/if(DoubleStackEmpty(DS,StackNo) return(NULL);if(StackNo=0)/*對(duì)0號(hào)棧進(jìn)行操作*/DS->top0-;return(DS->dataDS->top0+1);elseDS->top1+;return(DS->dataDS->top1-1);19.改寫(xiě)順序棧的進(jìn)棧成員函數(shù)Push(x)，要求當(dāng)棧滿時(shí)執(zhí)行一個(gè)stackFull( )操作進(jìn)行棧滿處理。其功能是：動(dòng)態(tài)創(chuàng)建一個(gè)比原來(lái)的棧數(shù)組大二倍的新數(shù)組，代替原來(lái)的棧數(shù)組，原來(lái)?xiàng)?shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置?！窘獯稹縱oid push(stack * S,elemtype x) if(StackEmpty(S) stackFull(S);/棧滿，做溢出處理S->top +;S->dataS->top = x;/進(jìn)棧void stackFull(stack *S)elemtype *temp;temp=calloc(3*MAXSIZE,sizeof(elemtype); /創(chuàng)建體積大二倍的數(shù)組for ( int i = 0; i <= S->top; i+ ) /傳送原數(shù)組的數(shù)據(jù)tempi = S->datai;free(S->data);/刪去原數(shù)組MAXSIZE *= 3; /數(shù)組最大體積增長(zhǎng)二倍S->data = temp;/新數(shù)組成為棧的數(shù)組空間20.根據(jù)教案中給出的優(yōu)先級(jí)，回答以下問(wèn)題：(1) 在表達(dá)式求值的過(guò)程中，如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，問(wèn)操作數(shù)棧(NS)中最多可存入多少個(gè)元素？(2) 如果表達(dá)式e含有n個(gè)運(yùn)算符，且括號(hào)嵌套的最大深度為6層，問(wèn)棧中最多可存入多少個(gè)元素？【解答】(1) 如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，則可能的運(yùn)算對(duì)象有n+1個(gè)。因此在利用后綴表達(dá)式求值時(shí)所用到的運(yùn)算對(duì)象棧中最多可存入n+1個(gè)元素。(2) 同上。21.表達(dá)式的中綴表示為a * x - b / x2，試?yán)脳⑺臑楹缶Y表示ax * bx2/ -。寫(xiě)出轉(zhuǎn)換過(guò)程中棧的變化。(表示乘方運(yùn)算)【解答】若設(shè)當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí)為icp(ch)，該運(yùn)算符進(jìn)棧后的優(yōu)先級(jí)為isp(ch)，則可規(guī)定各個(gè)算術(shù)運(yùn)算符的優(yōu)先級(jí)如下表所示。 運(yùn)算符 ; ( *,/, % +, - ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1isp也叫做棧內(nèi)(in stack priority)優(yōu)先數(shù)，icp也叫做棧外(in coming priority)優(yōu)先數(shù)。當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)大于isp(stack)時(shí)，則ch進(jìn)棧；當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)小于isp(stack)時(shí)，則位于棧頂?shù)倪\(yùn)算符退棧并輸出。從表中可知，icp(“(”)最高，但當(dāng)“(”進(jìn)棧后，isp(“(”)變得極低。其它運(yùn)算符進(jìn)入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的運(yùn)算符自左向右計(jì)算的要求。運(yùn)算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)“)”或棧底的“;”號(hào)與輸入流最后的“;”號(hào)配對(duì)時(shí)。前者將連續(xù)退出位于棧頂?shù)倪\(yùn)算符，直到遇到“(”為止。然后將“(”退棧以對(duì)消括號(hào)，后者將結(jié)束算法。步序掃描項(xiàng)項(xiàng)類型 動(dòng) 作棧的變化 輸 出 0F '' 進(jìn)棧, 讀下一符號(hào); 1 a操作數(shù)F 直接輸出, 讀下一符號(hào);A 2 *操作符F isp ( ' ; ' ) < icp ( ' * ' ), 進(jìn)棧, 讀下一符號(hào); *A 3 x操作數(shù)F 直接輸出, 讀下一符號(hào); *a x 4 -操作符F isp ( ' * ' ) > icp ( ' - ' ), 退棧輸出; a x * F isp ( ' ; ' ) < icp ( ' - ' ), 進(jìn)棧, 讀下一符號(hào); -a x * 5 b操作數(shù)F 直接輸出, 讀下一符號(hào); -a x * b 6 /操作符F isp ( ' - ' ) < icp ( '/' ), 進(jìn)棧, 讀下一符號(hào) ; -/a x * b 7 x操作數(shù)F 直接輸出, 讀下一符號(hào); -/a x * b x 8 操作符F isp ( ' / ' ) < icp ( '' ), 進(jìn)棧, 讀下一符號(hào); -/a x * b x 9 2操作數(shù)F 直接輸出, 讀下一符號(hào); -/a x * b x 2 10 ;操作符F isp ( '' ) > icp ( ' ; ' ), 退棧輸出; -/a x * b x 2 F isp ( ' / ' ) > icp ( ' ; ' ), 退棧輸出; -a x * b x 2/ F isp ( ' - ' ) > icp ( ' ; ' ), 退棧輸出; a x * b x 2/ - F 結(jié)束22.設(shè)循環(huán)隊(duì)列的容量為70（序號(hào)從1到70），經(jīng)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，有：（1）front=15，rear=46；（2）front=45，rear=10問(wèn)在上述兩種情況下，循環(huán)隊(duì)列中各有多少個(gè)元素？【解答】(1) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-front) %MAXSIZE = (70+46-15)%70=31(2) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-front) %MAXSIZE = (70+10-45)%70=3523.設(shè)用鏈表表示一個(gè)雙端隊(duì)列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫(xiě)基于此結(jié)構(gòu)的隊(duì)列的插入(enqueue)和刪除(dequeue)算法，并給出隊(duì)列空和隊(duì)列滿的條件。設(shè)此隊(duì)列含頭結(jié)點(diǎn)，隊(duì)頭指針front指向頭結(jié)點(diǎn)，限定在表頭端刪除隊(duì)列空：隊(duì)尾指針指向頭結(jié)點(diǎn)，即rear=front時(shí)，隊(duì)空隊(duì)列滿：因?yàn)槭擎湵?，所以，只有?nèi)存空間不足時(shí)才會(huì)有隊(duì)滿的問(wèn)題。void insertqueue(queuetype *Q,int location,elemtype x)/*Q:指向隊(duì)列的指針；location:插入位置，0表示隊(duì)頭，1表示隊(duì)尾；x:數(shù)據(jù)元素*/node *p;p=(node *)malloc(sizeof(node);p->data = x;if(location=0)/*在隊(duì)頭處插入*/p->next = Q->front->next;Q->front->next = p;if(Q->rear=Q->front)Q->rear = p;/*對(duì)空表插入*/else/*在隊(duì)尾處插入*/p->next = NULL;Q->rear->next = p;Q->rear = p;elemtype deletequeue(queuetype *Q)elemtype x;node * p;if(Q->rear = Q->front) return(NULL); /*空隊(duì)列*/p = Q->front->next;x = p->data;Q->front->next = p->next;if(Q->rear = p)Q->rear = Q->front/*對(duì)只有一個(gè)元素的隊(duì)列進(jìn)行刪除*/free(p);return(x);24.所謂回文，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。例如did，madamimadam，pop即是回文。試編寫(xiě)一個(gè)算法，以判斷一個(gè)串是否是回文?！窘獯?】將字符串中全部字符進(jìn)棧，然后將棧中的字符逐個(gè)與原字符串中的字符進(jìn)行比較。算法如下：int palindrome (string S) stacktype * st;int yes = 1, i = 0;while(Si != “0”)push (st,Si); i+; /*掃描字符串，所有字符進(jìn)棧*/i = 0;while(Si != “0” )/*比較字符串*/ if(Si = st.GetTop( )pop(st); i+; else yes = 0; break; return(yes);【解答2】采用遞歸算法，判斷從s到e中的字符串是否回文，通過(guò)函數(shù)返回是或不是。int palindrome(char A , int start, int end) if (Astart != Aend ) return 0; else if ( s > e ) return 1; else palindrome ( A, start+1, end-1 );25.設(shè)Ann為一個(gè)上三角矩陣，將A中所有非零元素按列序順次存入一維數(shù)組B中，則A與B元素的對(duì)應(yīng)關(guān)系是什么？【解答】上三角矩陣如下所示其數(shù)據(jù)元素滿足Aij=0，對(duì)所有的i>j上三角矩陣正好是一個(gè)下三角矩陣的轉(zhuǎn)秩，我們知道，一個(gè)下三角矩陣按行壓縮存儲(chǔ)時(shí)，矩陣元素與一維數(shù)組的對(duì)應(yīng)關(guān)系為AijàBi*(i+1)/2+j，對(duì)所有的i>j；因此，下三角矩陣按列序存儲(chǔ)在一維數(shù)組中的元素對(duì)應(yīng)關(guān)系為AijàBj*(j+1)/2+i，對(duì)所有的i<j.26.編寫(xiě)串的替換函數(shù)Replace(str,str1,str2)，將主串str中所有子串str1替換為str2?！窘獯稹恳?jiàn)書(shū)p58第 17 頁(yè) 共 16 頁(yè)