數(shù)據(jù)結(jié)構(gòu)第一章概論.ppt

1,數(shù)據(jù)結(jié)構(gòu),C語(yǔ)言版,2, 教材 數(shù)據(jù)結(jié)構(gòu) （ C語(yǔ)言版） 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社, 參考教材 1 數(shù)據(jù)結(jié)構(gòu) （ C語(yǔ)言版） 劉清 王瓊 電子工業(yè)出版社 2 數(shù)據(jù)結(jié)構(gòu)題集 （ C語(yǔ)言版） 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社,3,教學(xué)內(nèi)容（總學(xué)時(shí)64, 其中有12學(xué)時(shí)實(shí)驗(yàn)） 第一章 緒論 （6學(xué)時(shí)） 第二章 線性表 （8學(xué)時(shí)） 第三章 棧和隊(duì)列 （8學(xué)時(shí)） 第六章 樹 （10學(xué)時(shí)） 第七章 圖 （8學(xué)時(shí)） 第九章 查找 （4學(xué)時(shí)） 第十章 排序（6學(xué)時(shí)） 總復(fù)習(xí) （2學(xué)時(shí)） 共計(jì)52學(xué)時(shí),考核 平時(shí)成績(jī)10%實(shí)驗(yàn)20%考試成績(jī)70%,4,課程特點(diǎn)及教學(xué)方法,難度大 綜合性強(qiáng) 必須要有C語(yǔ)言基礎(chǔ) 關(guān)于教學(xué)的幾個(gè)新觀念 教學(xué)過(guò)程以學(xué)生為主體, 教師為主導(dǎo) 學(xué)生由知識(shí)技能的被動(dòng)接受者向知識(shí)技能的主動(dòng)探求者轉(zhuǎn)變,。教學(xué)目標(biāo)為使學(xué)生在知識(shí)、能力、素質(zhì)方面協(xié)調(diào)發(fā)展 能力包括自學(xué)能力、知識(shí)運(yùn)用能力、動(dòng)手能力、創(chuàng)新能力、發(fā)現(xiàn)問(wèn)題能力、分析問(wèn)題和解決問(wèn)題能力以及可持續(xù)發(fā)展能力,5,1.1 本課研究的問(wèn)題 1.2 什么是數(shù)據(jù)結(jié)構(gòu) 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 1.4 數(shù)據(jù)結(jié)構(gòu)的分類與表示 1.5 算法與算法分析,第一章 緒 論,6,計(jì)算機(jī)的發(fā)展 軟件 硬件 應(yīng)用領(lǐng)域,數(shù)據(jù)處理的種類和能力, 數(shù)據(jù),數(shù)值數(shù)據(jù),非數(shù)值數(shù)據(jù),數(shù) (整數(shù),實(shí)數(shù)) 字符 字符串 文字 圖形 圖象 聲音,數(shù)據(jù)：客觀對(duì)象的符號(hào)表示 數(shù)學(xué)中的整數(shù)、實(shí)數(shù)， 課程名，地名、書名,1.1 本課程研究的問(wèn)題,1.1 本課程研究的問(wèn)題,7, 數(shù)值問(wèn)題與非數(shù)值問(wèn)題,1）數(shù)值問(wèn)題 已知：游泳池的長(zhǎng)len和寬wide，求面積area,設(shè)計(jì) 求解問(wèn)題的方法 編程, 建模型： 問(wèn)題涉及的對(duì)象：游泳池的長(zhǎng)len 寬wide，面積area； 對(duì)象之間的關(guān)系：area=lenwide,1.1 本課程研究的問(wèn)題,main ( ) int len, wide ,area ; scanf (“%d %d%n”, ,8,在這類文檔管理的數(shù)學(xué)模型中, 計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系 , 這類數(shù)學(xué)模型稱為線性模型,1.1 本課程研究的問(wèn)題,9,1.1 本課程研究的問(wèn)題,迷宮問(wèn)題： 在迷宮中，每走到一處，接下來(lái)可走的通路有三條。計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過(guò)程中所有可能的通路都畫出，則可得一棵“樹”,10,數(shù)據(jù)結(jié)構(gòu)的研究問(wèn)題： 非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系， 及如何表示，如何存儲(chǔ)，如何處理。 本課程討論的問(wèn)題： 應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系， 及如何表示,如何存儲(chǔ)，如何處理。,1.1 本課程研究的問(wèn)題,11,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,1.2 什么是數(shù)據(jù)結(jié)構(gòu),1.2 什么是數(shù)據(jù)結(jié)構(gòu),整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,計(jì)算機(jī)管理圖書問(wèn)題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的、有按分類編排 如何將查詢圖書的這些信息存入計(jì)算機(jī)中 既要考慮查詢時(shí)間短，又要考慮節(jié)省空間,最簡(jiǎn)單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,數(shù)據(jù)元素在 計(jì)算機(jī)中的表示,如何將0,1,2,3,4,5,6,7,8,9這10個(gè)數(shù)存放在 計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲(chǔ)方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行 操作處理 (插入、刪除、修改、查找、排序),程序算法數(shù)據(jù)結(jié)構(gòu),12,13 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念,1.3 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念,數(shù)據(jù)（data)所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)。例如：學(xué)號(hào)，姓名，班名都是數(shù)據(jù)。 數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record） 。 數(shù)據(jù)項(xiàng)（data item）有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field) 數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。例如: 所有班名相同的記錄集合,13,對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問(wèn)題： 1） 數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作； 2） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；,數(shù)據(jù)的邏輯結(jié)構(gòu)： 數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。,數(shù)據(jù)結(jié)構(gòu)的基本操作： 指對(duì)數(shù)據(jù)結(jié)構(gòu)的加工處理,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) (物理結(jié)構(gòu))： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示,數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)： 基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法),13 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念,14,某班學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào) 姓名 專業(yè) 政治 面貌 ，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。,學(xué)號(hào) 姓名 專業(yè) 政治面藐 001 王洪 計(jì)算機(jī) 黨員 002 孫文 計(jì)算機(jī) 團(tuán)員 003 謝軍 計(jì)算機(jī) 團(tuán)員 004 李輝 計(jì)算機(jī) 團(tuán)員 005 沈祥福 計(jì)算機(jī) 黨員 006 余斌 計(jì)算機(jī) 團(tuán)員 007 鞏力 計(jì)算機(jī) 團(tuán)員 008 孔令輝 計(jì)算機(jī) 團(tuán)員,學(xué)生基本情況登記表的圖示,學(xué)生間學(xué)號(hào)順序關(guān)系 是一種線性結(jié)構(gòu)關(guān)系,一 常用的數(shù)據(jù)結(jié)構(gòu),1） 集合 2） 線性結(jié)構(gòu) 3） 樹結(jié)構(gòu) 4） 圖結(jié)構(gòu) 5）其它復(fù)雜結(jié)構(gòu),例,1.4 數(shù)據(jù)結(jié)構(gòu)的分類與表示,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,15,家族的族譜 假設(shè)某家族有10個(gè)成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關(guān)系可以用如下圖表示。,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,例,16,多叉路口交通燈管理問(wèn)題,例,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,17,數(shù)據(jù)結(jié)構(gòu)的表示,1、圖示表示 圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù) ，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；,學(xué)生基本情況表的圖示表示,家族樹的圖示表示,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,18,學(xué)生基本情況表的二元組表示（D，S）,2、二元組表示 二元組表示是用一個(gè)二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)， 其中 D 是數(shù)據(jù)元素集合，S 是 D 上關(guān)系的集合。,D = 001，002，003，004，005，006，007，008 S = R R= , , ,家族樹的二元組表示（D，S）,D = A，B，C，D，E，F(xiàn)，G，H，I，J S = R R = A,B, ,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,19,1、數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,(亦稱物理結(jié)構(gòu)),14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,20,數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn),數(shù)據(jù)結(jié)構(gòu)側(cè)重于解決問(wèn)題的策略和方法，即研究算法。 它不但要求給出問(wèn)題的一種算法，還要求算法的時(shí)空效率高、算法結(jié)構(gòu)和可讀性好、容易驗(yàn)證等等。,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,21,3、抽象數(shù)據(jù)結(jié)構(gòu)描述：,有限個(gè)數(shù)據(jù) 元素的集合,是D上 關(guān)系的有限集,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,有限個(gè)節(jié)點(diǎn)間 關(guān)系的集合,Group=（D , S , R）,ADT（Abstract Data Type），即抽象數(shù)據(jù)類型，是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作（運(yùn)算）。ADT只考慮數(shù)據(jù)的邏輯結(jié)構(gòu),22,ADT的定義可以用一個(gè)三元組表示。其中D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，R是對(duì)D的基本操作集。可以采用以下格式定義ADT： ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： ADT 抽象數(shù)據(jù)類型名 其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義可以用形式化偽碼描述，基本操作的定義格式為： 基本操作名（參數(shù)表） 初始條件： 操作結(jié)果：,23,ADT的定義與數(shù)據(jù)結(jié)構(gòu)的定義有著明顯的差別，它將基本操作與數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系在形式上封裝在一起，并以此來(lái)建模。大多數(shù)的抽象數(shù)據(jù)類型是由用戶自行設(shè)計(jì)和實(shí)現(xiàn)的。,例: 用ADT表示復(fù)數(shù)Complex。,ADT Complex 數(shù)據(jù)對(duì)象：D= ，R 數(shù)據(jù)關(guān)系： e1是實(shí)數(shù)，e是虛數(shù) 基本操作：主要加、減、乘、除等操作,24,GetReal(z) 初始條件：復(fù)數(shù)z已經(jīng)存在。 操作結(jié)果：返回復(fù)數(shù)z的實(shí)部值。,GetImage (z) 初始條件：復(fù)數(shù)z已經(jīng)存在。 操作結(jié)果：返回復(fù)數(shù)z的虛部值。,Add(z1, z2) 初始條件：z1,z2均為復(fù)數(shù)。 操作結(jié)果：返回復(fù)數(shù)z1和z2的和,Minus (z1, z2) 初始條件：z1,z2均為復(fù)數(shù)。 操作結(jié)果：返回復(fù)數(shù)z1減z2的差 。,Multiply (z1, z2) 初始條件：z1,z2均為復(fù)數(shù)。 操作結(jié)果：返回復(fù)數(shù)z1和z2的積,Multiply (z1, z2) 初始條件：z1,z2均為復(fù)數(shù)。 操作結(jié)果：返回復(fù)數(shù)z1除以z2的商,InitComplex(&z, v1,v2) 初始條件：無(wú)。 操作結(jié)果：構(gòu)造復(fù)數(shù)z，其實(shí)部和虛部分別賦以參數(shù)v1和v2的值, ADT Complex,25,例： 采用前面定義的抽象數(shù)據(jù)類型Complex所提供的各種操作函數(shù)，編制一個(gè)算法（C語(yǔ)言），用以計(jì)算復(fù)數(shù)： z=（(8-6i)(4+3i)）/（2+6i）-(3+3i)的值。,分析：為簡(jiǎn)單起見，不妨假定ADT Complex中的所有操作函數(shù)已經(jīng)實(shí)現(xiàn)，只要遵守ADT Complex中的約定即可。,26,算法： Complex z1, z2, z3, z4, z5;設(shè)置參數(shù) InitComplex( ,抽象數(shù)據(jù)類型需要用具體的數(shù)據(jù)類型來(lái)實(shí)現(xiàn)。采用什么樣的數(shù)據(jù)結(jié)構(gòu)表示數(shù)學(xué)模型，要服從于方便有效地實(shí)現(xiàn)該抽象數(shù)據(jù)類型上定義的大多數(shù)操作。,27,1.5 算法與算法分析,一 、算法的概念 算法 ：是解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列,算法的描述：采用C語(yǔ)言描述,15 算法與算法分析,算法的基本特征： 1）輸入：0個(gè)或多個(gè)輸入； 2）輸出：1個(gè)或多個(gè)輸出； 3）有窮性：算法必須在有限步內(nèi)結(jié)束； 4）確定性：組成算法的操作必須清晰無(wú)二義性。 5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。,28,算法的評(píng)價(jià)衡量算法優(yōu)劣的標(biāo)準(zhǔn) 正確性(correctness)：不含語(yǔ)法錯(cuò)誤 可讀性(readability)：便于維護(hù) 健壯性(robustness)：見錯(cuò)性好 效率與低存儲(chǔ)量,算法效率用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí) 行所消耗的時(shí)間來(lái)度量,29,例,試編寫算法：輸入一個(gè)正整數(shù)，并判斷是否為素?cái)?shù),一般使用結(jié)構(gòu)化程序設(shè)計(jì)方法解決問(wèn)題。常用的是逐步求精和分而治之的設(shè)計(jì)方法，用來(lái)開發(fā)軟件系統(tǒng)。一般情況下，采用分而治之將問(wèn)題逐步化小，直到達(dá)到人們能夠理解的程度，再用逐步求精找出算法，因而多把它們結(jié)合使用。,1、逐步求精方法把程序設(shè)計(jì)分為二步：第一步，只考慮“做什么”，即對(duì)問(wèn)題進(jìn)行分析，給出解決問(wèn)題的思路；第二步，再考慮“如何去做”，給出具體代碼。,30,2、分而治之的方法： 1)把問(wèn)題分成兩個(gè)或多個(gè)更小的問(wèn)題； 2)分別解決每個(gè)小問(wèn)題； 3)把各小問(wèn)題的解答組合起來(lái)，即可得到原問(wèn)題的解答。小問(wèn)題通常與原問(wèn)題相似，可以遞歸地使用分而治之策略來(lái)解決。,31,算法：int input(） /判斷X是否為素?cái)?shù)/ flog=1; i=2; while ( i= X-1 ) and ( flog=1 ) if ( X % i = =0) flog=0; i+; return ( flog ),本題用逐步求精方法完成： 1、第一步：分析所提出的問(wèn)題，設(shè)計(jì)程序的結(jié)構(gòu) 2、第二步：對(duì) “素?cái)?shù)”進(jìn)一步求精，設(shè)置一個(gè)標(biāo)志參數(shù)flog 3、第三步：對(duì) “x 是一個(gè)素?cái)?shù)”進(jìn)一步求精，根據(jù)素?cái)?shù)定義用i2,.,X，除以X，flog=0表示能除盡，為1則不能 4、第四步: 對(duì)“x不能被j整除”進(jìn)一步求精，根據(jù)flog的值，判斷X是否為素?cái)?shù),32,15 算法與算法分析,C語(yǔ)言程序： Main（） int x, flog, i; flog=1; scanf( “%d”, x ); for ( i =2, i=x-1, i+ ) if ( x % i = =0 ) flog=0 ,break if ( flog ) printf (“是一個(gè)素?cái)?shù)”) else printf (“非素?cái)?shù)”） ,33,例,試給你一個(gè)裝有16個(gè)硬幣的袋子。16個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你完成這一任務(wù)，提供一架天平用于找出偽幣。,第一種方法：逐步求精方法；兩個(gè)進(jìn)行比較，找 出較輕者，最多需要8次比較。,第二種方法：分而治之方 ；把16硬幣看成一個(gè)大 的問(wèn)題。,34,16,8輕,4輕,2輕,35,15 算法與算法分析,二、算法時(shí)間復(fù)雜度T（n） 本課程采用以求解問(wèn)題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。,算法的時(shí)間復(fù)雜度 一般來(lái)說(shuō)，設(shè)算法中基本操作的執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間復(fù)雜度記作： T(n) = O(f(n) 語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱為語(yǔ)句的頻度,36,一個(gè)算法的時(shí)間復(fù)雜度（Time Complexity，簡(jiǎn)稱為時(shí)間復(fù)雜性）T(n)是該算法的時(shí)間耗費(fèi)，是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。,例,求兩個(gè) n 階矩陣的乘法CAB的算法，寫出算法中帶標(biāo)號(hào)語(yǔ)句的頻度，并求該算法的時(shí)間復(fù)雜度,37,15 算法與算法分析,For ( i = 1; i=n; i+ ) (1) For (j = 1; j=n; j+ ) (2) x=0; (3) For (k = 1; k= n; k+ ) (4) c i j += a i k * b k j ; (5) c i j = x; (6) ,該算法主體是一個(gè)三重循環(huán)，先以標(biāo)號(hào)（2）的語(yǔ)句說(shuō)明其頻度：對(duì)于固定的i、j從1變到n,指令j+需執(zhí)行n+1步，而相對(duì)于外循環(huán)(1),i從1變到超過(guò)n，內(nèi)循環(huán)重復(fù)n次，故(2)的執(zhí)行頻度為n(n+1),(1) n+1,(2) n(n+1),(3) n2,(4) n2(n+1),(5) n3,(6) n2,標(biāo)號(hào)語(yǔ)句的頻度分別為：,算法時(shí)間復(fù)雜度為所有語(yǔ)句的頻度之和： T(n) = n+1+n(n+1)+n2+n2(n+1)+n3+n2 =2 n3 +4 n2 +2n+1 O(n3),38,15 算法與算法分析,有些算法，基本操作執(zhí)行次數(shù)與問(wèn)題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮 （1） 算法平均時(shí)間復(fù)雜度 （2） 算法在最壞情況下的時(shí)間復(fù)雜度,例,指出下列算法的時(shí)間復(fù)雜度： Void prume(int n) int i=2; While( ( x % i) ,39,算法:是一個(gè)有窮規(guī)則的集合，其中之規(guī)則確定了一個(gè)解決某一特定類型問(wèn)題的運(yùn)算序列。 算法具有五個(gè)特點(diǎn)：有窮性、確定性、輸入、輸出和能行性。 算法的正確性判定是:一個(gè)比較復(fù)雜的問(wèn)題，對(duì)于簡(jiǎn)單的算法，可以采用窮舉法或程序正確性證明等方法來(lái)確定算法的正確性；而對(duì)于復(fù)雜的算法，人們不可能采用窮舉法或程序正確性證明來(lái)驗(yàn)證算法的正確性，只能說(shuō)明算法在給定的測(cè)試下沒(méi)有錯(cuò)誤發(fā)生，而不能說(shuō)明算法是正確的。,40,算法分析: 評(píng)價(jià)一個(gè)算法的好壞主要是從算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度兩個(gè)方面來(lái)考察。 算法的時(shí)間復(fù)雜度和空間復(fù)雜度是兩個(gè)相互矛盾的性能指標(biāo)，一個(gè)算法要么其所占存儲(chǔ)空間較小，要么其運(yùn)行時(shí)間較短，兩者性能均好的算法往往難以找到。,41,本章節(jié)的重點(diǎn) 1數(shù)據(jù)結(jié)構(gòu)及其表示。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，數(shù)據(jù)呈現(xiàn)給用戶是其邏輯結(jié)構(gòu)，其物理存儲(chǔ)對(duì)用戶是透明的。為了有效地處理數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)必須給出數(shù)據(jù)集上操作的統(tǒng)一接口，而不管其存儲(chǔ)結(jié)構(gòu)。 2ADT是一種描述數(shù)據(jù)結(jié)構(gòu)的常用工具，它能很好地描述數(shù)據(jù)的邏輯結(jié)構(gòu)和其上的操作。在用ADT描述數(shù)據(jù)結(jié)構(gòu)時(shí)，可以不考慮其存儲(chǔ)結(jié)構(gòu)。,42,3結(jié)構(gòu)化程序設(shè)計(jì)方法是一種典型的程序設(shè)計(jì)方 法。由于結(jié)構(gòu)化程序設(shè)計(jì)方法將問(wèn)題劃分成一個(gè)個(gè)的相互獨(dú)立又相互聯(lián)系的子問(wèn)題，解決子問(wèn)題相對(duì)容易，而且子問(wèn)題的正確性也易于保證，因此結(jié)構(gòu)化程序設(shè)計(jì)方法是數(shù)據(jù)結(jié)構(gòu)中采用的一種典型設(shè)計(jì)方法。 4算法。算法是實(shí)現(xiàn)結(jié)構(gòu)化程序設(shè)計(jì)方法的基礎(chǔ)，一個(gè)子問(wèn)題可以用一個(gè)算法來(lái)實(shí)現(xiàn)，將各個(gè)子問(wèn)題的算法有機(jī)地結(jié)合起來(lái)就構(gòu)成了整個(gè)問(wèn)題的實(shí)現(xiàn)算法。,43,例,設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為： D（K R） K（K1，K2，K3，K9） RK1，K3， K1，K8， K2，K3， K2，K4， K2，K5， K3，K9 ，K5，K6 K8，K9 ，K9，K7 ，K4，K7 ，K4，K6 畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？,開始結(jié)點(diǎn)：是指無(wú)前趨的結(jié)點(diǎn)，,終端結(jié)點(diǎn)：是指無(wú)后續(xù)的結(jié)點(diǎn)，,只有K1和K2。,只有K6和K7。,14 數(shù)據(jù)結(jié)構(gòu)的分類與表示,44,已知m，n均為正整數(shù)，試用ADT描述求m和n的最小公倍數(shù)的算法。,例,算法的步驟如下： （1）計(jì)算r(m*n)； （2）若m等于n，則輸出最小公倍數(shù)r/m，算法結(jié)束； （3）若m大于n，計(jì)算m(m-n；否則計(jì)算n(n-m； （4）轉(zhuǎn)（2）。,分析：題設(shè)雖只要描述其求兩個(gè)正整數(shù)的最小公倍數(shù)，為了ADT描述的方便，我們可以針對(duì)整個(gè)正整數(shù)集來(lái)討論。 ADT是一種描述數(shù)據(jù)結(jié)構(gòu)的常用工具，針對(duì)具體問(wèn)題，只要按照ADT的描述規(guī)范實(shí)現(xiàn)就可以了。,45,下面是其ADT描述： ADT Positive_Int 數(shù)據(jù)對(duì)象：Dx | x是正整數(shù) 基本操作： LCM(x1, x2) 初始條件：要求x1和x2都是正整數(shù)。 操作結(jié)果：返回x1和x2的最小公倍數(shù)。 ADT Positive_Int;,46,基本操作LCM的C語(yǔ)言形式的具體實(shí)現(xiàn)為： int LCM( int x1, int x2 ) /* 求正整數(shù)x1和x2的最小公倍數(shù) */ int r = x1 * x2; /* 存放x1和x2的積 */ if( x1 x2 ) x1 = x1 x2; else x2 = x2 x1; return r / x1; /* 返回正整數(shù)x1和x2的最小公倍數(shù) */ ,47,作 業(yè) 1、寫出下題算法，并求出其時(shí)間復(fù)雜度。(C語(yǔ)言） 100元買100支筆, 其中鋼筆 3元/支, 圓珠筆 2元/支, 鉛筆 0.5元/支，用C語(yǔ)言編程輸出可能的各種組合方案。 2、有一個(gè)老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。假設(shè)有一架天平，請(qǐng)你設(shè)計(jì)一個(gè)算法用最少的比較次數(shù)找出最輕和最重的金塊。,48,算法的時(shí)間復(fù)雜度為O (N3),49,# define N 100 Void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=(N-3*i)/2; j+) if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d, %d, %dn%”, i, j, N-i-j); 時(shí)間復(fù)雜度為O(N2 ),解法2,50,線性結(jié)構(gòu),A , B , C , ，X ,Y , Z,學(xué) 生 成 績(jī) 表,線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié),A1， A2 Ai-1， Ai， Ai+1， An,A