C++課件第9章線性結(jié)構(gòu)(guo20120509)

1、本章內(nèi)容本章內(nèi)容1. 1. 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述2. 2. 線性表線性表3. 3. 棧棧4. 4. 隊(duì)列隊(duì)列5. 5. 數(shù)組數(shù)組 數(shù)據(jù)：數(shù)據(jù)：計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的符號(hào)的集合計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的符號(hào)的集合 。 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素集合。具有相同性質(zhì)的數(shù)據(jù)元素集合。 數(shù)據(jù)元素：數(shù)據(jù)元素：數(shù)據(jù)的基本單位，由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。又?jǐn)?shù)據(jù)的基本單位，由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。又稱為結(jié)點(diǎn)、頂點(diǎn)、記錄、表目等。稱為結(jié)點(diǎn)、頂點(diǎn)、記錄、表目等。 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)：具有獨(dú)立含義的數(shù)據(jù)的最小單位，又稱為域、字段。具有獨(dú)立含義的數(shù)據(jù)的最小單位，又稱為域、字段。9.1 9.1 數(shù)據(jù)

2、結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系n概念和術(shù)語(yǔ)概念和術(shù)語(yǔ)例：例：職工情況表職工情況表職工情況表是一種職工情況表是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，每個(gè)職工情況為一每個(gè)職工情況為一數(shù)據(jù)元素?cái)?shù)據(jù)元素，職工的每項(xiàng)基本信息為一個(gè)職工的每項(xiàng)基本信息為一個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)，部門的所有職工構(gòu)成一部門的所有職工構(gòu)成一個(gè)個(gè)數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象。9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述例：例：排隊(duì)問(wèn)題排隊(duì)問(wèn)題 Customer()Queue (B-1)Server () 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：排隊(duì)方式，數(shù)據(jù)間的邏輯關(guān)系。排

3、隊(duì)方式，數(shù)據(jù)間的邏輯關(guān)系。 存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：計(jì)算機(jī)中隊(duì)列的存儲(chǔ)方法。計(jì)算機(jī)中隊(duì)列的存儲(chǔ)方法。 運(yùn)算：運(yùn)算：排隊(duì)過(guò)程中各種操作的實(shí)現(xiàn)方法。排隊(duì)過(guò)程中各種操作的實(shí)現(xiàn)方法。n 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算n 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)：例：例：職工情況表職工情況表表尾元素 表頭元素中間元素 數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映出數(shù)據(jù)元素之間的數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映出數(shù)據(jù)元素之間的邏輯關(guān)系邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)獨(dú)立于計(jì)算機(jī)的。的。 9.1 9.1 數(shù)據(jù)結(jié)

4、構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述每個(gè)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，即為每個(gè)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，即為線性結(jié)構(gòu)線性結(jié)構(gòu)。n 數(shù)據(jù)邏輯結(jié)構(gòu)的分類：數(shù)據(jù)邏輯結(jié)構(gòu)的分類：1）集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是“屬于屬于同一集合同一集合”，集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。，集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。例：例：2）線性結(jié)構(gòu)：除第一個(gè)和最后一個(gè)元素外，其他每個(gè)元素）線性結(jié)構(gòu)：除第一個(gè)和最后一個(gè)元素外，其他每個(gè)元素都僅有一個(gè)都僅有一個(gè)直接前驅(qū)元素直接前驅(qū)元素和一個(gè)和一個(gè)直接后繼元素直接后繼元素。例：例：9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)

5、概述n 數(shù)據(jù)邏輯結(jié)構(gòu)的分類：數(shù)據(jù)邏輯結(jié)構(gòu)的分類：例：例：例：例：3）樹形結(jié)構(gòu)：每個(gè)元素若有直接前驅(qū)元素，只能有一個(gè)，但）樹形結(jié)構(gòu)：每個(gè)元素若有直接前驅(qū)元素，只能有一個(gè)，但可以有多個(gè)直接后繼元素?？梢杂卸鄠€(gè)直接后繼元素。 4）圖形結(jié)構(gòu)：每個(gè)元素都可以有多個(gè)直接前驅(qū)元素和多個(gè)直）圖形結(jié)構(gòu)：每個(gè)元素都可以有多個(gè)直接前驅(qū)元素和多個(gè)直接后繼元素。接后繼元素。 9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述n 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存儲(chǔ)器中的實(shí)現(xiàn)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存儲(chǔ)器中的實(shí)現(xiàn)。n 四種基本的存儲(chǔ)映象方式：四種基本的存儲(chǔ)映象方式：1）順序方式順序方式

6、2 2）鏈接方式鏈接方式3 3）索引方式索引方式4 4）散列方式散列方式繼續(xù)繼續(xù)9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述 將數(shù)據(jù)元素按照某種順序存放到一片將數(shù)據(jù)元素按照某種順序存放到一片連續(xù)的存儲(chǔ)單元連續(xù)的存儲(chǔ)單元內(nèi)，內(nèi)，數(shù)據(jù)元素之間的邏輯關(guān)系是通過(guò)它們?cè)诖鎯?chǔ)器中的數(shù)據(jù)元素之間的邏輯關(guān)系是通過(guò)它們?cè)诖鎯?chǔ)器中的相對(duì)位置相對(duì)位置來(lái)來(lái)體現(xiàn)的。體現(xiàn)的。例：例：英語(yǔ)字母表的順序存儲(chǔ)。英語(yǔ)字母表的順序存儲(chǔ)。ABCXYZ9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述順序方式順序方式順序存儲(chǔ)方式的優(yōu)點(diǎn)是：順序存儲(chǔ)方式的優(yōu)點(diǎn)是： 元素之間的邏輯關(guān)系通過(guò)它們?cè)诖鎯?chǔ)位置體現(xiàn)，因此存儲(chǔ)密度高。元素之間的邏輯關(guān)系通過(guò)它們?cè)诖?/p>

7、儲(chǔ)位置體現(xiàn)，因此存儲(chǔ)密度高。 可以快速地確定出任意元素的存儲(chǔ)位置，從而能夠?qū)崿F(xiàn)對(duì)元素的可以快速地確定出任意元素的存儲(chǔ)位置，從而能夠?qū)崿F(xiàn)對(duì)元素的 隨機(jī)、快速訪問(wèn)。隨機(jī)、快速訪問(wèn)。順序存儲(chǔ)方式的缺點(diǎn)是：順序存儲(chǔ)方式的缺點(diǎn)是： 插入或刪除元素時(shí)，可能會(huì)引起大量元素的移動(dòng)，實(shí)現(xiàn)效率低。插入或刪除元素時(shí)，可能會(huì)引起大量元素的移動(dòng)，實(shí)現(xiàn)效率低。 存儲(chǔ)空間需預(yù)先分配，如果定的太大會(huì)造成空間的浪費(fèi)，定的太存儲(chǔ)空間需預(yù)先分配，如果定的太大會(huì)造成空間的浪費(fèi)，定的太 小又可能會(huì)發(fā)生溢出。小又可能會(huì)發(fā)生溢出。 邏輯上相鄰的元素在物理位置上邏輯上相鄰的元素在物理位置上未必未必相鄰，元素間的邏輯相鄰，元素間的邏輯關(guān)系由關(guān)

8、系由附加的附加的指針域表示。指針域表示。第一個(gè)職工情況第一個(gè)職工情況第二個(gè)職工情況第二個(gè)職工情況最后一個(gè)職工情況最后一個(gè)職工情況head例：例：職工情況鏈表（鏈接方式存儲(chǔ)的線性結(jié)構(gòu)）職工情況鏈表（鏈接方式存儲(chǔ)的線性結(jié)構(gòu)）9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述鏈接方式鏈接方式鏈接存儲(chǔ)方式的優(yōu)點(diǎn)是：鏈接存儲(chǔ)方式的優(yōu)點(diǎn)是： 元素之間的邏輯關(guān)系通過(guò)結(jié)點(diǎn)的指針域指出，因此，在插入和刪除元元素之間的邏輯關(guān)系通過(guò)結(jié)點(diǎn)的指針域指出，因此，在插入和刪除元 素時(shí)，不會(huì)引起大量元素的移動(dòng)。素時(shí)，不會(huì)引起大量元素的移動(dòng)。 可動(dòng)態(tài)申請(qǐng)和釋放結(jié)點(diǎn)空間，所使用的存儲(chǔ)空間大小與實(shí)際存儲(chǔ)的數(shù)可動(dòng)態(tài)申請(qǐng)和釋放結(jié)點(diǎn)空間，所使用的

9、存儲(chǔ)空間大小與實(shí)際存儲(chǔ)的數(shù) 據(jù)元素的數(shù)量保持一致。據(jù)元素的數(shù)量保持一致。鏈接存儲(chǔ)方式的缺點(diǎn)是：鏈接存儲(chǔ)方式的缺點(diǎn)是： 不能實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的隨機(jī)訪問(wèn)。不能實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的隨機(jī)訪問(wèn)。 每個(gè)結(jié)點(diǎn)中的指針域會(huì)耗費(fèi)一些存儲(chǔ)空間。每個(gè)結(jié)點(diǎn)中的指針域會(huì)耗費(fèi)一些存儲(chǔ)空間。索引表索引表數(shù)據(jù)數(shù)據(jù)9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述關(guān)鍵字關(guān)鍵字 地址地址索引方式索引方式關(guān)鍵字：關(guān)鍵字：是指能夠惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素是指能夠惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的一個(gè)或多個(gè)數(shù)據(jù)的一個(gè)或多個(gè)數(shù)據(jù) 項(xiàng)。項(xiàng)。索引方式的優(yōu)點(diǎn)是：檢索速度快。索引方式的優(yōu)點(diǎn)是：檢索速度快。索引方式的缺點(diǎn)是：索引方式的缺點(diǎn)是：增加的索引表會(huì)占用較多的存儲(chǔ)空間；增

10、加的索引表會(huì)占用較多的存儲(chǔ)空間；在插入和刪除數(shù)據(jù)元素時(shí)需要修改索引表，因而會(huì)花費(fèi)更多的時(shí)間。在插入和刪除數(shù)據(jù)元素時(shí)需要修改索引表，因而會(huì)花費(fèi)更多的時(shí)間。 數(shù)據(jù)元素的存儲(chǔ)位置是用它的關(guān)鍵字計(jì)算出來(lái)的。數(shù)據(jù)元素的存儲(chǔ)位置是用它的關(guān)鍵字計(jì)算出來(lái)的。 散列方式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)又稱為哈希表、雜湊表等。散列方式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)又稱為哈希表、雜湊表等。 9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述散列方式散列方式散列方式的優(yōu)點(diǎn)是：檢索、增加和刪除元素的操作都很快。散列方式的優(yōu)點(diǎn)是：檢索、增加和刪除元素的操作都很快。散列方式的缺點(diǎn)是：如果使用了不好的散列函數(shù)，可能會(huì)出現(xiàn)存儲(chǔ)單元散列方式的缺點(diǎn)是：如果使用了不好的散列函

11、數(shù)，可能會(huì)出現(xiàn)存儲(chǔ)單元的沖突，為解決沖突需要額外的時(shí)間和空間開銷。的沖突，為解決沖突需要額外的時(shí)間和空間開銷。n 數(shù)據(jù)的運(yùn)算：數(shù)據(jù)的運(yùn)算：對(duì)數(shù)據(jù)對(duì)象中的數(shù)據(jù)所進(jìn)行的加工和處理。對(duì)數(shù)據(jù)對(duì)象中的數(shù)據(jù)所進(jìn)行的加工和處理。n 數(shù)據(jù)運(yùn)算的特點(diǎn)：數(shù)據(jù)運(yùn)算的特點(diǎn)： 數(shù)據(jù)的運(yùn)算定義在邏輯結(jié)構(gòu)之上，實(shí)現(xiàn)在存儲(chǔ)結(jié)構(gòu)之上。數(shù)據(jù)的運(yùn)算定義在邏輯結(jié)構(gòu)之上，實(shí)現(xiàn)在存儲(chǔ)結(jié)構(gòu)之上。 數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)用數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)用算法算法描述。描述。n 常用的數(shù)據(jù)運(yùn)算：常用的數(shù)據(jù)運(yùn)算：插入、刪除、查找、排序、更新等。插入、刪除、查找、排序、更新等。9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述1.什么是算法什么是算法 算法是對(duì)解決問(wèn)題方法的精確描

12、述，是用來(lái)完成某個(gè)特算法是對(duì)解決問(wèn)題方法的精確描述，是用來(lái)完成某個(gè)特定任務(wù)的有限步驟序列。定任務(wù)的有限步驟序列。 9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述例如例如:用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)M和和N的最大公因的最大公因數(shù)的算法為數(shù)的算法為: step1: 求求M除以除以N的余數(shù)的余數(shù)R; step2: 若若R=0,算法結(jié)束算法結(jié)束,即即N為為M和和N的最大公因數(shù)的最大公因數(shù) Step3: 否則否則,置置MN,NR,返回返回step12. 算法的基本特征算法的基本特征有窮性有窮性 一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，并且一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，并且每一步都能在有限的時(shí)間

13、內(nèi)完成。每一步都能在有限的時(shí)間內(nèi)完成。確定性確定性 算法中的每一條指令必須具有確切的含義，算法中的每一條指令必須具有確切的含義，且無(wú)二義性。且無(wú)二義性。可行性可行性 算法中描述的所有操作都可以通過(guò)讓已實(shí)算法中描述的所有操作都可以通過(guò)讓已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次完成?，F(xiàn)的基本運(yùn)算執(zhí)行有限次完成。輸入輸入 一個(gè)算法應(yīng)該有個(gè)或多個(gè)輸入。一個(gè)算法應(yīng)該有個(gè)或多個(gè)輸入。輸出輸出 一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。3. 算法的描述算法的描述 4. 算法的評(píng)價(jià)算法的評(píng)價(jià) 自然語(yǔ)言描述、程序設(shè)計(jì)語(yǔ)言描述、流程圖描述等。自然語(yǔ)言描述、程序設(shè)計(jì)語(yǔ)言描述、流程圖描述等。以下采用以下采用C+語(yǔ)

14、言語(yǔ)言作為描述算法的工具作為描述算法的工具 1 1）算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上：根據(jù)算法編寫出的程序在計(jì)算機(jī)上 運(yùn)行時(shí)所消耗的時(shí)間。運(yùn)行時(shí)所消耗的時(shí)間。2 2）算法的空間復(fù)雜度算法的空間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上：根據(jù)算法編寫出的程序在計(jì)算機(jī)上 運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小。運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小。9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述n算法時(shí)間復(fù)雜度的度量算法時(shí)間復(fù)雜度的度量 一般把程序運(yùn)行時(shí)一般把程序運(yùn)行時(shí)語(yǔ)句的執(zhí)行語(yǔ)句的執(zhí)行次數(shù)（不包括說(shuō)明語(yǔ)句）次數(shù)（不包括說(shuō)明語(yǔ)句）作為估算程序執(zhí)行時(shí)間的量度。作為估算程序執(zhí)行時(shí)間的量度。 例：例

15、：估算以下函數(shù)的時(shí)間復(fù)雜度。估算以下函數(shù)的時(shí)間復(fù)雜度。int min( int a , int n ) int k,i; k=0; /執(zhí)行執(zhí)行 1 次次 for(i=1; in; i+) /執(zhí)行執(zhí)行 n 次次 if(aiak) k=i;/執(zhí)行執(zhí)行n-1次次 return k; /執(zhí)行執(zhí)行 1 次次語(yǔ)句執(zhí)行頻度：語(yǔ)句執(zhí)行頻度：f(n)=2n+1忽略低次項(xiàng)，記為：忽略低次項(xiàng)，記為： f(n)=O(n) 它與它與 n 成正比成正比n 常見的算法時(shí)間復(fù)雜度常見的算法時(shí)間復(fù)雜度O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、O(n3) 、O(2n)n 時(shí)間函數(shù)的增長(zhǎng)率時(shí)間函數(shù)的增長(zhǎng)

16、率 9.1 9.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述 線性表是由（線性表是由（）個(gè)）個(gè)相同類型相同類型的數(shù)據(jù)元素的數(shù)據(jù)元素e e0 0、e e1 1、e en-1 n-1 組成的有限序列組成的有限序列 ?？沙橄蟮谋硎緸椋骸？沙橄蟮谋硎緸椋海╡0，e1，ei-1，ei，ei+1，en-1） 開始元素開始元素 中間元素中間元素 終端元素終端元素建空表、求表長(zhǎng)、查找、插入、刪除、排序等。建空表、求表長(zhǎng)、查找、插入、刪除、排序等。9.2 9.2 線性表線性表1.線性表的定義線性表的定義 線性表中元素的個(gè)數(shù)稱為表的線性表中元素的個(gè)數(shù)稱為表的長(zhǎng)度長(zhǎng)度。長(zhǎng)度為。長(zhǎng)度為0的表為的表為空表空表。元素在表中的序號(hào)稱做元素

17、的元素在表中的序號(hào)稱做元素的下標(biāo)下標(biāo)。2. 線性表常用的基本運(yùn)算線性表常用的基本運(yùn)算 n 以順序方式存儲(chǔ)的線性表稱為以順序方式存儲(chǔ)的線性表稱為順序表順序表。n 可以用一維數(shù)組實(shí)現(xiàn)順序表?？梢杂靡痪S數(shù)組實(shí)現(xiàn)順序表。例例：用用C+的一維數(shù)組實(shí)現(xiàn)對(duì)英文字母表的順序存儲(chǔ)。的一維數(shù)組實(shí)現(xiàn)對(duì)英文字母表的順序存儲(chǔ)。char table26;或：或： char *table=new char26; 應(yīng)該把存儲(chǔ)線性表的一維數(shù)組和實(shí)現(xiàn)順序表各種運(yùn)算的應(yīng)該把存儲(chǔ)線性表的一維數(shù)組和實(shí)現(xiàn)順序表各種運(yùn)算的函數(shù)封裝在一起，即定義函數(shù)封裝在一起，即定義順序表類順序表類。 9.2 9.2 線性表線性表繼續(xù)繼續(xù)n單擊超鏈接查看以

18、下函數(shù)的實(shí)現(xiàn)：?jiǎn)螕舫溄硬榭匆韵潞瘮?shù)的實(shí)現(xiàn)：構(gòu)造函數(shù)構(gòu)造函數(shù) Find() Search() Insert() Delete() output() 重載重載“”的函數(shù)的函數(shù)9.2 9.2 線性表線性表#include class SeqListprivate:int Maxsize; /線性表的容量線性表的容量int length; /線性表的長(zhǎng)度線性表的長(zhǎng)度char *element; public: SeqList(int m=10); /構(gòu)造函數(shù)構(gòu)造函數(shù) SeqList()delete element; /析構(gòu)函數(shù)析構(gòu)函數(shù) bool IsEmpty()return length=0; /

19、判表是否為空判表是否為空 int Length()return length; /返回表長(zhǎng)返回表長(zhǎng) bool Find(int i,char &x); /把下標(biāo)為把下標(biāo)為i的元的元SeqList:SeqList(int m) element=new charm; Maxsize=m; length=0;n函數(shù)的功能是：建立一個(gè)函數(shù)的功能是：建立一個(gè)空表空表。9.2 9.2 線性表線性表bool SeqList:Find(int i,char &x)if(ilength-1) return false;x=elementi;return true; n函數(shù)的功能是：把下標(biāo)為函數(shù)的功能是：把下標(biāo)為

20、i i的元素取至的元素取至x x。9.2 9.2 線性表線性表n函數(shù)的功能是：返回函數(shù)的功能是：返回x在表中的下標(biāo)在表中的下標(biāo) 。int SeqList:Search(const char &x) for(int i=0;ilength;i+)if(elementi=x) return i; return -1; 9.2 9.2 線性表線性表n函數(shù)的功能是：在下標(biāo)函數(shù)的功能是：在下標(biāo)i處插入元素處插入元素x 。bool SeqList:Insert(int i,const char &x) if(ilength) return false; /下標(biāo)越界下標(biāo)越界 if(length=Maxsiz

21、e) return false; /表已滿表已滿 for(int k=length-1;k=i;k-) elementk+1=elementk; elementi=x; length+; return true; 9.2 9.2 線性表線性表n函數(shù)的功能是：返回下標(biāo)為函數(shù)的功能是：返回下標(biāo)為i的元素至的元素至x，并刪除之，并刪除之 。bool SeqList:Delete(int i,char &x) if(Find(i,x)for(int k=i;klength-1;k+) elementk=elementk+1;length-;return true; else return false;

22、 9.2 9.2 線性表線性表n函數(shù)的功能是：輸出表中所有元素的值函數(shù)的功能是：輸出表中所有元素的值 。void SeqList:output(ostream &out)constfor(int i=0;ilength;i+)outelementi ;9.2 9.2 線性表線性表n函數(shù)的功能是：為方便輸出，重載函數(shù)的功能是：為方便輸出，重載“” 。ostream& operator(ostream &out,const SeqList &x)x.output(out);return out; 9.2 9.2 線性表線性表n 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 1）存儲(chǔ)密度高；）存儲(chǔ)密度高； 2）可方便地訪問(wèn)給定下標(biāo)

23、的元素。（隨機(jī)存?。┛煞奖愕卦L問(wèn)給定下標(biāo)的元素。（隨機(jī)存?。?順序表的優(yōu)缺點(diǎn)順序表的優(yōu)缺點(diǎn)n 缺點(diǎn)：缺點(diǎn)： 1）插入和刪除運(yùn)算的實(shí)現(xiàn)效率低。）插入和刪除運(yùn)算的實(shí)現(xiàn)效率低。 2）表的容量需預(yù)先指定，適應(yīng)性差。）表的容量需預(yù)先指定，適應(yīng)性差。n 順序表適用于表長(zhǎng)已知且插入和刪除操作不頻繁的線性表順序表適用于表長(zhǎng)已知且插入和刪除操作不頻繁的線性表9.2 9.2 線性表線性表例：例：將一串字符存入順序表，刪除其中所有的數(shù)字字符。將一串字符存入順序表，刪除其中所有的數(shù)字字符。 程序的輸出結(jié)果是：程序的輸出結(jié)果是： 1C+ 2FORTRAN 3PASCAL 4BASIC C+ FORTRAN PASCAL

24、 BASIC9.2 9.2 線性表線性表#include seqlist.hvoid main()char str=1C+ 2FORTRAN 3PASCAL 4BASIC SeqList L(100); /建空表建空表int i;for(i=0;stri!=0;i+)if(L.Insert(i,stri)=false)/向表中放數(shù)據(jù)向表中放數(shù)據(jù) cout”插入異常插入異常n”;break;coutLendl; /利用重載的插入運(yùn)算符輸出表中元素利用重載的插入運(yùn)算符輸出表中元素i=0;char x ;while(iL.Length()n以鏈接方式存儲(chǔ)的線性表稱為鏈表。以鏈接方式存儲(chǔ)的線性表稱為鏈

25、表。n常用的鏈表形式有單鏈表、雙鏈表和循環(huán)鏈表等常用的鏈表形式有單鏈表、雙鏈表和循環(huán)鏈表等 。單鏈表的一般形式：?jiǎn)捂湵淼囊话阈问剑簡(jiǎn)捂湵碇薪Y(jié)點(diǎn)的一般形式：?jiǎn)捂湵碇薪Y(jié)點(diǎn)的一般形式：datanext在一般形式的單鏈表中進(jìn)行插入、刪除操作時(shí)，必須在一般形式的單鏈表中進(jìn)行插入、刪除操作時(shí)，必須針對(duì)不同的情況采取不同的處理方法，這為編寫程序帶來(lái)一定針對(duì)不同的情況采取不同的處理方法，這為編寫程序帶來(lái)一定的難度和潛在的危險(xiǎn)。的難度和潛在的危險(xiǎn)。 空表：空表：head=NULL9.2 9.2 線性表線性表9.2 9.2 線性表線性表 空表：空表：n 帶頭結(jié)點(diǎn)的單鏈表的一般形式：帶頭結(jié)點(diǎn)的單鏈表的一般形式： 單

26、鏈表的常用操作：?jiǎn)捂湵淼某Ｓ貌僮鳎航毡?、判表空、求表長(zhǎng)、查找表中建空表、判表空、求表長(zhǎng)、查找表中元素、插入元素、刪除元素、清空表、輸出表中元素等元素、插入元素、刪除元素、清空表、輸出表中元素等繼續(xù)繼續(xù)n 單擊超鏈接查看以下函數(shù)的實(shí)現(xiàn)：?jiǎn)螕舫溄硬榭匆韵潞瘮?shù)的實(shí)現(xiàn)：構(gòu)造函數(shù)構(gòu)造函數(shù) 析構(gòu)函數(shù)析構(gòu)函數(shù) Find() Search() Insert() Delete() ClearList() output() 重載重載“”的函數(shù)的函數(shù)9.2 9.2 線性表線性表#include class Chain;/單鏈表類單鏈表類Chain的前視聲明的前視聲明class Node/單鏈表結(jié)點(diǎn)類的定義單鏈表

27、結(jié)點(diǎn)類的定義 friend class Chain;/定義類定義類Chain為友元為友元 private:char data;/結(jié)點(diǎn)的數(shù)據(jù)域結(jié)點(diǎn)的數(shù)據(jù)域 Node *next; /結(jié)點(diǎn)的指針域結(jié)點(diǎn)的指針域;class Chain /單鏈表類的定義單鏈表類的定義private:Node *head;/頭指針頭指針int length; /表長(zhǎng)表長(zhǎng) public:Chain:Chain()head=new Node;head-next=0;length=0; n函數(shù)的功能是：建立一個(gè)函數(shù)的功能是：建立一個(gè)空表空表。9.2 9.2 線性表線性表 空表：空表：Chain:Chain()ClearLis

28、t(); /釋放數(shù)據(jù)結(jié)點(diǎn)空間釋放數(shù)據(jù)結(jié)點(diǎn)空間delete head; /釋放頭結(jié)點(diǎn)空間釋放頭結(jié)點(diǎn)空間 head=0; n函數(shù)的功能是：釋放鏈表空間。函數(shù)的功能是：釋放鏈表空間。9.2 9.2 線性表線性表n函數(shù)的功能是：把下標(biāo)為函數(shù)的功能是：把下標(biāo)為i的元素取至的元素取至x。9.2 9.2 線性表線性表bool Chain:Find(int i,char &x)if(ilength-1) return false;Node *p=head-next;int k=0; /指針指針p的移動(dòng)次數(shù)的移動(dòng)次數(shù)while(knext;k+;x=p-data;return true;n函數(shù)的功能是：返回函數(shù)

29、的功能是：返回x在表中的下標(biāo)在表中的下標(biāo) 。9.2 9.2 線性表線性表int Chain:Search(const char &x)Node *p=head-next;int i=0;while(p!=0)if(p-data=x) return i;p=p-next;i+;return -1;n函數(shù)的功能是：在下標(biāo)函數(shù)的功能是：在下標(biāo)i處插入元素處插入元素x 。ai-1ai p q x 插入過(guò)程演示插入過(guò)程演示9.2 9.2 線性表線性表a0head.bool Chain:Insert(int i,char &x)if(ilength) return false;/下標(biāo)越界下標(biāo)越界Node

30、*p=head; /從頭結(jié)點(diǎn)開始從頭結(jié)點(diǎn)開始int k=0;while(knext;k+;Node *q;n函數(shù)的功能是：返回下標(biāo)為函數(shù)的功能是：返回下標(biāo)為i的元素至的元素至x，并刪除之，并刪除之 。刪除結(jié)點(diǎn)過(guò)程演示刪除結(jié)點(diǎn)過(guò)程演示ai-1aiai+1 p q9.2 9.2 線性表線性表a0head.bool Chain:Delete(int i,char &x)if(ilength-1) return false;/下標(biāo)越界下標(biāo)越界Node *p=head; /從頭結(jié)點(diǎn)開始從頭結(jié)點(diǎn)開始for(int k=0;knext;Node *q=p-next; /保存要?jiǎng)h除的結(jié)點(diǎn)地址保存要?jiǎng)h除的結(jié)點(diǎn)地

31、址x=q-data; /保存刪除結(jié)點(diǎn)的值保存刪除結(jié)點(diǎn)的值p-next=q-next; /改變第改變第i-1個(gè)結(jié)點(diǎn)的指?jìng)€(gè)結(jié)點(diǎn)的指n函數(shù)的功能是：把表清空，即將單鏈表置為空表函數(shù)的功能是：把表清空，即將單鏈表置為空表 。9.2 9.2 線性表線性表void Chain:ClearList()Node *p=head-next,*q;while(p!=0)q=p; /保存被刪除結(jié)點(diǎn)地址保存被刪除結(jié)點(diǎn)地址p=p-next; /p保存下一個(gè)待刪除結(jié)點(diǎn)地址保存下一個(gè)待刪除結(jié)點(diǎn)地址delete q; /釋放被刪除結(jié)點(diǎn)的空間釋放被刪除結(jié)點(diǎn)的空間head-next=0; length=0;n函數(shù)的功能是：輸出表

32、中所有元素的值函數(shù)的功能是：輸出表中所有元素的值 。void Chain:output(ostream &out)const Node *p=head-next; while(p!=0)outdatanext; 9.2 9.2 線性表線性表n函數(shù)的功能是：為方便輸出，重載函數(shù)的功能是：為方便輸出，重載“” 。ostream& operator(ostream &out,const Chain &x)x.output(out);return out;9.2 9.2 線性表線性表n 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 1）插入和刪除運(yùn)算的實(shí)現(xiàn)效率比較高。）插入和刪除運(yùn)算的實(shí)現(xiàn)效率比較高。 2）在存儲(chǔ)長(zhǎng)度變化比較大的線性

33、表時(shí)適應(yīng)性較好。）在存儲(chǔ)長(zhǎng)度變化比較大的線性表時(shí)適應(yīng)性較好。 以鏈接方式存儲(chǔ)線性表的優(yōu)缺點(diǎn)以鏈接方式存儲(chǔ)線性表的優(yōu)缺點(diǎn)缺點(diǎn)：缺點(diǎn)： 1）需要增加額外的空間表示元素之間的邏輯關(guān)系。）需要增加額外的空間表示元素之間的邏輯關(guān)系。 2）不便于對(duì)線性表中元素進(jìn)行隨機(jī)存取。）不便于對(duì)線性表中元素進(jìn)行隨機(jī)存取。 鏈表適用于表長(zhǎng)不確定且插入和刪除操作頻繁的線性表鏈表適用于表長(zhǎng)不確定且插入和刪除操作頻繁的線性表9.2 9.2 線性表線性表例：例：將一字符串存入單鏈表，刪除其中所有的數(shù)字字符。將一字符串存入單鏈表，刪除其中所有的數(shù)字字符。 程序的輸出結(jié)果是：程序的輸出結(jié)果是： 1C+ 2FORTRAN 3PASC

34、AL 4BASIC C+ FORTRAN PASCAL BASIC9.2 9.2 線性表線性表#include chain.hvoid main()char str=1C+ 2FORTRAN 3PASCAL 4BASIC Chain L; /建立單鏈表對(duì)象，空表建立單鏈表對(duì)象，空表int i;for(i=0;stri!=0;i+)if(L.Insert(i,stri)=false) cout”插入異常插入異常n”; break; coutLendl; /輸出表中元素輸出表中元素i=0;char x;while(inext , *q; while( ) p = p - next; if( p=N

35、ULL) q= ; q-data=x; = head-next; head-next=q; else coutxnext , *q; while(p!=NULL&p-data!=x) p = p - next; if( p=NULL) q=new Node; q-data=x; q-next= head-next; head-next=q; else coutx已存在已存在!n; n單循環(huán)鏈表單循環(huán)鏈表n設(shè)置尾指針的單循環(huán)鏈表設(shè)置尾指針的單循環(huán)鏈表9.2 9.2 線性表線性表n雙鏈表雙鏈表n雙循環(huán)鏈表雙循環(huán)鏈表9.2 9.2 線性表線性表?xiàng)５母拍睿５母拍睿?）1.棧的定義棧的定義 3. 棧的

36、特點(diǎn)棧的特點(diǎn) 棧中元素的變化是棧中元素的變化是按按后進(jìn)先出后進(jìn)先出原則進(jìn)行，因此又稱棧原則進(jìn)行，因此又稱棧為為后進(jìn)先出后進(jìn)先出（Last In First Out，簡(jiǎn)稱，簡(jiǎn)稱LIFO）表）表 。 棧是限定只能在棧是限定只能在表的同一端表的同一端進(jìn)行插入和刪除運(yùn)算的進(jìn)行插入和刪除運(yùn)算的線性表線性表。9.3 9.3 棧棧2.棧的術(shù)語(yǔ)棧的術(shù)語(yǔ) 棧頂：棧頂：允許進(jìn)行插入和刪除的一端。允許進(jìn)行插入和刪除的一端。 棧底棧底：與棧頂相對(duì)的一端。與棧頂相對(duì)的一端。 入棧入棧：向棧頂插入一個(gè)元素。向棧頂插入一個(gè)元素。 出棧出棧：從棧頂取出一個(gè)元素。從棧頂取出一個(gè)元素。棧的入棧和出棧操作可以穿插進(jìn)行，所以對(duì)應(yīng)于相

37、同的入棧的入棧和出棧操作可以穿插進(jìn)行，所以對(duì)應(yīng)于相同的入棧序列其出棧序列可以有多種。棧序列其出棧序列可以有多種。例：例：設(shè)設(shè)A , B , C 三個(gè)元素依次進(jìn)棧，則可能的出棧序列有：三個(gè)元素依次進(jìn)棧，則可能的出棧序列有：棧的概念（棧的概念（2）9.3 9.3 棧棧A , B , C A , C , B B , A , C B , C , AC , B , A 不可能的出棧序列：不可能的出棧序列： C , A , B 4. 棧的基本運(yùn)算：棧的基本運(yùn)算：入棧、出棧、判棧空、取棧頂元素、置棧空入棧、出棧、判?？?、取棧頂元素、置棧空練習(xí)練習(xí)9.3 9.3 棧棧n 以順序方式存儲(chǔ)的棧稱為以順序方式存儲(chǔ)的

38、棧稱為順序棧順序棧。n 順序?？梢杂靡痪S數(shù)組實(shí)現(xiàn)。順序?？梢杂靡痪S數(shù)組實(shí)現(xiàn)。n 棧頂指示器（棧頂指示器（top）：指示當(dāng)前棧頂位置）：指示當(dāng)前棧頂位置 。n 棧容量（棧容量（Maxsize）：棧中最多可以存放的元素個(gè)數(shù)。）：棧中最多可以存放的元素個(gè)數(shù)。順序棧（順序棧（1）9.3 9.3 棧棧 A B C D E 0 1 2 3 4 . Maxsize-1top棧底棧底棧頂棧頂stack運(yùn)算：運(yùn)算：判?？?、判棧滿、入棧、出棧、取棧頂元素、置?？张袟？?、判棧滿、入棧、出棧、取棧頂元素、置?？? 空棧：空棧：top=-1 棧滿：棧滿：top=Maxsize-1 9.3 9.3 棧棧n 字符型順序棧類

39、的定義與實(shí)現(xiàn)：字符型順序棧類的定義與實(shí)現(xiàn)：#include class SeqStackprivate: int top;/棧頂指示器棧頂指示器int Maxsize; /棧容量棧容量char * stack; public:SeqStack(int m=10)/構(gòu)造函數(shù)，建立空棧構(gòu)造函數(shù)，建立空棧 stack=new charm; /動(dòng)態(tài)申請(qǐng)?？臻g動(dòng)態(tài)申請(qǐng)棧空間 Maxsize=m; top=-1; SeqStack()delete stack;/析構(gòu)函數(shù)析構(gòu)函數(shù)9.3 9.3 棧棧例：例：利用棧實(shí)現(xiàn)將一個(gè)非負(fù)的十進(jìn)制整數(shù)轉(zhuǎn)換為利用棧實(shí)現(xiàn)將一個(gè)非負(fù)的十進(jìn)制整數(shù)轉(zhuǎn)換為B（2B16)進(jìn)進(jìn)制整數(shù)。

40、制整數(shù)。#include seqstack.h /順序棧類的定義和實(shí)現(xiàn)順序棧類的定義和實(shí)現(xiàn)void Base_conversion(long x,int base)char digit=0123456789ABCDEF,remainder,ch; SeqStack stk; /缺省棧容量為缺省棧容量為10 int temp=x; while(temp!=0) remainder=digittemp%base; if(stk.Push(remainder)=false)cout”棧滿棧滿n”; temp/=base; coutx對(duì)應(yīng)的對(duì)應(yīng)的base進(jìn)制數(shù)是：進(jìn)制數(shù)是：; while(!stk.I

41、sEmpty() stk.Top(ch); coutch; stk.Pop(); 隊(duì)列的概念（隊(duì)列的概念（1）1.隊(duì)列的定義隊(duì)列的定義 2. 隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn) 隊(duì)列中元素的變化是隊(duì)列中元素的變化是按按先進(jìn)先出先進(jìn)先出原則進(jìn)行，因此又稱隊(duì)原則進(jìn)行，因此又稱隊(duì)為為先進(jìn)先出先進(jìn)先出（First In First Out，簡(jiǎn)稱，簡(jiǎn)稱FIFO）表）表 。 只能在只能在表的一端表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的進(jìn)行插入，而在另一端進(jìn)行刪除的線性表線性表。9.4 9.4 隊(duì)列隊(duì)列3. 隊(duì)列的基本運(yùn)算隊(duì)列的基本運(yùn)算 入隊(duì)、出隊(duì)、判隊(duì)空、判隊(duì)滿、取隊(duì)頭元素、置隊(duì)空入隊(duì)、出隊(duì)、判隊(duì)空、判隊(duì)滿、取隊(duì)頭元素、

42、置隊(duì)空 順序隊(duì)列（順序隊(duì)列（1）9.4 9.4 隊(duì)列隊(duì)列n 以順序方式存儲(chǔ)的隊(duì)稱為以順序方式存儲(chǔ)的隊(duì)稱為順序隊(duì)順序隊(duì)。n 順序隊(duì)可以用一維數(shù)組實(shí)現(xiàn)。順序隊(duì)可以用一維數(shù)組實(shí)現(xiàn)。n 隊(duì)頭指示器（隊(duì)頭指示器（ front）：）：指示當(dāng)前隊(duì)頭位置。指示當(dāng)前隊(duì)頭位置。n 隊(duì)尾指示器（隊(duì)尾指示器（rear）：）：指示指示將要入隊(duì)元素將要入隊(duì)元素所在的位置。所在的位置。隊(duì)列操作演示隊(duì)列操作演示假溢出：假溢出：當(dāng)隊(duì)中還有空間可放數(shù)據(jù)，但不能執(zhí)行入隊(duì)操作。當(dāng)隊(duì)中還有空間可放數(shù)據(jù)，但不能執(zhí)行入隊(duì)操作。9.4 9.4 隊(duì)列隊(duì)列解決解決假溢出假溢出問(wèn)題的三種方法問(wèn)題的三種方法1）建立一個(gè)足夠大的存儲(chǔ)空間。）建立一個(gè)足

43、夠大的存儲(chǔ)空間。rear9.4 9.4 隊(duì)列隊(duì)列 C D 0 1 2 3 4frontE2）平移元素。）平移元素。3）循環(huán)隊(duì)列方式循環(huán)隊(duì)列方式。隊(duì)頭、隊(duì)尾指針循環(huán)移動(dòng)。隊(duì)頭、隊(duì)尾指針循環(huán)移動(dòng)。rear 1.入隊(duì)、出隊(duì)和取隊(duì)頭元素：入隊(duì)、出隊(duì)和取隊(duì)頭元素： 9.4 9.4 隊(duì)列隊(duì)列l(wèi)入隊(duì)：入隊(duì)： elemrear=x; elemrear=x; rear=rear=（rear+1rear+1）%Maxsize%Maxsize; ;l出隊(duì)：出隊(duì)：front=front=（front+1front+1）%Maxsize%Maxsize; ;l取隊(duì)頭元素：取隊(duì)頭元素： x=elemfront;x=ele

44、mfront;l求隊(duì)列長(zhǎng)度：求隊(duì)列長(zhǎng)度：方法方法1：(Maxsize+rear-front)%Maxsize方法方法2：設(shè)一個(gè)計(jì)數(shù)變量：設(shè)一個(gè)計(jì)數(shù)變量(count),由入隊(duì)和出隊(duì)操作控制計(jì)數(shù)由入隊(duì)和出隊(duì)操作控制計(jì)數(shù)9.4 9.4 隊(duì)列隊(duì)列2.判隊(duì)空和判隊(duì)滿的方法判隊(duì)空和判隊(duì)滿的方法 循環(huán)隊(duì)列隊(duì)空時(shí)：循環(huán)隊(duì)列隊(duì)空時(shí)： front=rear 9.4 9.4 隊(duì)列隊(duì)列 0 1 2 3 4frontrear循環(huán)隊(duì)列隊(duì)滿時(shí)：循環(huán)隊(duì)列隊(duì)滿時(shí)： front=rear A B C D E 0 1 2 3 4frontrear9.4 9.4 隊(duì)列隊(duì)列2.判隊(duì)空和判隊(duì)滿的方法判隊(duì)空和判隊(duì)滿的方法 方法方法1： 利用利用front和和rear的值判斷的值判斷“隊(duì)空隊(duì)空”和和“隊(duì)隊(duì)滿滿”： 隊(duì)空時(shí)：隊(duì)空時(shí)： front=rear 9.