《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》PPT課件.ppt

《《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》PPT課件.ppt（62頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）,任課教師：馮 向陽(yáng),教學(xué)計(jì)劃安排,開(kāi)課周次：1-16周 周一：5、6節(jié)，松1318 周四：1、2節(jié)，松1318 上機(jī)實(shí)踐： 周四：1、2節(jié) (第3周16周) 158 期終考試形式： 閉卷考試,教學(xué)計(jì)劃安排,本課程的內(nèi)容及學(xué)習(xí)的基本方法,本課程講述的主要內(nèi)容： 將分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、數(shù)組、樹(shù)型結(jié)構(gòu)、圖結(jié)構(gòu)、查找、排序等內(nèi)容。 學(xué)習(xí)本課程的基本方法： 上課認(rèn)真聽(tīng)講。 仔細(xì)閱讀教材及課件的講授內(nèi)容，體會(huì)并靈活掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念和知識(shí)點(diǎn)。 仔細(xì)閱讀教材及課件中的大量例題，多做算法練習(xí)。,本課程成績(jī)計(jì)算,平時(shí)成績(jī)占10% 上機(jī)實(shí)踐實(shí)驗(yàn)占20% 期終考

2、試占70% E-mail地址： 網(wǎng)絡(luò)硬盤URL：http:/,第1章 緒論,學(xué)習(xí)要點(diǎn) 熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。 了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。 熟悉類C語(yǔ)言的書(shū)寫規(guī)范、表示和實(shí)現(xiàn)方法。 理解算法五個(gè)要素的確切含義和對(duì)算法正確性的理解。 掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。,數(shù)據(jù)結(jié)構(gòu)的發(fā)展史,數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國(guó)外是從1968年才開(kāi)始設(shè)立的。 1968年美國(guó)唐歐克努特教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計(jì)算機(jī)程序設(shè)計(jì)技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯

3、結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。 隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，數(shù)據(jù)結(jié)構(gòu)廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域。 編譯程序利用堆棧、符號(hào)表和語(yǔ)法分析樹(shù)； 操作系統(tǒng)由過(guò)程并列表和文件支持，并利用由可用空間的并列表或表格組成的存儲(chǔ)管理模式； 人工智能程序利用堆棧、隊(duì)列、集、搜索樹(shù)、表格和圖； 數(shù)據(jù)庫(kù)利用串、并列表、樹(shù)、環(huán)和表格。,數(shù)據(jù)結(jié)構(gòu)討論的范疇,數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。它主要研究計(jì)算機(jī)加工對(duì)象的邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的表示形式以及實(shí)現(xiàn)各種基本操作的算法。它是學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)原理等計(jì)算機(jī)專業(yè)核心課程的基礎(chǔ)。掌握好這門課程的內(nèi)容，是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的必備條件。 Nika

4、laus Wirth (Pascal語(yǔ)言之父) Algorithm + Data Structures = Programs,問(wèn)題求解,程序編寫,數(shù)據(jù)結(jié)構(gòu),程序設(shè)計(jì),算法,數(shù)據(jù)結(jié)構(gòu)討論的范疇,數(shù)據(jù)處理的種類,數(shù)值數(shù)據(jù),非數(shù)值數(shù)據(jù),數(shù)值 (整數(shù),實(shí)數(shù)) 字符 字符串 文字 圖形 圖象 聲音,數(shù)值性計(jì)算,數(shù)值性計(jì)算： 數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型通常可以用一組線性或非線性的代數(shù)方程組或微分方程組來(lái)描述。 即使是不需要用計(jì)算機(jī)求解的簡(jiǎn)單問(wèn)題也需要一個(gè)數(shù)學(xué)模型來(lái)描述。 雞兔同籠問(wèn)題：二元一次方程組 房屋設(shè)計(jì)或橋梁設(shè)計(jì)中的結(jié)構(gòu)應(yīng)力分析：線性代數(shù)方程組 天氣預(yù)報(bào)：環(huán)流模式方程,數(shù)值性計(jì)算,例 已知：游泳池的長(zhǎng)l

5、en和寬wide，求面積area,(2)設(shè)計(jì) 求解問(wèn)題的方法 (3)編程 main ( ) int len, wide ,area ; scanf (“%d %d%n”, ,(1)建模型： 問(wèn)題涉及的對(duì)象：游泳池的長(zhǎng)len，寬wide，面積area； 對(duì)象之間的關(guān)系：area = len wide,非數(shù)值性計(jì)算,非數(shù)值性計(jì)算： 當(dāng)操作對(duì)象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理，就需要對(duì)之進(jìn)行非數(shù)值性處理。 當(dāng)計(jì)算機(jī)進(jìn)入非數(shù)值計(jì)算領(lǐng)域，特別是用在管理上的時(shí)候，計(jì)算機(jī)的操作對(duì)象之間的關(guān)系就無(wú)法用數(shù)學(xué)方程加以描述了。 應(yīng)用舉例1 學(xué)籍檔案管理 假

6、設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下頁(yè)的表1-1所示的學(xué)生信息。,表1-1 學(xué)生基本情況,非數(shù)值性計(jì)算(舉例1),非數(shù)值性計(jì)算(舉例1),特點(diǎn)： 每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格。 表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說(shuō)的線性結(jié)構(gòu)。 對(duì)它的操作通常是插入某個(gè)學(xué)生的信息，刪除某個(gè)學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。,非數(shù)值性計(jì)算(舉例2),1,12,21,123,132,312,213,231,321,3個(gè)對(duì)象的全排列過(guò)程,應(yīng)用舉例2：輸出n個(gè)對(duì)象的全排列 可以使用下頁(yè)所示的圖示描述。,非數(shù)值性計(jì)算(舉例2),

7、特點(diǎn)： 在求解過(guò)程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這就是我們所說(shuō)的樹(shù)形結(jié)構(gòu)。 對(duì)它的操作有：建立樹(shù)形結(jié)構(gòu)，輸出最底層結(jié)點(diǎn)內(nèi)容等等。 應(yīng)用舉例3 制定教學(xué)計(jì)劃 在制定教學(xué)計(jì)劃時(shí)，需要考慮各門課程的開(kāi)設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開(kāi)設(shè)情況如下頁(yè)的表1-2所示。,非數(shù)值性計(jì)算(舉例3),表1-2 計(jì)算機(jī)專業(yè)學(xué)生的必修課程,非數(shù)值性計(jì)算(舉例3),C4,C5,C2,C1,C9,C3,C7,C10,C11,C6,C8,C12,圖1-2 課程先后關(guān)系的圖形描述形式,非數(shù)值性計(jì)算(舉例3),特點(diǎn)： 課程之間的先后關(guān)系用圖結(jié)構(gòu)描述。

8、通過(guò)實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。 結(jié)論： 以上所舉例子中的數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問(wèn)題。因此，簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)是一門討論描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算) 及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)的學(xué)科。,基本概念和術(shù)語(yǔ)(數(shù)據(jù)),數(shù)據(jù)(data) 數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中，其含義是指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)集合。 例如，一個(gè)個(gè)人書(shū)庫(kù)管理程序所要處理的數(shù)據(jù)可能是下表所示的表格。,基本概念和術(shù)語(yǔ)(數(shù)據(jù)元素),數(shù)據(jù)元素(data element) 數(shù)據(jù)元素也稱為結(jié)點(diǎn)，是數(shù)據(jù)集合中的一個(gè)實(shí)體，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。 數(shù)據(jù)元素

9、按其組成可分為簡(jiǎn)單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。前者由一個(gè)數(shù)據(jù)項(xiàng)組成；后者由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念的多方面信息。,基本概念和術(shù)語(yǔ)(數(shù)據(jù)項(xiàng)),數(shù)據(jù)項(xiàng)(data item) 一般情況下，一個(gè)數(shù)據(jù)元素中含有若干個(gè)字段，也稱為數(shù)據(jù)項(xiàng)。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。 數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。,數(shù)據(jù)項(xiàng)之間的關(guān)系,數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在次序關(guān)系 例如，一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)來(lái)表示。 3214,6587,9345 = a1(3214),a2(6587),a3(9345) 在a1、a2和a3之間存在次序關(guān)系：、 3214,6587,9345 6587,3214,9345

10、 a1 a2 a3 a2 a1 a3,數(shù)據(jù)項(xiàng)之間的關(guān)系(續(xù)),數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在次序關(guān)系 又例，2行3列的二維數(shù)組a1,a2,a3,a4,a5,a6 行的次序關(guān)系: row = , , , 列的次序關(guān)系: col = , , ,基本概念和術(shù)語(yǔ)(數(shù)據(jù)結(jié)構(gòu)),數(shù)據(jù)結(jié)構(gòu)(data structure) 數(shù)據(jù)結(jié)構(gòu)是以數(shù)據(jù)項(xiàng)為元素的一種結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)的組成是由各數(shù)據(jù)項(xiàng)之間的關(guān)系和用來(lái)存儲(chǔ)、恢復(fù)這些數(shù)據(jù)項(xiàng)的存取函數(shù)來(lái)確定的。 為了敘述上的方便和避免產(chǎn)生混淆，通常把數(shù)據(jù)的邏輯結(jié)構(gòu)(logic structure)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)(storage structure)。,數(shù)

11、據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)(logic structure) 數(shù)據(jù)元素和數(shù)據(jù)元素之間的邏輯關(guān)系成為數(shù)據(jù)的邏輯結(jié)構(gòu)。 如下的表格數(shù)據(jù)中，各數(shù)據(jù)元素之間在邏輯上有一種線性關(guān)系。,數(shù)據(jù)的邏輯結(jié)構(gòu)的分類,數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類： 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。 樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。 圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合的關(guān)系外，別無(wú)其他關(guān)系。,數(shù)據(jù)的邏輯結(jié)構(gòu)的分類(續(xù)),數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類： 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 圖狀結(jié)構(gòu) 集合結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的形式定義,數(shù)據(jù)結(jié)構(gòu)的形式定義

12、為： 數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組： Data_Structure = (D,S) 其中: D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。 嚴(yán)格地講，以上定義僅是數(shù)據(jù)的邏輯結(jié)構(gòu)的定義。 例如，在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可看成一種數(shù)據(jù)結(jié)構(gòu) Complex = (C,R) 其中，C是含兩個(gè)實(shí)數(shù)的集合c1,c2；R = P，而P 是定義在集合C上的一種關(guān)系，其中有序偶表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部。,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storage structure) 是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)器中的具體實(shí)現(xiàn)。 與孤立的數(shù)據(jù)元素的表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(nèi)容，還要表示清楚數(shù)據(jù)

13、元素之間的邏輯關(guān)系。 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序映像和非順序映像，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(續(xù)),順序存儲(chǔ)結(jié)構(gòu)： 特點(diǎn)是借助于數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 特點(diǎn)是借助于指示數(shù)據(jù)元素地址的指針來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。 在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。 用高級(jí)語(yǔ)言程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通常可用該語(yǔ)言提供的數(shù)據(jù)類型來(lái)描述。,數(shù)據(jù)類型,數(shù)據(jù)類型： 是指程序設(shè)計(jì)語(yǔ)言中各變量可取的數(shù)據(jù)類型。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語(yǔ)言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。 一

14、方面，在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。 另一方面，在程序設(shè)計(jì)過(guò)程中，當(dāng)需要引入某種新的數(shù)據(jù)類型時(shí)，總是借助編程語(yǔ)言所提供的數(shù)據(jù)類型來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。,C+的基本數(shù)據(jù)類型及取值的范圍,抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型(Abstract Data Type 簡(jiǎn)稱ADT)： ADT是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 ADT的兩個(gè)重要特征： 數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口(即外界使用它

15、的方法)。 數(shù)據(jù)封裝：將實(shí)體的外部特征和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱蔽其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。 ADT需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。,抽象數(shù)據(jù)類型的格式定義,ADT的格式定義： 和數(shù)據(jù)結(jié)構(gòu)的形式定義相對(duì)應(yīng)，ADT可用一個(gè)三元組表示： ADT_Data_Structure = (D,S,P) 其中: D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。 ADT可用以下格式來(lái)定義： ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： ADT抽象數(shù)據(jù)類型名,抽象數(shù)據(jù)類型(舉例),例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義： ADT Complex 數(shù)據(jù)對(duì)象：D = e1,e

16、2 | e1,e2 RealSet 數(shù)據(jù)關(guān)系：R1 = | e1是復(fù)數(shù)的實(shí)數(shù)部分， | e2是復(fù)數(shù)的虛數(shù)部分 基本操作： InitComplex( &Z,v1,v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù)Z，其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。 DestroyComplex( &Z ) 操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &RealPart) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用RealPart返回復(fù)數(shù)Z的實(shí)部值。 GetImag( Z, &ImagePart) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用ImagePart返回復(fù)數(shù)Z的虛部值。 Add( z1,z2,&sum) 初始條件：z1,z

17、2是復(fù)數(shù)。 操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。 ADT Complex,抽象數(shù)據(jù)類型(舉例),其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為： 基本操作名 (參數(shù)表) 初始條件： 操作結(jié)果： 基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。 初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則省略之。 操作結(jié)果說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。,算法和算法設(shè)計(jì)的過(guò)程,算法(algorithm)： 算法是解決某個(gè)特定問(wèn)題的一種方

18、法或一個(gè)過(guò)程。 計(jì)算機(jī)對(duì)數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。 設(shè)計(jì)算法的基本過(guò)程： 通過(guò)對(duì)問(wèn)題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型。 確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法。 選用某種語(yǔ)言將算法轉(zhuǎn)換成程序。 調(diào)試并運(yùn)行這些程序。,算法的特征,算法應(yīng)該具有下列五個(gè)特性： 有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。 確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。 可行性：算法中描述的每一步操作都可以通過(guò)已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。 輸入：一個(gè)算

19、法應(yīng)該有零個(gè)或多個(gè)輸入。 輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說(shuō)的輸出是指與輸入有某種特定關(guān)系的量。,算法(舉例),舉例： 問(wèn)題：按從大到小的順序重新排列x,y,z三個(gè)數(shù)值的內(nèi)容。 算法： 輸入x,y,z三個(gè)數(shù)值； 從三個(gè)數(shù)值中挑選出最小者并換到x中； 從y,z中挑選出最小者并換到y(tǒng)中； 輸出排序后的結(jié)果。,選擇算法描述語(yǔ)言的原則,選擇算法描述語(yǔ)言的原則： 該語(yǔ)言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能； 該語(yǔ)言應(yīng)該盡可能地簡(jiǎn)捷，以便于掌握、理解； 使用該語(yǔ)言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計(jì)語(yǔ)言。 類C描述語(yǔ)言是通過(guò)對(duì)C語(yǔ)言進(jìn)行精心篩選保留的一個(gè)核心子集，并為了便于描述，又

20、做了若干擴(kuò)展修改，從而增強(qiáng)了語(yǔ)言的描述功能。 以下對(duì)其作簡(jiǎn)要說(shuō)明。,算法描述語(yǔ)言(續(xù)),預(yù)定義常量及類型： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。 typedef char ElemType,算法描述語(yǔ)言(續(xù)),算法描述為以下的函數(shù)類型： 函數(shù)類型 函數(shù)名 (函數(shù)參數(shù)表) 語(yǔ)句序列； 為了簡(jiǎn)化函數(shù)的書(shū)寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說(shuō)明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可

21、以不做變量說(shuō)明，必要時(shí)給出相應(yīng)的注釋即可。另外，在書(shū)寫算法時(shí)，應(yīng)該養(yǎng)成對(duì)重點(diǎn)語(yǔ)句段落添加注解的良好習(xí)慣。,算法描述語(yǔ)言(續(xù)),在算法描述中可以使用的賦值語(yǔ)句形式有： 簡(jiǎn)單賦值 變量名 = 表達(dá)式； 串聯(lián)賦值 變量名1 = 變量名2 = = 變量名n = 表達(dá)式； 成組賦值 (變量名1，變量名n) = (表達(dá)式1， ，表達(dá)式n)； 結(jié)構(gòu)賦值 結(jié)構(gòu)名1 = 結(jié)構(gòu)名2； 結(jié)構(gòu)名 = (值1，值2，值n)； 條件賦值 變量名 = 條件表達(dá)式?表達(dá)式1：表達(dá)式2； 交換賦值 變量名1 變量名2；,算法描述語(yǔ)言(續(xù)),在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有： 條件語(yǔ)句1 if (表達(dá)式) 語(yǔ)句； 條件語(yǔ)

22、句2 if (表達(dá)式) 語(yǔ)句； else 語(yǔ)句； 開(kāi)關(guān)語(yǔ)句1 switch (表達(dá)式) case 值1：語(yǔ)句序列1；break; case 值n：語(yǔ)句序列n；break； default： 語(yǔ)句序列n+1; ,算法描述語(yǔ)言(續(xù)),在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有： 開(kāi)關(guān)語(yǔ)句2 switch (表達(dá)式) case 條件1：語(yǔ)句序列1；break; case條件n：語(yǔ)句序列n；break； default： 語(yǔ)句序列n+1; ,算法描述語(yǔ)言(續(xù)),在算法描述中可以使用的循環(huán)結(jié)構(gòu)語(yǔ)句形式有： for 循環(huán)語(yǔ)句 for (表達(dá)式1；循環(huán)條件表達(dá)式；表達(dá)式2) 語(yǔ)句； while 循環(huán)語(yǔ)句 wh

23、ile (循環(huán)條件表達(dá)式) 語(yǔ)句； do-while 循環(huán)語(yǔ)句 do 語(yǔ)句序列； while (循環(huán)條件表達(dá)式)；,算法描述語(yǔ)言(續(xù)),在算法描述中可以使用的結(jié)束語(yǔ)句形式有： 函數(shù)結(jié)束語(yǔ)句 return 表達(dá)式； return; case或循環(huán)結(jié)束語(yǔ)句 break； 異常結(jié)束語(yǔ)句 exit (異常代碼)； 在算法描述中可以使用的輸入輸出語(yǔ)句形式有： 輸入語(yǔ)句 scanf (格式串，表達(dá)式1，表達(dá)式n)； 輸出語(yǔ)句 printf (格式串，表達(dá)式1，表達(dá)式n)； 方括號(hào)()中的內(nèi)容是可以省略的部分。,算法描述語(yǔ)言(續(xù)),在算法描述中使用的注釋格式有： 單行注釋 / 文字序列 在算法描述中可以使用

24、的擴(kuò)展函數(shù)有： 求最大值 max (表達(dá)式1，表達(dá)式n)； 這個(gè)函數(shù)返回參數(shù)表中n個(gè)表達(dá)式計(jì)算結(jié)果中的最大值。 求最小值 min (表達(dá)式1，表達(dá)式n)； 這個(gè)函數(shù)返回參數(shù)表中n個(gè)表達(dá)式計(jì)算結(jié)果中的最小值。,算法描述語(yǔ)言(舉例),【算法1-1】用類C描述將三個(gè)數(shù)值排序的算法： void Three_Sort (int *x, int *y, int *z) / 將x,y,z三個(gè)指針?biāo)甘镜膬?nèi)容按從大到小的順序重新排列 if( *y *x & *y *z ) *x *y； / 挑選出最小的數(shù)值并換到x指針?biāo)傅拇鎯?chǔ)單元中 else if( *z *x & *z *y ) *x *z ； if(

25、*z *y ) *y *z； / 在y和z所指示的存儲(chǔ)單元中挑選出較小者換到y(tǒng)中 ,算法設(shè)計(jì)的原則,算法設(shè)計(jì)的原則： 正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。 可讀性；算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。 健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。 時(shí)間與空間效率：算法的時(shí)間與空間效率是指將算法交換為程序后，

26、該程序在計(jì)算機(jī)上運(yùn)行時(shí)所花費(fèi)的時(shí)間及所占據(jù)空間的度量。,算法正確性的理解,對(duì)算法是否正確的理解可以有以下四個(gè)層次： 程序中不含語(yǔ)法錯(cuò)誤； 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。 通常以第3層的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。,算法的時(shí)間效率,算法的時(shí)間效率主要由兩個(gè)因素組成： 所需處理問(wèn)題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費(fèi)的時(shí)間就多； 在解決問(wèn)題的過(guò)程中，基本操作的執(zhí)行次數(shù)。 通常有兩種衡量算法效率的方法： 事后統(tǒng)計(jì)法 有兩個(gè)缺陷 必須執(zhí)行程序； 其他因

27、素掩蓋算法本質(zhì)。 事前分析估算法 和算法執(zhí)行時(shí)間相關(guān)的因素： 算法選用的策略； 問(wèn)題的規(guī)模； 編寫程序的語(yǔ)言； 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量； 計(jì)算機(jī)執(zhí)行指令的速度。,算法的時(shí)間復(fù)雜度,時(shí)間復(fù)雜度 一般情況下，可以將一個(gè)算法所花費(fèi)的時(shí)間設(shè)計(jì)成一個(gè)以數(shù)據(jù)量n為自變量的函數(shù)T(n)=O(f(n)。 這個(gè)函數(shù)在正整數(shù)定義域范圍內(nèi)一定是單調(diào)遞增的。它表示隨數(shù)據(jù)量n的增大，算法執(zhí)行時(shí)間函數(shù)T(n)的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同。稱函數(shù)T(n)為算法的(漸進(jìn))時(shí)間復(fù)雜度。,算法的時(shí)間復(fù)雜度,大O記法： 這種描述中使用的基本參數(shù)是n，即問(wèn)題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。 這里的O表示量級(jí)

28、(order)。例如，二分檢索是O(logn)的，就是說(shuō)它需要通過(guò)logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組。 記法O(f(n)表示：當(dāng)n增大時(shí)，運(yùn)行時(shí)間至多將以正比于f(n)的速度增長(zhǎng)。 從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量標(biāo)準(zhǔn)。 算法的執(zhí)行時(shí)間 = 原操作(i)的執(zhí)行次數(shù) 原操作(i)的執(zhí)行時(shí)間,算法的時(shí)間復(fù)雜度(舉例1),例一：在下列程序段中 for( i = 1; i = n; +i ) for( j = 1; j = n; +j ) ci,j = 0; for( k = 1; k = n; +k ) ci,j

29、 += ai,k * bk,j; 基本操作：乘法操作 時(shí)間復(fù)雜度：O(n3),算法的時(shí)間復(fù)雜度(舉例2),例二：在下列程序段中 Void select_sort( int a, int n ) / 將a中的整數(shù)序列重新排列成自小至大的順序 for( i = 0; i n 1; + i ) j = i; for( k = i +1; k n; +k ) if( ak aj ) j = k; if( j != i ) aj ai; 基本操作：比較(數(shù)據(jù)元素)操作 時(shí)間復(fù)雜度：O(n2),算法的時(shí)間復(fù)雜度(舉例3),例三：在下列程序段中 i = 1; while( i = n ) i = i * 5

30、; 基本操作：乘法操作 假設(shè)基本操作的執(zhí)行次數(shù)為y，則： 5y = n，y取最大值時(shí)，5y = n 即 基本操作的最多執(zhí)行次數(shù)為 y = log5n 時(shí)間復(fù)雜度：O(log5n),算法的空間復(fù)雜度,空間復(fù)雜度 類似于算法的時(shí)間復(fù)雜度，算法的存儲(chǔ)空間的需求可以設(shè)計(jì)成一個(gè)以問(wèn)題的規(guī)模n為自變量的函數(shù)S(n)=O(g(n)。 這個(gè)函數(shù)表示隨問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率和函數(shù)g(n)的增長(zhǎng)率相同。稱函數(shù)S(n)為算法的空間復(fù)雜度。 算法的存儲(chǔ)量包括： 輸入數(shù)據(jù)所占空間； 程序本身所占空間； 輔助變量所占空間。,算法的空間復(fù)雜度(續(xù)),空間復(fù)雜度 輔助空間就是除算法代碼本身和輸入輸出數(shù)據(jù)

31、所占據(jù)的空間外，算法臨時(shí)開(kāi)辟的存儲(chǔ)空間單元。 若輸入數(shù)據(jù)所空間只取決于問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的額外空間。 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。 若所需存儲(chǔ)量依賴于特定的輸入，除特別指明外，通常按最壞的情況考慮。,第1章 基本知識(shí)結(jié)構(gòu)圖,緒 論,數(shù)據(jù)結(jié)構(gòu)概念的引出,基本概念和術(shù)語(yǔ),抽象數(shù)據(jù)類型,算法和算法分析,數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)對(duì)象,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)類型,存儲(chǔ)結(jié)構(gòu),抽象數(shù)據(jù)類型的定義,抽象數(shù)據(jù)類型的表示,抽象數(shù)據(jù)類型的實(shí)現(xiàn),算法設(shè)計(jì)的要求,算法設(shè)計(jì)的度量,算法存儲(chǔ)空間的需求,課后作業(yè),1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？ 2.簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。 3.分析下面各程序段的時(shí)間復(fù)雜度。,2. s=0; for (i=0; in; i+) for(j=0; jn; j+) s+=Bij; sum=s;,1. for (i=0; in; i+) for (j=0; jm; j+) Aij=0;,x=0; for(i=1; in; i+) for (j=1; j=n-i; j+) x+;,4. i=1; while(i=n) i=i*3;,