課件數(shù)據(jù)結(jié)構(gòu)1ch

1、數(shù)據(jù)結(jié)構(gòu)教師介紹: 姓名: 姜存理 畢業(yè)學(xué)校: 同濟(jì)大學(xué) 辦公室:綜合樓501 辦公室電話: 50214252 第一章 緒言1.1 什么是數(shù)據(jù)結(jié)構(gòu) 程序=數(shù)據(jù)結(jié)構(gòu)+算法例1 書目自動(dòng)檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號索引表線性表例2 人機(jī)對奕問題樹.多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科1.2 基本概念和術(shù)語數(shù)據(jù)（data)所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號數(shù)據(jù)元素（da

2、ta element）數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record）數(shù)據(jù)項(xiàng)（data item）有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系線性結(jié)構(gòu)一個(gè)對一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)一個(gè)對多個(gè)，如樹圖狀結(jié)構(gòu)多個(gè)對多個(gè)，如圖數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)算法設(shè)計(jì) 邏輯結(jié)構(gòu)算法實(shí)現(xiàn) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)分為：順序存儲結(jié)

3、構(gòu)借助元素在存儲器中的相對位置來表示 數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù) 元素間的邏輯關(guān)系元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲1536元素21400元素11346元素3 元素41345h存儲地址 存儲內(nèi)容 指針 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346 鏈?zhǔn)酱鎯?h 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲 鏈

4、式存儲 線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)類型高級語言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱例 C語言中，提供int, char, float, double等基本 數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉 等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADT)Abstract Data Type 簡稱ADT;是指一個(gè)數(shù)學(xué)模型以及定義在

5、此數(shù)學(xué)模型上的一組操作。4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADT)Abstract Data Type 簡稱ADT;是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。例如: “整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語言無關(guān)?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADT)抽象數(shù)據(jù)類型還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個(gè)相對獨(dú)立的模塊時(shí)，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內(nèi)部給出它們的表示和實(shí)現(xiàn)細(xì)節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的描

6、述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D 是數(shù)據(jù)對象， S 是 D 上的關(guān)系集， P 是對 D 的基本操作集。 4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型ADT 有兩個(gè)重要特征:數(shù)據(jù)抽象 ：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義格式ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）初始

7、條件：初始條件描述操作結(jié)果：操作結(jié)果描述 4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義格式例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義格式基本操作：ADT Complex plex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值 plex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。4、數(shù)據(jù)

8、類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義格式基本操作（續(xù)） ：GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1, z2 的和值。 ADT Complex4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的實(shí)現(xiàn)如果，一旦有定義好的ADT，那么根據(jù)選用的高級語言即可具體實(shí)現(xiàn)。 下面以C語言為例，實(shí)現(xiàn)上述的“復(fù)數(shù)”ADT4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的實(shí)現(xiàn)/* 存儲結(jié)構(gòu)的定義 */ typedef struct float realpart；

9、 float imagpart； complex；4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的實(shí)現(xiàn)/* 基本操作的函數(shù)原型說明 */void Assign(complex &Z, float realval,float imagval)；/ 構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) / realval 和 imagval 的值float GetReal( cpmplex Z )；/ 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( cpmplex Z )；/ 返回復(fù)數(shù) Z 的虛部值void add(complex plex z2, complex &sum )； / 以 sum 返回兩個(gè)復(fù)數(shù) z

10、1, z2 的和 4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的實(shí)現(xiàn)/* 基本操作的細(xì)節(jié)實(shí)現(xiàn) */void add(complexz1, complexz2, complex &sum ) / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 抽象數(shù)據(jù)類型的實(shí)現(xiàn)對于某些高級語言已經(jīng)有相應(yīng)的概念，如C+中的類;而有些則沒有，如C語言中，此時(shí)只能結(jié)構(gòu)體來處理數(shù)據(jù)結(jié)構(gòu)，而用函數(shù)來處理操作。4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型4、數(shù)據(jù)類型和抽象數(shù)據(jù)類型AD

11、T角度的數(shù)據(jù)結(jié)構(gòu)層次圖1.4 算法的描述和算法分析簡介算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性算法的描述采用C語言算法的評價(jià)衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲量算法效率用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量1.事后統(tǒng)計(jì)利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分 缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序 所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本 身的優(yōu)劣 2.事前分析估計(jì)一個(gè)高級語言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于： 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機(jī)器代碼質(zhì)量 機(jī)器執(zhí)行指令速度 同一個(gè)算法用不同的語