【正文】 每一層遞歸調(diào)用所需保存的信息構(gòu)成運(yùn)行時(shí)棧的一個(gè) 工作記錄 棧頂?shù)墓ぷ饔涗洷４娴氖钱?dāng)前調(diào)用函數(shù)的信息，所以棧頂?shù)墓ぷ饔涗浺卜Q為 活動(dòng)記錄 。 例 ：漢諾塔問(wèn)題的遞歸求解過(guò)程 2134A BC4AB C213A B C213 4A B C2134(a) (b)(c)(d) 遞歸過(guò)程和運(yùn)行時(shí)棧 遞歸函數(shù)的執(zhí)行過(guò)程具有三個(gè)特點(diǎn)： （ 1）函數(shù)名相同； （ 2）不斷地自調(diào)用； （ 3）最后被調(diào)用的函數(shù)要最先被返回。 當(dāng)一個(gè)問(wèn)題存在上述兩個(gè)基本要素時(shí)，設(shè)計(jì)該問(wèn)題的遞歸算法的方法是： （ 1）把對(duì)原問(wèn)題的求解表示成對(duì)子問(wèn)題求解的形式。 else (x在數(shù)組 a中，下標(biāo)為 + bn)。 bn = bSearch(a, x, 0, 7)。 int x = 17。 //在上半?yún)^(qū)查找 else return bSearch(a, x, mid + 1, high)。 if(x == a[mid]) return mid。 if(low high) return 1。 } catch(Exception e){ (())。 try{ fn = fact(3)。 return n * y。 else{ x = n 1。 if(n 0){ throw new Exception(參數(shù)錯(cuò)！ )。 例如：階乘函數(shù)的定義 1 當(dāng) n=0時(shí) n= n*(n1) 當(dāng) n0時(shí) 2. 問(wèn)題的解法存在自調(diào)用 例如：折半查找算法 0 1 2 43 5 6 7第 一 次 : 下 標(biāo)元 素 值1 3 4 1 75 1 8 3 1 3 30 1 2 43 5 6 7第 二 次 : 下 標(biāo)元 素 值1 3 4 1 75 1 8 3 1 3 30 1 2 43 5 6 7第 三 次 : 下 標(biāo)元 素 值1 3 4 1 75 1 8 3 1 3 3l o w h i g hm i dl o w h i g hm i dl o wh i g hm i dx a [ m i d ]x a [ m i d ]x = = a [ m i d ] 遞歸算法的執(zhí)行過(guò)程 例 1：階乘的遞歸算法 public static long fact(int n) throws Exception{ int x。在三元組鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域由稀疏矩陣非零元的行號(hào)、列號(hào)和元素值組成。 數(shù)組結(jié)構(gòu) 稀疏矩陣 三元組的內(nèi)存示意圖 112456...0123456m a x S i z e 1...352147...1 11 72 51 93 75 0...s i z e = 6676r o w sc o l sd N u mr o w c o l v a l u ev 轉(zhuǎn)置操作的內(nèi)存示意圖 352147...0123456m a x S i z e 1...112456...1 11 72 51 93 75 0...766r o w sc o l sd N u mr o w c o l v a l u e123457...0123456m a x S i z e 1421516...1 92 51 13 71 75 0...766r o w sc o l sd N u mr o w c o l v a l u e( a )( b )...v v（ a）無(wú)序轉(zhuǎn)置；（ b）有序轉(zhuǎn)置 三元組鏈表 稀疏矩陣 的所有三元組也可采用鏈表結(jié)構(gòu)存儲(chǔ)。 2 稀疏矩陣類 對(duì)于稀疏矩陣來(lái)說(shuō)，矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)是矩陣操作的基本數(shù)據(jù)，因此，這些成分要設(shè)計(jì)為成員變量。三元組的鏈表結(jié)構(gòu)存儲(chǔ)就是把稀疏矩陣的所有三元組存儲(chǔ)在一個(gè)鏈表中。 稀疏矩陣和對(duì)應(yīng)的三元組線性表 ????????????????????500000000003700000000019000000000000250001701100{{1,3,11},{1,5,17},{2,2,25},{4,1,19},{5,4,37},{6,7,50}}(a) (b)1 2 3 4 5 6 7123456列號(hào)行號(hào) 稀疏矩陣 的壓縮存儲(chǔ)結(jié)構(gòu)主要有三元組的數(shù)組結(jié)構(gòu)存儲(chǔ)和三元組的鏈表結(jié)構(gòu)存儲(chǔ)兩大類型。 稀疏矩陣的壓縮存儲(chǔ) 稀疏矩陣的壓縮存儲(chǔ) 方法，是只存儲(chǔ)矩陣中的非零元素。簡(jiǎn)單說(shuō)，稀疏矩陣就是非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于元素個(gè)數(shù)的矩陣。 不等長(zhǎng)的二維數(shù)組結(jié)構(gòu) 0123 稀疏矩陣 對(duì)一個(gè) m n的矩陣，設(shè) s為矩陣元素個(gè)數(shù)的總和，有s=m*n，設(shè) t為矩陣中非零元素個(gè)數(shù)的總和，滿足 t＜＜s的矩陣稱作 稀疏矩陣 。 特殊矩陣的壓縮存儲(chǔ) 1 只存儲(chǔ)相同矩陣元素的一個(gè)副本 此種壓縮存儲(chǔ)方法是：找出特殊矩陣數(shù)據(jù)元素的分布規(guī)律，只存儲(chǔ)相同矩陣元素的一個(gè)副本。一般采用二維數(shù)組來(lái)存儲(chǔ)矩陣元素。 矩陣用兩維數(shù)組處理最為方便。常用的另一種實(shí)現(xiàn)方法是基于哈希表來(lái)實(shí)現(xiàn)。 集合類 集合 的特點(diǎn)是數(shù)據(jù)元素?zé)o序且不重復(fù)。 （ 6）數(shù)據(jù)元素個(gè)數(shù) size()：返回集合中的數(shù)據(jù)元素個(gè)數(shù)。 （ 5）相等 eqauls(otherSet)：當(dāng)前對(duì)象集合是否和集合 otherSet相等。 （ 4）包含 include(otherSet)：當(dāng)前對(duì)象集合是否包含集合 otherSet。 （ 3）屬于 contain(obj)：數(shù)據(jù)元素 obj是否屬于集合。 操作集合 （ 1）添加 add(obj)：在集合中添加數(shù)據(jù)元素 obj。 集合的運(yùn)算 主要有三種：兩個(gè)集合的并 A∪ B、兩個(gè)集合的交 A∩B、兩個(gè)集合的差 AB。 如果一個(gè)數(shù)據(jù)元素 x在一個(gè)集合 A中，則說(shuō)數(shù)據(jù)元素 x屬于 集合 A；如果一個(gè)數(shù)據(jù)元素 x不在一個(gè)集合 A中，就說(shuō)數(shù)據(jù)元素 x不屬于 集合 A。Vector類在 集合 集合 的概念 集合（ Set） 是具有某種相似特性的事物的全體。要說(shuō)明的是，國(guó)內(nèi)的大部分教材和科技書籍都把 Vector類翻譯為向量類，但這里的向量和數(shù)學(xué)上的向量概念完全不同。如果程序開始時(shí)定義的數(shù)組長(zhǎng)度為 10，且數(shù)組中已經(jīng)存放了若干數(shù)據(jù)元素，要在程序運(yùn)行過(guò)程中擴(kuò)充數(shù)組長(zhǎng)度為 20，且把數(shù)組中原先存放的數(shù)據(jù)元素原樣保存，則系統(tǒng)不提供直接支持，需要應(yīng)用程序自己實(shí)現(xiàn)。 Java語(yǔ)言（以及大部分高級(jí)程序設(shè)計(jì)語(yǔ)言）支持的數(shù)組操作有 ： （ 1）分配內(nèi)存空間 （ 2）獲得數(shù)組長(zhǎng)度 （ 3）存數(shù)組元素 （ 4）取數(shù)組元素 2 對(duì)象數(shù)組 除了可以定義基本數(shù)據(jù)類型的數(shù)組外， Java語(yǔ)言還可以定義對(duì)象數(shù)組 。其約束條件為： 0≤i≤getLength()1。其約束條件為： 0≤i≤getLength()1。 （ 2）取數(shù)組長(zhǎng)度 getLength()：取數(shù)組的長(zhǎng)度。對(duì)一個(gè)有 n個(gè)數(shù)據(jù)元素的 一維 數(shù)組，設(shè) a0是下標(biāo)為 0的數(shù)組元素， Loc(a0)是 a0的內(nèi)存單元地址， k是每個(gè)數(shù)據(jù)元素所需的字節(jié)個(gè)數(shù)，則數(shù)組中任一數(shù)據(jù)元素 ai的內(nèi)存單元地址 Loc(ai)可由下面公式求出： Loc(ai) = Loc(a0) + i k ( 0≤i＜ n ) 5 對(duì)一個(gè) m行 n列的 二維 數(shù)組，設(shè) a00是行下標(biāo)和列下標(biāo)均為 0的數(shù)組元素， Loc(a00)是 a00的存儲(chǔ)地址， k是每個(gè)數(shù)據(jù)元素所需的字節(jié)個(gè)數(shù)，則數(shù)組中任一數(shù)據(jù)元素 aij的內(nèi)存單元地址 Loc(aij)可由下面公式求出： Loc(aij) = Loc(a00) + (i n + j) k ( 0≤i＜ m, 0≤j＜ n） 1 2 34 5 67 8 9147258369(c) 列優(yōu)先順序存儲(chǔ)結(jié)構(gòu)(b) 行優(yōu)先順序存儲(chǔ)結(jié)構(gòu)123456789第1行第2行第3行第1列第2列第3列(a) 二維數(shù)組的邏輯結(jié)構(gòu)下標(biāo)028765431下標(biāo)028765431二維數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 數(shù)組 抽象數(shù)據(jù)類型 數(shù)據(jù)集合 數(shù)組的數(shù)據(jù)集合可以表示為 a0, a1, a2, ..., an1，且 限定數(shù)組元素必須存儲(chǔ)在地址連續(xù)的內(nèi)存單元中。kt‖ =‖ 比 較1?kt‖ ==第 5章 數(shù)組、集合和矩陣 數(shù)組 向量類 集合 矩陣類 特殊矩陣 稀疏矩陣 本章主要知識(shí)點(diǎn)： ● 數(shù)組的定義、實(shí)現(xiàn)機(jī)制和 Java語(yǔ)言支持的數(shù)組功能 ● 向量類擴(kuò)充的數(shù)組功能以及這些擴(kuò)充功能的實(shí)現(xiàn)方法 ● 集合的概念和集合類的設(shè)計(jì)方法 ● 矩陣類的設(shè)計(jì)方法 ● 特殊矩陣的概念和特殊矩陣的壓縮存儲(chǔ)方法 ● 稀疏矩陣的概念和稀疏矩陣的壓縮存儲(chǔ)方法，主要是稀疏矩陣的三元組以及三元組的幾種典型存儲(chǔ)結(jié)構(gòu) 數(shù)組 數(shù)組的定義 數(shù)組 是 n（ n≥1）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,...,an1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限集合。t0t. . .139。t0t . . .kt右 滑39。 5 計(jì)算 next[j]值的函數(shù)設(shè)計(jì)方法 設(shè)有 next[j]=k，即在模式串 t中存在“ t0t1…tk 1” = “tj ktjk+1…tj 1”（ 0kj），其中 k為滿足等式的最大值，則計(jì)算 next[j+1]的值有兩種情況： （ 1）若 tk=tj，則表明在模式串 t中有“ t0t1…tk” = “tj ktjk+1…tj” ，且不可能存在任何一個(gè) k’k滿足上式， 因此有： next[j+1] = next[j] + 1 = k + 1 （ 2）若 tk≠tj，則可把計(jì)算 next[j+1]值的問(wèn)題看成是一個(gè)如圖 47的模式匹配問(wèn)題，即把模式串 t’向右滑動(dòng)至 k’=next[k]（ 0k’kj）。 比較過(guò)程有兩種情況： 一是 j增加到某個(gè)值或 j退回到某個(gè) j=next[j]值時(shí)有 si=tj，則此時(shí) i和 j分別增 1再繼續(xù)比較； 二是 j退回到 j=1時(shí)，令主串和子串的下標(biāo)各增 1，隨后比較 si+1和 t0。令 i的初值為 start， j的初值為 0。 3 模式串中最大真子串的求法 模式串中每個(gè)字符的最大真子串構(gòu)成一個(gè)數(shù)組，定義為模式串的 next[j]函數(shù)。因此，對(duì)于主串s=“s0s1…sn 1”，子串 t=“t0t1…tm 1”，可以首先計(jì)算出模式串 t中每個(gè)字符的最大真子串的字符個(gè)數(shù) k。又因有 t0=t2， s2=t2，所以必有 s2=t0，因此下來(lái)可直接比較 s3和 t1。此時(shí)有 s0＝ t0＝’ a’，s1＝ t1＝’ b’， s2＝ t2＝’ a’， s3≠t3。 （ 2）第二種情況。但是因t0≠t1，而 s1=t1，所以一定有 s1≠t0。這可分兩種情況 : （ 1）第一種情況。KMP算法 的特點(diǎn)主要是，消除了 BruteForce算法的主串比較位置在相當(dāng)多個(gè)字符比較相等后，只要有一個(gè)字符比較不相等，主串位置便需要回退的缺點(diǎn)。若存在模式串 t中的每個(gè)字符依次和主串 s中的一個(gè)連續(xù)字符序列相等，則模式匹配成功，函數(shù)返回模式串