【正文】 N=1 Stum=2 Stre=67 ave= total= 45 N=1 Stum=2 Stre=67 ave= total= 45 N=1 Stum=2 Stre=67 ave= N=0 Stum=1 Stre=45 ave= N=0 Stum=1 Stre=45 ave= N=0 Stum=1 Stre=45 ave= N=0 Stum=1 Stre=45 ave= 126 ? 例 ： 試編寫程序，輸入一個(gè)整數(shù)，將其各位上的數(shù)按逆序存放在一個(gè)數(shù)組中。 ?提示： 設(shè)轉(zhuǎn)換函數(shù)是 reverse(int *a,int n)，其中第一個(gè)參數(shù)是存放位的數(shù)組，第二個(gè)參數(shù)是待處理的數(shù)。要將 n的各位放在 a中，就要將n/10（當(dāng) n≥10 時(shí)）放在 a+1中。如：將 n=12345（ ≥ 10），存放在數(shù)組 a中，就要將 1234放在a+1中，為此，就要將 123放在 a+2中，以此類推。當(dāng) n10時(shí)，將 n放于 a中，遞歸調(diào)用結(jié)束。 ?提示： 迭代公式為： x1=(x0+a/x0)/2 ? 例 ：用遞歸算法實(shí)現(xiàn)牛頓迭代法，求平方根。 127 ? 例 ：已知遞歸函數(shù)（其中 DIV為整除）： F(n)= 1 n=0 n*F(n DIV 2) n0 試寫出求 F(n)的非遞歸算法。 ?提示： 用棧實(shí)現(xiàn)。在棧的元素中記錄三個(gè)值： 當(dāng)前要求的值； n； 遞歸調(diào)用函數(shù) F(n DIV 2)的返回值， F(n) n F(n div 2) 因此有 : sta[top][0]=sta[top][1]*sta[top][2]。 sta[top][2]=sta[top+1][0]。 128 ? 例 ： Ackerman函數(shù)定義如下 ： n+1 m=0 akm(m,n) = akm(m1,1) m≠0,n=0 akm(m1,akm(m,n1)) m≠0,n≠0 試寫出求該函數(shù)的非遞歸算法。 ?提示： Ackerman函數(shù)是一個(gè)遞歸定義的而不是原始遞歸的函數(shù)。這里我們用棧結(jié)構(gòu)實(shí)現(xiàn)其非遞歸的程序。我們定義棧元素有 4項(xiàng)內(nèi)容： m、 m n和 r ； 當(dāng) r為 0時(shí)，表示調(diào)用 akm(m,n)，處理時(shí)直接彈棧；當(dāng) r為 1時(shí)，表示調(diào)用 akm(m1,akm(m,n1))，此時(shí)不彈棧而計(jì)算 akm(m1,n)，即計(jì)算 akm(m,n1)。 129 ? 例 ：輸入 M個(gè)不同的字符，從中選出 N個(gè)字符，輸出所有可能的選擇方案。說明： （ 1） M、 N均由鍵盤輸入； （ 2）假定輸入的 M和 N均合法，輸入的 M個(gè)字符均不同。 ?提示：如有 M字母 “ abcde”，從中選 3個(gè)不同的字母，我們可以把這樣的問題遞歸描述為： 遞歸處理 遞歸處理 從 “ abcde”中選 3個(gè)不同的字母 選 a后再?gòu)?“ bcde”中選 2個(gè) 選 b后再?gòu)?“ cde”中選一個(gè) 選 c后再?gòu)?“ bde”中選一個(gè) 選 d后再?gòu)?“ bce”中選一個(gè) 選 e后再?gòu)?“ bcd”中選一個(gè) 選 b后再?gòu)?“ acde”中選 2個(gè) 選 a后再?gòu)?“ cde”中選一個(gè) 選 c后再?gòu)?“ ade”中選一個(gè) 選 d后再?gòu)?“ ace”中選一個(gè) 選 e后再?gòu)?“ acd”中選一個(gè) 選 c后再?gòu)?“ abde”中選 2個(gè) 仿上 選 d后再?gòu)?“ abce”中選 2個(gè) 仿上 選 e后再?gòu)?“ abcd”中選 2個(gè) 仿上 130 ? 例 ：從文件 ，將其中不同整數(shù)及其出現(xiàn)次數(shù)，按整數(shù)由大到小的次序輸出到文件。要求：用一個(gè)有序二叉樹存儲(chǔ)數(shù)據(jù) 。 ?提示： 首先我們要定義樹形的描述，對(duì)于樹的描述只需定義出樹的結(jié)點(diǎn)定義及其相關(guān)的操作，在這里就是樹的插入操作和遍歷操作。然后是文件操作。 ?遞歸函數(shù)：按從小到大的順序（中序）輸出 void T_tree(FILE *fp, struct node *t){ if (t==NULL) return。 T_tree(fp,tleft)。 fprintf(fp,\n%d %d,tval,tcount)。 T_tree(fp,tright)。 } 131 ? 例 ：試編寫一個(gè)遞歸函數(shù)，函數(shù)的輸入為一個(gè)帶括號(hào)的包含加、減、乘、除四則運(yùn)算表達(dá)式的字符串，例如“ （ a+b） *(c+d)”，該函數(shù)根據(jù)運(yùn)算符優(yōu)先級(jí)來構(gòu)造一棵二叉樹，樹的根節(jié)點(diǎn)為優(yōu)先級(jí)最低的運(yùn)算符。該函數(shù)最終返回二叉樹的根節(jié)點(diǎn)，并用后序遍歷方式遍歷生成的二叉樹。假設(shè)表達(dá)式中的操作數(shù)都是長(zhǎng)度是 1的串。 ?提示： 首先要描述二叉樹，包括定義樹的結(jié)點(diǎn)，其支持的操作有創(chuàng)建結(jié)點(diǎn)、后序遍歷。然后分析四則表達(dá)式，生成二叉樹 。 ?遞歸函數(shù)： 遞歸函數(shù)的核心算法可以描述如下： NODE *creatTree(char *bstr) { /*創(chuàng)建表達(dá)式對(duì)應(yīng)的二叉樹 */ 把 bstr分解成 bstr1 ω bstr2。 /*ω 是 bstr中最后運(yùn)算的操作符*/ if ((head=head=createNode(ω))!=NULL){ headleft=creatTree(bstr1)。 headright=creatTree(bstr2)。 } } 其中，分解 bstr就是找出其中最后運(yùn)算的操作符 ω 。 132 ? 例 ：試?yán)眠f歸方法判別用鏈表表示的兩個(gè)非遞歸列表是否相等。程序中的非遞歸列表定義如下： （ 1） 無元素的空列表是非遞歸列表； （ 2）由元素序列組成的一個(gè)列表，其中的元素可以是一個(gè)字符，或者是滿足本定義的一個(gè)列表。例如： ?提示： 首先要定義結(jié)構(gòu)描述列表的元素，然后根據(jù)定義編寫判定相等的函數(shù)。 ?表結(jié)點(diǎn)定義 ： typedef struct node{ int tag。 union u{ char data。 struct node *link。 } un 。 struct node *next。 }NODE。 0 a 1 ^ 0 b 0 c ^ s 133 第 3章 排序部分 134 例 冒泡排序 冒泡排序是交換排序 。 方法：對(duì)于 i=0， 1， 2， … ， n1，在第 i個(gè)與第 n個(gè)元素之間，包括二者，選極大（?。┲捣庞诘?i個(gè)位置； 選取方式是從第 n個(gè)元素開始，每次都與前一個(gè)關(guān)鍵字比較，將大（?。┱摺案　鄙先?，直至第 i+1元素。 135 例 冒泡排序 47 47 47 47 78 56 56 56 78 47 47 47 58 36 36 78 56 56 56 58 47 56 78 78 36 36 36 58 56 56 47 47 23 58 58 58 58 36 36 36 36 36 36 58 23 23 23 23 23 23 23 23 23 23 136 例 冒泡排序 void bSort(int a[],int order[],int len){ int i,j。 for(i=0。ilen。i++){ for(j=len1。ji。j){ if(a[j]a[j1]){ int t=a[j]。a[j]=a[j1]。a[j1]=t。 t=order[j]。 order[j]=order[j1]。order[j1]=t。 } } } } 137 例 冒泡排序 void bSort(int a[],int order[],int len){ int i,j。 for(i=0。ilen。i++){ for(j=len1。ji。j){ if(a[order[j]]a[order[j1]]){ int t=order[j]。 order[j]=order[j1]。 order[j1]=t。 } } } } 138 例 希爾排序 ? 希爾排序是一種插入排序 ,即將一個(gè)數(shù)記錄按規(guī)定的關(guān)鍵字序插入到一已排序的數(shù)列中。 ? 希爾排序用步長(zhǎng)控制參與排序的元素 。 139 例 希爾排序 ? 如步長(zhǎng) k，則考慮的數(shù)列為： aj aj+k aj+2k aj+3k … a j+i*k … 當(dāng) aj aj+k aj+2k aj+3k … a j+i*k已排序，則將aj+(i+1)*k插入到前面的數(shù)列中。 ? 當(dāng) k=1時(shí)，對(duì) a2， a3， … ，依次執(zhí)行插入后，就完成了排序過程。 140 例 希爾排序 k=4 （ 47） 56 36 78 23 58 49 60 38 k=4 47 （ 56） 36 78 23 58 49 60 38 k=4 47 58 （ 36） 78 23 56 49 60 38 k=4 47 58 49 （ 78） 23 56 36 60 38 k=4 （ 47） 58 49 78 （ 23） 56 36 60 38 141 例 希爾排序 k=1時(shí) （ 49） 78 47 60 38 58 36 56 23 （ 78）（ 49） 47 60 38 58 36 56 23 （ 78）（ 49）（ 47） 60 38 58 36 56 23 （ 78）（ 60）（ 49）（ 47） 38 58 36 56 23 （ 78）（ 60）（ 49）（ 47）（ 38） 58 36 56 23 （ 78）（ 60）（ 58）（ 49）（ 47）（ 38） 36 56 23 （ 78）（ 60）（ 58）（ 49）（ 47）（ 38）（ 36） 56 23 （ 78）（ 60）（ 58）（ 56）（ 49）（ 47）（ 38）（ 36） 23 （ 78）（ 60）（ 58）（ 56）（ 49）（ 47）（ 38）（ 36）（ 23） 142 例 希爾排序 void shell(int a[],int n){ int k,j, i, t。 for(k=n/2。k0。k=k/3+1){ /*k是步長(zhǎng) */ for(j=k。jn。j++){ /*在步長(zhǎng) k時(shí) */ for(t=a[j],i=jk。i=0 amp。amp。 a[i]t。i=ik){ a[i+k]=a[i]。 } a[i+k]=t。 } if(k==1)break。 } } 143 例 快速排序 ? 快速排序是一種交換排序 。 ? 基本思想是：以某一個(gè)關(guān)鍵字將整個(gè)數(shù)列分成二部分：大于該關(guān)鍵字的部分和小于該關(guān)鍵字的部分。然后對(duì)每一部分再執(zhí)行該排序算法。 144 例 快速排序 （ 47） 56 36 78 23 58 49 60 （ 47） 56 36 78 23 58 49 （ 60） 60 （ 56） 36 78 23 58