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

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