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