大學(xué)《數(shù)據(jù)結(jié)構(gòu)教程》(第5版) 李春葆 清華大學(xué)出版社課件第1章 緒論

1、數(shù)據(jù)結(jié)構(gòu)目標(biāo):一方面理解數(shù)據(jù)結(jié)構(gòu)中的基本概念掌握幾種常見(jiàn)邏輯結(jié)構(gòu)對(duì)應(yīng)的算法及相應(yīng)存儲(chǔ)結(jié)構(gòu)上的算法實(shí)現(xiàn)初步了解算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析方法。另一方面通過(guò)本課程算法設(shè)計(jì)和上機(jī)實(shí)現(xiàn)的訓(xùn)練，培養(yǎng)學(xué)生聯(lián)系實(shí)際分析問(wèn)題、解決問(wèn)題的能力，提高編程能力和自學(xué)能力。同時(shí)為算法設(shè)計(jì)與分析、操作系統(tǒng)、編譯原理等后續(xù)課程的學(xué)習(xí)奠定良好的編程基礎(chǔ)要求:多讀、多想、多練 總學(xué)時(shí)：總學(xué)時(shí)：48 理論學(xué)時(shí)：理論學(xué)時(shí)：32 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：16教材：教材： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教程教程(第第5版版) 李春葆李春葆 清華大學(xué)出版社清華大學(xué)出版社教學(xué)參考書：教學(xué)參考書：(1)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社(2)數(shù)據(jù)

2、結(jié)構(gòu)算法解析 高一凡 清華大學(xué)出版社第第1章：緒論章：緒論第第2章：線性表（重點(diǎn)）章：線性表（重點(diǎn)）第第3章：棧和隊(duì)列（重點(diǎn)）章：棧和隊(duì)列（重點(diǎn)）第第4章：串、多維數(shù)組與廣義表章：串、多維數(shù)組與廣義表第第5章：樹和二叉樹（重點(diǎn)）章：樹和二叉樹（重點(diǎn)）第第6章：圖（重點(diǎn)）章：圖（重點(diǎn)）第第7章：查找（重點(diǎn)）章：查找（重點(diǎn)）第第8章：內(nèi)部排序（重點(diǎn)）章：內(nèi)部排序（重點(diǎn)）數(shù)據(jù)結(jié)構(gòu)第1章 緒 論 1、了解數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)概念及邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系2、了解算法的定義、算法的特性、算法的時(shí)間代價(jià)、算法的空間代價(jià)3、掌握計(jì)算語(yǔ)句頻度和估算算

3、法時(shí)間復(fù)雜度的方法教學(xué)要求教學(xué)要求重點(diǎn)重點(diǎn)：1、基本概念：數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等2、算法含義、特性、算法時(shí)間復(fù)雜度分析難點(diǎn)：難點(diǎn)：算法時(shí)間復(fù)雜度分析重點(diǎn)重點(diǎn)、難點(diǎn)難點(diǎn) l1.1.1 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容l1.1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)l1.1.3 數(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ì)算問(wèn)題。主要研究非數(shù)值計(jì)算問(wèn)題。（多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)） 例例1-1 電話號(hào)碼查詢問(wèn)題：電話號(hào)碼查詢問(wèn)題： 電話號(hào)碼薄電話號(hào)碼薄(a1,b1)(a2,b2).(an,bn) 其中：其中：

4、ai為某人姓名，為某人姓名，bi為該人的電話號(hào)碼；為該人的電話號(hào)碼； 要求：設(shè)計(jì)一個(gè)算法，給定一個(gè)姓名時(shí)能查出此人的電話號(hào)碼？ 非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：如果姓名和電話號(hào)碼的排列次序無(wú)規(guī)律，則只能逐一比較如果姓名和電話號(hào)碼的排列次序無(wú)規(guī)律，則只能逐一比較姓名進(jìn)行查找；姓名進(jìn)行查找；如果姓名是按字典順序組織，則查找就快捷多了；如果姓名是按字典順序組織，則查找就快捷多了；要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法）的效率電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法）的效率。諸如此類的還有諸如此類的還

5、有考試成績(jī)查詢問(wèn)題考試成績(jī)查詢問(wèn)題、企業(yè)進(jìn)、銷、存企業(yè)進(jìn)、銷、存管理系統(tǒng)管理系統(tǒng)等。等。 例例1-2 田徑賽的時(shí)間安排問(wèn)題（無(wú)向圖的著色問(wèn)田徑賽的時(shí)間安排問(wèn)題（無(wú)向圖的著色問(wèn)題）題） ：設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。成比賽。 非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：姓 名項(xiàng)目 1項(xiàng)目 2項(xiàng)目 3丁 一跳高跳 遠(yuǎn)100 米馬 二標(biāo) 槍鉛 球張 三標(biāo) 搶100 米200 米李 四鉛 球2

6、00 米跳 高王 五跳 遠(yuǎn)200 米 （1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目： 跳高 跳遠(yuǎn) 標(biāo)槍 鉛球 100米 200米 a b c d e f （2）用頂點(diǎn)代表比賽項(xiàng)目）用頂點(diǎn)代表比賽項(xiàng)目 不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。 （3）某選手比賽的項(xiàng)目必定有邊相連（不能同時(shí)）某選手比賽的項(xiàng)目必定有邊相連（不能同時(shí)比賽）。比賽）。 非數(shù)值計(jì)算問(wèn)題非數(shù)值計(jì)算問(wèn)題 -田徑賽的時(shí)間安排問(wèn)題解法田徑賽的時(shí)間安排問(wèn)題解法姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一 a b e馬二 c d 張三 c e f李四 d f a王五 b faebfdc比賽時(shí)間比賽項(xiàng)目1a，c2b，d

7、3e4f 只需安排四個(gè)單位時(shí)間進(jìn)行比賽不直接相連的頂點(diǎn)就可以同時(shí)進(jìn)行比賽&求解非數(shù)值計(jì)算的問(wèn)題：求解非數(shù)值計(jì)算的問(wèn)題： 主要考慮的是設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。 即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？織和存儲(chǔ)？ 因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。之間的關(guān)系和操作的學(xué)科。是介于數(shù)學(xué)、計(jì)算機(jī)硬件和軟件之間的一門是介于數(shù)學(xué)、計(jì)算機(jī)硬件和軟件之間的一門核心課程。核心課程。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-答：答：計(jì)算機(jī)內(nèi)的

8、數(shù)值運(yùn)算依靠方程式，而計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算非數(shù)值運(yùn)算（如（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，運(yùn)算效率可能有明顯的差異。運(yùn)算效率可能有明顯的差異。 數(shù)據(jù)（data）：是信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。 數(shù)據(jù)元素（data element）：是數(shù)據(jù)的基本單位。 數(shù)據(jù)項(xiàng)（data item）： 是組成數(shù)據(jù)元素的、有獨(dú)立含義、不可分割

9、的最小單位。 數(shù)據(jù)對(duì)象（data object）：是相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)集合的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu)（data structure）：是指互相之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的形式定義為一個(gè)二元組：data_structure =(d，r)其中，d是數(shù)據(jù)元素的有限集，r是d上關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。有一數(shù)據(jù)結(jié)構(gòu)采用二元組描述為有一數(shù)據(jù)結(jié)構(gòu)采用二元組描述為d_s=(d，r)，其中：其中：d= a，b，c，d，e，f，g；r=，1）順序存儲(chǔ)結(jié)構(gòu)2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3）索引存儲(chǔ)結(jié)構(gòu) p84）哈希（或散列）存儲(chǔ)結(jié)構(gòu) p8數(shù)據(jù)的運(yùn)算主要有修改

10、、插入、刪除、查找、排序。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。l1.2.1 1.2.1 數(shù)據(jù)類型數(shù)據(jù)類型l1.2.2 1.2.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型數(shù)據(jù)類型（data type）是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合，即該類型的取值范圍及該類型中可允許使用的一組運(yùn)算。 比如：整型抽象數(shù)據(jù)類型:用于表示實(shí)際應(yīng)用問(wèn)題的數(shù)據(jù)模型以及定義在該模型上的一組操作;可用以下三元組表示： adt=（d,s,p）其中：d是數(shù)據(jù)元素的有限集；s是d上關(guān)系集；p是對(duì)d的基本操作集。抽象數(shù)據(jù)類型的定義格式如下：adt 抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象：結(jié)構(gòu)關(guān)系

11、：基本操作：adt 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型的2個(gè)重要特征：p14數(shù)據(jù)抽象(抽象出數(shù)據(jù)的邏輯結(jié)構(gòu)和邏輯結(jié)構(gòu)上的運(yùn)算)數(shù)據(jù)封裝 (把外部特性和內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離,并對(duì)用戶隱藏實(shí)現(xiàn)細(xì)節(jié)汽車空調(diào)按鈕)adt list 數(shù)據(jù)元素：所有ai屬于同一數(shù)據(jù)對(duì)象，i=1，2，n，n0；用一組人排隊(duì)來(lái)想 結(jié)構(gòu)關(guān)系：所有數(shù)據(jù)元素ai（i=1，2，n-1）存在次序關(guān)系，a1無(wú)前趨，an無(wú)后繼；基本操作：設(shè)l為list，則有initlist(l)：初始化線性表；listlength(l)：求線性表的表長(zhǎng)；getdata(l,i)：取線性表的第i個(gè)元素；inslist(l,i,b)：在線性表的第i個(gè)位置插入元素b；de

12、llist(l,i)：刪除線性表的第i個(gè)數(shù)據(jù)元素；adt list;l1 1. .3.1 3.1 算法特性算法特性l1 1. .3.2 3.2 算法描述算法描述1）有窮有窮性性(有窮步、每一步對(duì)應(yīng)有窮的時(shí)間有窮步、每一步對(duì)應(yīng)有窮的時(shí)間)2）確定性確定性(含義確定、輸入含義確定、輸入相同時(shí)結(jié)果確定）相同時(shí)結(jié)果確定）（咬死了獵人咬死了獵人的狗的狗）3）可行性可行性(每一個(gè)操作都能準(zhǔn)確執(zhí)行。例：每一個(gè)操作都能準(zhǔn)確執(zhí)行。例：x/0 ？）？）4）輸入輸入(0個(gè)或多個(gè)輸入）個(gè)或多個(gè)輸入）5）輸出輸出(1個(gè)或多個(gè)輸出）個(gè)或多個(gè)輸出）算法的含義：對(duì)特定問(wèn)題求解步驟的一種描述對(duì)特定問(wèn)題求解步驟的一種描述算法具有

13、5個(gè)重要特性：p14void test( )int n=8；while(n%8=0)/死循環(huán) n+=8；printf(“%dn”,n)；1）正確性正確性( (能實(shí)現(xiàn)預(yù)先規(guī)定的功能和性能能實(shí)現(xiàn)預(yù)先規(guī)定的功能和性能) )2）可讀性可讀性（易讀、易理解）（易讀、易理解）3）健壯健壯性性（當(dāng)輸入非法數(shù)據(jù)時(shí)，能檢測(cè)出錯(cuò)誤，（當(dāng)輸入非法數(shù)據(jù)時(shí)，能檢測(cè)出錯(cuò)誤，并進(jìn)行適當(dāng)?shù)奶幚聿⑦M(jìn)行適當(dāng)?shù)奶幚恚┤纾┤? :輸入輸入3 3條邊條邊, ,計(jì)算三角形面積計(jì)算三角形面積4）高效高效性性（運(yùn)行的時(shí)間和空間需求）（運(yùn)行的時(shí)間和空間需求） 自然語(yǔ)言 程序流程圖、n-s圖等算法描述工具 程序設(shè)計(jì)語(yǔ)言( (定義函數(shù)定義函數(shù))

14、) 偽碼語(yǔ)言算法在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間取決于下列因素：1 1）硬件的速度硬件的速度2 2）書寫程序的語(yǔ)言書寫程序的語(yǔ)言3 3）編譯程序所生成目標(biāo)代碼的質(zhì)量編譯程序所生成目標(biāo)代碼的質(zhì)量4 4）問(wèn)題的問(wèn)題的規(guī)模規(guī)模前前3 3者都與具體機(jī)器相關(guān)者都與具體機(jī)器相關(guān), ,而數(shù)據(jù)結(jié)構(gòu)只討論算而數(shù)據(jù)結(jié)構(gòu)只討論算法本身的效率高低法本身的效率高低, ,所以只與程序執(zhí)行的數(shù)據(jù)量所以只與程序執(zhí)行的數(shù)據(jù)量相關(guān)相關(guān), ,也就是考慮最后也就是考慮最后1 1條條, ,抽象為問(wèn)題規(guī)模抽象為問(wèn)題規(guī)模語(yǔ)句頻度語(yǔ)句頻度指的指的是語(yǔ)句是語(yǔ)句的重復(fù)執(zhí)行的次數(shù)的重復(fù)執(zhí)行的次數(shù)【例1-6】for(i=1;i=n;i+)/頻度

15、為頻度為n+1for(j=1;j=n;j+)/頻度為頻度為n*(n+1) cij=aij+bij; /頻度為頻度為n2該該算法的執(zhí)行時(shí)間，用算法的執(zhí)行時(shí)間，用t（n）表示。表示。t(n)=2n2+2n+1算法的時(shí)間復(fù)雜度t(n)是該算法的時(shí)間度量記作 t(n)=o(f(n)一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用t(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，t（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是t(n)的同數(shù)量級(jí)函數(shù)（記作t(n)=(f(n),稱(f(n) 為算法的漸近時(shí)間復(fù)雜度漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。例如，若t(n)=n

16、(n+1)/2,則有 t(n)/n2=1/2+1/n，當(dāng)n時(shí)，t(n)/n2=1/2故它的時(shí)間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級(jí)相同。顯然,被稱做問(wèn)題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)與算法的執(zhí)行時(shí)間成正比的原操作;多數(shù)情況下，它就是它就是最深層循環(huán)內(nèi)最深層循環(huán)內(nèi)的語(yǔ)句中的語(yǔ)句中的的原操作原操作，它的執(zhí)行次數(shù)和包含它的語(yǔ)句頻，它的執(zhí)行次數(shù)和包含它的語(yǔ)句頻度相同。度相同。語(yǔ)句的頻度指的是該語(yǔ)句的重復(fù)執(zhí)行的次數(shù)語(yǔ)句的頻度指的是該語(yǔ)句的重復(fù)執(zhí)行的次數(shù)一般情況下一般情況下,對(duì)一個(gè)問(wèn)題對(duì)一個(gè)問(wèn)題(或一類算法或一類算法)只需選只需選擇一種基本操作來(lái)討論算法的時(shí)間復(fù)雜度即擇一種基本操作來(lái)討論算法的

17、時(shí)間復(fù)雜度即可可+x;s=0;時(shí)間復(fù)雜度為o(1)。沒(méi)有循環(huán)語(yǔ)句，其基本運(yùn)算次數(shù)與問(wèn)題規(guī)模無(wú)關(guān)，稱為常數(shù)階，記作o(1)。for(i =1;i=n;+i)+x;s+=x;時(shí)間復(fù)雜度為o(n)。一重循環(huán)，其基本運(yùn)算次數(shù)與問(wèn)題規(guī)模n成線性增長(zhǎng)關(guān)系，稱為線性階，記為o(n)for(j =1;j=n;+j) for(k=1;k=n;+k) +x; s+=x;時(shí)間復(fù)雜度為o(n2)。二重循環(huán)，其基本運(yùn)算次數(shù)于問(wèn)題規(guī)模n成平方級(jí)增長(zhǎng)關(guān)系，稱為平方階，記為o(n2)。for ( j=1;j=n;+j) for(k=1;k=j;+k) +x;s+=x;時(shí)間復(fù)雜度為? 課后思考題：例1-11 x=1; for

18、(i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; 由于內(nèi)循環(huán)的執(zhí)行次數(shù)雖與規(guī)模n無(wú)直接關(guān)系，但與外循環(huán)的變量取值有關(guān)。分析過(guò)程：分析算法規(guī)律可知時(shí)間頻度t(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = + = + 由于有1/6 t（n)/ n3 1，故時(shí)間復(fù)雜度為(n3)。nkk1).321 (nkkk12)1(nkk122nkk12216)12)(1(nnn2)1( nn各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：o(1)o(log2n)o(n)o(n*log2n)o(n2)o(n3)o(2n)o(n!)指的是該算法在運(yùn)行過(guò)程中所耗費(fèi)的輔助存儲(chǔ)空間，如果一個(gè)算法所耗費(fèi)的存儲(chǔ)空間與問(wèn)題規(guī)模n無(wú)關(guān)，記作s(n)=o(1)。有關(guān):s(n)=o(f(n)1.1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念掌握數(shù)據(jù)結(jié)構(gòu)的