Ch01 數(shù)據(jù)結(jié)構(gòu)概論01(1)

1、第一章 數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)電子教案1什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍钏惴ǘx模板算法簡單性能分析與度量第一章 數(shù)據(jù)結(jié)構(gòu)概念2“學(xué)生”表格3“課程”表格4學(xué)生(學(xué)號,姓名,性別,籍貫)課程(課程號,課程名,學(xué)分)選課(學(xué)號,課程號,成績) “選課單”包含如下信息 學(xué)號 課程編號 成績 時間 學(xué)生選課系統(tǒng)中的實體之間是一種網(wǎng)狀關(guān)系5UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp6數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機(jī)中，被計算機(jī)程序識別

2、和處理的符號的集合。數(shù)據(jù)的分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)7姓名所在院系性別出生日期年 月職務(wù)業(yè)績數(shù)據(jù)元素 (data element)數(shù)據(jù)的基本單位。在計算機(jī)程序中常作為一個整體進(jìn)行考慮和處理。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。8數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素和數(shù)據(jù)元素之間都不會是孤立的，而是有這樣或那樣的關(guān)系的，這種關(guān)系稱為結(jié)構(gòu)。9什么是數(shù)據(jù)結(jié)構(gòu)定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)元素的集合，R

3、是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。10例：N 個網(wǎng)點之間的連通關(guān)系樹形關(guān)系網(wǎng)狀關(guān)系15615243624311數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式包括三個方面：數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示；數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。本書1.1.3節(jié)先從邏輯的角度出發(fā)分析數(shù)據(jù)的結(jié)構(gòu)類別。12數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)。13數(shù)據(jù)邏輯結(jié)構(gòu)的分類線性結(jié)構(gòu) 線性表非

4、線性結(jié)構(gòu) 樹 圖（或網(wǎng)絡(luò)）14線性結(jié)構(gòu)樹形結(jié)構(gòu)樹 二叉樹 二叉搜索樹bindevetclibuser1413121123456789103158710119987456623131115堆結(jié)構(gòu) “最大”堆 “最小”堆12354871110291641012115123698716圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634不難發(fā)現(xiàn)：樹有層次感，而圖和網(wǎng)絡(luò)沒有。17數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)（也叫物理結(jié)構(gòu)）；數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。 順序存儲表示 鏈接存儲表示 索引存儲表示 散列存儲表示主要用于內(nèi)存的存儲表示主要用于外存 (文件

5、) 的存儲表示見課本P.6, 上數(shù)第2段 18數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容分析實際問題，確定時空限制，建立數(shù)學(xué)模型（數(shù)據(jù)的邏輯結(jié)構(gòu)）及基本運算。在計算機(jī)上實現(xiàn)（把邏輯結(jié)構(gòu)轉(zhuǎn)換為物理結(jié)構(gòu)，并實現(xiàn)運算）。評價。19抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合，以及定義于這個值集合上的一組操作的總稱。C+語言中的基本數(shù)據(jù)類型 char int float double void 字符型 整型 浮點型 雙精度型 無值 20構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成?；緮?shù)據(jù)類型可以看作是計算機(jī)中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來

6、使用的。數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。 21抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。特點是：信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離。抽象數(shù)據(jù)類型可用（D, R, P）三元組表示，其中，D 是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），R是 D上的關(guān)系集合，P 是對 D 的基本操作集合。 22抽象數(shù)據(jù)類型查找 登錄 刪除 修改 符 號 表23抽象數(shù)據(jù)類型的描述其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操

7、作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）前置條件：先決條件描述后置條件：操作結(jié)果描述24基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。 “前置條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。 “后置條件”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。25自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber IS Objects: 一個整數(shù)的有序子集合,它開始于0, 結(jié) 束于機(jī)器能表示的最大整數(shù)(MaxInt)。 Function: 對于所有的 x, y NaturalNumber; False, True Boolean, +、-、 0，返回 false；否則返回trueDelete ( ID )：Student前置條件：學(xué)生信息表不空，且存在學(xué)號為ID的學(xué)生后置條件：刪除學(xué)號為ID的學(xué)生，并返回被刪學(xué)生信息 END Student30關(guān)于前置條件的判斷問題 一般用if else來判斷，也可以用C+提供的assert函數(shù)來實現(xiàn)。 如：a