第1章緒論 數(shù)據(jù)結(jié)構(gòu)與算法Java版

1、第一章第一章 緒論緒論 第一章第一章 緒緒 論論 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 1.3 算法與算法分析算法與算法分析 1.4 Java提供的泛型方法提供的泛型方法 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 第一章第一章 緒緒 論論 重點(diǎn)：重點(diǎn)： u數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語(yǔ) u算法及算法的分析方法算法及算法的分析方法 難點(diǎn)：難點(diǎn)： u時(shí)間復(fù)雜度的估算時(shí)間復(fù)雜度的估算 第一章第一章 緒緒 論論 課前思考課前思考 你過(guò)去是否聽(tīng)說(shuō)過(guò)你過(guò)去是否聽(tīng)說(shuō)過(guò)“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”？ 你知道數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論什么內(nèi)你知道數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論什么內(nèi) 容的學(xué)科嗎？容的學(xué)

2、科嗎？ 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 Niklaus Wirth： （著名的瑞士科學(xué)家沃思教授） Algorithm + Data Structures = Programs ( 算算 法法 + 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) = 程程 序序 ） 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 算算 法法: 程程 序序: : 為計(jì)算機(jī)處理問(wèn)題而編 制的一組指令集 處理問(wèn)題的策略 （是對(duì)數(shù)據(jù)運(yùn)算的描述，是程序的邏輯抽象） 問(wèn)題的數(shù)學(xué)模型，它反 映數(shù)據(jù)及其之間關(guān)系。 （存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)） 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 問(wèn)題求解的主要步驟：?jiǎn)栴}求解的主要步驟： 1. 1.確定求解問(wèn)題的

3、確定求解問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)模型； 2. 2.確定確定存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)； 3. 3.設(shè)計(jì)設(shè)計(jì)算法算法； 4. 4.編程編程并測(cè)試結(jié)果。并測(cè)試結(jié)果。 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 程序設(shè)計(jì)的實(shí)質(zhì)程序設(shè)計(jì)的實(shí)質(zhì)是在于解決兩是在于解決兩 個(gè)主要問(wèn)題：個(gè)主要問(wèn)題：一是一是根據(jù)實(shí)際問(wèn)題選根據(jù)實(shí)際問(wèn)題選 擇一種好的數(shù)據(jù)結(jié)構(gòu)；擇一種好的數(shù)據(jù)結(jié)構(gòu)；二是二是設(shè)計(jì)一設(shè)計(jì)一 個(gè)好的算法，而好的算法在很大程個(gè)好的算法，而好的算法在很大程 度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié) 構(gòu)。構(gòu)。 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例1 1】N個(gè)數(shù)的選擇問(wèn)題個(gè)數(shù)

4、的選擇問(wèn)題 算法：算法：? ? 模型：模型：? ? 如何選擇？如何選擇？ N個(gè)數(shù)在計(jì)算機(jī)中的組織個(gè)數(shù)在計(jì)算機(jī)中的組織 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例2 2】生產(chǎn)訂單的自動(dòng)查詢問(wèn)題生產(chǎn)訂單的自動(dòng)查詢問(wèn)題 算法：算法：? ? 模型：模型：? ? 如何查詢？如何查詢？ 生產(chǎn)訂單數(shù)據(jù)在計(jì)算機(jī)生產(chǎn)訂單數(shù)據(jù)在計(jì)算機(jī) 中的組織中的組織 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例3 3】城市網(wǎng)絡(luò)的鋪設(shè)問(wèn)題城市網(wǎng)絡(luò)的鋪設(shè)問(wèn)題 算法：算法：? ? 模型：模型：? ? 如何為城市的各小區(qū)之如何為城市的各小區(qū)之 間鋪設(shè)網(wǎng)絡(luò)線路間鋪設(shè)網(wǎng)絡(luò)線路,使投資使投資 最小最小?(對(duì)

5、對(duì) n 個(gè)小區(qū)只需鋪個(gè)小區(qū)只需鋪 設(shè)設(shè) n-1 條線路條線路) 圖的最小生成樹(shù)圖的最小生成樹(shù) 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 方面 過(guò)程 數(shù)據(jù)表示數(shù)據(jù)處理 抽象邏輯結(jié)構(gòu)基本運(yùn)算 實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)算法 評(píng)價(jià) 不同數(shù)據(jù)結(jié)構(gòu)的比較和算 法性能分析 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系: : 簡(jiǎn)單地說(shuō)簡(jiǎn)單地說(shuō), , 本課程研究的內(nèi)容包括以下三方面：本課程研究的內(nèi)容包括以下三方面： 1. 1. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 2. 2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)/ /物理結(jié)構(gòu)物理結(jié)構(gòu) 3. 3. 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) l數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)

6、與數(shù)據(jù)結(jié)構(gòu) l數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型 l抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 所有能所有能被輸入被輸入到計(jì)算機(jī)中，且能被計(jì)算到計(jì)算機(jī)中，且能被計(jì)算 機(jī)機(jī)處理處理的的符號(hào)的總稱符號(hào)的總稱。如：實(shí)數(shù)、整數(shù)、。如：實(shí)數(shù)、整數(shù)、 字符（串）、圖形和聲音等。字符（串）、圖形和聲音等。 數(shù)據(jù)數(shù)據(jù)(Data):(Data): 是是計(jì)算機(jī)操作對(duì)象計(jì)算機(jī)操作對(duì)象的集合。的集合。 是計(jì)算機(jī)處理的是計(jì)算機(jī)處理的信息的信息的某種特定的符某種特定的符 號(hào)號(hào)表示形式表示形式。 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 是數(shù)據(jù)（集合）中的一個(gè)是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體個(gè)體” 數(shù)據(jù)元素（數(shù)據(jù)元素（Data

7、Element):Data Element): 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位基本單位 不同場(chǎng)合也叫不同場(chǎng)合也叫結(jié)點(diǎn)、頂點(diǎn)、記錄結(jié)點(diǎn)、頂點(diǎn)、記錄 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 數(shù)據(jù)項(xiàng)（數(shù)據(jù)項(xiàng)（Data ItemData Item） ： 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的最小最小單位單位 數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成 例如：例如： 描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素 稱之為稱之為組合項(xiàng)組合項(xiàng), ,其它為其它為簡(jiǎn)單項(xiàng)簡(jiǎn)單項(xiàng) 年月日 姓名 俱樂(lè)部名稱 出生日期 參加日期 職務(wù)業(yè)績(jī) 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 數(shù)據(jù)對(duì)象（數(shù)據(jù)對(duì)

8、象（Data ObjectData Object） ： 是性質(zhì)相同的數(shù)據(jù)元素的集合是性質(zhì)相同的數(shù)據(jù)元素的集合 例如：例如：學(xué)生成績(jī)表是一個(gè)數(shù)據(jù)對(duì)象學(xué)生成績(jī)表是一個(gè)數(shù)據(jù)對(duì)象 學(xué)號(hào)姓名數(shù)學(xué)分析 普通物理高等代數(shù) 20001 20002 20003 20004 20005 張三 李四 丁一 馬二 王五 90 80 67 98 56 56 87 67 90 87 89 67 87 67 68 數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象中的數(shù)據(jù)元素不會(huì)是孤立的不會(huì)是孤立的， 而是彼此相關(guān)的而是彼此相關(guān)的，這種彼此之間的關(guān)系稱為，這種彼此之間的關(guān)系稱為 “結(jié)構(gòu)結(jié)構(gòu)”, ,如書(shū)中表如書(shū)中表1.11.1、圖圖1.2(a)1

9、.2(a)、圖、圖 1.3 1.3 都形成了其特定的結(jié)構(gòu)。都形成了其特定的結(jié)構(gòu)。 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data StructureData Structure） ： 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)操作數(shù)據(jù)操作 線性線性結(jié)構(gòu)結(jié)構(gòu) (1:1(1:1的關(guān)系的關(guān)系) ) 樹(shù)形樹(shù)形結(jié)構(gòu)結(jié)構(gòu) (1:n(1:n的關(guān)系的關(guān)系) ) 圖狀圖狀結(jié)構(gòu)結(jié)構(gòu) (m:n(m:n的關(guān)系的關(guān)系) ) 集合集合結(jié)構(gòu)結(jié)構(gòu) ( (松散關(guān)系松散關(guān)系) ) 順序順序存儲(chǔ)存儲(chǔ) 鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)存儲(chǔ) 索引索引存儲(chǔ)存儲(chǔ) 散列散列存儲(chǔ)存儲(chǔ) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素

10、的集是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集 合合 : :創(chuàng)建、銷(xiāo)毀、插入、刪除、修改等創(chuàng)建、銷(xiāo)毀、插入、刪除、修改等 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 邏輯結(jié)構(gòu)可用二元組形式定義為邏輯結(jié)構(gòu)可用二元組形式定義為: : Data_Structures = (D, R) 其中其中: : D 是數(shù)據(jù)元素的有限集，是數(shù)據(jù)元素的有限集， R是是 D上關(guān)系的有限集。上關(guān)系的有限集。 也可用數(shù)據(jù)的也可用數(shù)據(jù)的邏輯結(jié)構(gòu)圖邏輯結(jié)構(gòu)圖來(lái)形象表示之。來(lái)形象表示之。 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 【例例1 1】設(shè)有數(shù)據(jù)結(jié)構(gòu)為：設(shè)有數(shù)據(jù)結(jié)構(gòu)為： B=（D，R），其中：），其中： D=k1,k2,k3,.k

11、9 R=, , 畫(huà)出其邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系畫(huà)出其邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些，哪些 結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)？結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)？ k2 k1 k4 k5 k3 k8 k6 k9 k7 開(kāi)始結(jié)點(diǎn)為開(kāi)始結(jié)點(diǎn)為k1,k2(無(wú)前驅(qū)的結(jié)點(diǎn)）無(wú)前驅(qū)的結(jié)點(diǎn)） 終端結(jié)點(diǎn)為終端結(jié)點(diǎn)為k6,k7(無(wú)后繼的結(jié)點(diǎn)）無(wú)后繼的結(jié)點(diǎn)） 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 【例例2 2】矩陣矩陣 中中9 9個(gè)元素之間存在個(gè)元素之間存在 兩種關(guān)系，一種是行關(guān)系，一種是列關(guān)系，兩種關(guān)系，一種是行關(guān)系，一種是列關(guān)系，試試 給出其邏輯結(jié)構(gòu)的二元組表示形式。給出其邏輯結(jié)構(gòu)的二元組表示形式。

12、 987 654 321 aaa aaa aaa ， ， ， 其邏輯結(jié)構(gòu)的二元組表示形式為：其邏輯結(jié)構(gòu)的二元組表示形式為： B= B=（D D，R R），其中：，其中： D=a1,a2,a9 R=ROW,COL ROW= , COL= , 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 其實(shí)數(shù)據(jù)類(lèi)型反映三個(gè)方面的內(nèi)容：其實(shí)數(shù)據(jù)類(lèi)型反映三個(gè)方面的內(nèi)容： 存儲(chǔ)結(jié)構(gòu)，取值范圍和允許進(jìn)行的操作。存儲(chǔ)結(jié)構(gòu)，取值范圍和允許進(jìn)行的操作。 在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中， 每個(gè)數(shù)據(jù)都應(yīng)有一個(gè)每個(gè)數(shù)據(jù)都應(yīng)有一個(gè)所屬的、確定的數(shù)所屬的、確定的數(shù) 據(jù)類(lèi)型。據(jù)類(lèi)型。 1.2 基本概念與術(shù)語(yǔ)基本概念與

13、術(shù)語(yǔ) 在在JavaJava語(yǔ)言中，語(yǔ)言中，簡(jiǎn)單數(shù)據(jù)簡(jiǎn)單數(shù)據(jù)可描述為可描述為 JavaJava內(nèi)置的內(nèi)置的8 8種種基本的數(shù)據(jù)類(lèi)型基本的數(shù)據(jù)類(lèi)型之一；而之一；而 對(duì)于對(duì)于復(fù)雜數(shù)據(jù)復(fù)雜數(shù)據(jù)則可通過(guò)則可通過(guò)類(lèi)的聲明類(lèi)的聲明來(lái)引入來(lái)引入 新的數(shù)據(jù)類(lèi)型。其中類(lèi)的對(duì)象新的數(shù)據(jù)類(lèi)型。其中類(lèi)的對(duì)象(object)(object) 是新的類(lèi)型的實(shí)例，類(lèi)的成員變量確定是新的類(lèi)型的實(shí)例，類(lèi)的成員變量確定 了新的數(shù)據(jù)類(lèi)型的數(shù)據(jù)表示方法和存儲(chǔ)了新的數(shù)據(jù)類(lèi)型的數(shù)據(jù)表示方法和存儲(chǔ) 結(jié)構(gòu)，類(lèi)的構(gòu)造函數(shù)和成員函數(shù)確定了結(jié)構(gòu)，類(lèi)的構(gòu)造函數(shù)和成員函數(shù)確定了 新的數(shù)據(jù)類(lèi)型的操作。新的數(shù)據(jù)類(lèi)型的操作。 可用可用JavaJava語(yǔ)言中的

14、語(yǔ)言中的“數(shù)組數(shù)組”類(lèi)型來(lái)類(lèi)型來(lái) 實(shí)現(xiàn)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)，用，用JavaJava語(yǔ)言中提供語(yǔ)言中提供 的的“對(duì)象引用對(duì)象引用”來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 例如：學(xué)生成績(jī)表基于數(shù)組的順序例如：學(xué)生成績(jī)表基于數(shù)組的順序 存儲(chǔ)結(jié)構(gòu)可描述如下：存儲(chǔ)結(jié)構(gòu)可描述如下： - -學(xué)生成績(jī)記錄的類(lèi)描述學(xué)生成績(jī)記錄的類(lèi)描述 package ch01; public class ResultsRecord private String studentNum; / 學(xué)號(hào)學(xué)號(hào) private String studentName; / 學(xué)生姓名學(xué)生姓名 pri

15、vate float mathScore; / 數(shù)學(xué)分析數(shù)學(xué)分析 private float physicalScore; / 普通物理普通物理 private float algebraScore; / 普通物理普通物理 public String getStudentNum() return studentNum; public void setStudentNum(String studentNum) this.studentNum=studentNum; 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) - -基于數(shù)組的順序存儲(chǔ)的類(lèi)描述基于數(shù)組的順序存儲(chǔ)的類(lèi)描述 package ch01; pub

16、lic class SqResults private ResultsRecord listElem； /存放學(xué)生成績(jī)的存儲(chǔ)空間存放學(xué)生成績(jī)的存儲(chǔ)空間 private int cluLen; / 當(dāng)前學(xué)生成績(jī)表的長(zhǎng)度當(dāng)前學(xué)生成績(jī)表的長(zhǎng)度 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) 以后將全部以后將全部采用采用JavaJava接口表示抽象數(shù)接口表示抽象數(shù) 據(jù)類(lèi)型據(jù)類(lèi)型。下面通過(guò)兩個(gè)具體實(shí)例來(lái)說(shuō)明。下面通過(guò)兩個(gè)具體實(shí)例來(lái)說(shuō)明 抽象數(shù)據(jù)類(lèi)型的描述和實(shí)現(xiàn)。抽象數(shù)據(jù)類(lèi)型的描述和實(shí)現(xiàn)。 抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型(Abstract Data Type,(Abstract Data Type, 簡(jiǎn)稱簡(jiǎn)稱ADT)AD

17、T)是指一是指一數(shù)據(jù)值數(shù)據(jù)值的集合和定義在的集合和定義在 這個(gè)集合上的一組這個(gè)集合上的一組操作操作。它不包括數(shù)據(jù)。它不包括數(shù)據(jù) 的計(jì)算機(jī)存儲(chǔ)表示，而且這里的操作是的計(jì)算機(jī)存儲(chǔ)表示，而且這里的操作是 脫離了具體實(shí)現(xiàn)的抽象操作，即不涉及脫離了具體實(shí)現(xiàn)的抽象操作，即不涉及 它的實(shí)現(xiàn)細(xì)節(jié)。它的實(shí)現(xiàn)細(xì)節(jié)。換句話說(shuō)換句話說(shuō)，抽象數(shù)據(jù)類(lèi)，抽象數(shù)據(jù)類(lèi) 型是指隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)并且不涉型是指隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)并且不涉 及操作的實(shí)現(xiàn)細(xì)節(jié)的數(shù)據(jù)類(lèi)型。及操作的實(shí)現(xiàn)細(xì)節(jié)的數(shù)據(jù)類(lèi)型。 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) /復(fù)數(shù)抽象數(shù)據(jù)類(lèi)型的接口表示復(fù)數(shù)抽象數(shù)據(jù)類(lèi)型的接口表示 public interface ICo

18、mplex public double getReal(); / 取實(shí)部取實(shí)部 public void setReal(double real); / 修改實(shí)部修改實(shí)部 public double getImag(); / 取虛部取虛部 public void setImag(double imag); / 修改虛部修改虛部 public void add(IComplex Z); / 兩個(gè)實(shí)數(shù)的求和兩個(gè)實(shí)數(shù)的求和 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) public class Complex implements IComplex private double real; / 實(shí)部實(shí)部 pr

19、ivate double imag; / 虛部虛部 / 構(gòu)造一個(gè)實(shí)數(shù)構(gòu)造一個(gè)實(shí)數(shù) public (double real, double imag) this.real = real; this.imag = imag; / 取實(shí)部取實(shí)部 public double return real; 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) public class Complex implements IComplex / 修改實(shí)部修改實(shí)部 public void (double real) this.real = real; / 取虛部取虛部 public double getImag() retur

20、n imag; / 修改虛部修改虛部 public void (double imag) this.imag = imag; 1.2 基本概念與術(shù)語(yǔ)基本概念與術(shù)語(yǔ) public class Complex implements IComplex / 兩個(gè)實(shí)數(shù)的求和兩個(gè)實(shí)數(shù)的求和 public void (IComplex Z) if (Z != null) real += Z.getReal(); imag += Z.getImag(); 1.3 算法與算法分析算法與算法分析 l算法的基本概念算法的基本概念 l算法的描述算法的描述 l算法分析算法分析 1.3 算法與算法分析算法與算法分析 何謂

21、算法？何謂算法？ 算法算法是是對(duì)特定問(wèn)題求解步驟的一種對(duì)特定問(wèn)題求解步驟的一種 描述，是指令的有限序列。其中每條指描述，是指令的有限序列。其中每條指 令表示一個(gè)或多個(gè)操作令表示一個(gè)或多個(gè)操作。嚴(yán)格來(lái)講，一。嚴(yán)格來(lái)講，一 個(gè)算法一般應(yīng)具有以下個(gè)算法一般應(yīng)具有以下5 5種性質(zhì)：種性質(zhì)： 1 1有窮性有窮性 2 2確定性確定性 3 3有效性有效性 4 4輸入輸入 5 5輸出輸出 1.3 算法與算法分析算法與算法分析 算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)的目標(biāo): : 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下 目標(biāo)：目標(biāo)： 1正確性正確性 2. . 可讀性可讀性 3健壯性健壯性 4高效率高效率（時(shí)

22、間與空間）（時(shí)間與空間） 1.3 算法與算法分析算法與算法分析 本教程描述算法全部采用本教程描述算法全部采用JavaJava程序程序 設(shè)計(jì)語(yǔ)言設(shè)計(jì)語(yǔ)言。 【例例1 1】給出求整型數(shù)組給出求整型數(shù)組a a中最大值的中最大值的 算法算法 。 public static int maxEle(int a) int n=a.length; int max=a0; for (int i=1;in;i+) if (maxai) max=ai; return max; 1.3 算法與算法分析算法與算法分析 【例例2 2】給出將整型數(shù)組給出將整型數(shù)組a中數(shù)據(jù)元素中數(shù)據(jù)元素 實(shí)現(xiàn)就地逆置的算法實(shí)現(xiàn)就地逆置的算法

23、 。 public static void reverse(int a) int n=a.length; int temp; for (int i=0,j=n-1; ij; i+,j-) temp=ai; ai=aj; aj=temp; 1.3 算法與算法分析算法與算法分析 算法分析算法分析算法復(fù)雜度的評(píng)判算法復(fù)雜度的評(píng)判 算法復(fù)雜度算法復(fù)雜度 時(shí)間時(shí)間復(fù)雜度復(fù)雜度 空間空間復(fù)雜度復(fù)雜度 1.3 算法與算法分析算法與算法分析 l時(shí)間復(fù)雜度時(shí)間復(fù)雜度 通常有兩種衡量算法時(shí)間通常有兩種衡量算法時(shí)間( (效率效率) )的方法的方法: : 事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法 事前分析估算法事前分析估算法 缺點(diǎn)：缺點(diǎn)

24、：1 1必須執(zhí)行程序必須執(zhí)行程序 2 2其它因素掩蓋算法本質(zhì)其它因素掩蓋算法本質(zhì) 1.3 算法與算法分析算法與算法分析 和算法執(zhí)行時(shí)間相關(guān)的因素：和算法執(zhí)行時(shí)間相關(guān)的因素： 1 1算法選用的策略算法選用的策略 2 2問(wèn)題的規(guī)模問(wèn)題的規(guī)模 3 3編寫(xiě)程序的語(yǔ)言編寫(xiě)程序的語(yǔ)言 4 4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 5 5計(jì)算機(jī)執(zhí)行指令的硬件速度計(jì)算機(jī)執(zhí)行指令的硬件速度 6 6程序運(yùn)行的軟件環(huán)境程序運(yùn)行的軟件環(huán)境 l時(shí)間復(fù)雜度時(shí)間復(fù)雜度 1.3 算法與算法分析算法與算法分析 一個(gè)特定一個(gè)特定算法的算法的“運(yùn)行工作量運(yùn)行工作量” 的大小，只依賴于的大小，只依賴于問(wèn)題的規(guī)模問(wèn)題

25、的規(guī)模（通常用（通常用 整數(shù)量整數(shù)量n n表示），或者說(shuō)，表示），或者說(shuō)，它是問(wèn)題規(guī)模它是問(wèn)題規(guī)模 的函數(shù)。的函數(shù)。假如，記為假如，記為T(mén) T(n),并將稱并將稱T (n) T (n) 為算法的為算法的時(shí)間復(fù)雜度。時(shí)間復(fù)雜度。 【定義】【定義】 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 T (n) = O(f(n) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)存在正常數(shù)存在正常數(shù)c c和和N N，對(duì)所有的，對(duì)所有的 n(n n(nN)N)滿足滿足0 0T(n) T(n) c cf(n)f(n)。 例如：例如：T(n)=4n3+3n2+2n+1= O(n3)? 其中其中c=10,N=1c=10,N=1 1.3 算法與算法分析算法與

26、算法分析 如何估算如何估算 算法的時(shí)間復(fù)雜度？算法的時(shí)間復(fù)雜度？ 1.3 算法與算法分析算法與算法分析 算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類(lèi)型的操作） 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 = = 原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 1.3 算法與算法分析算法與算法分析 【例例1 1】變量計(jì)量變量計(jì)量 x = 0 ; y = 0 ; s = 0 ; for(k=1;k=n;+k) +x;s+=x; for(i=1;i=n;+i)

27、 for(j=1;j=n;+j) +y;s+=y; 語(yǔ)句頻度語(yǔ)句頻度 n+1 n n+1 n(n+1) n2 T(n)=O(n2) 1.3 算法與算法分析算法與算法分析 【例例2 2】?jī)蓚€(gè)矩陣相乘兩個(gè)矩陣相乘 public static void squareMult (int a, int b, int c, int n) for (int i=0;jn;j+) for (int j=0;jn;j+) cij=0; for (int k=0;kn;k+) cij+=aik*bkj; 語(yǔ)句頻度語(yǔ)句頻度 n n n(n+1)n(n+1) n n2 2 n n2 2(n+1)(n+1) n n3

28、3 T(n)=O(n3) 1.3 算法與算法分析算法與算法分析 從算法中選取一種對(duì)于所研究的從算法中選取一種對(duì)于所研究的 問(wèn)題來(lái)說(shuō)是問(wèn)題來(lái)說(shuō)是 關(guān)鍵操作關(guān)鍵操作 的原操作，以的原操作，以 該關(guān)鍵操作該關(guān)鍵操作 在算法中重復(fù)執(zhí)行的次在算法中重復(fù)執(zhí)行的次 數(shù)（語(yǔ)句頻度）數(shù)（語(yǔ)句頻度） 作為算法運(yùn)行時(shí)間作為算法運(yùn)行時(shí)間 的衡量準(zhǔn)則。的衡量準(zhǔn)則。 1.3 算法與算法分析算法與算法分析 【例例3 3】求下列算法的關(guān)鍵求下列算法的關(guān)鍵操作語(yǔ)句的語(yǔ)句頻操作語(yǔ)句的語(yǔ)句頻 度及算法的時(shí)間復(fù)雜度度及算法的時(shí)間復(fù)雜度 public static myOut() for (i=1; i=n; i=10*i) prin

29、tf(%4d, i); 解：解：設(shè)關(guān)鍵操作語(yǔ)句的語(yǔ)句頻度為設(shè)關(guān)鍵操作語(yǔ)句的語(yǔ)句頻度為f(n), 則有則有10f(n) n,所以所以 f(n) log10n 故故: T(n)=O(log10n) 1.3 算法與算法分析算法與算法分析 有些算法在規(guī)模相同的情況之下，有些算法在規(guī)模相同的情況之下， 其語(yǔ)句頻度會(huì)因輸入的其語(yǔ)句頻度會(huì)因輸入的數(shù)據(jù)值數(shù)據(jù)值或輸入或輸入 的的數(shù)據(jù)順序數(shù)據(jù)順序不同而不同，則時(shí)間復(fù)雜不同而不同，則時(shí)間復(fù)雜 度也會(huì)不同，為此有度也會(huì)不同，為此有最好最好、最壞最壞和和平平 均均時(shí)間復(fù)雜度之分。時(shí)間復(fù)雜度之分。 1.3 算法與算法分析算法與算法分析 【例例4 4】如下算法如下算法實(shí)現(xiàn)

30、的功能是在數(shù)組實(shí)現(xiàn)的功能是在數(shù)組a0:n-1a0:n-1 中查找值為中查找值為x x的數(shù)據(jù)元素。若找到，則返回的數(shù)據(jù)元素。若找到，則返回x x在在 a a中的位置；否則，返回中的位置；否則，返回-1-1。求其時(shí)間復(fù)雜度求其時(shí)間復(fù)雜度。 public static int rSearch(int a,int x) int n=a.length; for(int i=0; ini+); if (i=n) return -1; else return i; 最好最好時(shí)間復(fù)雜度：O(1) 最壞最壞時(shí)間復(fù)雜度：O(n) 平均平均時(shí)間復(fù)雜度：O(n) 1.3 算法與算法分析算法與算法分析 【例例5 5】如

31、下算法是用冒泡排序法對(duì)數(shù)組如下算法是用冒泡排序法對(duì)數(shù)組a a中的中的 n n個(gè)整型數(shù)據(jù)元素進(jìn)行排序，求該算法的時(shí)間個(gè)整型數(shù)據(jù)元素進(jìn)行排序，求該算法的時(shí)間 復(fù)雜度。復(fù)雜度。 public static void bubbleSort(int a, int n) int temp,flag=1; for (int i=1;in i+) flag=0; for (int j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=tmep; 最好最好時(shí)間復(fù)雜度：O(n) 最壞最壞時(shí)間復(fù)雜度：O(n2) 1.3 算法與算法分析算法與算法分析 按增長(zhǎng)率由小至大的順序排列有：按增長(zhǎng)

32、率由小至大的順序排列有： 注意注意 多項(xiàng)式時(shí)間算法多項(xiàng)式時(shí)間算法的時(shí)間復(fù)雜度： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3) 指數(shù)時(shí)間算法指數(shù)時(shí)間算法的時(shí)間復(fù)雜度： O(2n)O(n!)O(nn) 總之，總之，隨著的增大，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)隨著的增大，指數(shù)時(shí)間算法和多項(xiàng)式時(shí) 間算法在所需時(shí)間上間算法在所需時(shí)間上相差非常懸殊相差非常懸殊。 1.3 算法與算法分析算法與算法分析 【問(wèn)題描述問(wèn)題描述】給定一整數(shù)序列給定一整數(shù)序列A A1 1， A A2 2，. A. An n （可能有負(fù)數(shù)），求（可能有負(fù)數(shù)），求A A1 1A An n的一個(gè)子序列的一個(gè)子序列A Ai

33、iA Aj j， 使得使得A Ai i到到A Aj j的和最大。例如：整數(shù)序列的和最大。例如：整數(shù)序列 -2, 11, -2, 11, -4, 13, -5, 2, -5, -3, 12, -9-4, 13, -5, 2, -5, -3, 12, -9的最大子序的最大子序 列的和為列的和為2121（從（從A A2 2到到A A9 9）。）。 下面介紹四種實(shí)現(xiàn)方法下面介紹四種實(shí)現(xiàn)方法 1.3 算法與算法分析算法與算法分析 public static int maxSub_1(int sequence) int max = 0; int n= sequence.length; int sum =

34、0; /第一重循環(huán)執(zhí)行一次則計(jì)算出長(zhǎng)度為第一重循環(huán)執(zhí)行一次則計(jì)算出長(zhǎng)度為i的所有子序列和的最大值的所有子序列和的最大值 for (int i = 1; i = n; i+) for (int j = 0; j n; j+) sum = 0; for (int k = j; k j + i return max; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: O(n3) 1.3 算法與算法分析算法與算法分析 public static int maxSub_2(int sequence) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0;

35、 i n; i+) sum = 0; for (int j = i; j max) max = sum; return max; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: O(n2) 1.3 算法與算法分析算法與算法分析 public static int maxSum(int sequence) if (left=right) if (sequence left0) return sequeneceleft; else return 0; int mid=(left+right)/2; int maxLeftSum=maxSum(sequenece,left,mid); int maxRightSum=max

36、Sum(sequenece,mid+1,right); int maxLeftBorderSum=0,leftBorderSum=0; for(int i=mid; i=left; i-) leftBorderSum+= sequence i; if(leftBorderSummaxLeftBorderSum) maxLeftBorderSum=leftBorderSum; 1.3 算法與算法分析算法與算法分析 public static int maxSum(int sequence) int maxRightBorderSum=0,rightBorderSum=0; for(int i=m

37、id+1; imaxRightBorderSum) maxRightBorderSum=rightBorderSum; return max3(maxLeftSum,maxRightSum, maxLeftBorderSum+maxRightBorderSum); 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: O(nlog2n) 1.3 算法與算法分析算法與算法分析 public static int max3( int a,int b,int c) int max=ab:a?b; max=maxc:max?c; retrun max; public static int maxSub_3( int sequenc

38、e) return maxSum(a,0, sequence.length-1); 1.3 算法與算法分析算法與算法分析 public static int maxSub_4(int sequence) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i max) max = sum; else if (sum 0) sum = 0; return max; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: O(n) 1.4 Java提供的泛型方法提供的泛型方法 若若除去除去數(shù)據(jù)對(duì)象的基本數(shù)據(jù)對(duì)象的基本類(lèi)型外類(lèi)型外，實(shí)現(xiàn)，實(shí)現(xiàn) 方法相同方法相同的，則可用泛型方法來(lái)描述這的，則可用泛型方法來(lái)描述這 種基本功能。種基本功能。 1.1.使用使用ObjectObject表示