數(shù)據(jù)結(jié)構(gòu)清華大學(xué)學(xué)習(xí)教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)清華大學(xué)清華大學(xué)第一頁，共72頁。第一章第一章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j (sh j ji u)ji u)概念概念第1頁/共72頁第二頁，共72頁。 學(xué)學(xué) 號號 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚(yáng)劉激揚(yáng) 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 島島 1979.07 3 98165 盧聲凱盧聲凱 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕

2、 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北 京京 1981.01 8 98310 蔡曉莉蔡曉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12第2頁/共72頁第三頁，共72頁。 課程編號課程編號 課課 程程 名名 學(xué)時學(xué)時 024002 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計算機(jī)原理計算機(jī)原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機(jī)技術(shù)微機(jī)技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 48第3頁/共72頁

3、第四頁，共72頁。學(xué)生學(xué)生( (學(xué)號學(xué)號, ,姓名姓名, ,性別性別(xngbi),(xngbi),籍貫籍貫) )課程課程(kchng)(kchng)( (課程課程(kchng)(kchng)號號, ,課程課程(kchng)(kchng)名名, ,學(xué)分學(xué)分) )選課選課( (學(xué)號學(xué)號, ,課程課程(kchng)(kchng)號號, ,成績成績) )第4頁/共72頁第五頁，共72頁。/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第5頁/共72頁第六頁，共72頁。第6頁/共72頁第七頁，共72頁。姓名姓名 所在院系所

4、在院系 性別性別 出生日期出生日期 年年 月月職務(wù)職務(wù) 業(yè)績業(yè)績數(shù)據(jù)數(shù)據(jù)(shj)(shj)元素元素 (data element) (data element)n數(shù)據(jù)的基本單位。在計算機(jī)程序中常作為一數(shù)據(jù)的基本單位。在計算機(jī)程序中常作為一個整體進(jìn)行考慮和處理。個整體進(jìn)行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data (Data Item)Item)組成。數(shù)據(jù)項是具有獨(dú)立含義的最小組成。數(shù)據(jù)項是具有獨(dú)立含義的最小標(biāo)識單位。標(biāo)識單位。n數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)(ji din)(ji din)、記錄。記錄。第7頁/共72頁第八頁，共

5、72頁。定義定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成數(shù)據(jù)元素之間的關(guān)系組成(z chn)。記為：。記為： Data_Structure = D, R 其中，其中，D 是某一數(shù)據(jù)元素的集合，是某一數(shù)據(jù)元素的集合，R 是該集是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。第8頁/共72頁第九頁，共72頁。 156152436243第9頁/共72頁第十頁，共72頁。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織(zzh)形式形式n包括三個方面：包括三個方面：n數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)元素間的

6、邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；n數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲內(nèi)的表示，數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示；即數(shù)據(jù)的存儲表示；n數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算(yn sun)，即對數(shù)據(jù)元素施加，即對數(shù)據(jù)元素施加的操作。的操作。第10頁/共72頁第十一頁，共72頁。數(shù)據(jù)的邏輯數(shù)據(jù)的邏輯(lu j)結(jié)構(gòu)結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)據(jù)的存儲無關(guān)(wgun)；n數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；來的數(shù)據(jù)模型；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)

7、據(jù)元素本身的形式、內(nèi)容無關(guān)無關(guān)(wgun)；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)關(guān)(wgun)。第11頁/共72頁第十二頁，共72頁。數(shù)據(jù)數(shù)據(jù)(shj)的邏輯結(jié)的邏輯結(jié)構(gòu)分類構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)(jigu)n 線性表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)(jigu)n 樹樹n 圖（或網(wǎng)絡(luò)）圖（或網(wǎng)絡(luò)）第12頁/共72頁第十三頁，共72頁。線性結(jié)構(gòu)線性結(jié)構(gòu)(jigu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)(jigu)樹樹 二叉樹二叉樹 二叉搜索二叉搜索(su (su su)su)樹樹bindevetclibuser1413121123456789103158710119987

8、4566231311第13頁/共72頁第十四頁，共72頁。堆結(jié)構(gòu)堆結(jié)構(gòu)(jigu)123548711102916410121151236987第14頁/共72頁第十五頁，共72頁。圖結(jié)構(gòu)圖結(jié)構(gòu)(jigu) (jigu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)(jigu)(jigu)12543611331814665161921125634第15頁/共72頁第十六頁，共72頁。數(shù)據(jù)數(shù)據(jù)(shj)的存儲結(jié)構(gòu)的存儲結(jié)構(gòu)n數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)；實現(xiàn)；n數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。n 順序存儲表示順序存儲表示(biosh)n 鏈接

9、存儲表示鏈接存儲表示(biosh)n 索引存儲表示索引存儲表示(biosh)n 散列存儲表示散列存儲表示(biosh)主要用于內(nèi)存主要用于內(nèi)存(ni cn)的存儲表示的存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示第16頁/共72頁第十七頁，共72頁。第17頁/共72頁第十八頁，共72頁。n構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。據(jù)類型組成。n構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。n基本數(shù)據(jù)類型可以看作是計算機(jī)中已實基本數(shù)據(jù)類型可以看作是計算機(jī)中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?，F(xiàn)的數(shù)據(jù)結(jié)構(gòu)。n數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它

10、是從編數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用程者的角度來使用(shyng)的。的。n數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運(yùn)算。據(jù)類型的變量，才能參加運(yùn)算。 第18頁/共72頁第十九頁，共72頁。第19頁/共72頁第二十頁，共72頁。抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號號 表表第20頁/共72頁第二十一頁，共72頁。ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象：數(shù)據(jù)對象的定義(dngy) 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義(dngy) 基本操作：基本操作的

11、定義基本操作：基本操作的定義(dngy) ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）基本操作名（參數(shù)表）前置條件：前置條件：先決條件描述先決條件描述后置條件：后置條件：操作結(jié)果描述操作結(jié)果描述第21頁/共72頁第二十二頁，共72頁。第22頁/共72頁第二十三頁，共72頁。第23頁/共72頁第二十四頁，共72頁。第24頁/共72頁第二十五頁，共72頁。第25頁/共72頁第二十六頁，共72頁。面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍?ginin)n面向?qū)ο竺嫦驅(qū)ο?= = 對象類繼承通信對象類繼承通信n對象對象n在應(yīng)用問題中出現(xiàn)的各種在應(yīng)用問題中出現(xiàn)的各種( zhn)( zhn)實實體、事件、規(guī)

12、格說明等。體、事件、規(guī)格說明等。n由一組屬性值和在這組值上的一組服務(wù)由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成。（或稱操作）構(gòu)成。n與與C C中構(gòu)造數(shù)據(jù)類型不同在于：中構(gòu)造數(shù)據(jù)類型不同在于：C C中的構(gòu)造中的構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與操作分?jǐn)?shù)據(jù)類型的變量僅涉及屬性值，與操作分離，而離，而C+C+中的對象則不然。中的對象則不然。第26頁/共72頁第二十七頁，共72頁。n類類 (class)，實例，實例 (instance)n具有相同屬性和服務(wù)的對象歸于同一類，形成具有相同屬性和服務(wù)的對象歸于同一類，形成類。類。n類中的對象為該類的實例。類中的對象為該類的實例。n同一類的實例同一類

13、的實例n共享類的屬性和類的操作；共享類的屬性和類的操作；n通過繼承共享其父類的公共通過繼承共享其父類的公共(gnggng)的和保的和保護(hù)性的屬性和操作；護(hù)性的屬性和操作；n同一類的不同實例有不同的屬性值。同一類的不同實例有不同的屬性值。第27頁/共72頁第二十八頁，共72頁。四邊形類及其對象四邊形類及其對象(duxing)屬性aPoint1 aPoint2aPoint3 aPoint4服務(wù)服務(wù)Draw( )move(x, y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(

14、45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服務(wù)服務(wù)服務(wù)服務(wù)quadrilateral第28頁/共72頁第二十九頁，共72頁。派生類派生類繼承的特性繼承的特性+特有的特性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形第29頁/共72頁第三十頁，共72頁。第30頁/共72頁第三十一頁，共72頁。Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPoly

15、gon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral第31頁/共72頁第三十二頁，共72頁。第32頁/共72頁第三十三頁，共72頁。算法算法(sun f)(sun f)設(shè)計設(shè)計 自頂向下，逐步求精自頂向下，逐步求精 第33頁/共72頁第三十四頁，共72頁。 void selectSort ( int a , const int n ) /對對n個整數(shù)個整數(shù)a0,a1,an-1按遞增順序按遞增順序(shnx)排序排序 for (int i = 0

16、; i n-1; i+) int k = i; /從從ai查到查到an-1, 找最小整數(shù)找最小整數(shù), 在在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; 第34頁/共72頁第三十五頁，共72頁。定義定義 適合多種數(shù)據(jù)類型的類定義或算法，在特定適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過環(huán)境下通過(tnggu)(tnggu)簡單地代換，變成針簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。對具體某種數(shù)據(jù)類型的類定義或算法。第35頁/共72頁第三十六頁，共72頁。用模板用模

17、板(mbn)定義用于排序的數(shù)據(jù)表類定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H#define DATALIST_H#include /K是表項關(guān)鍵碼是表項關(guān)鍵碼類型類型template / /E是是表項類型表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);第36頁/共72頁第三十七頁，共72頁。 public: dataList (int size = 10) : listSize (size), elem

18、ent (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 第37頁/共72頁第三十八頁，共72頁。類中所有操作作為模板函數(shù)的實現(xiàn)類中所有操作作為模板函數(shù)的實現(xiàn)template void dataList : sw

19、ap (int m1, int m2) /交換由交換由m1, m2為下標(biāo)的為下標(biāo)的(bio de)數(shù)組元數(shù)組元素的值素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;第38頁/共72頁第三十九頁，共72頁。template int dataList:minKey (int low, int high) /查找數(shù)組查找數(shù)組Elementlow到到Elementhigh中具中具/有最小關(guān)鍵碼值的表項，函數(shù)返回有最小關(guān)鍵碼值的表項，函數(shù)返回(fnhu)其位置其位置 int min = low; for (int

20、 i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義定義(dngy)的重載的重載操作操作第39頁/共72頁第四十頁，共72頁。template ostream& operator (ostream& outStream, dataList outList) outStream “輸出數(shù)組內(nèi)容輸出數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl;

21、ouStream “輸出數(shù)組當(dāng)前輸出數(shù)組當(dāng)前(dngqin)大小大小 : ” outList.listSize endl; return outStream; 第40頁/共72頁第四十一頁，共72頁。 template istream& operator (istream& inStream, dataList inList) /輸入輸入(shr)對象為對象為inList，輸入，輸入(shr)流對象流對象為為inStream cout inList.listSize; cout “輸入輸入(shr)數(shù)組元素值數(shù)組元素值 : n”; for (int i = 0; i inLis

22、t.listSize; i+) cout “元素元素” i inList.elementi; return inStream; 第41頁/共72頁第四十二頁，共72頁。template void dataList : sort ( ) /按非遞減按非遞減(djin)順序?qū)樞驅(qū)istSize個關(guān)鍵碼個關(guān)鍵碼element0到到/elementArraySize-1排序排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif 第42頁/共72頁第四

23、十三頁，共72頁。使用模板的選擇排序使用模板的選擇排序(pi x)算法的主函算法的主函數(shù)數(shù) #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; 第43頁/共72頁第四十四頁，共72頁。 dataList TestList (SZ); cin TestList; cout TestList endl; Te

24、stList.Sort ( ); cout TestList endl; return 0; 定義定義(dngy)對象對象時，代入實際數(shù)時，代入實際數(shù)據(jù)類型據(jù)類型重載重載(zhn zi)友元操作友元操作標(biāo)準(zhǔn)標(biāo)準(zhǔn)(biozhn)IO操作操作消息通信消息通信第44頁/共72頁第四十五頁，共72頁。第45頁/共72頁第四十六頁，共72頁。第46頁/共72頁第四十七頁，共72頁。第47頁/共72頁第四十八頁，共72頁。例如，給出順序搜索例如，給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an-1中搜索

25、與給定值中搜索與給定值 x 相等的元相等的元/素，函數(shù)返回素，函數(shù)返回(fnhu)其位置，失敗返回其位置，失敗返回(fnhu)-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;第48頁/共72頁第四十九頁，共72頁。 插裝 time( ) 的計時程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout

26、 n runTime endl;事實上，算法運(yùn)行時間要受輸入規(guī)模、利用編譯程序(bin y chn x)生成的目標(biāo)代碼的質(zhì)量、計算機(jī)程序指令系統(tǒng)的品質(zhì)和速度等制約。第49頁/共72頁第五十頁，共72頁。第50頁/共72頁第五十一頁，共72頁。第51頁/共72頁第五十二頁，共72頁。第52頁/共72頁第五十三頁，共72頁。n程序步確定方法程序步確定方法(fngf)n插入計數(shù)全局變量插入計數(shù)全局變量countn建表，列出個語句的程序步建表，列出個語句的程序步例例 以迭代以迭代(di di)(di di)方式求累加和的方式求累加和的函數(shù)函數(shù) float sum (float a , int n) f

27、loat sum (float a , int n) float s = 0.0; float s = 0.0; for (int i = 0; i n; for (int i = 0; i n; i+)i+) s = s + ai; s = s + ai; return s; return s; 第53頁/共72頁第五十四頁，共72頁。在求累加和程序中加入在求累加和程序中加入 count 語句語句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計統(tǒng)計(tngj)執(zhí)行語句條數(shù)執(zhí)行語句條數(shù) for (int i = 0; i

28、 n; i+) count += 2; /針對針對 for 語句語句s += ai;count+; /針對賦值語句針對賦值語句 count += 2; /針對針對 for 的的最后一次最后一次 count+; /針對針對 return 語句語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 3*n+4第54頁/共72頁第五十五頁，共72頁。第55頁/共72頁第五十六頁，共72頁。注意注意(zh y)： 一個語句本身的程序步數(shù)可能不等于該語句一次一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語句賦值語句x =

29、 sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為 1；一次執(zhí)行對函數(shù)一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程序步數(shù)為的調(diào)用需要的程序步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+5第56頁/共72頁第五十七頁，共72頁。第57頁/共72頁第五十八頁，共72頁。例例 求兩個求兩個(lin )n階方陣的乘積階方陣的乘積C = ABvoid MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2

30、n+2) Cij = 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2第58頁/共72頁第五十九頁，共72頁。第59頁/共72頁第六十頁，共72頁。第60頁/共72頁第六十一頁，共72頁。T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;第61頁/共72頁第六十二頁，共72頁。第62頁/共72頁第六十三頁，共72頁。 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行中各行 sumi = 0.0; /數(shù)據(jù)累加數(shù)據(jù)累加 for (int j = 0; j n; j+