《《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt（175頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu) 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 簡單數(shù)據(jù)結(jié)構(gòu) 簡單的數(shù)據(jù)結(jié)構(gòu) ， 包括順序表 、 鏈表 、 棧 、 隊列和 廣義表 ， 它們和上一章介紹過的數(shù)組和串一起都同屬 于 線性結(jié)構(gòu) 。 在線性結(jié)構(gòu)中 ， 數(shù)據(jù)元素之間的關(guān)系是一對一的次 序關(guān)系 ， 其邏輯特征為： 存在一個惟一地被稱作 “ 第一個 ” 的數(shù)據(jù)元素； 存在一個惟一地被稱作 “ 最后一個 ” 的數(shù)據(jù)元素； 除第一個之外 ， 每個數(shù)據(jù)元素都只有一個前趨； 除最后一個之外 ， 每個數(shù)據(jù)元素都只有一個后繼 。 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.1 順序表 3.1.1 線性表

2、的基本概念 3.1.2 線性表的順序存儲結(jié)構(gòu) 順序表 3.1.3 順序表上的基本運算 線性表的基本概念 線性表 （ Linear List） 是一種最簡單最常用的數(shù)據(jù)結(jié)構(gòu) 。 一個線性表是由 n（ n0） 個相同類型數(shù)據(jù)元素 （ 結(jié)點 ） 組 成的 有限序列 。 表中有且僅有一個第一個結(jié)點 ， 它沒有前 趨而只有一個后繼；有且僅有一個最后一個結(jié)點 ， 它沒有 后繼而只有一個前趨；其余結(jié)點都只有一個前趨和一個后 繼 。 根據(jù)結(jié)點之間的關(guān)系可以排成一個線性序列： （ a1， a2， a3， a4， ， an） 其中： a1為第一個結(jié)點 ， an為最后一個結(jié)點；對于 i=2 n， ai-1是 ai的

3、前趨 ， ai是 ai-1的后繼； n稱作線性表的 長度 ， n為 0時稱作 空表 。 線性表的例子 線性表中的數(shù)據(jù)元素 （ 結(jié)點 ） 可以是一個數(shù) 、 一個符號 、 一頁書 、 一個記錄等 。 下面給出線性表的幾個例子： （ “ A”， “ B”， ， “ Z”） 是一個線性表 ， 稱作字母表 ， 表中 的數(shù)據(jù)元素都是單個大寫字母字符； （ 3， 7， 9， 12， 66， 87） 是一個線性表 ， 表中的每個數(shù)據(jù)元素都 是一個整數(shù)； 學生成績表也是一個線性表 ， 表中的數(shù)據(jù)元素為描述一個學生高 考情況的一個記錄 ， 它由姓名 、 準考證號 、 數(shù)學 、 語文 、 英語 、 理綜 、 總分七

4、個數(shù)據(jù)項組成 。 線性表的形式化定義 線性表的形式化定義如下： Linear List=(D,R) 其中： D=ai|ai Do， i=1， 2， ， n， n 0； R=|ai-1,ai Do， i=2， 3， ， n； Do為某個數(shù)據(jù)對象 。 線性表是一種相當靈活的數(shù)據(jù)結(jié)構(gòu) ， 其長度可根 據(jù)需要增減 ， 即對數(shù)據(jù)元素不僅可以訪問 ， 還可 進行插入和刪除 。 線性表的基本運算 置空表 setnull(L)：將線性表 L置為空表 。 求長度 length(L)：計算線性表 L中數(shù)據(jù)元素的個數(shù) 。 取元素 get(L,i)：取出線性表 L中第 i個數(shù)據(jù)元素； 要求 ilength(L)。 取

5、前趨 prior(L,x)：取出線性表 L中值為 x的元素的 前趨元素；要求 x的位序大于 1。 取后繼 next(L,x)：取出線性表 L中值為 x的元素的 后繼元素；要求 x的位序小于 length(L)。 定位序 locate(L,x)：確定元素 x在線性表 L中的位置 ， 并給出位置序號；若 L中無 x返回 0。 線性表的基本運算（續(xù)） 插入 insert(L,x,i)：在線性表 L中第 i個位置上插入值為 x的新 元素 ， 使表長增 1；要求 1ilength(L)+1。 刪除 delete(L,i)：刪除線性表 L中的第 i個元素 ， 使表長減 1； 要求 1ilength(L)。

6、 利用這些基本運算 ， 可以實現(xiàn)線性表的其它較復雜運算 ， 如線性表的分拆 、 合并 、 逆置等 。 在實際應用中 ， 當線性表作為一個運算對象時 ， 所需的運 算種類不一定相同 ， 不同的運算將構(gòu)成不同的抽象數(shù)據(jù)類 型 。 這里所給出的運算是定義在邏輯結(jié)構(gòu)上的抽象運算 ， 而運 算的實現(xiàn)要依賴于所采用的存儲結(jié)構(gòu) 。 3.1 順序表 3.1.1 線性表的基本概念 3.1.2 線性表的順序存儲結(jié)構(gòu) 順序表 3.1.3 順序表上的基本運算 線性表的順序存儲結(jié)構(gòu) 順序表 順序表 （ sequential list） 是用一組 地址連續(xù) 的存儲單 元依次存放線性表中的各個數(shù)據(jù)元素 ， 是一種最簡單 最

7、自然的線性表存儲方法 。 這組地址連續(xù)的存儲空間的大小依線性表中的數(shù)據(jù) 元素個數(shù)而定 ， 線性表中第一個元素存放在這組空間 的開始處 ， 第二個元素緊跟著存放在第一個元素之 后 ， ， 余類推 。 顯然 ， 順序表中相鄰的數(shù)據(jù)元素在計算機內(nèi)的存儲 位置也相鄰； 換句話說 ， 順序表以數(shù)據(jù)元素在計算機內(nèi)的 物理位 置相鄰 來表示數(shù)據(jù)元素在線性表中的邏輯相鄰關(guān)系 。 線性表的存儲地址計算公式 由于線性表中的數(shù)據(jù)元素具有相同的類型 ， 所以可 以很容易地確定順序表中每個數(shù)據(jù)元素在存儲空間中 與起始單元的相對位置； 假定線性表中每個數(shù)據(jù)元素需要占用 c個存儲單元 ， loc(a1)是第一個數(shù)據(jù)元素的存

8、儲地址 （ 也稱作基地 址 ） ， 則第 i個數(shù)據(jù)元素的存儲地址可由下式確定： loc(ai)=loc(a1)+(i-1)*c 其中： 1ilength(L)+ 1。 顯然 ， 順序表是一種可隨機存取的數(shù)據(jù)結(jié)構(gòu) 。 線性表的順序存儲結(jié)構(gòu)示意圖 順序表的順序存儲結(jié)構(gòu)（續(xù)） 由于在高級程序設(shè)計語言中的一維數(shù)組 （ 或向量 ） 在計算機內(nèi)分配的是一片連續(xù)的存儲單元 ， 所以可借 助一維數(shù)組為順序表開辟存儲空間存儲表中的數(shù)據(jù)元 素 。 考慮到線性表因插入 、 刪除運算長度可變 ， 數(shù)組的 容量要足夠大 （ 可設(shè)為 MAXSIZE， 其值依實際問題而 定 ） ， 并設(shè)一指示器變量 last指向表中的最后

9、一個元 素位置 。 為了討論方便 ， 我們假定元素是從數(shù)組下標為 1的位 置開始存放 ， 即 last=0時為空表 。 順序表的類型描述 #define MAXSIZE 500 typedef struct elemtyPe dataMAXSIZE; int last; sequenlist; 即把順序表類型 sequenlist描述為一個結(jié)構(gòu)體 ， 域 data數(shù)組存放表中的數(shù)據(jù)元素 ， 域 last存放表長 ， datalast存放表中最后一個元素 。 elemtype為表中數(shù)據(jù)元素的類型 ， 對于不同的實際問 題可以為不同的具體類型 ， 如整型 int、 實型 float、 字符型 ch

10、ar、 雙精度實型 double、 或其它結(jié)構(gòu)類型等 。 3.1 順序表 3.1.1 線性表的基本概念 3.1.2 線性表的順序存儲結(jié)構(gòu) 順序表 3.1.3 順序表上的基本運算 順序表上的基本運算 在定義了線性表的順序存儲結(jié)構(gòu)之后 ， 就可以討論 各種基本運算的實現(xiàn)問題了 。 順序表上的許多運算是很容易實現(xiàn)的 。 例如： 置空表就是使表長為 0， 即 (*L).last=0； 求表長就是讀出 last域的值 ， 即 (*L).last； 取元素就是按位序取出 data 域中相應元素 ， 即 (*L).datai；取前趨就是將元素 x的位序前一個元素取出 ， 即 (*L).datalocate(

11、L,x)-1； 取后繼即取出 (*L).datalocate(L,x)+1的值等 。 這里只討論定位序 、 插入和刪除運算的實現(xiàn)算法 。 1. 定位序 locate(L,x) 定位序即按值查找 ， 確定元素 x在順序表 L中的位置 。 最簡單的方法是從第一個元素起和 x比較 ， 直到找到 一個值為 x的數(shù)據(jù)元素返回它的位置序號 （ 即數(shù)組下 標 ） ， 或者找遍表中所有元素均無值為 x的元素時返 回 0。 其算法描述如下： int locate(L,x) sequenlist *L; elemtyPe x; int i=1; while(ilast) 定位序 （續(xù)） if(iL-last) r

12、eturn 0; /*未找到值為 x的元素返回 0*/ else return i; /*找到值為 x的元素返回它的位序 i*/ /*locate*/ 該算法的主要時間花費在于查找比較的循環(huán) 。 當 a1=x時一次比較成功 ， 當 an=x時 n次比較成功 ， 在 x 分 布位置等概率的情況下平均比較次數(shù)為 (n+1)/2；查找 不成功時的比較次數(shù)為 n+1。 所以算法的時間復雜度 為 O(n)。 2. 插入 insert(L,x,i) 插入運算 是指在順序表 L的第 i個元素之前加入一個 新元素 x。 插入的結(jié)果使 x 在順序表中第 i個元素位置 上 ， 使順序表的長度由 n變?yōu)?n+1。

13、插入新元素 x后 ， 部分數(shù)據(jù)元素間的邏輯關(guān)系發(fā)生了 改變 ， 要求物理存儲位置也要相應變化 。 除非 i=n+1， 否則必須將位序為 i,i+1, ,n的數(shù)據(jù)元 素向后移動一個元素位置 ， 空出第 i個位置插入新元 素 x；在 i=n+1時直接將新元素 x插入表尾 。 在順序表中插入新元素 x的過程 插入運算的算法描述 void insert(L,x,i) sequenlist *L; elemtype x; int i; int j; if(i(L-last+1) printf(“插入位置不正確 n”); else if(L-last=MAXSIZE) printf(“表已滿 ， 發(fā)生上溢

14、 n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/ 插入運算算法的時間復雜度 算法中的數(shù)據(jù)元素移動是從第 n個元素到第 i個元素 依次后移的 。 算法中的主要時間開銷在于后移元素的 for循環(huán) ， 循環(huán)執(zhí)行 n-i+1次 。 當 i=n+1時不需移動元素是最 好情況 ， 當 i=1時需移動元素 n次是最壞情況 ， 在插 入位置等概率分布時的平均移動次數(shù)為 n/2。 所以算法最好情況下的時間復雜度為 O(1)， 在最壞 情況下的時間復雜度為 O(n)， 在平均情況下的時

15、間 復雜度也是 O(n)。 3.刪除 delete(L,i) 刪除運算是把順序表中第 i個元素刪掉 ， 使順序表的 長度由 n變?yōu)?n-1， 其部分元素的邏輯關(guān)系和存儲位置 也發(fā)生相應變化 ， 即 由 （ a1,a2, ,ai-1,ai,ai+1, ,an） 變成為 （ a1,a2, ,ai-1,ai+1, ,an） 。 除非 i=n時直接刪除 ， 否則需要從第 i+1元素到第 n元 素依次前移一個元素位置 。 在順序表中刪除第 i個元素過程 刪除運算的算法描述 void delete(L,i) sequenlist *L; int i; int j; if(iL-last) printf(“

16、刪除位置不正確 n”); else for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last=L-last-1; /*delete*/ 刪除運算算法的時間復雜度 由刪除過程可以看出 ， 通過元素 ai+1到 an的依次前移 就達到了刪除 ai的目的 。 該算法的時間開銷也主要是在元素的移動 。 當 i=n時最好不需移動 ， 當 i=1時最壞需移動 n-1次 ， 在等概率的情況下需平均移動元素 (n-1)/2次 。 其時 間復雜度在最好 、 最壞和平均的情況下分別為 O(1)， O(n)和 O(n)。 舉例 刪除順序表中的重復元素 一個順序表中可能含有一些值相同

17、的重復元素 ， 題目 要求對于值相同的重復元素只保留位序最小的一個而 刪除其它多余的元素 。 如 （ 5， 2， 2， 3， 5， 2） 經(jīng)刪除重復元素后變?yōu)?（ 5， 2， 3） 算法思路 ：從順序表中第一個元素起 ， 逐個檢查它后 面是否有值相同的其它元素 ， 若有便刪除之；直到表 中所有元素都已無重復元素為止 。 為此 ， 算法中需設(shè) 兩重循環(huán) ， 外層控制清除的趟數(shù) ， 內(nèi)層控制每趟的檢 查范圍 。 刪除順序表中的重復元素的算法描述 void Purge(L) sequenlist *L; int i,j,k; i=1; while(ilast) j=i+1; while(jlast)

18、 if(L-dataj=L-datai) for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/ 舉例 有序表的合并 順序表 A和 B的元素均按由小到大的升序排列 ， 編 寫算法將它們合并成為順序表 C， 要求 C中元素也是 從小到大的升序排列 。 算法思路 ：依次掃描 A和 B中元素 ， 比較當前兩個 元素值 ， 將較小的元素賦給 C， 直到其中一個順序 表掃描完畢 ， 然后將另一個順序表中剩余元素賦給 C即可 。 有序表的合并的算法描述 void merge(C,A,B) sequenli

19、st *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-datak+=B-dataj+; C-last=k-1; /*merge*/ 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.2 鏈表 順序表的特點是 ， 邏輯關(guān)系上相鄰的兩個元素在物理位置上 也相鄰 。 這一特點使得順序表有如下兩個優(yōu)點： 無需為表示數(shù)據(jù)元素之間的關(guān)系而額外增加存儲空間； 可以隨機存取表中

20、任一數(shù)據(jù)元素 ， 元素存儲位置可以用一個簡單 、 直觀的公式表示 。 這一特點也造成了這種存儲結(jié)構(gòu)的兩個缺點： 插入和刪除運算必須移動大量 （ 幾乎一半 ） 數(shù)據(jù)元素 ， 效率較低； 必須預先分配存儲空間 ， 造成空間利用率低 ， 且表的容量難以擴充 。 本節(jié)介紹線性表的另一種存儲結(jié)構(gòu) 鏈式存儲結(jié)構(gòu) 。 它不 要求邏輯上相鄰的元素在物理位置上也相鄰 ， 為表示元素之 間的關(guān)系要增加額外存儲空間 ， 也不能隨機存取數(shù)據(jù)元素； 但是它沒有順序存儲結(jié)構(gòu)所具有的缺點 。 3.2 鏈表 3.2.1 線性表的鏈式存儲結(jié)構(gòu) 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線

21、性表應用舉例 一元多項式相加問題 線性表的鏈式存儲結(jié)構(gòu) 鏈表 線性表的 鏈式存儲結(jié)構(gòu) ， 是用一組任意的存儲單元 （ 這組存 儲單元的地址可以連續(xù) ， 也可以不連續(xù) ） 來存放線性表中的各 個數(shù)據(jù)元素的 。 為了表示出每個數(shù)據(jù)元素與其后繼之間的關(guān)系 ， 對每個元素 除了存儲元素本身的信息外 ， 還需存儲指示該元素的后繼元素 的地址；這兩部分信息組成一個結(jié)點 。 存放數(shù)據(jù)元素信息的域 data稱作 數(shù)據(jù)域 ， 存放后繼元素地址信 息的域 next稱作 指針域 或 鏈域 。 一個線性表的 n個元素通過每 個結(jié)點的指針域拉成一條 “ 鏈子 ” ， 所以稱之 鏈表 （ Linked List） 。 由

22、于這種鏈表中每個結(jié)點只含有一個指向后繼的指針 ， 所以稱作 線性鏈表 或 單鏈表 （ Single Linked List） 。 單鏈表存儲舉例 對于線性表 （ mon,tue,wed,thu,fri,sat,sun） ， 其單鏈 表存儲示意圖如下圖 。 單鏈表 由于單鏈表中每個結(jié)點的存儲地址是放在其前趨結(jié) 點的指針域中 ， 因此整個鏈表的存取必須從第一個 結(jié)點開始；需設(shè)立頭指針指示鏈表中的第一個結(jié)點 。 這樣就可以由頭指針找到第一個結(jié)點 ， 再由第一個 結(jié)點的指針域找到第二個結(jié)點 ， ， 依次順著指 針域找到每個結(jié)點 。 此外 ， 在鏈表中最后一個結(jié)點沒有后繼 ， 該結(jié)點的 指針域為空 ，

23、用 NULL或 表示空指針域 。 單鏈表（續(xù)） 對于單鏈表 ， 我們并不關(guān)心各個結(jié)點的實際存儲位 置 ， 而關(guān)心的是結(jié)點間的邏輯次序關(guān)系 ， 故可將單 鏈表 （ mon,tue,wed,thu,fri,sat,sun） 的畫成如下圖 。 其中用箭頭表示的指針域中的指針 。 由上圖可以很 清楚地看出 ， 線性表的鏈式存儲結(jié)構(gòu)是通過鏈指針 來表示數(shù)據(jù)元素之間的邏輯關(guān)系的 ， 是非順序存儲 結(jié)構(gòu) 。 整個單鏈表可由頭指針惟一確定 ， 所以常用 頭指針名來命名一個單鏈表 ， 如稱表 H則意味著該單 鏈表的頭指針為 H。 單鏈表的 類型 描述 typedef struct node elemtype d

24、ata; struct node *next; LinkList; LinkList *H,*P; 需要說明的是 ， 定義 LinkList與 struct node為相同類 型不同的類型標識符 （ 名字 ） ， 是為了用它說明單鏈表類型 ， 這種方法有利于提高程序或算法的可讀性 。 另外 ， 指針變量所指向的結(jié)點地址并不是在程序中顯式給 出 ， 而是在程序的執(zhí)行過程中用標準函數(shù) malloc根據(jù)需要 動態(tài)生成的 。 單鏈表結(jié)點空間的申請與釋放 malloc函數(shù)的返回值類型在 ANSI C版本中是 void *類型 ， 所以動態(tài)生成的結(jié)點類型必須強制轉(zhuǎn)換為指向該結(jié)點的指針類 型 。 具體方法為

25、 P=(LinkList*)malloc(sizeof(LinkList); 它獲得一個單鏈表類型結(jié)點 ， 結(jié)點地址在指針變量 P。 如下圖 當要釋放結(jié)點空間時可用標準函數(shù) free完成 ， 即 free(P); 它釋放指針 P所指結(jié)點空間給內(nèi)存 。 對結(jié)點中兩個域的訪問 ， 只能通過指向該結(jié)點的指針進行 ， 如 P-data和 P-next 或者 (*P).data和 (*P).next 3.2 鏈表 3.2.1 線性表的鏈式存儲結(jié)構(gòu) 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題 單鏈表上的基本運算 為了方便運算 ， 使

26、單鏈表的空表和非空表的處理一 致 ， 通常在單鏈表的第一個結(jié)點前增加一個頭結(jié)點 。 頭結(jié)點的數(shù)據(jù)類型和其它結(jié)點一致 ， 它的數(shù)據(jù)域無 定義 ， 指針域中存放第一個數(shù)據(jù)結(jié)點的地址 ， 空表 時指針域為空 。 空表和非空表的圖形表示如下： 若無特殊說明 ， 本章算法均采用帶頭結(jié)點的單鏈表 。 1.建立單鏈表 在單鏈表中每個元素的存儲空間是在需要時才申請 ， 其邏輯 關(guān)系靠指針來表示 ， 所以在建立單鏈表的過程中更多關(guān)心的 是指針的鏈接 。 一開始先申請并生成頭結(jié)點 ， 然后每讀入一個數(shù)據(jù)元素申請 一個結(jié)點 ， 填入數(shù)據(jù)后插入表尾 ， 為此要設(shè)一個尾指針 r。 具體的算法描述如下： LinkList

27、 *CreateLinkList() char ch; int x; LinkList *head; /*head為頭結(jié)點指針 */ LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList); head-next=NULL; 建立單鏈表（續(xù)） r=head; /*尾指針初始化 */ ch=getchar(); while(ch!=*) /*“*”為輸入數(shù)據(jù)結(jié)束符號 */ scanf(“%d”, P=(LinkList *)malloc(sizeof(LinkList); P-data=x; P-next=NULL; r-next=P; r

28、=r-next; ch=getchar(); return head; /*CreateLinkList*/ 該算法的時間復雜度為 O(n)。 單鏈表建立過程示例 線性表 （ 25， 45， 18， 76， 29） 的單鏈表動態(tài)建立過程如下 圖： 2.求表長 只要設(shè)一個移動指針掃描整個單鏈表 ， 就可以統(tǒng)計出元素個 數(shù)即表長 。 其算法描述如下： int LengthLinkList(L) LinkList *L; LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表長 */ /*LengthLink

29、List*/ 該算法掃描整個單鏈表 ， 時間復雜度為 O(n)。 3.元素的查找方法一 單鏈表上元素的查找分 按值查找 和按序號查找。 按值查找 的方法是，從第一個結(jié)點起判斷當前結(jié)點的值是否 等于給定值，若找到返回該結(jié)點地址，否則繼續(xù)下一個結(jié)點； 若整個表中未找到返回 NULL。算法描述如下： LinkList *LocateLinkList(L,x) LinkList *L; elemtyPe x; LinkList *P; P=L-next; while(P!=NULL) return P; /*返回找到的結(jié)點位置或 NULL*/ /*LocateLinkList*/ 元素的查找方法二 按

30、序號查找 的方法是，從第一個結(jié)點起做 i次指針傳遞返回該 結(jié)點地址，若找不到 i次已到表尾則返回 NULL， 算法描述如下： LinkList *GetLinkList(L,i) LinkList *L; int i; LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; /*GetLinkList*/ 這兩個算法的時間復雜度在最壞情況下和等概率平均情況下都 為 O(n)。 4.插入 在單鏈表中插入元素只需修改有關(guān)結(jié)點的指針域內(nèi)容 ， 不需 象順序表那樣移動

31、元素 。 插入運算有 前插 和 后插 兩種：設(shè) P指向單鏈表中某結(jié)點 ， S指 向待插入的新結(jié)點 ， 把 *S插入到 *P的前面稱作 前插 ， 而把 *S 插入 *P的后面稱作 后插 。 后插操作的命令如下 ， 且操作次序不能交換 。 S-next=P-next; P-next=S; 后插的示意圖如下圖： 插入（續(xù)） 前插需要 *P的前趨 *q， 然后再完成在 *q之后插入 *S的后插； 這就需要從第一個結(jié)點開始查找 *P的前趨 *q， 使得時間開銷 由后插的 O(1)上升到 O(n)。 能不能也用 O(1)的時間開銷完成 前插呢 ？ 回答是肯定的 。 我們只要先把 *S插入到 *P的后面 ，

32、 然后再將 P-data與 S-data互相交換即可；這樣既能滿足邏輯 關(guān)系 ， 也能使得時間開銷為 O(1)。 其操作過程為 S-next=P-next; P-next=S; x=P-data; P-data=S-data; S-data=x; 插入算法描述 在單鏈表 L中第 i個位置上插入值為 x的元素的算法描述： LinkList *insertLinkList(L,x,i) LinkList *L; elemtyPe x; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1個結(jié)點 */ if(P=NULL) Printf(“第 i

33、-1個元素不存在 ， 參數(shù) i有錯 n”); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; /*insertLinkList*/ 該算法的時間復雜度為 O(n)。 5.刪除 設(shè) P為指向單鏈表中某結(jié)點的指針 ， 刪除 P所指結(jié)點即 *P的操 作示意圖如下圖 。 由示意圖可見 ， 要刪除 *P先要找到 *P的前趨結(jié)點 *q， 然后完 成指針的變化操作即可 。 顯然要找到 *P的前趨得有 O(n)的時間開銷 。 在找到 *q的前提 下 ， 刪除 *P的操作可由下列語句實現(xiàn)： q-next

34、=P-next; free (P); 刪除（續(xù)） 若要刪除 P所指結(jié)點的后繼結(jié)點 （ 假設(shè)存在 ） ， 時間開銷 為 O(1),直接完成刪除即可： S=P-next; P-next=S-next; free S; 要刪除單鏈表 L中的第 i個結(jié)點 ， 關(guān)鍵是先找出第 i-1個結(jié) 點 （ 即前趨結(jié)點 ） ， 然后完成刪除并釋放被刪結(jié)點空間的 工作 。 刪除單鏈表 L中的第 i個結(jié)點算法 LinkList *deleteLinkList(L,i) LinkList *L; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1個結(jié)點 */ if(

35、P=NULL) Printf(“第 i-1個元素不存在 ， 參數(shù) i 有錯 n”); else S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 該算法的時間復雜度為 O(n)。 舉例 將單鏈表 H逆置 所謂 逆置 是指結(jié)點間的關(guān)系相反 ， 即前趨變后繼而后繼變前 趨 。 如圖 (a)的單鏈表逆置后成為圖 (b)的單鏈表 。 算法思路 ：依次從原鏈表中取出每個結(jié)點 ， 每次都把它作為 第一個結(jié)點插入到新鏈表中去 。 為此要借用兩個指針變量 P和 q， P用來指向原鏈表中的當前第一個結(jié)點 ， q用來指向從原表 取出的每一個結(jié)點并利用它插入到

36、新鏈表中去 ， 當 P為空時完 成逆置 。 將單鏈表 H逆置的算法描述 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-next; q-next=H-next; H-next=q; *reverse*/ 該算法沒有開辟新的存儲空間 ， 對鏈表順序掃描一遍就完成 了逆置 ， 時間開銷為 O(n)。 3.2 鏈表 3.2.1 線性表的鏈式存儲結(jié)構(gòu) 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題

37、循環(huán)鏈表 循環(huán)鏈表 （ Circular Linked List） 是鏈式存 儲結(jié)構(gòu)的另一種形式 ， 其特點是表中最后一個結(jié)點的 指針域指向頭結(jié)點 ， 使整個鏈表構(gòu)成一個環(huán) ， 可以從 表中任一結(jié)點出發(fā)訪問遍所有結(jié)點 （ 即遍歷 ） 。 單循環(huán)鏈表的空表和非空表兩種狀態(tài)如下圖所示： 單循環(huán)鏈表上的基本運算與單鏈表基本一致 ， 差別 僅在于對最后一個結(jié)點的循環(huán)處理上；單鏈表是判斷 指針是否為空 （ NULL） ， 而單循環(huán)鏈表是判斷指針是 否指向頭結(jié)點 。 求循環(huán)鏈表的表長算法描述 int Lengthcircularlist(L) LinkList *L; LinkList *P; int j

38、=0; P=L; While(P-next!=L) /*與求單鏈表表長差別僅在于把 NULL換為頭指針 L*/ P=P-next; j+; return j; /*Lengthcircularlist*/ 循環(huán)鏈表（續(xù)） 有時對鏈表常做的操作是在表尾和表頭進行 。 為了找尾結(jié)點必須從頭結(jié)點開始掃描全部結(jié)點 ， 時 間開銷為 O(n)；而找頭結(jié)點僅 O(1)時間 。 改進的方法是不設(shè)頭指針而設(shè)尾指針 。 這樣找到頭 結(jié)點和尾結(jié)點都只需要 O(1)的時間 ， 頭結(jié)點為 (*(*r).next).next而尾結(jié)點為 r， 對于在鏈表的頭尾 操作的應用十分方便 。 帶尾指針的循環(huán)鏈表 如下圖所示： 雙

39、向鏈表 在單循環(huán)鏈表中 ， 雖然可以從任一已知結(jié)點出發(fā)找到其 前趨結(jié)點 ， 但需耗時 O(n)， 原因在于每個結(jié)點只有一個 指向后繼的指針域 。 如果希望能夠快速確定任一結(jié)點的前趨 ， 就必須付出空 間代價 ， 即增加一個指針域存儲其前趨信息 ， 這樣每個 結(jié)點就有兩個方向不同的鏈 ， 稱之為 雙向鏈表 （ double linked list） 。 如果讓每條鏈都構(gòu)成一個環(huán) ， 則稱為 雙向循環(huán)鏈表 （ double circular linked list） 。 雙向鏈表的使用往往做成雙循環(huán)鏈表 ， 和單循環(huán)鏈表類 似 ， 也是由頭指針標識 ， 也可以增加頭結(jié)點方便運算 。 雙向鏈表的結(jié)點

40、定義和類型 typedef struct dupnode elemtype data; struct dupnode *prior,*next; dulinklist; dulinklist *H; 雙向鏈表是一種對稱結(jié)構(gòu) ， 每個結(jié)點都既有指向其前趨 的指針 ， 也有指向其后繼的指針；每個結(jié)點的地址既放 在其后繼結(jié)點的前趨域中 ， 也放在其前趨結(jié)點的后繼域 中 。 即有 P-next-prior=P=P-prior-next 雙向鏈表示意圖 雙向鏈表插入運算 與單鏈表相比雙向鏈表的運算要方便得多 。 然而由于要 涉及多指針域的運算 ， 對于某些運算要注意運算的先后 順序 。 在 *P之前插入

41、 *S的步驟為： P-prior-next=s; S-prior=P-prior; S-next=P; P-prior=S; 盡管上面的指針操作順序不是惟一的 ， 但是也不能任意 次序 ， 必須保證操作 在操作 之前完成 ， 否則 *P的前 趨域的信息就丟掉了 ， 導致不能正確地插入 *S。 雙向鏈表插入運算的示意圖 雙向鏈表的刪除運算 刪除 P所指結(jié)點 （ 即 *P） 的操作步驟為： P-prior-next=P-next; P-next-prior=P-prior; free (P); 在雙向鏈表中刪除一個結(jié)點的運算如下圖所示： 3.2 鏈表 3.2.1 線性表的鏈式存儲結(jié)構(gòu) 鏈表 3.2

42、.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題 一元多項式 一個一元多項式可以表示為 P(x)=a0+a1x+a2x2+ +anxn 其中： a0,a1,a2, ,an這 n+1個系數(shù)惟一確定了多項式 ， 而 每一項的指數(shù)隱含在系數(shù) ai的序號中 ， 所以一元多項式 可以由線性表 （ a0,a1, ,an） 來表示 。 設(shè) A=(a0,a1, ,an )， B=(b0,b1, ,bm)， 則多項式加法就是 求 A+B=C。 其中： C=(a0+b0,a1+b1, ,am+bm,am+1, ,an) 或 C=（ a0+b0,a1+b1,

43、， an+bn,bn+1, ,bm） 。 一元多項式在計算機中的表示 如何在計算機中表示描述多項式的線性表呢 ？ 我們首先考 慮用順序表 （ 即順序存儲結(jié)構(gòu) ） 。 如果只存儲系數(shù)讓指數(shù)隱含在系數(shù)序號中 ， 則會浪費存儲 空間 ， 如 T(x)=3+5x200+7x1000的線性表長度為 1001， 而其中僅 有三個非零元素 ， 故應當避免 。 解決的辦法是對每一非零項用 （ 系數(shù) ， 指數(shù) ） 二元組 ， T(x) 只需存儲 （ 3， 0） ， （ 5， 200） 和 （ 7， 1000） 三個有序?qū)?， 顯然對高階稀疏多項式這種方法較好 。 順序存儲便于訪問 ， 但插入刪除需大量移動元素

44、， 所以對 只需求多項式的值無需修改系數(shù)和指數(shù)值的情況下 ， 采用順 序表結(jié)構(gòu)較好 。 一元多項式的數(shù)據(jù)類型定義 如果是多項式的運算問題如相加和相乘等 ， 考慮到 會產(chǎn)生新的項和系數(shù)為零項減少這兩種情況 ， 宜考 慮采用鏈式存儲結(jié)構(gòu)即單鏈表實現(xiàn) 。 其數(shù)據(jù)類型可如下定義： typedef struct linknode float coef; int exp; struct linknode *next; polynomial; 多項式的鏈式存儲表示示例 假設(shè)使用頭結(jié)點 ， 前述的 T(X)= 3+5x200+7x1000可表示 為如下圖所示的結(jié)構(gòu)： 多項式相加算法的思路 不產(chǎn)生新結(jié)點而利用原

45、有結(jié)點空間 ， 設(shè)兩個指針變 量 p和 q分別指向 A和 B兩個多項式單鏈表的第一個結(jié) 點 ， 依次比較兩指針所指結(jié)點的指數(shù)項 。 若指數(shù)相等系數(shù)相加 ， 和不為零修改 *p的系數(shù)項并 刪除 *q， 和為零刪除 *p和 *q； 若指數(shù)不等 ， p-expexp時 *p為和多項式中的一 項 ， p-expq-exp時把 *q插在 *p之前 （ *q為和多項 式中的一項 ） ； 所有操作之后要相應移動指針 。 直到其中一個鏈空 ， 把另一個鏈剩下的結(jié)點插在 *p之后 。 多項式相加算法的描述 void polyadd(A,B) polynomial *A,*B; polynomial *p,*q,

46、*s,*r; float x; p=A-next; q=B-next; s=A; while(p!=NULL) q-next=p; /*把 p接在 q所指結(jié)點后 */ s-next=q; /*把 q接入結(jié)果鏈 */ s=q; q=r; else if(p-expexp) s=p; p=p-next; 多項式相加算法的描述（續(xù)） else x=p-coef+q-coef; if(x!=0) p-coef=x; s=p; else s-next=p-next; free(p); p=s-next; r=q; q=q-next; free(r); if(q!=NULL) s-next=q; /*把

47、q鏈剩余結(jié)點鏈入結(jié)果鏈 */ free(B); /* polyadd*/ 該算法的比較次數(shù)與 A、 B兩個多項式的長度 m和 n有關(guān) ， 算法 的時間復雜度為 O(m+n)。 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現(xiàn) 3.3.3 鏈棧及運算實現(xiàn) 3.3.4 棧的應用舉例 遞歸的實現(xiàn) 棧的概念 棧 （ stack） 是操作受限的線性表 ， 限定對元素 的插入和刪除運算只能在表的一端進行 。 通常把進行插入和刪除操作的這一端稱作 棧頂 （ top） ， 另一端稱作 棧底 （

48、bottom） ； 把棧的插入元素操作稱作 進棧 、 入棧 或 壓入 ； 棧的刪除元素操作稱作 退棧 、 出棧 或 彈出 ； 當棧中沒有元素時稱作 空棧 。 棧的概念（續(xù)） 由棧的定義可知 ， 每一次 入棧 的 元素都在原棧頂元素之上成為新 的棧頂元素 ， 每一次 出棧 的元素 總是當前棧頂元素使次棧頂元素 成為新的棧頂元素 ， 即最后進棧 的元素總是最先出棧 。 所以棧也 稱作 后進先出 （ Last In First Out） 表 ， 簡稱 LIFO表 。 如右圖 所示 ， 元素是以 a1,a2, ,an-1,an 的次序進棧 ， 出棧的次序則是 an,an-1, ,a2,a1。 棧的基本

49、運算 置空棧 setnull(s)：將棧 S設(shè)置成空棧 ， 即不管棧的原來 狀態(tài)如何一律置為空棧； 判棧空 empty(s)：返回一個布爾值 ， 當棧 S為空時返回 1， 否則返回 0； 進棧 push(s,x)：該操作把元素 X壓入棧 S中 ， 成為新的棧 頂元素； 出棧 pop(s)：該操作從棧頂彈出棧頂元素并返回 ， 棧 S為空 時返回 NULL； 讀棧頂元素 gettop(s)：該操作返回棧 S的棧頂元素 ， 當棧 S為空時返回 NULL；它與 pop(s)的差別僅在于沒有彈出棧頂 元素 ， 棧 S 的狀態(tài)沒有改變 ， 只是讀棧頂元素的值并返回 。 3.3 棧 3.3.1 棧的概念及運

50、算 3.3.2 順序棧及運算實現(xiàn) 3.3.3 鏈棧及運算實現(xiàn) 3.3.4 棧的應用舉例 遞歸的實現(xiàn) 順序棧 利用順序存儲結(jié)構(gòu)實現(xiàn)的棧稱作 順序棧 （ sequential stack） 。 類似于順序表 ， 棧中的數(shù)據(jù)元素用一個預設(shè)的足夠長度的 一維數(shù)組來存放 ， 棧底位置可以設(shè)在數(shù)組的任一端點 ， 而 棧頂是隨著插入和刪除運算而變化的 ， 用 top指針指示當前 棧頂?shù)奈恢?。 順序棧的類型描述如下： #define MAXSIZE 100 typedef struct elemtype dataMAXSIZE; int top; seqstack; seqstack *s; 順序棧（續(xù)）

51、通常把 0下標端設(shè)為棧底 ， 這樣棧空時棧頂指針 top=-1， 棧 滿時棧頂指針 top= MAXSIZE-1； 入棧 時棧頂指針加 1（ 即 s-top+） ， 然后數(shù)據(jù)元素進棧； 出棧 時在讀出棧頂數(shù)據(jù)元素后棧頂指針減 1， 即 s-top-。 在棧滿時做入棧操作會產(chǎn)生空間不足的情況 ， 簡稱 上溢 （ overflow） ； 而在?？諘r做出棧操作會產(chǎn)生無元素可出的情況 ， 簡稱 下 溢 （ underflow） 。 上溢和下溢兩種情況均應該避免 ， 而棧空在應用中通常作 為算法 （ 或程序 ） 的控制轉(zhuǎn)移條件 。 棧頂指針與數(shù)據(jù)元素之間的關(guān)系 順序棧的基本運算 空棧操作 置空棧算法 v

52、oid setnull(seqstack *s) /*不論棧 S狀態(tài)如何 ， 都置 top為 -1*/ s-top=-1; 判棧空算法 int empty(seqstack *s) /*依 top值 ， 在空棧時返回 1， 否則返回 0*/ if(s-top=-1) return 1; else return 0; 順序棧的基本運算 進棧 進棧算法 int push(seqstack *s,elemtype x) /*把元素 x壓入棧 s中 */ if(s-top=MAXSIZE-1) return 0; /*棧上溢進棧不成功返回 0標志 */ else s-top+; /*棧頂指針加 1*/

53、 s-datas-top=x; /*元素 x進棧 */ return 1; /*進棧成功返回 1標志 */ 順序棧的基本運算 出棧 出棧算法 elemtype pop(seqstack *s) if(s-top=-1) return NULL; else s-top-; /*棧頂指針減 1*/ return s-datas-top+1; /*返回原棧頂元素的值 */ 順序棧的基本運算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(seqstack *s) /*讀棧頂元素并返回其值 */ if(s-top=-1) return NULL; /*棧空無元素返回 NULL*/ else

54、 return s-datas-top; /*否則返回棧頂元素值 */ 兩棧共享 在一個應用程序中需要使用多個棧的時候 ， 為了提高空間 的使用效率 ， 減少預分配空間過多造成的浪費 ， 又能降低 發(fā)生棧上溢而產(chǎn)生錯誤中斷的可能性 ， 可以讓多個棧共享 存儲空間 。 例如兩棧共享一維數(shù)組空間 ， 可按 “ 底設(shè)兩端 、 相向而動 、 迎面增長 ” 的方式組織 共享棧 ， 如下圖所示 。 僅當兩個棧頂相遇才會發(fā)生上溢 ， 棧頂可以越過中間點 ， 顯然比各用一半空間發(fā)生上溢的概率要小得多 。 兩棧共享的數(shù)據(jù)類型定義 兩棧共享的數(shù)據(jù)類型可如下定義： typedef struct elemtype s

55、tackm; /*m為數(shù)組長度 ， 可依具體問題而定 */ int top2; /* top0和 top1分別為兩棧的棧頂指針 */ sharedstack; 兩棧共享的基本運算 置空棧 置空棧算法 void setnull(sharedstack *s) s-top0=-1; /*0號?？諡?-1*/ s-top1=m; /*1號棧空為 m*/ 兩棧共享的基本運算 進棧 進棧算法 int push(sharedstack *s,int i,elemtype x) /* i=0,1為兩棧的編號 ， 算法把元素 x壓入棧 si 中 */ if(i1|s-top0+1=s-top1) return

56、 0; else if(i=0) s-stack+s-top0=x; else s-stack-s-top1=x; return 1; 兩棧共享的基本運算 出棧 出棧算法 elemtype pop(sharedstack *s,int i) /*彈出 i號棧的棧頂元素 */ if(i1) return NULL; /*參數(shù)出錯無法彈出 */ else if(i=0) if (s-top0=-1) return NULL; /*0號棧無法彈出 */ else return s-stacks-top0-; else if(s-top1=m) return NULL; /*1號棧無法彈出 */ el

57、se return s-stacks-top1+; 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現(xiàn) 3.3.3 鏈棧及運算實現(xiàn) 3.3.4 棧的應用舉例 遞歸的實現(xiàn) 鏈棧的基本概念 利用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱作 鏈棧 （ link stack） 。 鏈棧中的每個數(shù)據(jù)元素用一個結(jié)點表 示 ， 其結(jié)構(gòu)形式與單鏈表完全相同 。 鏈棧從本質(zhì)上講就是單鏈表 ， 無非是 限制了插入和刪除運算只能在鏈頭進 行 ， 所以可以說鏈棧就是限制插入和 刪除運算只能在鏈頭進行的單鏈表 。 由于在鏈頭運算 ， 所以不用象單鏈表 那樣附加頭結(jié)點 ， 更方便運算 ， 如右 圖所示 。 鏈棧的類型定義

58、鏈棧的類型定義如下： typedef struct node elemtype data; struct node *next; linkstack; linkstack *top; /*棧頂指針 ， 即鏈頭指針 */ 鏈棧的基本運算 空棧操作 置空棧算法 void setnull(linkstack *top) top=NULL; /*只要置 top為空即可 */ 判棧空算法 int empty(linkstack *top) /*?？辗祷?1否則返回 0*/ if(top=NULL) return 1; else return 0; 鏈棧的基本運算 進棧 進棧算法 void push(li

59、nkstack *top,elemtype x) /*注意：鏈棧不會發(fā)生上溢 ！ */ linkstack *p; p=(linkstack*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; 鏈棧的基本運算 出棧 出棧算法 elemtype pop(linkstack *top) linkstack *p; elemtype x; if(top=NULL) return NULL; /*棧為空無元素彈出 */ else p=top; /*保存棧頂指針于 P中 */ x=top-data; top=top-next; free (p)

60、; return x; /*返回彈出元素的值 */ 鏈棧的基本運算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(linkstack *top) if(top=NULL) return NULL; /*若棧為空返回空 */ else return top-data; /*否則返回棧頂元素的值 */ 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現(xiàn) 3.3.3 鏈棧及運算實現(xiàn) 3.3.4 棧的應用舉例 遞歸的實現(xiàn) 棧的應用 棧在計算機學科有著許多重要的應用 。 例如： 把十進制整數(shù)轉(zhuǎn)換為二進制整數(shù)的方法是 “ 除 2取余 ， 逆序排列 ” ， 利用棧來記下每次余

61、數(shù)最后輸出棧中內(nèi)容 即可； 在語言翻譯中要把十進制表達式的中綴形式先轉(zhuǎn)換成后 綴形式 ， 然后把后綴表達式翻譯成為一條條運算指令 ， 在后續(xù)課程 編譯原理 中大家會看到都得使用棧結(jié)構(gòu) 來完成； 在算法設(shè)計中的需要回溯處理的問題如迷宮問題 、 二叉 樹的遍歷 、 圖的遍歷等非遞歸算法的設(shè)計需要借助棧來 完成 ， 把遞歸過程轉(zhuǎn)換為非遞歸過程也需要借助棧結(jié)構(gòu)； 還有語言翻譯中的函數(shù)調(diào)用 ， 過程調(diào)用 ， 遞歸子程序處 理等等都離不開棧的應用 。 棧的應用舉例 遞歸的實現(xiàn) 遞歸 是算法和程序設(shè)計中的一個重要概念 ， 也是算法和程 序設(shè)計的一種重要方法和手段 。 在高級程序設(shè)計語言中有過程 、 函數(shù)和子

62、程序等程序模塊 的概念 ， 這些程序模塊是架構(gòu)結(jié)構(gòu)化程序的基本單位 。 當這些模塊直接或間接地在程序中調(diào)用了自身 ， 就稱作 遞 歸程序模塊 ； 直接調(diào)用自身的稱為 直接遞歸 ， 間接調(diào)用自身的稱為 間接遞歸 。 遞歸的概念對于程序模塊而存在 ， 即遞歸過程 、 遞歸函數(shù) 、 遞歸子程序等 ， 其前提是問題定義的遞歸特性和數(shù)據(jù)結(jié)構(gòu)的 遞歸特性 。 而問題定義的遞歸特性主要靠我們在對求解問題本 身的分析和理解的過程中去發(fā)現(xiàn) 。 棧的應用舉例 遞歸的實現(xiàn) (續(xù) ) 在 C語言中 ， 當一個函數(shù)體內(nèi)出現(xiàn)了自身的函數(shù)名 （ 即直接調(diào)用自身 ） ， 就稱該函數(shù)為 直接遞歸函數(shù) ； 當一個函數(shù)通過調(diào)用其它

63、函數(shù)來調(diào)用了自身 ， 如 函數(shù) A調(diào)用函數(shù) B， 函數(shù) B調(diào)用函數(shù) C， 函數(shù) C又調(diào)用 了函數(shù) A， 這種情況下稱函數(shù)為 間接遞歸函數(shù) （ A、 B、 C都是間接遞歸函數(shù) ） 。 遞歸的實現(xiàn) 求階乘 階乘函數(shù)可遞歸定義如下： 必須注意 ， 遞歸定義不能是無限循環(huán)地定義 ！ 任何遞歸定 義必須同時滿足如下兩個條件： 被定義項在定義中的應用 （ 即作為定義項的出現(xiàn) ） 應 具有更小的 “ 尺度 ” ； 被定義項在最小 “ 尺度 ” 上的定義不是遞歸的 。 例如上述的階乘函數(shù)定義中 ， 被定義項 n！ 在定義中的應用 (n-1)!具有比原來 n更小的 “ 尺度 ” n-1；同時 n！ 在最小 “

64、尺度 ” 為 0上的定義由自然數(shù) 1直接定義不是遞歸的 。 這兩 個條件實際上構(gòu)成了遞歸程序設(shè)計的基本原則 。 此外 ， 通常把反映條件 的部分 （ 即遞歸結(jié)束條件 ） 寫在 遞歸程序模塊的開頭處 。 遞歸的實現(xiàn) 求階乘 (續(xù) ) 許多實際問題是可以遞歸定義的 ， 對于這些問題 很容易寫出它們的遞歸求解算法 。 計算階乘函數(shù)的遞歸算法如下： int fact(int n) if(n=0) return 1; else return n*fact(n-1); 遞歸的實現(xiàn) 求階乘 (續(xù) ) 遞歸函數(shù)的運行引起遞歸調(diào)用 。 例如 ， fact(4)的執(zhí)行中遞歸函數(shù)出現(xiàn)的調(diào)用 返回 過程如下圖所示：

65、fact(4) fact(3) fact(2) fact(1) fact(0) 1 1 2 6 24 函數(shù) 調(diào)用與返回 返回值 函數(shù)的調(diào)用與返回 通常 ， 當一個函數(shù)調(diào)用另一個函數(shù)時 ， 在執(zhí)行被調(diào) 用函數(shù)前系統(tǒng)要預先做三件事情： 將所有的實參和函數(shù)返回地址等信息傳遞給被調(diào)用函數(shù)； 為被調(diào)用函數(shù)的局部變量分配存儲空間 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口處 。 而在從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前 ， 系統(tǒng)也需要 做如下三件事情： 保存被調(diào)用函數(shù)的計算結(jié)果； 釋放為被調(diào)用函數(shù)局部變量分配的數(shù)據(jù)空間； 按返回地址將控制轉(zhuǎn)移給調(diào)用函數(shù) 。 函數(shù)的嵌套調(diào)用 當多個函數(shù)構(gòu)成嵌套調(diào)用時 ， 系統(tǒng)按照先調(diào)用后 返回的

66、原則進行工作 。 這種信息的傳遞和控制轉(zhuǎn)移符合后進先出的原則 ， 使用棧來實現(xiàn)是非常自然的 。 系統(tǒng)將整個程序運行期間所需要的存儲空間都利 用一個工作棧來管理 ， 每當調(diào)用 （ 或執(zhí)行 ） 一個函 數(shù)時 ， 就為它在棧頂分配一個存儲區(qū)； 每當退出 （ 或執(zhí)行完 ） 一個函數(shù)時 ， 就釋放為它 所分配的存儲區(qū)； 當前工作的函數(shù)的數(shù)據(jù)區(qū)總在工作棧的當前棧頂 位置 。 函數(shù)的嵌套調(diào)用時棧變化過程 函數(shù)嵌套調(diào)用時工作棧的變化情況如下圖 ， 其中的 1和 2表 示返回地址 ， 是程序中的語句標號 。 遞歸函數(shù)的執(zhí)行過程 遞歸函數(shù)的執(zhí)行過程類似于嵌套調(diào)用時的情況 ， 只不過是在直接遞歸時的調(diào)用函數(shù)和被調(diào)用函數(shù)是 同一個函數(shù)罷了 。 例如前述的 fact函數(shù) ， 從遞歸調(diào)用開始 ， 每遞歸 調(diào)用深入一層 ， 就在工作棧的棧頂為所有形參局部 變量和返回地址開辟空間保存 ， 每退出一層遞歸就 從棧頂釋放為本層開辟的空間并返回調(diào)用層 。 由于是同一個函數(shù) ， 其返回地址應為同一語句位 置設(shè)為 r。 遞歸調(diào)用 fact(4)的工作棧變量情況 遞歸的實現(xiàn)小結(jié) 利用遞歸算法 （ 函數(shù) 、 過程 、 子程序等 ）