第2章 數(shù)據(jù)結(jié)構(gòu)

1、? 算法算法? 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述? 線性結(jié)構(gòu)線性結(jié)構(gòu)? 棧和隊列棧和隊列? 樹樹? 圖圖第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是討論非數(shù)值類問題的對象描述、信息組織方法及其相應(yīng)的操作。 第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)電子計算機的主要用途：電子計算機的主要用途： 早期：早期： 主要用于數(shù)值計算。主要用于數(shù)值計算。 后來：后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域處理逐漸擴大到非數(shù)值計算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）數(shù)學(xué)模型數(shù)學(xué)模型選擇計算機語言選擇計算機語言編出程序編出程序測試測試最終解答最終解答數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加

2、以描述數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容算法算法數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述線性結(jié)構(gòu)線性結(jié)構(gòu)棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1. 算法的特征算法: 對問題求解的描述，具有以下五個重要的特征： 1）有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束。 2）確切性：算法的每一步驟必須有確切的定義。 3）輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況。 4）輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法沒有實際意義。 5）可行性：比如，永動機則不可行。一、算法2、算法的描述: 1）流程圖 2）偽代碼類似

3、程序設(shè)計語言 3、算法的基本結(jié)構(gòu) 算法代碼化的過程:1）順序結(jié)構(gòu) 2）分支結(jié)構(gòu) 3）循環(huán)結(jié)構(gòu)一、算法 算法的時間復(fù)雜度是指（ ）。A. 執(zhí)行算法程序所需要的時間B. 算法程序的長度C. 算法執(zhí)行過程中所需要的基本運算次數(shù)D. 算法程序中的指令條數(shù)一、算法 算法的空間復(fù)雜度是指（ ）。A. 算法程序的長度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間D. 算法執(zhí)行過程中的所需要的存儲空間一、算法4、算法效率衡量方法與準(zhǔn)則 :時間復(fù)雜度：Windows程序設(shè)計中，指執(zhí)行時間的長短。空間復(fù)雜度：指存儲空間的大小。 一、算法5、算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系:計算機科學(xué)家沃斯（計算機科學(xué)家沃斯（N.Wi

4、rth）提出的）提出的:“算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=程序程序” 一、算法 計算機內(nèi)的數(shù)值運算依靠方程式，而計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算則要依靠數(shù)據(jù)結(jié)構(gòu)。 同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。運算效率可能有明顯的差異。算法算法數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述線性結(jié)構(gòu)線性結(jié)構(gòu)棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 特性相同的數(shù)據(jù)元素構(gòu)成的集合中，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱之為數(shù)據(jù)結(jié)構(gòu) 。 Data_Structure =（D，R） 其中，其中，D是數(shù)據(jù)元素的有限集，是數(shù)據(jù)元素的

5、有限集，R是是D上關(guān)系的有上關(guān)系的有限集。限集。二、數(shù)據(jù)結(jié)構(gòu)概述例1 線性數(shù)據(jù)結(jié)構(gòu) =（D，R） D = 1，2，3，4，5，6，7，8，9，10 R = ，二、數(shù)據(jù)結(jié)構(gòu)概述例2 圖形數(shù)據(jù)結(jié)構(gòu) =（D，R）D = 1，2，3，4，5，6，7，8，9R = ，二、數(shù)據(jù)結(jié)構(gòu)概述 例3 樹形結(jié)構(gòu) =（D，R）D = a，b，c，d，e，f，g，h，i，j，k，lR = ，二、數(shù)據(jù)結(jié)構(gòu)概述四類基本的數(shù)據(jù)結(jié)構(gòu) 集合結(jié)構(gòu)。各元素間沒有直接的關(guān)聯(lián)。 線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。 樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的關(guān)系。 圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，也稱作

6、網(wǎng)狀結(jié)構(gòu)。二、數(shù)據(jù)結(jié)構(gòu)概述不同聯(lián)系不同聯(lián)系系主任負(fù)責(zé)系11班級包含學(xué)生1N產(chǎn)品組成零件MN一對一聯(lián)系一對多聯(lián)系多對多聯(lián)系（1）Data_Structure=(D,S)，其中，其中， D= 01，02，03，04，05 S= （2） S=(D, R) D= a, b, c, d, e, f R= , , , , 解解: 上述表達式可用圖形表示為：上述表達式可用圖形表示為：aebcfd習(xí)題：將下述表達式用圖形的形式表示出來集合結(jié)構(gòu)線性結(jié)構(gòu)（3） Data_Structure=（D，S），其中，），其中， D= 01，02，03，04，05 ，06，07 S=（01，02），（），（01，03），（

7、），（01，04），（），（02，05），（），（02，06），（），（03，07） （4）d1d2d3d4d501020304050607樹形結(jié)構(gòu)圖狀結(jié)構(gòu)邏輯結(jié)構(gòu)可細(xì)分為4類：集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹形結(jié)構(gòu)；圖狀結(jié)構(gòu)集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹形結(jié)構(gòu)；圖狀結(jié)構(gòu)一對一關(guān)系一對一關(guān)系一對多關(guān)系一對多關(guān)系多對多關(guān)系多對多關(guān)系非線性非線性結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類按數(shù)據(jù)結(jié)構(gòu)的性質(zhì)劃分 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系 （設(shè)計算法 數(shù)學(xué)模型） 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的映像 （存儲結(jié)構(gòu)，算法的實現(xiàn)）按數(shù)據(jù)結(jié)構(gòu)的操作來劃分 靜態(tài)結(jié)構(gòu)操作后數(shù)據(jù)的結(jié)構(gòu)特征保持不變（如數(shù)組）。 半靜態(tài)結(jié)構(gòu)操作后數(shù)據(jù)的結(jié)構(gòu)特性

8、只允許很小變遷（如棧、隊列）。動態(tài)結(jié)構(gòu)操作后，數(shù)據(jù)的結(jié)構(gòu)特性變化比較靈活，可隨機地重新組織結(jié)構(gòu)（如指針）。二、數(shù)據(jù)結(jié)構(gòu)概述下面敘述正確的是（ ）。 A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B. 算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù) C. 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止 D. 以上3種描述都不對二、數(shù)據(jù)結(jié)構(gòu)概述按數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)的存儲方式來劃分 順序存儲結(jié)構(gòu)借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系 索引存儲結(jié)構(gòu)在存儲結(jié)點的同時，還建立附加的索引表，索引表中的每一項稱為索引項，形

9、式為：關(guān)鍵字，地址。 散列存儲結(jié)構(gòu)根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。說明：四種存儲方法可結(jié)合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲映像。二、數(shù)據(jù)結(jié)構(gòu)概述算法算法數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述線性結(jié)構(gòu)線性結(jié)構(gòu)棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)線性表線性表線性表的定義線性表的定義 線性表線性表是是n(n=0)個數(shù)據(jù)元素的個數(shù)據(jù)元素的有限序列有限序列，表中，表中各個元素具有相同的屬性。各個元素具有相同的屬性。 記做：記做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，其中，ai-1稱為稱為ai 的的直接前趨元素直接前趨元素，ai+1是是ai的的直直接后繼元素接后繼

10、元素 線性表的長度：線性表的長度：表中的元素個數(shù)表中的元素個數(shù) n 三、線性結(jié)構(gòu) 數(shù)據(jù)處理的最小單位是（ ）。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 數(shù)據(jù)結(jié)構(gòu)思考：補充補充數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項，是數(shù)據(jù)的最小單位，數(shù)據(jù)項定義的內(nèi)容包括： 名稱、編號（I）、別名、簡述 類型、長度 取值范圍 item數(shù)據(jù)項定義舉例數(shù)據(jù)項定義舉例數(shù)據(jù)項名：年級數(shù)據(jù)項名：年級別名：別名：取值及含義：取值及含義： freshmen，一年級，一年級 sophomore，二年級，二年級 junior，三年級，三年級 senior，四年級，四年級注釋：注釋：F，M，J，S可分別用可分別用1，2，3，4代替代替記錄線性表

11、的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 順序表順序表線性表的線性表的順序存儲表示表示順序表，隨機存取三、線性結(jié)構(gòu)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 單鏈表單鏈表線性表的線性表的鏈?zhǔn)酱鎯Ρ硎颈硎?數(shù)據(jù)域（數(shù)據(jù)域（data）和指針域（指針域（next） 三、線性結(jié)構(gòu)結(jié)點：數(shù)據(jù)元素的存儲映象數(shù)據(jù)元素的存儲映象數(shù)據(jù)域數(shù)據(jù)域指針域指針域鏈表：n n個結(jié)點鏈接成起來形成一個鏈表，即為線性表的個結(jié)點鏈接成起來形成一個鏈表，即為線性表的 鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)。a1a2ai-1aian指針域為空指針域為空數(shù)據(jù)元素數(shù)據(jù)元素直接后繼位置直接后繼位置頭結(jié)點頭結(jié)點LL 數(shù)據(jù)結(jié)構(gòu)是討論非數(shù)值類問題的對象描

12、述、信息組織方法及其相應(yīng)的操作 設(shè)有一個電話號碼薄，有N個人的姓名和電話號碼。要求設(shè)計一個程序，按人名查找號碼，若不存在則給出不存在的信息。三、線性結(jié)構(gòu)三、線性結(jié)構(gòu)順序表的表示：順序表的表示：順序存儲定義：把邏輯上相鄰的元素存儲在物理 位置上相鄰的存儲單元中。采用順序存儲結(jié)構(gòu)存儲的線性表采用順序存儲結(jié)構(gòu)存儲的線性表簡言之：邏輯相鄰，物理也相鄰順序存儲方法：順序存儲方法：用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次 存放線性表的數(shù)據(jù)元素。存放線性表的數(shù)據(jù)元素。線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)線性表順序存儲結(jié)構(gòu)的特點線性表順序存儲結(jié)構(gòu)的特點1、邏輯上相鄰的物理元素，其物理位

13、置上也相鄰 2、若已知線性表中第1個元素的存儲位置，則線性表中任意一個元素的位置都可由公式計算得出。 即，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。例：例：一個一維數(shù)組一個一維數(shù)組M，下標(biāo)范圍是，下標(biāo)范圍是0到到9，每個數(shù)組元素，每個數(shù)組元素用用相鄰的的5個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素組元素M0的第一個字節(jié)的地址是的第一個字節(jié)的地址是98，則，則M3的第一個的第一個字節(jié)的地址是字節(jié)的地址是 。113 非數(shù)值計算問題 例1.2 田徑賽的時間安排問題： 設(shè)有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）。要求設(shè)

14、計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。姓名姓名項目項目1項目項目2項目項目3丁一丁一跳高跳高跳遠(yuǎn)跳遠(yuǎn)100米米馬二馬二標(biāo)槍標(biāo)槍鉛球鉛球張三張三標(biāo)槍標(biāo)槍100米米200米米李四李四鉛球鉛球200米米跳高跳高王五王五跳遠(yuǎn)跳遠(yuǎn)200米米三、線性結(jié)構(gòu)（1）設(shè)用如下六個不同的編碼代表不同的項目： 跳高跳高 跳遠(yuǎn)跳遠(yuǎn) 標(biāo)槍標(biāo)槍 鉛球鉛球 100米米 200米米 A B C D E F姓名姓名項目項目1項目項目2項目項目3丁一丁一 A B E馬二馬二 C D 張三張三 C E F李四李四 D F A王五王五 B F （2）用頂點（圓圈）代表比賽項目 不能同時進行比賽的項目之間連上一條邊。不能同時進行

15、比賽的項目之間連上一條邊。比賽比賽時間時間比賽比賽項目項目1A，C2B，D3E4F2、線性表、線性表順序存儲結(jié)構(gòu)的特點順序存儲結(jié)構(gòu)的特點：邏輯相鄰，物理相鄰3、優(yōu)點：、優(yōu)點：可以可以隨機存取表中的任何一個元素表中的任何一個元素4、缺點：、缺點：在插入、刪除時，需要移動大量元素在插入、刪除時，需要移動大量元素1、線性表的定義、線性表的定義 L=（a1，a2，an）其中，其中，n n是線性表的長度。當(dāng)是線性表的長度。當(dāng)n n0 0時，時，L L是一個空表是一個空表 小結(jié)：ABCD順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)ABCD鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)L=（A, B, C, D）用一組任意的存儲單元存儲線性表的元素

16、邏輯相鄰，物理不一定相鄰ai除表示本身信除表示本身信息之外，還要表息之外，還要表示其直接后繼的示其直接后繼的地址地址線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)例：一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針是指向鏈表中第一頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。尋找第一個結(jié)點的地址。

17、7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31答：X= Y= Z= , 首址= 末址= 。例：現(xiàn)有一個有5個元素的線性表 L=23，17，47，05， 31，若它以鏈?zhǔn)浇Y(jié)構(gòu)存儲在下列100119號地址空間中，每個結(jié)點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)）組成，如下圖所示。問：其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點起始地址為多少？末結(jié)點的起始地址為多少？100100119119104104108108116116112112116NULL(0)100108112 線性表中結(jié)點間的關(guān)系是 的。一對一 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為： A

18、. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲結(jié)構(gòu) D. 鏈?zhǔn)酱鎯Y(jié)構(gòu)【答案】C 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。 A. 110 B. 108 C. 100 D. 120【答案】B三、線性結(jié)構(gòu) 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址: A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以【答案】D三、線性結(jié)構(gòu)已知：已知：線性表線性表A A和和B B，分別由，分別由單鏈表單鏈表LaLa和和LbLb存儲，其中數(shù)據(jù)存儲，其中數(shù)據(jù) 元素按值元素按值非遞減有序排列非遞減有序排列（即已經(jīng)有序）；

19、（即已經(jīng)有序）；例：例：兩個鏈表的歸并兩個鏈表的歸并重點是鏈表重點是鏈表要求：要求：將將A A和和B B歸并為一個新的線性表歸并為一個新的線性表C C , C , C的數(shù)據(jù)元素仍按的數(shù)據(jù)元素仍按 值非遞減排列。設(shè)線性表值非遞減排列。設(shè)線性表C C由單鏈表由單鏈表 Lc Lc 存儲。存儲。假設(shè)：假設(shè)：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）預(yù)測：預(yù)測：合并后的合并后的C C = =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（應(yīng)用舉例）鏈表示意圖：合并

20、算法設(shè)計：算法設(shè)計：算法主要包括算法主要包括搜索、比較、插入搜索、比較、插入三個操作：三個操作：搜索：搜索：需要設(shè)立需要設(shè)立三個指針三個指針來指向來指向La 、Lb和和Lc c鏈表；鏈表；比較：比較：比較比較La a和和Lb b表中結(jié)點數(shù)據(jù)的大??；表中結(jié)點數(shù)據(jù)的大??；插入：插入：將將La a和和Lb b表表中數(shù)據(jù)中數(shù)據(jù)較小的結(jié)點插入新鏈表較小的結(jié)點插入新鏈表Lc c 。3 5 8 11 LaLb2 6 8 11 9 Lc 2 3 5 6 8 8 9 11 11線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)PcPa、Pb用于搜索用于搜索La和和Lb，Pc指向新鏈表指向新鏈表Lc的當(dāng)前結(jié)點。的當(dāng)前結(jié)點。鏈表鏈表Lc存儲在

21、新開辟的空間中存儲在新開辟的空間中，歸并過程示意如下：，歸并過程示意如下：Lb2 6 8 119 3 5 8 11 LaLc 2 3 5 Pa6 Pb8 PcPbPcPaPaPcPcPbPcPaPb線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表線性表順序存儲順序存儲特征：特征：邏輯相鄰，物理也相鄰；邏輯相鄰，物理也相鄰；優(yōu)點：優(yōu)點：隨機存取結(jié)構(gòu)隨機存取結(jié)構(gòu)缺點：缺點：插入、刪除需要移動大量元素插入、刪除需要移動大量元素改進方案：改進方案：鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：“一對一一對一” 或或 “1:11:1”存儲結(jié)構(gòu)：存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯樞虼鎯?、鏈?zhǔn)酱鎯\運 算：算：插入、刪除插入、刪除小

22、結(jié)：三、線性結(jié)構(gòu) 在線性表的在線性表的第第i i個位置前個位置前插入一個元素的示插入一個元素的示意圖如下：意圖如下：1213212428304277121321242830427712345678123456789插入插入i=5i=5三、線性結(jié)構(gòu)123456789121321242528304277123456781213212428304277i=5刪除順序表中刪除順序表中第第i i個個元素的示意圖如下：元素的示意圖如下：三、線性結(jié)構(gòu)算法算法數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述線性結(jié)構(gòu)線性結(jié)構(gòu)棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 棧 棧的應(yīng)用舉例 隊列四、棧和隊列棧的定義 棧（S

23、tack）是限定只能在表的一端進行插入和刪除操作的線性表，又稱限定性線性表結(jié)構(gòu)。2. 棧的結(jié)構(gòu)特點和操作 棧頂（Top）、棧底（Bottom）、先入后出（LIFO） 棧堆棧結(jié)構(gòu)示意圖 棧棧是限定僅在表尾進行插入或刪除操作的線性表。表尾稱為棧頂top；表頭稱為棧底bottom；例：棧S=（a1，a2，an-1 ，an）棧頂棧底入棧：在棧頂插入一個元素的操作；出棧：從棧頂刪除一個元素的操作；基本操作：在棧頂進行插入、刪除、棧的初始化、 判空及取棧頂元素 棧basebase為棧底指針，始終指向棧底，base=NULL表示棧結(jié)構(gòu)不存在；top為棧頂指針，初值指向棧底，top入棧：插入新的棧頂元素，指針

24、top加1-先插入后加1A即top=base，表示?？?。BCD出棧：指針top減1，刪除棧頂元素-先減1后刪除非空棧的棧頂指針top始終指向棧頂元素的下一個位置EFtoptoptop棧滿棧滿top-base=stacksizebasetopABCDEFtoptoptoptoptoptop?？諚？杖霔Ｈ霔USH(s,x):stop+=x;出棧出棧 POP(s,x):x=s-top;例：一個棧的輸入序列為1，2，3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？可以通過窮舉所有可能性來求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、

25、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321；合計有5種可能性。 棧例：設(shè)依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是： A. a，b，c，d B. c，d，a，b C. b，c，d，a D. a，c，d，b若輸入序列是若輸入序列是 ,PjPkPi (PjPkPi) ，一定不存在這樣的輸出序列一定不存在這樣的輸出序列 ,PiPjPk 即對于輸入序列即對于輸入序列1，2，3，不存在輸出序列，不存在輸出序列3，1，2 棧隊列的定義 隊列（Queue）是限定只能在表的一端進行插入，在表的另一端進行刪除操

26、作的線性表。2. 隊列的結(jié)構(gòu)特點和操作 隊列頭（front）、隊列尾（rear），先入先出（FIFO） 隊列隊列是只允許在表的一端進行插入，另一端進行刪除。隊列是只允許在表的一端進行插入，另一端進行刪除。允許插入的一端稱為隊尾（rear）；允許刪除的一端稱為隊頭（front）；特點：特點：先進先出先進先出/FIFOa1 a2 a3 an隊頭隊尾入隊列出隊列 隊列 串（即字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個字符組成 字符串，由零個或多個字符組成的有限序列。 S“a0a1.an-1”串的長度：n空串：n=0，Null String子串與主串，子串的位置（從0開始）串的比較：最大相等前綴

27、子序列補充串 下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是（ ）A線性鏈表B棧C循環(huán)鏈表D順序表【答案】B四、棧和隊列 下列關(guān)于棧的敘述中正確的是（ ） A在棧中只能插入數(shù)據(jù)B在棧中只能刪除數(shù)據(jù)C棧是先進先出的線性表D棧是先進后出的線性表【答案】D四、棧和隊列 下列關(guān)于隊列的敘述中正確的是（ ） A在隊列中只能插入數(shù)據(jù)B在隊列中只能刪除數(shù)據(jù)C隊列是先進先出的線性表D隊列是先進后出的線性表【答案】C四、棧和隊列 下列敘述中，正確的是（ ）A線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的B線性鏈表中的表頭元素一定存儲在其他元素的前面C線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面D線性鏈表中的各