數(shù)據(jù)結(jié)構(gòu)-計(jì)143課程導(dǎo)引

1、1課程導(dǎo)引1 什么是數(shù)據(jù)結(jié)構(gòu) ?2 基本概念和術(shù)語3 數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)結(jié)構(gòu)4 本課程的主要內(nèi)容及上課安排1. 什么是數(shù)據(jù)結(jié)構(gòu)？例如 數(shù)值計(jì)算的程序設(shè)計(jì)問題 結(jié)構(gòu)靜力分析計(jì)算 線性代數(shù)方程組 預(yù)報(bào)人口增長情況 微分方程組3非數(shù)值計(jì)算的程序設(shè)計(jì)問題 例1 對(duì)于一個(gè)由12個(gè)099之間的無序整數(shù)組成的集合(20,15,60,25,70, 12, 17,10,14,18,21,32),請(qǐng)編寫查找程序,查找出其中任一整數(shù)的位置。List程序設(shè)計(jì)思路：數(shù)組存儲(chǔ)(順序存儲(chǔ))+順序查找數(shù)據(jù)對(duì)象： ？無序整數(shù)序列問題：有無更好的方法？4程序設(shè)計(jì)：對(duì)特定算法的計(jì)算機(jī)實(shí)現(xiàn)算 法：處理問題的策略,對(duì)特定問題求解步驟的

2、一種描述數(shù)據(jù)結(jié)構(gòu)：編程語言：程序的實(shí)現(xiàn)方式問題的數(shù)學(xué)模型,數(shù)據(jù)的表示方式Niklaus Wirth Algorithm+Data Structures Programming 5例2 求最近點(diǎn)問題（Neareset Neighbour）67例3 人機(jī)對(duì)奕問題Tree.8算 法： ？對(duì)奕的規(guī)則和策略數(shù)據(jù)對(duì)象： ？格局和格局間的關(guān)系9例4 多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECEDGraph10算 法： ？對(duì)圖中頂點(diǎn)的染色問題數(shù)據(jù)對(duì)象： ？通路和通路間的關(guān)系11 數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)據(jù)對(duì)象(非數(shù)值計(jì)算）在計(jì)算機(jī)中的表示及其上操作的實(shí)現(xiàn)。概括地說，1

3、22. 基本概念和術(shù)語（1）數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：所有能被輸入到計(jì)算機(jī)中，且被計(jì)算 機(jī)處理的符號(hào)的集合，計(jì)算機(jī)操作對(duì)象的總稱。 是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。13 數(shù)據(jù)元素： 數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。14數(shù)據(jù)項(xiàng)：數(shù)據(jù)結(jié)構(gòu)中討論的最小單位 數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合例如：圖書館中的書（數(shù)據(jù)元素）書名作者號(hào)分類號(hào)出版社出版時(shí)間數(shù)據(jù)結(jié)構(gòu)003TP311.13清華大學(xué)出版社199715數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。例如，一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示。(3214,6587,9345)-a1(3214),a2(6587),a3(9345)在a1、

4、a2和a3之間存在“次序”關(guān)系、3214,6587,9345a1 a2 a36587,3214,9345a2 a1 a3、16數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。 若這種關(guān)系描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。17數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：樹形結(jié)構(gòu)線性結(jié)構(gòu)圖狀結(jié)構(gòu) 集合結(jié)構(gòu)18數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)-邏輯結(jié)構(gòu)在存儲(chǔ)器中的表示（映象）例如，一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示。(3214,6587,9345)-a1(3214),a2(6587),a3(9345)L

5、INT=D, SD=a1, a2, a3S=, 19數(shù)據(jù)元素的表示方法(無需討論) 用二進(jìn)制（bit）的位串表示數(shù)據(jù)元素 (321)10=(501)8=(101000001)2 A=(101)8=(001000001)2數(shù)據(jù)元素也稱為元素或結(jié)點(diǎn)。 20關(guān)系的表示方法（表示的方法） 順序存儲(chǔ)結(jié)構(gòu)(Arrays) 以存儲(chǔ)位置的相鄰表示后繼關(guān)系。y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C。 而C是一個(gè)隱含值，因此，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。xy 優(yōu)點(diǎn)：存儲(chǔ)密度高;隨機(jī)存取。缺點(diǎn)：連續(xù)分配,需預(yù)先分配最大空間;插入元素?;刪除元素?21元素n.元素i.元素2元素1LoLo+cLo+(i-1

6、)*cLo+（n-1)*c存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+(i-1)*c22 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(Linked Lists) 以附加信息（指針）表示后繼。需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置。y x結(jié)點(diǎn)X的數(shù)據(jù)域結(jié)點(diǎn)X的指針域 缺點(diǎn)：存儲(chǔ)密度高;順序存取。優(yōu)點(diǎn)：離散分配,無需預(yù)先分配最大空間;插入元素?;刪除元素?231536元素21400元素11346元素3 元素41345h存儲(chǔ)地址 存儲(chǔ)內(nèi)容 指針 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346h數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)（數(shù)組存儲(chǔ)）：把邏輯上相鄰的結(jié)

7、點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。索引存儲(chǔ)結(jié)構(gòu)：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。散列存儲(chǔ)結(jié)構(gòu)：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。25 當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。本書用C語言描述。怎樣描述存儲(chǔ)結(jié)構(gòu)？26（2）數(shù)據(jù)類型 在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。 數(shù)據(jù)類型是一個(gè)對(duì)象集合和一組定義在這些對(duì)象上操作的總稱。數(shù)據(jù)類型C

8、語言中，提供int, char, float, double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型。28 （3）抽象數(shù)據(jù)類型（Abstract Data Type簡稱ADT）(1.4 Data Abstraction) 是一個(gè)數(shù)據(jù)類型,其數(shù)據(jù)對(duì)象和對(duì)象上的操作的規(guī)格說明獨(dú)立于對(duì)象的存儲(chǔ)表示和對(duì)象上操作的實(shí)現(xiàn).怎樣描述邏輯結(jié)構(gòu)？29抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D,S,P)三元組表示其中，D是數(shù)據(jù)元素集， S是D上的關(guān)系集， P是對(duì)D的基本操作集。30structure 抽象數(shù)據(jù)類型名 is

9、 objects ： functions ： end 抽象數(shù)據(jù)類型名 其中：數(shù)據(jù)對(duì)象的定義用偽碼描述，基本操作的定義格式為 基本操作名(參數(shù)表):= if (初始條件) return 操作結(jié)果; else return 錯(cuò)誤;31“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則省略之?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。32Structure LINT is Objects: a1, a2, a3, a1 表示高位，a2表示中間位數(shù)，a3表示低位,三者均為整數(shù). Functions: 對(duì)所有

10、x,y LINT; TRUE, FALSE Boolean且其中+,-,和 = 是通常所用的整數(shù)操作. LINT Zero() := 0 Boolean IsZero(x) := if (x = 0) return FALSE Else return TRUE LINT Add(x,y) := if (x+y)=INT_MAX) return x +y; Else return INT_MAX. LINT Subtraction(x,y) := return x y; LINT Multiply(x, y) := return x * y; LINT Mod(x, y) := return x

11、 mod y;End LINTADT LINT33Structure NaturalNumber is Objects: 整數(shù)的有序子序列,該子序列從0開始,到計(jì)算機(jī)上的最大整數(shù)(INT_MAX)結(jié)束. Functions: 對(duì)所有x,y NaturalNumber; TRUE, FALSE Boolean且其中+,-,和 = 是通常所用的整數(shù)操作. NaturalNumber Zero() := 0 Boolean IsZero(x) := if (x) return FALSE Else return TRUE NaturalNumber Add(x,y) := if (x+y)=INT_

12、MAX) return x +y Else return INT_MAX Boolean Equal(x,y) := if (x=y) return TRUE Else return FALSE; NaturalNumber Successor(x) := if (x = INT_MAX) return x Else return x+1; NaturalNumber Substract(x,y) := if (x y) return 0; Else return x y; End NaturalNumberADT NaturalNumber 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)操作：查找、排序、插入、刪除、修改等 線性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線性表(List)棧(Stack)隊(duì)(Queue)樹形結(jié)構(gòu)(Tree)圖狀結(jié)構(gòu)(Graph)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 散列存儲(chǔ) 索引存儲(chǔ)集合結(jié)構(gòu)353. 數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)結(jié)構(gòu)-橫向基本概念：數(shù)據(jù)結(jié)構(gòu)和算法-Chapter 1線性結(jié)構(gòu)-Chapter 2,3,4 線性表（List）：多項(xiàng)式、稀疏矩陣 棧和隊(duì)列樹型結(jié)構(gòu)-Chapter 5樹二叉樹森林圖狀結(jié)構(gòu)-Chapter 6無向圖與無向網(wǎng)有向圖與有向網(wǎng)集合結(jié)構(gòu)-Chapter 7和8 用以上三者結(jié)構(gòu)表示，內(nèi)容貫穿其中。Hashing單獨(dú)取