




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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ú)取
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 人才入職合同范例范例
- 中止合同范例
- 個(gè)人銷售手機(jī)合同范例
- 青少年中華民族共同體意識(shí)與主觀幸福感的關(guān)系
- 基于深度學(xué)習(xí)的電機(jī)故障特征分析及診斷
- 買房帶續(xù)租合同范例
- 借用機(jī)械設(shè)備合同范例
- 資源受限環(huán)境下金融領(lǐng)域命名實(shí)體識(shí)別的研究
- 入股驛站合同范例
- 冷庫股合同范例
- 牛津深圳版初中英語中考英語詞匯匯總(七至九年級(jí))
- 【高中語文】《李憑箜篌引》(同步課件)+高二語文+(統(tǒng)編版選擇性必修中冊(cè))
- 人衛(wèi)版急診與災(zāi)難醫(yī)學(xué)之呼吸困難教學(xué)課件
- 骨質(zhì)疏松的中醫(yī)治療
- 中醫(yī)科運(yùn)用PDCA循環(huán)縮短出院患者離院時(shí)間品管圈QCC持續(xù)質(zhì)量改進(jìn)成果匯報(bào)
- 老年人的溝通交流護(hù)理課件
- SEER數(shù)據(jù)庫的申請(qǐng)及數(shù)據(jù)提取方法與流程
- 2022礦產(chǎn)地質(zhì)勘查規(guī)范鹽類第2部分:現(xiàn)代鹽湖鹽類
- 自然環(huán)境及特征(考向3:自然環(huán)境的地域差異(雪線、林線)) 【知識(shí)精講精研】 高考地理二輪核心考點(diǎn)突破課堂
- GB/T 43200-2023機(jī)器人一體化關(guān)節(jié)性能及試驗(yàn)方法
- 紅樓夢(mèng)第二回極好課件
評(píng)論
0/150
提交評(píng)論