《數(shù)據(jù)結(jié)構(gòu)與算法----教學(xué)ppt課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與算法----教學(xué)ppt課件.ppt（49頁珍藏版）》請在匯文網(wǎng)上搜索。

1、計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ)第第2章章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法第第1節(jié)節(jié) 概述概述一、數(shù)據(jù)結(jié)構(gòu)討論與研究的范疇一、數(shù)據(jù)結(jié)構(gòu)討論與研究的范疇二、算法二、算法第第 2 頁頁學(xué)習(xí)內(nèi)容與要求學(xué)習(xí)內(nèi)容與要求學(xué)習(xí)內(nèi)容與要求學(xué)習(xí)內(nèi)容與要求學(xué)學(xué)習(xí)和了解數(shù)據(jù)和了解數(shù)據(jù)結(jié)構(gòu)所研究的內(nèi)容；掌握構(gòu)所研究的內(nèi)容；掌握數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)和存構(gòu)和存儲結(jié)構(gòu)的定構(gòu)的定義和基本和基本分分類；學(xué)學(xué)習(xí)和掌握與數(shù)據(jù)和掌握與數(shù)據(jù)結(jié)構(gòu)有關(guān)的名構(gòu)有關(guān)的名詞術(shù)語（如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)（如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)象、數(shù)據(jù)類型、抽象數(shù)據(jù)型、抽象數(shù)據(jù)類型型ADT等等）；等等）；學(xué)學(xué)習(xí)和了解算法的概念、特點以及算法的和了解算法

2、的概念、特點以及算法的評價價標(biāo)準(zhǔn)。準(zhǔn)。第第 3 頁頁程程 序序:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):算法算法:利用計算機語言編制的一組利用計算機語言編制的一組具有確定功能的指令集合。具有確定功能的指令集合。處理問題的策略。處理問題的策略。問題或?qū)ο蟮臄?shù)學(xué)模型問題或?qū)ο蟮臄?shù)學(xué)模型(如如何描述數(shù)據(jù)的外部表現(xiàn)形式何描述數(shù)據(jù)的外部表現(xiàn)形式和內(nèi)部存儲結(jié)構(gòu)和內(nèi)部存儲結(jié)構(gòu))。第第 4 頁頁一、數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)研究和討論的范疇研究和討論的范疇第第 5 頁頁“學(xué)生學(xué)生”數(shù)據(jù)數(shù)據(jù)123456789第第 6 頁頁“課程課程”數(shù)據(jù)數(shù)據(jù)第第 7 頁頁“選課選課”數(shù)據(jù)數(shù)據(jù)學(xué)號課程編號成績時間981640240028206.6.1098

3、1640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024學(xué)生學(xué)生課程課程第第 8 頁頁學(xué)生學(xué)生(學(xué)號學(xué)號,姓名姓名,性別性別,籍貫籍貫)課程課程(課程號課程號,課程名課程名,學(xué)分學(xué)分)選課選課(學(xué)號學(xué)號,課程號課程號,成績成績)“選課”數(shù)據(jù)包含如下信息:學(xué)號 課程編號 成績 時間 學(xué)生選課系統(tǒng)中“學(xué)生”和“課程”這兩個實體構(gòu)成了網(wǎng)狀（圖狀）關(guān)系（即“選課”關(guān)系）。第第 9 頁頁UNIXUNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖第第 1

4、0 頁頁數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容 1.綜合上述例子可見，描述這類非數(shù)值計綜合上述例子可見，描述這類非數(shù)值計 算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而 是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。2.2.簡單地說，作為一門學(xué)科，數(shù)據(jù)結(jié)構(gòu)簡單地說，作為一門學(xué)科，數(shù)據(jù)結(jié)構(gòu) 主要研究主要研究非數(shù)值計算的程序設(shè)計問題非數(shù)值計算的程序設(shè)計問題 當(dāng)中計算機的當(dāng)中計算機的操作對象操作對象（數(shù)據(jù)）（數(shù)據(jù)）以及以及 它們之間的它們之間的關(guān)系關(guān)系（邏輯結(jié)構(gòu)和物理結(jié)（邏輯結(jié)構(gòu)和物理結(jié) 構(gòu)）構(gòu)）和和操作操作（算法實現(xiàn)）（算法實現(xiàn)）。第第 11 頁頁若干名詞術(shù)語

5、若干名詞術(shù)語數(shù)據(jù)（數(shù)據(jù)（data）數(shù)據(jù)元素（數(shù)據(jù)元素（data element）數(shù)據(jù)數(shù)據(jù)項（data item）數(shù)據(jù)數(shù)據(jù)對象（象（data object）數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)（構(gòu)（data structure）數(shù)據(jù)數(shù)據(jù)類型（型（data type）抽象數(shù)據(jù)抽象數(shù)據(jù)類型（型（ADT）第第 12 頁頁數(shù)據(jù)（數(shù)據(jù)（數(shù)據(jù)（數(shù)據(jù)（datadata）數(shù)據(jù)數(shù)據(jù)：計算機中能算機中能識別和和處理的一切符號。理的一切符號。（是信息的是信息的載體，是描述客體，是描述客觀事物的事物的數(shù)、字數(shù)、字符符以及所有能以及所有能輸入到入到計算機中、被算機中、被計算機程算機程序序識別和和處理的理的符號的集合符號的集合。）數(shù)數(shù)值性數(shù)據(jù)性數(shù)

6、據(jù) 非數(shù)非數(shù)值性數(shù)據(jù)性數(shù)據(jù)第第 13 頁頁數(shù)據(jù)元素數(shù)據(jù)元素 和數(shù)據(jù)項和數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)元素：是是組成組成數(shù)據(jù)的數(shù)據(jù)的基本單位基本單位。（在計算機程序中常作為一個整體進在計算機程序中常作為一個整體進行考慮和處理。數(shù)據(jù)元素又可稱為行考慮和處理。數(shù)據(jù)元素又可稱為元元素、結(jié)點、記錄素、結(jié)點、記錄。）數(shù)據(jù)項數(shù)據(jù)項是是具有獨立含義的最小標(biāo)識具有獨立含義的最小標(biāo)識單位。單位。（有時一個數(shù)據(jù)元素可以由若有時一個數(shù)據(jù)元素可以由若干干數(shù)據(jù)項數(shù)據(jù)項組成。組成。）第第 14 頁頁數(shù)據(jù)對象數(shù)據(jù)對象數(shù)據(jù)對象數(shù)據(jù)對象具有相同性具有相同性質(zhì)的數(shù)據(jù)成的數(shù)據(jù)成員（數(shù)據(jù)（數(shù)據(jù)元素）的集合，數(shù)據(jù)的子集元素）的集合，數(shù)據(jù)的子集。例：

7、例：整數(shù)數(shù)據(jù)整數(shù)數(shù)據(jù)對象象 N=0,1,2,學(xué)生數(shù)據(jù)學(xué)生數(shù)據(jù)對象象有有窮集和無集和無窮集集第第 15 頁頁什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)定義定義:由某一由某一數(shù)據(jù)對象數(shù)據(jù)對象及該對象中所有數(shù)據(jù)及該對象中所有數(shù)據(jù)成員之間的成員之間的關(guān)系關(guān)系組成。組成。第第 16 頁頁數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏數(shù)據(jù)的邏 輯結(jié)構(gòu)輯結(jié)構(gòu)。數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，即表示，即數(shù)據(jù)的存儲表示數(shù)據(jù)的存儲表示（物理結(jié)構(gòu)、（物理結(jié)構(gòu)、物理表示）。物理表示）。數(shù)據(jù)的運算，即數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操對數(shù)據(jù)元素施加的操作作。作

8、為學(xué)科，數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織作為學(xué)科，數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織 形式，包括以下內(nèi)容：形式，包括以下內(nèi)容：第第 17 頁頁數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從數(shù)據(jù)的邏輯關(guān)系從數(shù)據(jù)的邏輯關(guān)系上描述數(shù)據(jù)上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，與數(shù)據(jù)的存儲無關(guān)，與數(shù)據(jù)元素本身的具體形式、內(nèi)容與數(shù)據(jù)元素本身的具體形式、內(nèi)容無關(guān)。無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來問題抽象出來的數(shù)據(jù)模型。的數(shù)據(jù)模型。第第 18 頁頁數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)可歸結(jié)為以下可歸結(jié)為以下四類：四類：線性線性結(jié)構(gòu)：一對一關(guān)系樹形樹形結(jié)構(gòu)：一對多關(guān)系圖狀圖狀結(jié)構(gòu)：多對多關(guān)系集

9、合集合結(jié)構(gòu)：簡單隸屬關(guān)系第第 19 頁頁數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式 二元組二元組K=D,R 其中，其中，D 是某一數(shù)據(jù)對象，是某一數(shù)據(jù)對象，R 是該對象中是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。一般表所有數(shù)據(jù)成員之間的關(guān)系的有限集合。一般表現(xiàn)形式如下：現(xiàn)形式如下：D=d1,d2,dnR=r1,r2,rm關(guān)鍵字關(guān)鍵字：數(shù)據(jù)元素中可用于標(biāo)識該數(shù)據(jù)元素的數(shù)據(jù)元素中可用于標(biāo)識該數(shù)據(jù)元素的某個分量（數(shù)據(jù)項）。通常用關(guān)鍵字區(qū)別不同某個分量（數(shù)據(jù)項）。通常用關(guān)鍵字區(qū)別不同的數(shù)據(jù)元素。的數(shù)據(jù)元素。第第 20 頁頁D01,02,03,04,05,

10、06,07,08,09,10R1=,R2=,R3=,第第 21 頁頁R1=,用連線表示數(shù)據(jù)元素之間的聯(lián)系用連線表示數(shù)據(jù)元素之間的聯(lián)系第第 22 頁頁R2=,第第 23 頁頁R3=,第第 24 頁頁由上述數(shù)據(jù)由上述數(shù)據(jù)結(jié)構(gòu)的描述可得出構(gòu)的描述可得出結(jié)論：相同：相同數(shù)據(jù)元素的集合（即同一數(shù)據(jù)數(shù)據(jù)元素的集合（即同一數(shù)據(jù)對象），因象），因其關(guān)系的不同而構(gòu)成不同的數(shù)據(jù)其關(guān)系的不同而構(gòu)成不同的數(shù)據(jù)邏輯結(jié)構(gòu)。構(gòu)。對一一實際應(yīng)用用問題，合理，合理選擇數(shù)據(jù)數(shù)據(jù)邏輯結(jié)構(gòu)才能構(gòu)才能夠設(shè)計出有效的算法。出有效的算法。例：根據(jù)下列選課情況安排考試日程，使得在不沖突的例：根據(jù)下列選課情況安排考試日程，使得在不沖突的情況下

11、用盡可能短的時間安排所有考試。情況下用盡可能短的時間安排所有考試。學(xué)生姓名學(xué)生姓名選修課選修課1選修課選修課2選修課選修課3甲甲ABC乙乙DE丙丙DCF丁丁EFA戊戊BF第第 25 頁頁數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機內(nèi)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機內(nèi) 部的存儲方式，依賴于計算機語部的存儲方式，依賴于計算機語言。言。存儲結(jié)構(gòu)分類存儲結(jié)構(gò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) 散列結(jié)構(gòu)散列結(jié)構(gòu)第第 26 頁頁順序存儲（矢量存儲）結(jié)構(gòu)順序存儲（矢量存儲）結(jié)構(gòu) 所有元素存放在一片連續(xù)的存儲單元中，邏輯上所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存

12、放到計算機內(nèi)存中其存儲地址仍然相鄰。相鄰的元素存放到計算機內(nèi)存中其存儲地址仍然相鄰。鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：所有元素可以存放在不連續(xù)的存儲單元中，元所有元素可以存放在不連續(xù)的存儲單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素素之間的關(guān)系通過地址確定，邏輯上相鄰的元素放到計算機內(nèi)存后其存儲地址不一定是相鄰的。放到計算機內(nèi)存后其存儲地址不一定是相鄰的。第第 27 頁頁順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖第第 28 頁頁數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)數(shù)據(jù)類型型:定定義：一一組性性質(zhì)相同的相同的值的集合的集合,以及定以及定義于于

13、這個個值集合上的一集合上的一組操作的操作的總稱。稱。C C+語語言中的數(shù)據(jù)言中的數(shù)據(jù)類類型型 char int float double void char int float double void 字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無無值 基本數(shù)據(jù)類型（原子類型）：可以看作是計基本數(shù)據(jù)類型（原子類型）：可以看作是計算機中程序設(shè)計語言已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。算機中程序設(shè)計語言已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。構(gòu)造型數(shù)據(jù)類型：由相同或不同成分的類型構(gòu)造型數(shù)據(jù)類型：由相同或不同成分的類型構(gòu)成，如數(shù)組、結(jié)構(gòu)體、類構(gòu)成，如數(shù)組、結(jié)構(gòu)體、類、指針、指針等。等。第第 29 頁頁抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型抽

14、象數(shù)據(jù)類型抽象數(shù)據(jù)類型 由用由用戶定定義，用以表示，用以表示實際應(yīng) 用用問題問題的的數(shù)據(jù)模型。數(shù)據(jù)模型。由由基本的數(shù)據(jù)基本的數(shù)據(jù)類型型組成成,并包并包 括括一一組相關(guān)的服相關(guān)的服務(wù)（或稱操作）。（或稱操作）。第第 30 頁頁抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法:抽象數(shù)據(jù)類型從形式上可用抽象數(shù)據(jù)類型從形式上可用（D，R，O）三元組表示。其中：三元組表示。其中：D是數(shù)據(jù)對象，是數(shù)據(jù)對象，R是是D上上的關(guān)系集，的關(guān)系集，O是對是對D的基本操作集的基本操作集 。一般采用如下格式描述一般采用如下格式描述ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)

15、系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名第第 31 頁頁ADT基本操作的定義格式基本操作的定義格式基本操作名（基本操作名（參數(shù)表參數(shù)表）初始條件初始條件：初始條件描述初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述操作結(jié)果描述 參數(shù)：參數(shù)：賦值參數(shù)賦值參數(shù)只為操作提供輸入值只為操作提供輸入值;引用參數(shù)引用參數(shù)以以&打頭，除可提供輸入值外，還將返回操作結(jié)果。打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件：初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng) 滿足的條件，若不滿足，則操作

16、失敗，并返回相滿足的條件，若不滿足，則操作失敗，并返回相 應(yīng)出錯信息應(yīng)出錯信息。若初始條件為空若初始條件為空,則省略之。則省略之。操作結(jié)果操作結(jié)果：說明操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的說明操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的 變化狀況和應(yīng)返回的結(jié)果。變化狀況和應(yīng)返回的結(jié)果。第第 32 頁頁例如，抽象數(shù)據(jù)類型例如，抽象數(shù)據(jù)類型“復(fù)數(shù)復(fù)數(shù)”的定的定義：義：數(shù)據(jù)對象：數(shù)據(jù)對象：De1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1|e1是復(fù)數(shù)的實數(shù)部分，是復(fù)數(shù)的實數(shù)部分，e2 是復(fù)數(shù)的虛數(shù)部分是復(fù)數(shù)的虛數(shù)部分 ADT Complex 第第 33 頁頁基本操作：基本操作：AssignComplex(&Z,v1,v2)操作結(jié)果：操作結(jié)果：構(gòu)造一個復(fù)數(shù)構(gòu)造一個復(fù)數(shù) Z Z，其實部和虛，其實部和虛部分別被賦以參數(shù)部分別被賦以參數(shù)v1v1和和v2v2的值。的值。DestroyComplex(&Z)操作結(jié)果：操作結(jié)果：復(fù)數(shù)復(fù)數(shù)Z Z被銷毀。被銷毀。GetReal(Z,&realPart)初始條件：初始條件：復(fù)數(shù)已存在。復(fù)數(shù)已存在。操作結(jié)果：操作結(jié)果：用用realPart返回復(fù)數(shù)返回復(fù)數(shù)Z Z的實部值。的實部值。第第