數(shù)據(jù)結構講義ppt課件(編輯修改稿)
2025-02-15 08:06 本頁面
【文章內(nèi)容簡介】 據(jù)類型 (DT)： 一個 值的集合 及定義在該集合上的 一組操作， 用以刻畫操作對象的特性。 在高級語言中，包含： – 原子類型 值不可分解 ? int, char, unsigned char, char * 等 – 結構類型 — 可以分解 ? 數(shù)組等 在底層硬件系統(tǒng)中，包含： ? 位、字節(jié)、字等原子類型（與、或、移位等） “ 數(shù)據(jù)類型 ” 的作用： – 對計算機來說，解釋計算機內(nèi)存信息的手段 – 對用戶來說，實現(xiàn)信息隱蔽，將用戶不必了解的細節(jié)封裝在類型中。 基本概念和術語 29 ? 抽象數(shù)據(jù)類型（ ADT）： 一個 數(shù)學模型 以及定義在該模型上的一組操作 。 ADT實際上定義了一個數(shù)據(jù)結構的 邏輯結構 以及在此結構上的 一組算法 ,包含了該數(shù)據(jù)結構的全部內(nèi)容。 ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對象： 〈 數(shù)據(jù)對象的定義 〉 數(shù)據(jù)關系： 〈 數(shù)據(jù)關系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類型名 ? 抽象數(shù)據(jù)類型與數(shù)據(jù)類型的聯(lián)系： – 同數(shù)據(jù)類型本質上是一個概念，其 “ 抽象 ” 主要在于數(shù)學模型的數(shù)學抽象特性； – 范疇更廣，可以根據(jù)用戶需要進行定義。 30 基本概念和術語 邏輯結構 ADT （對用戶透明） User 1 User 2 User n ……... 實現(xiàn) 1 實現(xiàn) 2 實現(xiàn) 3 31 基本概念和術語 例 1 抽象數(shù)據(jù)類型復數(shù)的定義： ADT Complex { 數(shù)據(jù)對象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關系： R1＝ {e1,e2 ｜ e1是復數(shù)的實數(shù)部分 , e2 是復數(shù)的虛數(shù)部分 } 基本操作： InitComplex( amp。Z, v1, v2 ) 操作結果：構造復數(shù) Z,其實部和虛部分別被賦以參數(shù) v1和 v2的值。 GetReal( Z, amp。realPart ) 初始條件：復數(shù)已存在。 操作結果：用 realPart返回復數(shù) Z的實部值。 GetImag( Z, amp。ImagPart ) 初始條件：復數(shù)已存在。 操作結果：用 ImagPart返回復數(shù) Z的虛部值。 Add( z1,z2, amp。sum ) 初始條件： z1,z2是復數(shù)。 操作結果：用 sum返回兩個復數(shù) z1,z2的和值。 } ADT Complex 32 基本概念和術語 還可以實現(xiàn)其它操作，譬如： 復數(shù)相乘，復數(shù)共軛等。 ? C語言實現(xiàn) 基本概念和術語 typedef struct { float realpart； float imagpart； }plex； // 存儲結構的定義 void GetReal( plex Z, float amp。realpart )； // 返回復數(shù) Z 的實部值 void Getimag( plex Z, float amp。imagpart )； // 返回復數(shù) Z 的虛部值 …… // 基本操作的函數(shù)原型說明 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結構 非線性結構 順序存儲 鏈式存儲 線性表 樹形結構 圖形結構 小結：數(shù)據(jù)結構的三個方面： 基本概念和術語 34 ? 預定義常量和類型 ? typedef ? 算法用函數(shù)描述 ? 賦值語句 ? 選擇語句 ? 循環(huán)語句 抽象數(shù)據(jù)類型的表示和實現(xiàn) 35 ? 結束語句 ? 輸入輸出語句 ? 注釋 ? 基本函數(shù) ? 邏輯運算 本課程采用類 C語言 (介于偽代碼和 C語言 )描述各種抽象數(shù)據(jù)類型的表示和實現(xiàn)。 ? 預定義常量和類型： //函數(shù)結果狀態(tài)代碼 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 typedef int Status // Status是函數(shù)的類型 ,其值是函數(shù)結果狀態(tài)代碼 typedef xxx ElemType ? typedef： 類型定義描述。 36 抽象數(shù)據(jù)類型的表示和實現(xiàn) ? 算法用函數(shù)描述： 注意 C++中的引用調用。 例 1:c中的指針調用 . void main() { int a, b。 a=5。 b=3。 swan(amp。a, amp。b)。 printf(a, b)。 } void swan(int *x, int *y) { int temp。 temp=*x。 *x=*y。 *y=temp。 } 例 2:c++中的引用調用 . void main() { int a, b。 a=5。 b=3。 swan(a, b)。 printf(a, b)。 } void swan(int amp。x, int amp。y) { int temp。 temp=x。 x=y。 y=temp。 } 37 抽象數(shù)據(jù)類型的表示和實現(xiàn) ? 賦值語句： ? 簡單賦值： 變量名 =表達式； ? 串聯(lián)賦值： 變量名 1=變量名 2=…= 變量名 k=表達式； ? 成組賦值： （變量名 1， … ，變量名 k） =（表達式 1， … ，表達式 k）； 結構變量名 =結構變量名； 結構變量名 = （表達式 1， … ，表達式 k）； 變量名
教學課件相關推薦
鄂ICP備17016276號-1