數(shù)據(jù)結(jié)構(gòu)教程學習教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)教程教程第一頁，共47頁。第1頁/共47頁第二頁，共47頁。v編程基礎(chǔ)v考研(ko yn)課程v計算機等級考試課程v程序員考試課程第2頁/共47頁第三頁，共47頁。第3頁/共47頁第四頁，共47頁。第4頁/共47頁第五頁，共47頁。第5頁/共47頁第六頁，共47頁。第6頁/共47頁第七頁，共47頁。&（2）算法的選擇依賴于作為）算法的選擇依賴于作為(zuwi)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)算法）。算法）。&軟件軟件=程序程序+文檔（軟件工程文檔（軟件工程的觀點）的觀點） -數(shù)據(jù)結(jié)構(gòu)的概數(shù)據(jù)結(jié)構(gòu)的概念念(ginin) 第一章

2、第一章 緒論緒論第7頁/共47頁第八頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)的概數(shù)據(jù)結(jié)構(gòu)的概念念(ginin) 第一章第一章 緒論緒論第8頁/共47頁第九頁，共47頁。&數(shù)據(jù)元素之間的相互關(guān)系一般數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學方程加以描述無法用數(shù)學方程加以描述 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第9頁/共47頁第十頁，共47頁。 非數(shù)值非數(shù)值(shz)計算計算問題：問題： -數(shù)據(jù)結(jié)構(gòu)的概數(shù)據(jù)結(jié)構(gòu)的概念念(ginin) 第一章第一章 緒論緒論第10頁/共47頁第十一頁，共47頁。 非數(shù)值非數(shù)值(shz)計算計算問題：問題：姓 名 項目 1 項目 2 項目

3、 3 丁 一 跳高 跳 遠 100 米 馬 二 標 槍 鉛 球 張 三 標 搶 100 米 200 米 李 四 鉛 球 200 米 跳 高 王 五 跳 遠 200 米 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第11頁/共47頁第十二頁，共47頁。（3）某選手比賽的項目必）某選手比賽的項目必定有邊相連（不能同時比定有邊相連（不能同時比賽）。賽）。 非數(shù)值計算問題非數(shù)值計算問題 -田徑賽的時間安排田徑賽的時間安排(npi)問題解法問題解法 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第12頁/共47頁第十三頁，共47頁。姓名項目1項目2項

4、目3丁一 A B E馬二 C D 張三 C E F李四 D F A王五 B FAEBFDC比賽時間比賽項目1A，C2B，D3E4F 只需安排四個單位(dnwi)時間進行比賽 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第13頁/共47頁第十四頁，共47頁。作的學科。作的學科。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第14頁/共47頁第十五頁，共47頁。數(shù)學結(jié)構(gòu)數(shù)學結(jié)構(gòu)”的內(nèi)容。的內(nèi)容。&70年代后期，我國高校陸續(xù)開設(shè)該年代后期，我國高校陸續(xù)開設(shè)該課程。課程。 -數(shù)據(jù)結(jié)構(gòu)的概數(shù)據(jù)結(jié)構(gòu)的概念念(ginin) 第一章第一章 緒論緒

5、論第15頁/共47頁第十六頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第16頁/共47頁第十七頁，共47頁。&一個數(shù)據(jù)元素可由若干個數(shù)一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。分割的最小單位。&數(shù)據(jù)對象數(shù)據(jù)對象(Data Object)：是性：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。據(jù)的一個子集。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第17頁/共47頁第十八頁，共47頁。&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？

6、&幾個幾個(j )概念：概念：&數(shù)據(jù)類型（數(shù)據(jù)類型（Data Type)：在一種程：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。類。&例例1、 在在FORTRAN語言中，變量的語言中，變量的數(shù)據(jù)類型有整型、實型、和復數(shù)型數(shù)據(jù)類型有整型、實型、和復數(shù)型 &例例2、在、在C語言中語言中&數(shù)據(jù)類型：基本類型和構(gòu)造類型數(shù)據(jù)類型：基本類型和構(gòu)造類型&基本類型：整型、浮點型、字符型基本類型：整型、浮點型、字符型&構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義針、枚舉型、自定義 -數(shù)據(jù)結(jié)構(gòu)

7、數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第18頁/共47頁第十九頁，共47頁。&什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？&幾個概念：幾個概念：&抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type簡稱簡稱ADT）&抽象數(shù)據(jù)類型是用戶在數(shù)據(jù)類型抽象數(shù)據(jù)類型是用戶在數(shù)據(jù)類型基礎(chǔ)上基礎(chǔ)上& 新定義新定義(dngy)的數(shù)據(jù)類型的數(shù)據(jù)類型&抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義(dngy)包括包括數(shù)據(jù)組成數(shù)據(jù)組成& 和對數(shù)據(jù)的處理操作和對數(shù)據(jù)的處理操作&抽象數(shù)據(jù)類型是數(shù)據(jù)和數(shù)據(jù)的使抽象數(shù)據(jù)類型是數(shù)據(jù)和數(shù)據(jù)的使用者的一個

8、接口用者的一個接口&抽象數(shù)據(jù)類型的三元組表示抽象數(shù)據(jù)類型的三元組表示 （D，S，P）& D：數(shù)據(jù)對象：數(shù)據(jù)對象 & S：D上的關(guān)系集上的關(guān)系集& P：對：對D的基本操作的基本操作 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第19頁/共47頁第二十頁，共47頁。&什么是數(shù)據(jù)什么是數(shù)據(jù)(shj)結(jié)構(gòu)？結(jié)構(gòu)？&幾個概念：幾個概念：&抽象數(shù)據(jù)抽象數(shù)據(jù)(shj)類型的定義：包類型的定義：包括數(shù)據(jù)括數(shù)據(jù)(shj)對象定義、數(shù)據(jù)對象定義、數(shù)據(jù)(shj)關(guān)系定義和基本操作定義，關(guān)系定義和基本操作定義，書寫格式為：書寫格式

9、為：& ADT：抽象數(shù)據(jù)：抽象數(shù)據(jù)(shj)類型類型名名& 數(shù)據(jù)數(shù)據(jù)(shj)對象：數(shù)據(jù)對象：數(shù)據(jù)(shj)對象的定義對象的定義& 數(shù)據(jù)數(shù)據(jù)(shj)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)(shj)邏輯關(guān)系的定義邏輯關(guān)系的定義& 基本操作：基本操作的定義基本操作：基本操作的定義& ADT 抽象數(shù)據(jù)抽象數(shù)據(jù)(shj)類型類型名名& （P9 例例 1-6） -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第20頁/共47頁第二十一頁，共47頁。儲表示儲表示 方式把它們存儲在計算機的方式把它們存儲在計算機的存儲器中，并在其上定義了一個運存儲器

10、中，并在其上定義了一個運算的集合。算的集合。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第21頁/共47頁第二十二頁，共47頁。&是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。它依賴于計算機語言。&運算（算法）運算（算法） -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第22頁/共47頁第二十三頁，共47頁。個直接前趨和直接后繼。個直接前趨和直接后繼。&例如：樹、圖、多維數(shù)組、廣義例如：樹、圖、多維數(shù)組、廣義表等。表等。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章

11、緒論緒論第23頁/共47頁第二十四頁，共47頁。&數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：數(shù)據(jù)結(jié)構(gòu)的三個方面的含義之：&邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)-劃分方法二劃分方法二&一、集合一、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了結(jié)構(gòu)中的數(shù)據(jù)元素除了(ch le)同屬于一種類型外，別無同屬于一種類型外，別無其它關(guān)系。其它關(guān)系。&二、線性結(jié)構(gòu)二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。素之間存在一對一的關(guān)系。&三、樹型結(jié)構(gòu)三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。素之間存在一對多的關(guān)系。&四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中結(jié)構(gòu)中

12、的數(shù)據(jù)元素之間存在多對多的關(guān)系。的數(shù)據(jù)元素之間存在多對多的關(guān)系。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第24頁/共47頁第二十五頁，共47頁。&（3）索引存儲方法）索引存儲方法&（4）散列存儲方法）散列存儲方法&同一種邏輯結(jié)構(gòu)可采用不同的存儲同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（以上四種之一或組合），這方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時主要考慮的是運算方便及算法的時空要求?？找?。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第25頁/共47頁第二十六頁，共47頁。 -數(shù)據(jù)結(jié)

13、構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第26頁/共47頁第二十七頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第27頁/共47頁第二十八頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第28頁/共47頁第二十九頁，共47頁。(5)output n(6)end返回(fnhu)第29頁/共47頁第三十頁，共47頁。-&一個算法有一個算法有n（n=0)個初個初始數(shù)據(jù)的輸入。始數(shù)據(jù)的輸入。&（5）輸出數(shù)據(jù)）輸出數(shù)據(jù)-&一個算法有一個或多個的一個算法有一個或多個

14、的有效信息的輸出。有效信息的輸出。&思考：算法與程序有何區(qū)思考：算法與程序有何區(qū)別？別？ -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第30頁/共47頁第三十一頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第31頁/共47頁第三十二頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念(ginin) 第一章第一章 緒論緒論第32頁/共47頁第三十三頁，共47頁。數(shù)據(jù)都能得出滿足數(shù)據(jù)都能得出滿足(mnz)規(guī)格規(guī)格說明要求的結(jié)果（窮舉）。說明要求的結(jié)果（窮舉）。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章

15、 緒論緒論返回(fnhu)第33頁/共47頁第三十四頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第34頁/共47頁第三十五頁，共47頁。 -數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念的概念 第一章第一章 緒論緒論第35頁/共47頁第三十六頁，共47頁。算法效率算法效率(xio l)的度量：采用時間復的度量：采用時間復雜度雜度例1.5 分析以下(yxi)程序段的時間復雜度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /第36頁/共47頁第三十七頁，共47頁。12) 12)(1(2nnnn則該程序段的時間(shjin)復雜度：T(n)=)(2222nOn第37頁/共47頁第三十八頁，共47頁。/* 1 * /* 2 * /nnf)(2nnf2log)(nnf2log)()(loglog1)(1)(22nOnnfnT第38頁/共47頁第三十九頁，共47頁。循環(huán)(xnhun)分析執(zhí)行次數(shù)。第39頁/共47頁第四十頁，共47頁。 niijniijjkjkniijjkjnTjjnT1111111111)()1(1 . 1111)(故相加個注共因為第40頁/共47頁第四十一頁，共47頁。nini