課件數(shù)據(jù)結構1ch

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

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

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

4、式存儲 線性表棧隊樹形結構圖形結構數(shù)據(jù)結構的三個方面：數(shù)據(jù)類型高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱例 C語言中，提供int, char, float, double等基本 數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉 等構造數(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;是指一個數(shù)學模型以及定義在

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

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

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

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

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

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

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