【正文】 [m++]=str[j]。else {if (str[j]b[0]) {flag=0。}else b[0]=str[j]。}}}if(flag) /*滿足出棧規(guī)則則輸出str[]中的序列*/{ printf( %2d:,cont++)。for(i=0。in。i++)printf(%d,str[i])。printf(\n)。8}}int main(){int str[100],n,i。printf(input a int:)。 /*輸出排列的元素個(gè)數(shù)*/scanf(%d,amp。n)。for(i=0。in。i++) /*初始化排列集合*/str[i]=i+1。printf(input the result:\n)。perm(str,0,n)。printf(\n)。return 0。}當(dāng)參與進(jìn)出棧的元素個(gè)數(shù)為4 時(shí)，輸出的結(jié)果如下圖所示。該算法執(zhí)行的時(shí)間復(fù)雜度為O（n!）。隨著n 的增大，算法的執(zhí)行效率非常的低。非遞歸解法：（）對(duì)一組數(shù)窮盡所有排列，還可一種更直接的方法，將一個(gè)排列看作一個(gè)長(zhǎng)整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)，將這組整數(shù)按從小到大的順序排成一個(gè)數(shù)列，從對(duì)應(yīng)最小的整數(shù)開(kāi)始，按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每一個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來(lái)實(shí)現(xiàn)。倘若當(dāng)前排列為1,2,4,6,5,3，并令其對(duì)應(yīng)的長(zhǎng)整數(shù)為124653。要尋找比長(zhǎng)整數(shù)124653 更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中的6 比它的前一位數(shù)字4 大，則說(shuō)明還有可能對(duì)應(yīng)更大整數(shù)的排列。但為順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6 與數(shù)字4 交換得到的排列為126453 就不是排列124653 的下一個(gè)排列。為得到排列124653 的下一個(gè)排列，應(yīng)從已考察過(guò)的那部分?jǐn)?shù)字中選出比數(shù)字4 大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字5，與數(shù)字4 交換。該數(shù)字也是從后向前考察過(guò)程中第一個(gè)比4 大的數(shù)字，5 與4 交換后，得到排列125643。在前面數(shù)字1，2，5 固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列顛倒，如將數(shù)字6，4，3 的排列順序顛倒，得到排列1,2,5,3,4,6，這才是排列1，2，4，6，95，3 的下一個(gè)排列。按照以上想法可以編寫非遞歸程序?qū)崿F(xiàn)n 個(gè)數(shù)的全排列，對(duì)滿足進(jìn)出棧規(guī)則的排列則計(jì)數(shù)并輸出。/*本程序輸出1 2 ... n 個(gè)序列進(jìn)棧出棧的序列*/include int pl(int n){ int a[100]。 /*最大處理范圍為99 個(gè)數(shù)*/int flag=1,flag1=0。FILE *rf 。int i,j,k,x,count=0。rf = fopen(, w) 。 /* 用于存放進(jìn)出棧序列結(jié)果*/for (i=1。i=n。i++) /*初始序列*/a[i]=i。while (flag) /* 還剩余未輸出的排列*/{ flag1=1。 /* 判斷本次排列是否符合進(jìn)棧出棧序列 */for (i=1。i=n。i++){ j=i+1。while (j=n amp。amp。 a[j]a[i]) j++。 /* 找a[i]后第一個(gè)比a[i]小__________的元素a[j]*/k=j+1。while (k=n) /* 如果a[j]后還有比a[i]小且比a[j]大的元素,則此排列無(wú)效*/{if ( a[k] a[i] amp。amp。 a[k]a[j]) flag1=0。k++。}}if (flag1){ for (i=1。i=n。i++) /*輸出當(dāng)前排列*/{ printf(%4d,a[i])。 fprintf(rf,%4d,a[i])。}printf(\n)。 fprintf(rf,\n)。count++。 /*計(jì)數(shù)器加1*/}i=n。 /*從后向前找相鄰位置后大前小的元素值*/while (i1 amp。amp。 a[i]a[i1]) i。if (i==1) flag=0。 /*未找到則結(jié)束*/else{j=i1。i=n。/* 若找到,則在該位置的后面從右向左找第一個(gè)比該元素大的值*/while (ij amp。amp。 a[i]a[j]) i。k=a[j]。 /*交換兩元素的值*/a[j]=a[i]。a[i]=k。k=j+1。 /*對(duì)交換后后面的數(shù)據(jù)由小到大排序*/10for ( i=k+1。i=n。i++) /*插入排序*/{ j=i1。x=a[i]。while (j=k amp。amp。 xa[j]) { a[j+1]=a[j]。 j。}a[j+1]=x。}}}fclose(rf)。return count。 /*返回排列總個(gè)數(shù)*/}void main(){int n,m=0。printf(please input n:)。 /*輸入排列規(guī)模*/scanf(%d,amp。n)。m=pl(n)。printf(\nm=%d,m)。 /*輸出滿足進(jìn)出棧的排列總個(gè)數(shù)*/}程序運(yùn)行時(shí)如果輸入4，則輸出的結(jié)果如下圖所示。該算法的時(shí)間復(fù)雜度也是O(n!)。結(jié)論：如果n 個(gè)數(shù)按編號(hào)由小到大的順序進(jìn)棧，進(jìn)棧的過(guò)程中可以出棧，則所有可能的出棧序列的總數(shù)為：( 1) ! !(2 )!n n nn+11第3 章 線性表的鏈?zhǔn)酱鎯?chǔ) 選擇題（1）兩個(gè)有序線性表分別具有n 個(gè)元素與m 個(gè)元素且n≤m，現(xiàn)將其歸并成一個(gè)有序表，其最少的比較次數(shù)是（ A ）。A．n B．m C．n ? 1 D．m + n（2）非空的循環(huán)單鏈表head 的尾結(jié)點(diǎn)（由p 所指向）滿足（ C ）。A．pnext==NULL B．p==NULL C．pnext==head D．p==head（3）在帶頭結(jié)點(diǎn)的單鏈表中查找x 應(yīng)選擇的程序體是（ C ）。A．node *p=headnext。 while (p amp。amp。 pinfo!=x) p=pnext。if (pinfo==x) return p else return NULL。B．node *p=head。 while (pamp。amp。 pinfo!=x) p=pnext。 return p。C．node *p=headnext。 while (pamp。amp。pinfo!=x) p=pnext。 return p。D．node *p=head。 while (pinfo!=x) p=pnext 。 return p。（4）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ D ）。A．必須是連續(xù)的 B．部分地址必須是連續(xù)的C．一定是不連續(xù)的 D．連續(xù)不連續(xù)都可以（5）在一個(gè)具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是（ B ）。A．O(1) B．O(n) C．O(n2) D．O(nlog2n)（6）用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（ D ）。A．僅修改隊(duì)頭指針 B．僅修改隊(duì)尾指針C．隊(duì)頭、隊(duì)尾指針都要修改 D．隊(duì)頭,隊(duì)尾指針都可能要修改（7）若從鍵盤輸入n 個(gè)元素，則建立一個(gè)有序單向鏈表的時(shí)間復(fù)雜度為（ B ）。A．O(n) B．O(n2) C．O(n3) D．O(n ? log2n)（8）下面哪個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)（ D ）。A．順序表 B．鏈表 C．散列表 D．隊(duì)列（9）在一個(gè)單鏈表中，若刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ A ）。A．pnext=pnextnext。 B．p=pnext。 pnext=pnextnext。C．pnext=pnext。 D．p =pnextnext。（10）在一個(gè)單鏈表中，若p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p 之后插入s 所指結(jié)點(diǎn)，則執(zhí)行（ B ）。A．snext=p。pnext=s。 B．snext=pnext。pnext=s。C．snext=pnext。p=s。 D．pnext=s。snext=p。 設(shè)計(jì)一個(gè)算法，求一個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。【答】：?jiǎn)捂湵泶鎯?chǔ)結(jié)構(gòu)定義如下（相關(guān)文件：）include 12include typedef struct node{ int data。struct node *next。}linknode。typedef linknode *linklist。/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklist creatlinklist(){ linklist head,r,x,s。head=r=(linklist)malloc(sizeof(linknode))。printf(\n 請(qǐng)輸入一組以0 結(jié)束的整數(shù)序列：\n)。scanf(%d,amp。x)。while (x){ s=(linklist)malloc(sizeof(linknode))。sdata=x。rnext=s。r=s。scanf(%d,amp。x)。}rnext=NULL。return head。}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/void print(linklist head){ linklist p。p=headnext。printf(List is:\n)。while(p){ printf(%5d,pdata)。p=pnext。}printf(\n)。}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點(diǎn)個(gè)數(shù)的算法程序如下：int count(linklist head){ int c=0。linklist p=head。while (p){c++。13p=pnext。}return c。} 設(shè)計(jì)一個(gè)算法，求一個(gè)帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚海瑢?shí)現(xiàn)本題功能的算法程序如下（）include int count(linklist head){ int c=0。linklist p=headnext。while (p){c++。p=pnext。}return c。}main() /*測(cè)試函數(shù)*/{linklist head。head=creatlinklist()。print(head)。printf(\nLength of head is:%d,count(head))。getch()。}當(dāng)輸入5 個(gè)數(shù)據(jù)時(shí)，產(chǎn)生的輸出結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表中值為y 的結(jié)點(diǎn)前面插入一個(gè)值為x 的結(jié)點(diǎn)。即使值為x 的新結(jié)點(diǎn)成為值為y 的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚篿nclude void insert(linklist head,int y,int x){/*在值為y 的結(jié)點(diǎn)前插入一個(gè)值為x 的結(jié)點(diǎn)*/linklist pre,p,s。pre=head。p=headnext。14while (p amp。amp。 pdata!=y){ pre=p。p=pnext。}if (p)/*找到了值為y 的結(jié)點(diǎn)*/{ s=(linklist)malloc(sizeof(linknode))。sdata=x。snext=p。prenext=s。}}void main() /*測(cè)試程序*/{linklist head。int y,x。head=creatlinklist()。 /*創(chuàng)建單鏈表*/print(head)。 /*輸出單鏈表*/printf(\n 請(qǐng)輸入y 與x 的值:\n)。scanf(%d %d,amp。y,amp。x)。insert(head,y,x)。print(head)。}程序的一種運(yùn)行結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中各個(gè)結(jié)點(diǎn)值是否有序。【答】：include int issorted(linklist head,char c)/*當(dāng)參數(shù)c=’a’時(shí)判斷鏈表是否為升序，當(dāng)參數(shù)c=’d’是判斷鏈表是否為降序*/{ int flag=1。linklist p=headnext。switch (c){case 39。a39。:/*判斷帶頭結(jié)點(diǎn)的單鏈表head 是否為升序*/15while (p amp。amp。pnext amp。amp。 flag){if (pdata=pnextdata) p=pnext。else flag=0。}break。case 39。d39。:/*判斷帶頭結(jié)點(diǎn)的單鏈表head 是否為降序*/while (p amp。amp。pnext amp。amp。 flag){if (pdata=pnextdata) p=pnext。else flag=0。}break。}return flag。}int main() /*測(cè)試程序*/{ linklist head。head=creatlinklist()。print(head)。if (issorted(head,39。a39。)) printf(單鏈表head 是升序排列的！\n)。