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

上傳人:za****8 文檔編號:22690918 上傳時(shí)間:2021-05-30 格式:PPT 頁數(shù):175 大小:1.41MB
收藏 版權(quán)申訴 舉報(bào) 下載
《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt_第1頁
第1頁 / 共175頁
《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt_第2頁
第2頁 / 共175頁
《算法與數(shù)據(jù)結(jié)構(gòu)》第3章簡單數(shù)據(jù)結(jié)構(gòu)ppt.ppt_第3頁
第3頁 / 共175頁

下載文檔到電腦,查找使用更方便

14.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《《算法與數(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)O碌慕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)S嘟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ù) 、 過程 、 子程序等 )

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!