【正文】 數(shù)組和廣義表 廣義表的遞歸算法 遞歸函數(shù) 一個(gè) 含直接或間接調(diào)用本函數(shù)語句 的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件 : 1)在每一次調(diào)用自己時(shí)，必須是 (在某種意義上 )更接近于解 。 2)必須有一個(gè) 終止 處理或計(jì)算的 準(zhǔn)則 。 第五章 數(shù)組和廣義表 例如 : 梵塔的遞歸函數(shù) void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z)。 else { hanoi(n1, x, z, y)。 move(x, n, z)。 hanoi(n1, y, x, z)。 } } // hanoi 第五章 數(shù)組和廣義表 求階乘算法： n!=n*(n1)! int fact(int n ) { if (n==0 ) return 1。 else return n*fact(n1)。 } // fact 第五章 數(shù)組和廣義表 對于一個(gè) 輸入規(guī)模為 n 的函數(shù)或問題，用某種方法把輸入 分割成 k(1k≤ n)個(gè)子集 ，從而 產(chǎn)生 l 個(gè)子問題 ，分別求解這 l 個(gè)問題， 得出 l 個(gè)問題的子解 ，再用某種方法把它們 組合成原來問題的解 。若子問題還相當(dāng)大，則可以反復(fù)使用分治法，直至最后所分得的子問題足夠小，以至可以直接求解為止。 分治法的設(shè)計(jì)思想為 : 在利用分治法求解時(shí)，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解 第五章 數(shù)組和廣義表 例如 :焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個(gè)盤分成兩個(gè)子集 (1至 n1 和 n )，從而產(chǎn)生下列三個(gè)子問題 : 1) 將 1至 n1號盤從 x 軸移動至 y 軸 。 3) 將 1至 n1號盤從 y軸移動至 z軸 。 2) 將 n號盤從 x 軸移動至 z 軸 。 可遞歸求解 Hanoi(n1, x, z, y) 第五章 數(shù)組和廣義表 廣義表從結(jié)構(gòu)上可以分解成： 廣義表 = 表頭 + 表尾 或者 廣義表 = 子表 1 + 子表 2 + + 子表 n 因此常利用分治法求解之。 算法設(shè)計(jì)中的關(guān)鍵問題是，如何將 l 個(gè)子問題的解組合成原問題的解。 第五章 數(shù)組和廣義表 廣義表的頭、尾鏈表存儲表示： typedef enum {ATOM, LIST} ElemTag。 // ATOM==0:原子 , LIST==1:子表 typedef struct GLNode { ElemTag tag。 // 標(biāo)志域 union{ AtomType atom。 // 原子結(jié)點(diǎn)的數(shù)據(jù)域 struct {struct GLNode *hp, *tp。} ptr。 }。 } *GList tag=1 hp tp ptr 表結(jié)點(diǎn) tag=0 atom 原子結(jié)點(diǎn)： 第五章 數(shù)組和廣義表 例一 求廣義表的深度 例二 復(fù)制廣義表 例三 創(chuàng)建廣義表的存儲結(jié)構(gòu) 第五章 數(shù)組和廣義表 例 1: 求廣義表的深度 設(shè)廣義表 LS為： LS = ( ?1, ?2, ???, ?n ) 則 LS的深度定義為： 0 當(dāng) LS為原子時(shí) DEPTH（ LS） = 1 當(dāng) LS為空表時(shí) 1+ Max{ DEPTH（ ?i） } n≥ 1 1≤i≤n 在按數(shù)學(xué)式子寫遞歸算法時(shí)，一定不要懷疑它的正確性?。? 第五章 數(shù)組和廣義表 int GlistDepth(Glist L) { // 返回指針 L所指的廣義表的深度 for (max=0, pp=L。 pp。 pp=pp){ dep = GlistDepth(pp)。 if (dep max) max = dep。 } return max + 1。 } // GlistDepth if (!L) return 1。 //L為空表 if (Ltag == ATOM) return 0。 第五章 數(shù)組和廣義表 for (max=0, pp=L。 pp。 pp=pp){ dep = GlistDepth(pp)。 if (dep max) max = dep。 } 例如 : pp pp pp pp pp pp 1 1 1 L … ?第五章 數(shù)組和廣義表 例二 復(fù)制廣義表 新的廣義表由新的表頭和表尾構(gòu)成。 可以直接求解的兩種簡單情況為 : 空表復(fù)制求得的新表自然也是空表 。 原子結(jié)點(diǎn)可以直接復(fù)制求得。 將廣義表分解成表頭和表尾兩部分，分別(遞歸 )復(fù)制求得新的表頭和表尾， 第五章 數(shù)組和廣義表 若 LS= NULL 則 NEWLS=NULL 否則 產(chǎn)生結(jié)點(diǎn) NEWLS 和 LS相同，即若 LS為元素結(jié)點(diǎn)，則直接將 LS的值賦給 NEWLS，否則為表結(jié)點(diǎn)，則完成下列工作： 將表頭 LS 復(fù)制到 NEWLS 將表尾 LS 復(fù)制到 NEWLS 復(fù)制求廣義表的算法描述如下 : 第五章 數(shù)組和廣義表 Status CopyGList(GList amp。T, GList L) { //采用頭尾鏈表存儲結(jié)構(gòu)，由廣義表 L復(fù)制得到廣義表 T if (!L) T = NULL。 // 復(fù)制空表 else { if ( !(T = （ Glist)(malloc(sizeof( GLNode))) ) exit(OVERFLOW)。 // 建表結(jié)點(diǎn) Ttag = Ltag。 if (Ltag == ATOM) Tatom = Latom。 // 復(fù)制單原子結(jié)點(diǎn) else { } } // else return OK。 } // CopyGList 分別復(fù)制表頭和表尾 第五章 數(shù)組和廣義表 CopyGList(T, L)。 // 復(fù)制求得表頭 T L CopyGList(T, L)。 // 復(fù)制求得表尾 T 的一個(gè)副本 L 第五章 數(shù)組和廣義表 例三 創(chuàng)建廣義表的存儲結(jié)構(gòu) 對應(yīng)廣義表的不同存儲結(jié)構(gòu)，相應(yīng)地有不同的創(chuàng)建存儲結(jié)構(gòu)的算法。下面以擴(kuò)展線性鏈表存儲結(jié)構(gòu)為例： 第五章 數(shù)組和廣義表 假設(shè)以字符串 S = ?(?1, ?2, ???, ?n )? 的形式定義廣義表 L，建立相應(yīng)的存儲結(jié)構(gòu) 。 由于 S中的每個(gè)子串 ?i定義 L 的一個(gè) 子表 ，從而產(chǎn)生 n 個(gè)子問題，即分別由這 n個(gè)子串 (遞歸 )建立 n 個(gè)子表，再 組合 成 一個(gè)廣義表。 可以直接求解的兩種簡單情況為 : 由串 ?( )?建立的廣義表是 空表 。 由單字符建立的子表只有一個(gè)原子結(jié)點(diǎn)。 第五章 數(shù)組和廣義表 如何由子表組合成一個(gè)廣義表？ 首先分析廣義表和子表在存儲結(jié)構(gòu)中的關(guān)系。 先看第一個(gè)子表和廣義表的關(guān)系 : 1 L 指向廣義表 的頭指針 指向第一個(gè) 子表的頭指針 第五章 數(shù)組和廣義表 再看相鄰兩個(gè)子表之間的關(guān)系 : 1 1 指向第 i+1個(gè) 子表的頭指針 指向第 i個(gè) 子表的頭指針 可見，兩者之間通過表結(jié)點(diǎn)相鏈接。 第五章 數(shù)組和廣義表 若 S = ?( )? 則 L = NULL 否則 構(gòu)造第一個(gè)表結(jié)點(diǎn) *L, 并從串 S 中分解出第一個(gè)子串 ?1,對應(yīng)創(chuàng)建第一個(gè)子廣義表 L。 若剩余串非空，則構(gòu)造第二個(gè)表結(jié)點(diǎn) L, 并從串 S 中分解出第二個(gè)子串 ?2, 對應(yīng)建第二個(gè)子廣義表 ………。 依次類推，直至剩余串為空串止。 第五章 數(shù)組和廣義表 Status CreateGList(Glist amp。L, String S) { if (!StrCompare(S,emp)) L = NULL。 // 創(chuàng)建空表 else { if(!(L = （ GList)malloc(sizeof( GLNode)))) exit(OVERFLOW)。 // 生成表結(jié)點(diǎn) if(StrLength(S)==1) {Ltag=ATOM。Latom=S。}//創(chuàng)建單原子 else { Ltag=List。 p=L。 SubString(sub,S,2,StrLength(S)2)。 // 脫去串 S 的外層括弧 } // else return OK。 } // CreateGList 由 sub中所含 n個(gè)子串建立 n個(gè)子表 。 第五章 數(shù)組和廣義表 do { sever(sub, hsub)。 // 從 sub中分離出表頭串 hsub CreateGList(p,hsub)。 q=p。 //創(chuàng)建由串 hsub定義的廣義表 p。 if (!StrEmpty(sub) { if(!(p=GList)malloc(sizeof( GLNode)))) exit(OVERFLOW)。 // 建下一個(gè)子表的表結(jié)點(diǎn) *(p) ptag=LIST。 q=p。 }//if } while (!StrEmpty(sub))。 q = NULL。 // 表尾為空表 } //else 第五章 數(shù)組和廣義表 本章小結(jié)： 1. 了解數(shù)組的兩種存儲表示方法 ， 并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計(jì)算方法 。 2. 掌握對特殊矩陣進(jìn)行壓縮存儲時(shí)的下標(biāo)變換公式 。 3. 了解稀疏矩陣的兩類壓縮存儲方法的特點(diǎn)和適用范圍 ， 領(lǐng)會以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法 。 第五章 數(shù)組和廣義表 4. 掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲表示方法，讀者可根據(jù)自己的習(xí)慣熟練掌握任意一種結(jié)構(gòu)的鏈表，學(xué)會對非空廣義表進(jìn)行分解的兩種分析方法：即可將一個(gè)非空廣義表分解為表頭和表尾兩部分或者分解為 n個(gè)子表。 5. 學(xué)習(xí)利用分治法的算法設(shè)計(jì)思想編制遞歸算法的方法。 第五章 數(shù)組和廣義表 習(xí)題五 ： ： 利用稀疏矩陣的三元組壓縮存儲 、 實(shí)現(xiàn)壓縮存儲時(shí)的矩陣轉(zhuǎn)置運(yùn)算；