數(shù)據(jù)結(jié)構(gòu)講義ppt課件-在線瀏覽
2025-03-08 08:06本頁(yè)面
【正文】 3 運(yùn)算 — 解決具體問(wèn)題的基本操作 ? 算法設(shè)計(jì)，依賴(lài)于計(jì)算機(jī)如何存儲(chǔ)問(wèn)題的數(shù)學(xué)模型。沃斯 )： — 世界著名計(jì)算機(jī)科學(xué)家， PASCAL語(yǔ)言發(fā)明人 Data structure + Algorithm = Programming 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序設(shè)計(jì) ? 程序設(shè)計(jì) ：為計(jì)算機(jī)處理問(wèn)題編制一組指令集 ? 算法 ： 處理問(wèn)題的策略 ? 數(shù)據(jù)結(jié)構(gòu) ：?jiǎn)栴}的數(shù)學(xué)模型、 存儲(chǔ)結(jié)構(gòu)、運(yùn)算等 19 什么是數(shù)據(jù)結(jié)構(gòu) 概括地說(shuō) ： 數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述 現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型 (非數(shù)值計(jì)算 )及其上的操作 在計(jì)算機(jī)中如何 表示和實(shí)現(xiàn) ”的學(xué)科。在計(jì)算機(jī)科學(xué)中是指所有 能輸入到計(jì)算機(jī)中 并 被計(jì)算機(jī)程序處理 的 符號(hào)的總稱(chēng) 。 一個(gè)數(shù)據(jù)元素可由若干個(gè) 數(shù)據(jù)項(xiàng) 組成。 基本概念和術(shù)語(yǔ) 21 姓名 地址 李 1 XXX 李 2 XXX …… 張 1 XXX 張 2 XXX …… 王 1 XXX 王 2 XXX …… 22 數(shù)據(jù)元素 例 : 通訊錄 基本概念和術(shù)語(yǔ) 數(shù)據(jù)項(xiàng) ? 數(shù)據(jù)結(jié)構(gòu) (Data Structure)： 是相互之間存在一種或多種 特定關(guān)系 的 數(shù)據(jù)元素的集合 。 線性結(jié)構(gòu)： 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 圖狀結(jié)構(gòu)： 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。 例：復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下： Complex=(C， R) C是含兩個(gè)實(shí)數(shù)的集合 {C1， C2}，表示復(fù)數(shù)的實(shí)部 和虛部。 25 基本概念和術(shù)語(yǔ) 二元組 (twotuple) 數(shù)據(jù)表示 +關(guān)系表示 該定義僅是對(duì)操作對(duì)象的一種數(shù)學(xué)描述，或者說(shuō)，是從操作對(duì)象抽 象出來(lái)的數(shù)學(xué)模型。 ? 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) ： 結(jié)點(diǎn) （數(shù)據(jù)元素）和 數(shù)據(jù)域 （數(shù)據(jù)項(xiàng)）； 順序存儲(chǔ)結(jié)構(gòu)： 用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系； 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針，用此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。 在高級(jí)語(yǔ)言中，包含： – 原子類(lèi)型 值不可分解 ? int, char, unsigned char, char * 等 – 結(jié)構(gòu)類(lèi)型 — 可以分解 ? 數(shù)組等 在底層硬件系統(tǒng)中，包含： ? 位、字節(jié)、字等原子類(lèi)型（與、或、移位等） “ 數(shù)據(jù)類(lèi)型 ” 的作用： – 對(duì)計(jì)算機(jī)來(lái)說(shuō)，解釋計(jì)算機(jī)內(nèi)存信息的手段 – 對(duì)用戶(hù)來(lái)說(shuō)，實(shí)現(xiàn)信息隱蔽，將用戶(hù)不必了解的細(xì)節(jié)封裝在類(lèi)型中。 ADT實(shí)際上定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)的 邏輯結(jié)構(gòu) 以及在此結(jié)構(gòu)上的 一組算法 ,包含了該數(shù)據(jù)結(jié)構(gòu)的全部?jī)?nèi)容。 30 基本概念和術(shù)語(yǔ) 邏輯結(jié)構(gòu) ADT （對(duì)用戶(hù)透明） User 1 User 2 User n ……... 實(shí)現(xiàn) 1 實(shí)現(xiàn) 2 實(shí)現(xiàn) 3 31 基本概念和術(shù)語(yǔ) 例 1 抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義： ADT Complex { 數(shù)據(jù)對(duì)象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 ｜ e1是復(fù)數(shù)的實(shí)數(shù)部分 , e2 是復(fù)數(shù)的虛數(shù)部分 } 基本操作： InitComplex( amp。 GetReal( Z, amp。 操作結(jié)果：用 realPart返回復(fù)數(shù) Z的實(shí)部值。ImagPart ) 初始條件：復(fù)數(shù)已存在。 Add( z1,z2, amp。 操作結(jié)果：用 sum返回兩個(gè)復(fù)數(shù) z1,z2的和值。 ? C語(yǔ)言實(shí)現(xiàn) 基本概念和術(shù)語(yǔ) typedef struct { float realpart； float imagpart； }plex； // 存儲(chǔ)結(jié)構(gòu)的定義 void GetReal( plex Z, float amp。imagpart )； // 返回復(fù)數(shù) Z 的虛部值 …… // 基本操作的函數(shù)原型說(shuō)明 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線性表 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu) 小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 基本概念和術(shù)語(yǔ) 34 ? 預(yù)定義常量和類(lèi)型 ? typedef ? 算法用函數(shù)描述 ? 賦值語(yǔ)句 ? 選擇語(yǔ)句 ? 循環(huán)語(yǔ)句 抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn) 35 ? 結(jié)束語(yǔ)句 ? 輸入輸出語(yǔ)句 ? 注釋 ? 基本函數(shù) ? 邏輯運(yùn)算 本課程采用類(lèi) C語(yǔ)言 (介于偽代碼和 C語(yǔ)言 )描述各種抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)。 36 抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn) ? 算法用函數(shù)描述： 注意 C++中的引用調(diào)用。 a=5。 swan(amp。b)。 } void swan(int *x, int *y) { int temp。 *x=*y。 } 例 2:c++中的引用調(diào)用 . void main() { int a, b。 b=3。 printf(a, b)。x, int amp。 temp=x。 y=temp。 break。 break； default ： 語(yǔ)句序列 n+1。 表達(dá)式 2。 ? while 循環(huán)： while(條件表達(dá)式 ) 循環(huán)語(yǔ)句 。 }while(條件表達(dá)式 )。 或 return。 ? 異常結(jié)束： exit(異常代碼 )； 抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn) ? 輸入輸出語(yǔ)句： ? 輸入語(yǔ)句： scanf([格式串 ]，變量名 1， … ，變量名 n) ； ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1