《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt

《《算法與數(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頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

4、個(gè)數(shù)據(jù)項(xiàng)組成 。 線性表的形式化定義 線性表的形式化定義如下： Linear List=(D,R) 其中： D=ai|ai Do， i=1， 2， ， n， n 0； R=|ai-1,ai Do， i=2， 3， ， n； Do為某個(gè)數(shù)據(jù)對象 。 線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu) ， 其長度可根 據(jù)需要增減 ， 即對數(shù)據(jù)元素不僅可以訪問 ， 還可 進(jìn)行插入和刪除 。 線性表的基本運(yùn)算 置空表 setnull(L)：將線性表 L置為空表 。 求長度 length(L)：計(jì)算線性表 L中數(shù)據(jù)元素的個(gè)數(shù) 。 取元素 get(L,i)：取出線性表 L中第 i個(gè)數(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。 線性表的基本運(yùn)算（續(xù)） 插入 insert(L,x,i)：在線性表 L中第 i個(gè)位置上插入值為 x的新 元素 ， 使表長增 1；要求 1ilength(L)+1。 刪除 delete(L,i)：刪除線性表 L中的第 i個(gè)元素 ， 使表長減 1； 要求 1ilength(L)。

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

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

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

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

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

11、L,x)-1； 取后繼即取出 (*L).datalocate(L,x)+1的值等 。 這里只討論定位序 、 插入和刪除運(yùn)算的實(shí)現(xiàn)算法 。 1. 定位序 locate(L,x) 定位序即按值查找 ， 確定元素 x在順序表 L中的位置 。 最簡單的方法是從第一個(gè)元素起和 x比較 ， 直到找到 一個(gè)值為 x的數(shù)據(jù)元素返回它的位置序號 （ 即數(shù)組下 標(biāo) ） ， 或者找遍表中所有元素均無值為 x的元素時(shí)返 回 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*/ 該算法的主要時(shí)間花費(fèi)在于查找比較的循環(huán) 。 當(dāng) a1=x時(shí)一次比較成功 ， 當(dāng) an=x時(shí) n次比較成功 ， 在 x 分 布位置等概率的情況下平均比較次數(shù)為 (n+1)/2；查找 不成功時(shí)的比較次數(shù)為 n+1。 所以算法的時(shí)間復(fù)雜度 為 O(n)。 2. 插入 insert(L,x,i) 插入運(yùn)算 是指在順序表 L的第 i個(gè)元素之前加入一個(gè) 新元素 x。 插入的結(jié)果使 x 在順序表中第 i個(gè)元素位置 上 ， 使順序表的長度由 n變?yōu)?n+1。

13、插入新元素 x后 ， 部分?jǐn)?shù)據(jù)元素間的邏輯關(guān)系發(fā)生了 改變 ， 要求物理存儲位置也要相應(yīng)變化 。 除非 i=n+1， 否則必須將位序?yàn)?i,i+1, ,n的數(shù)據(jù)元 素向后移動(dòng)一個(gè)元素位置 ， 空出第 i個(gè)位置插入新元 素 x；在 i=n+1時(shí)直接將新元素 x插入表尾 。 在順序表中插入新元素 x的過程 插入運(yùn)算的算法描述 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*/ 插入運(yùn)算算法的時(shí)間復(fù)雜度 算法中的數(shù)據(jù)元素移動(dòng)是從第 n個(gè)元素到第 i個(gè)元素 依次后移的 。 算法中的主要時(shí)間開銷在于后移元素的 for循環(huán) ， 循環(huán)執(zhí)行 n-i+1次 。 當(dāng) i=n+1時(shí)不需移動(dòng)元素是最 好情況 ， 當(dāng) i=1時(shí)需移動(dòng)元素 n次是最壞情況 ， 在插 入位置等概率分布時(shí)的平均移動(dòng)次數(shù)為 n/2。 所以算法最好情況下的時(shí)間復(fù)雜度為 O(1)， 在最壞 情況下的時(shí)間復(fù)雜度為 O(n)， 在平均情況下的時(shí)

15、間 復(fù)雜度也是 O(n)。 3.刪除 delete(L,i) 刪除運(yùn)算是把順序表中第 i個(gè)元素刪掉 ， 使順序表的 長度由 n變?yōu)?n-1， 其部分元素的邏輯關(guān)系和存儲位置 也發(fā)生相應(yīng)變化 ， 即 由 （ a1,a2, ,ai-1,ai,ai+1, ,an） 變成為 （ a1,a2, ,ai-1,ai+1, ,an） 。 除非 i=n時(shí)直接刪除 ， 否則需要從第 i+1元素到第 n元 素依次前移一個(gè)元素位置 。 在順序表中刪除第 i個(gè)元素過程 刪除運(yùn)算的算法描述 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*/ 刪除運(yùn)算算法的時(shí)間復(fù)雜度 由刪除過程可以看出 ， 通過元素 ai+1到 an的依次前移 就達(dá)到了刪除 ai的目的 。 該算法的時(shí)間開銷也主要是在元素的移動(dòng) 。 當(dāng) i=n時(shí)最好不需移動(dòng) ， 當(dāng) i=1時(shí)最壞需移動(dòng) n-1次 ， 在等概率的情況下需平均移動(dòng)元素 (n-1)/2次 。 其時(shí) 間復(fù)雜度在最好 、 最壞和平均的情況下分別為 O(1)， O(n)和 O(n)。 舉例 刪除順序表中的重復(fù)元素 一個(gè)順序表中可能含有一些值相同

17、的重復(fù)元素 ， 題目 要求對于值相同的重復(fù)元素只保留位序最小的一個(gè)而 刪除其它多余的元素 。 如 （ 5， 2， 2， 3， 5， 2） 經(jīng)刪除重復(fù)元素后變?yōu)?（ 5， 2， 3） 算法思路 ：從順序表中第一個(gè)元素起 ， 逐個(gè)檢查它后 面是否有值相同的其它元素 ， 若有便刪除之；直到表 中所有元素都已無重復(fù)元素為止 。 為此 ， 算法中需設(shè) 兩重循環(huán) ， 外層控制清除的趟數(shù) ， 內(nèi)層控制每趟的檢 查范圍 。 刪除順序表中的重復(fù)元素的算法描述 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中元素 ， 比較當(dāng)前兩個(gè) 元素值 ， 將較小的元素賦給 C， 直到其中一個(gè)順序 表掃描完畢 ， 然后將另一個(gè)順序表中剩余元素賦給 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 隊(duì)列 3.5 廣義表 3.2 鏈表 順序表的特點(diǎn)是 ， 邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上 也相鄰 。 這一特點(diǎn)使得順序表有如下兩個(gè)優(yōu)點(diǎn)： 無需為表示數(shù)據(jù)元素之間的關(guān)系而額外增加存儲空間； 可以隨機(jī)存取表中

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

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

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

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

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

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

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

27、 *CreateLinkList() char ch; int x; LinkList *head; /*head為頭結(jié)點(diǎn)指針 */ 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*/ 該算法的時(shí)間復(fù)雜度為 O(n)。 單鏈表建立過程示例 線性表 （ 25， 45， 18， 76， 29） 的單鏈表動(dòng)態(tài)建立過程如下 圖： 2.求表長 只要設(shè)一個(gè)移動(dòng)指針掃描整個(gè)單鏈表 ， 就可以統(tǒng)計(jì)出元素個(gè) 數(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*/ 該算法掃描整個(gè)單鏈表 ， 時(shí)間復(fù)雜度為 O(n)。 3.元素的查找方法一 單鏈表上元素的查找分 按值查找 和按序號查找。 按值查找 的方法是，從第一個(gè)結(jié)點(diǎn)起判斷當(dāng)前結(jié)點(diǎn)的值是否 等于給定值，若找到返回該結(jié)點(diǎn)地址，否則繼續(xù)下一個(gè)結(jié)點(diǎn)； 若整個(gè)表中未找到返回 NULL。算法描述如下： LinkList *LocateLinkList(L,x) LinkList *L; elemtyPe x; LinkList *P; P=L-next; while(P!=NULL) return P; /*返回找到的結(jié)點(diǎn)位置或 NULL*/ /*LocateLinkList*/ 元素的查找方法二 按

30、序號查找 的方法是，從第一個(gè)結(jié)點(diǎn)起做 i次指針傳遞返回該 結(jié)點(diǎn)地址，若找不到 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*/ 這兩個(gè)算法的時(shí)間復(fù)雜度在最壞情況下和等概率平均情況下都 為 O(n)。 4.插入 在單鏈表中插入元素只需修改有關(guān)結(jié)點(diǎn)的指針域內(nèi)容 ， 不需 象順序表那樣移動(dòng)

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

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

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

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

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

36、新鏈表中去 ， 當(dāng) P為空時(shí)完 成逆置 。 將單鏈表 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*/ 該算法沒有開辟新的存儲空間 ， 對鏈表順序掃描一遍就完成 了逆置 ， 時(shí)間開銷為 O(n)。 3.2 鏈表 3.2.1 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 鏈表 3.2.2 單鏈表上的基本運(yùn)算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應(yīng)用舉例 一元多項(xiàng)式相加問題

37、循環(huán)鏈表 循環(huán)鏈表 （ Circular Linked List） 是鏈?zhǔn)酱?儲結(jié)構(gòu)的另一種形式 ， 其特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的 指針域指向頭結(jié)點(diǎn) ， 使整個(gè)鏈表構(gòu)成一個(gè)環(huán) ， 可以從 表中任一結(jié)點(diǎn)出發(fā)訪問遍所有結(jié)點(diǎn) （ 即遍歷 ） 。 單循環(huán)鏈表的空表和非空表兩種狀態(tài)如下圖所示： 單循環(huán)鏈表上的基本運(yùn)算與單鏈表基本一致 ， 差別 僅在于對最后一個(gè)結(jié)點(diǎn)的循環(huán)處理上；單鏈表是判斷 指針是否為空 （ NULL） ， 而單循環(huán)鏈表是判斷指針是 否指向頭結(jié)點(diǎn) 。 求循環(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ù)） 有時(shí)對鏈表常做的操作是在表尾和表頭進(jìn)行 。 為了找尾結(jié)點(diǎn)必須從頭結(jié)點(diǎn)開始掃描全部結(jié)點(diǎn) ， 時(shí) 間開銷為 O(n)；而找頭結(jié)點(diǎn)僅 O(1)時(shí)間 。 改進(jìn)的方法是不設(shè)頭指針而設(shè)尾指針 。 這樣找到頭 結(jié)點(diǎn)和尾結(jié)點(diǎn)都只需要 O(1)的時(shí)間 ， 頭結(jié)點(diǎn)為 (*(*r).next).next而尾結(jié)點(diǎn)為 r， 對于在鏈表的頭尾 操作的應(yīng)用十分方便 。 帶尾指針的循環(huán)鏈表 如下圖所示： 雙

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

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

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

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

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

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

45、有結(jié)點(diǎn)空間 ， 設(shè)兩個(gè)指針變 量 p和 q分別指向 A和 B兩個(gè)多項(xiàng)式單鏈表的第一個(gè)結(jié) 點(diǎn) ， 依次比較兩指針?biāo)附Y(jié)點(diǎn)的指數(shù)項(xiàng) 。 若指數(shù)相等系數(shù)相加 ， 和不為零修改 *p的系數(shù)項(xiàng)并 刪除 *q， 和為零刪除 *p和 *q； 若指數(shù)不等 ， p-expexp時(shí) *p為和多項(xiàng)式中的一 項(xiàng) ， p-expq-exp時(shí)把 *q插在 *p之前 （ *q為和多項(xiàng) 式中的一項(xiàng) ） ； 所有操作之后要相應(yīng)移動(dòng)指針 。 直到其中一個(gè)鏈空 ， 把另一個(gè)鏈?zhǔn)Ｏ碌慕Y(jié)點(diǎn)插在 *p之后 。 多項(xiàng)式相加算法的描述 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é)點(diǎn)后 */ s-next=q; /*把 q接入結(jié)果鏈 */ s=q; q=r; else if(p-expexp) s=p; p=p-next; 多項(xiàng)式相加算法的描述（續(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鏈?zhǔn)Ｓ嘟Y(jié)點(diǎn)鏈入結(jié)果鏈 */ free(B); /* polyadd*/ 該算法的比較次數(shù)與 A、 B兩個(gè)多項(xiàng)式的長度 m和 n有關(guān) ， 算法 的時(shí)間復(fù)雜度為 O(m+n)。 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊(duì)列 3.5 廣義表 3.3 棧 3.3.1 棧的概念及運(yùn)算 3.3.2 順序棧及運(yùn)算實(shí)現(xiàn) 3.3.3 鏈棧及運(yùn)算實(shí)現(xiàn) 3.3.4 棧的應(yīng)用舉例 遞歸的實(shí)現(xiàn) 棧的概念 棧 （ stack） 是操作受限的線性表 ， 限定對元素 的插入和刪除運(yùn)算只能在表的一端進(jìn)行 。 通常把進(jìn)行插入和刪除操作的這一端稱作 棧頂 （ top） ， 另一端稱作 棧底 （

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

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

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

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

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

53、 s-datas-top=x; /*元素 x進(jìn)棧 */ return 1; /*進(jìn)棧成功返回 1標(biāo)志 */ 順序棧的基本運(yùn)算 出棧 出棧算法 elemtype pop(seqstack *s) if(s-top=-1) return NULL; else s-top-; /*棧頂指針減 1*/ return s-datas-top+1; /*返回原棧頂元素的值 */ 順序棧的基本運(yùn)算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(seqstack *s) /*讀棧頂元素并返回其值 */ if(s-top=-1) return NULL; /*?？諢o元素返回 NULL*/ else

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

55、tackm; /*m為數(shù)組長度 ， 可依具體問題而定 */ int top2; /* top0和 top1分別為兩棧的棧頂指針 */ sharedstack; 兩棧共享的基本運(yùn)算 置空棧 置空棧算法 void setnull(sharedstack *s) s-top0=-1; /*0號?？諡?-1*/ s-top1=m; /*1號?？諡?m*/ 兩棧共享的基本運(yùn)算 進(jìn)棧 進(jìn)棧算法 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; 兩棧共享的基本運(yùn)算 出棧 出棧算法 elemtype pop(sharedstack *s,int i) /*彈出 i號棧的棧頂元素 */ if(i1) return NULL; /*參數(shù)出錯(cuò)無法彈出 */ 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 棧的概念及運(yùn)算 3.3.2 順序棧及運(yùn)算實(shí)現(xiàn) 3.3.3 鏈棧及運(yùn)算實(shí)現(xiàn) 3.3.4 棧的應(yīng)用舉例 遞歸的實(shí)現(xiàn) 鏈棧的基本概念 利用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧稱作 鏈棧 （ link stack） 。 鏈棧中的每個(gè)數(shù)據(jù)元素用一個(gè)結(jié)點(diǎn)表 示 ， 其結(jié)構(gòu)形式與單鏈表完全相同 。 鏈棧從本質(zhì)上講就是單鏈表 ， 無非是 限制了插入和刪除運(yùn)算只能在鏈頭進(jìn) 行 ， 所以可以說鏈棧就是限制插入和 刪除運(yùn)算只能在鏈頭進(jìn)行的單鏈表 。 由于在鏈頭運(yùn)算 ， 所以不用象單鏈表 那樣附加頭結(jié)點(diǎn) ， 更方便運(yùn)算 ， 如右 圖所示 。 鏈棧的類型定義

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

59、nkstack *top,elemtype x) /*注意：鏈棧不會發(fā)生上溢 ！ */ linkstack *p; p=(linkstack*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; 鏈棧的基本運(yùn)算 出棧 出棧算法 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; /*返回彈出元素的值 */ 鏈棧的基本運(yùn)算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(linkstack *top) if(top=NULL) return NULL; /*若棧為空返回空 */ else return top-data; /*否則返回棧頂元素的值 */ 3.3 棧 3.3.1 棧的概念及運(yùn)算 3.3.2 順序棧及運(yùn)算實(shí)現(xiàn) 3.3.3 鏈棧及運(yùn)算實(shí)現(xiàn) 3.3.4 棧的應(yīng)用舉例 遞歸的實(shí)現(xiàn) 棧的應(yīng)用 棧在計(jì)算機(jī)學(xué)科有著許多重要的應(yīng)用 。 例如： 把十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)的方法是 “ 除 2取余 ， 逆序排列 ” ， 利用棧來記下每次余

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

62、程序等程序模塊 的概念 ， 這些程序模塊是架構(gòu)結(jié)構(gòu)化程序的基本單位 。 當(dāng)這些模塊直接或間接地在程序中調(diào)用了自身 ， 就稱作 遞 歸程序模塊 ； 直接調(diào)用自身的稱為 直接遞歸 ， 間接調(diào)用自身的稱為 間接遞歸 。 遞歸的概念對于程序模塊而存在 ， 即遞歸過程 、 遞歸函數(shù) 、 遞歸子程序等 ， 其前提是問題定義的遞歸特性和數(shù)據(jù)結(jié)構(gòu)的 遞歸特性 。 而問題定義的遞歸特性主要靠我們在對求解問題本 身的分析和理解的過程中去發(fā)現(xiàn) 。 棧的應(yīng)用舉例 遞歸的實(shí)現(xiàn) (續(xù) ) 在 C語言中 ， 當(dāng)一個(gè)函數(shù)體內(nèi)出現(xiàn)了自身的函數(shù)名 （ 即直接調(diào)用自身 ） ， 就稱該函數(shù)為 直接遞歸函數(shù) ； 當(dāng)一個(gè)函數(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ù) ） 。 遞歸的實(shí)現(xiàn) 求階乘 階乘函數(shù)可遞歸定義如下： 必須注意 ， 遞歸定義不能是無限循環(huán)地定義 ！ 任何遞歸定 義必須同時(shí)滿足如下兩個(gè)條件： 被定義項(xiàng)在定義中的應(yīng)用 （ 即作為定義項(xiàng)的出現(xiàn) ） 應(yīng) 具有更小的 “ 尺度 ” ； 被定義項(xiàng)在最小 “ 尺度 ” 上的定義不是遞歸的 。 例如上述的階乘函數(shù)定義中 ， 被定義項(xiàng) n！ 在定義中的應(yīng)用 (n-1)!具有比原來 n更小的 “ 尺度 ” n-1；同時(shí) n！ 在最小 “

64、尺度 ” 為 0上的定義由自然數(shù) 1直接定義不是遞歸的 。 這兩 個(gè)條件實(shí)際上構(gòu)成了遞歸程序設(shè)計(jì)的基本原則 。 此外 ， 通常把反映條件 的部分 （ 即遞歸結(jié)束條件 ） 寫在 遞歸程序模塊的開頭處 。 遞歸的實(shí)現(xiàn) 求階乘 (續(xù) ) 許多實(shí)際問題是可以遞歸定義的 ， 對于這些問題 很容易寫出它們的遞歸求解算法 。 計(jì)算階乘函數(shù)的遞歸算法如下： int fact(int n) if(n=0) return 1; else return n*fact(n-1); 遞歸的實(shí)現(xiàn) 求階乘 (續(xù) ) 遞歸函數(shù)的運(yùn)行引起遞歸調(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)用與返回 通常 ， 當(dāng)一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)時(shí) ， 在執(zhí)行被調(diào) 用函數(shù)前系統(tǒng)要預(yù)先做三件事情： 將所有的實(shí)參和函數(shù)返回地址等信息傳遞給被調(diào)用函數(shù)； 為被調(diào)用函數(shù)的局部變量分配存儲空間 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口處 。 而在從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前 ， 系統(tǒng)也需要 做如下三件事情： 保存被調(diào)用函數(shù)的計(jì)算結(jié)果； 釋放為被調(diào)用函數(shù)局部變量分配的數(shù)據(jù)空間； 按返回地址將控制轉(zhuǎn)移給調(diào)用函數(shù) 。 函數(shù)的嵌套調(diào)用 當(dāng)多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí) ， 系統(tǒng)按照先調(diào)用后 返回的

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