算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1、湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院1、理解算法的基本概念及特性、理解算法的基本概念及特性2、掌握算法的三大結(jié)構(gòu)并了解其描述方法、掌握算法的三大結(jié)構(gòu)并了解其描述方法 3、結(jié)合實(shí)例理解算法設(shè)計(jì)方法：窮舉法、回溯法、遞歸法、結(jié)合實(shí)例理解算法設(shè)計(jì)方法：窮舉法、回溯法、遞歸法、分治法、貪心法以及動(dòng)態(tài)規(guī)劃分治法、貪心法以及動(dòng)態(tài)規(guī)劃4、認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)研究的三大內(nèi)容、認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)研究的三大內(nèi)容5、了解程序設(shè)計(jì)概念，了解程序設(shè)計(jì)語言的發(fā)展及分類、了解程序設(shè)計(jì)概念，了解程序設(shè)計(jì)語言的發(fā)展及分類 6.16.1算法的概念算法的概念6.2 6.

2、2 算法策略算法策略v 1974年圖靈獎(jiǎng)獲得者年圖靈獎(jiǎng)獲得者Donald Ervin Knuth: v 計(jì)算機(jī)科學(xué)就是算法的研究計(jì)算機(jī)科學(xué)就是算法的研究v The Art of Computer Programming6.1 6.1 算法的概念算法的概念算法算法（Algorithm）是一組有窮的規(guī)則，它們規(guī)定了解決某）是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算，是對(duì)解題方案的準(zhǔn)確與完一特定類型問題的一系列運(yùn)算，是對(duì)解題方案的準(zhǔn)確與完整的描述。整的描述。算法是一種解決問題的方法，是數(shù)學(xué)及其應(yīng)用的重要組成算法是一種解決問題的方法，是數(shù)學(xué)及其應(yīng)用的重要組成部分。部分。 6.1.2算

3、法的特性v算法的一般應(yīng)包含以下特性：算法的一般應(yīng)包含以下特性：v（1 1）有窮性。）有窮性。v（2 2）確定性。）確定性。v（3 3）可行性。）可行性。v（4 4） 輸入。輸入。v（5 5） 輸出輸出。6.1.36.1.3算法與計(jì)算機(jī)程序算法與計(jì)算機(jī)程序計(jì)算機(jī)計(jì)算機(jī)輸入輸入輸出輸出算法算法問題問題算法與計(jì)算機(jī)之間的關(guān)系算法與計(jì)算機(jī)之間的關(guān)系在計(jì)算機(jī)科學(xué)中，在計(jì)算機(jī)科學(xué)中，算法算法要用計(jì)算機(jī)算法語言要用計(jì)算機(jī)算法語言描述，描述，算法算法代表用計(jì)算機(jī)解一類問題的精確、代表用計(jì)算機(jī)解一類問題的精確、有效的方法。有效的方法。算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=計(jì)算機(jī)程序計(jì)算機(jī)程序6.1.4算法的控制結(jié)構(gòu)與描述

4、v1 1、算法的控制結(jié)構(gòu)、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱之為算法的算法中各操作之間的執(zhí)行順序稱之為算法的控制結(jié)構(gòu)。控制結(jié)構(gòu)。算法一般都可以用算法一般都可以用順序結(jié)構(gòu)順序結(jié)構(gòu)、分支結(jié)構(gòu)分支結(jié)構(gòu)、循循環(huán)結(jié)構(gòu)環(huán)結(jié)構(gòu)三種基本控制結(jié)構(gòu)組合而成。三種基本控制結(jié)構(gòu)組合而成。（1 1）、自然語言）、自然語言自然語言自然語言是人們?nèi)粘＿M(jìn)行交流的語言，如漢語、英語等是人們?nèi)粘＿M(jìn)行交流的語言，如漢語、英語等優(yōu)點(diǎn)優(yōu)點(diǎn)：通俗易懂，即使沒有學(xué)過算法也能看懂算法執(zhí)行通俗易懂，即使沒有學(xué)過算法也能看懂算法執(zhí)行缺點(diǎn)缺點(diǎn)：不夠嚴(yán)謹(jǐn)，容易出現(xiàn)歧義和錯(cuò)誤不夠嚴(yán)謹(jǐn)，容易出現(xiàn)歧義和錯(cuò)誤2、算法的描述、算法的描述v（2 2）、

5、流程圖）、流程圖 用圖直觀地描述一個(gè)工作過程的具體步驟用圖直觀地描述一個(gè)工作過程的具體步驟 常用來描述算法的圖形工具有常用來描述算法的圖形工具有：流程圖或程序框圖、：流程圖或程序框圖、N-SN-S圖和圖和PADPAD圖。圖。 優(yōu)點(diǎn)優(yōu)點(diǎn)：直觀形象，簡(jiǎn)潔明了。：直觀形象，簡(jiǎn)潔明了。 缺點(diǎn)缺點(diǎn)：畫起來費(fèi)事，不易修改。：畫起來費(fèi)事，不易修改。常用的流程圖符號(hào)常用的流程圖符號(hào)：（3 3）偽代碼）偽代碼6.1.56.1.5算法的設(shè)計(jì)要求算法的設(shè)計(jì)要求 v1 1、正確性。、正確性。 v2 2、可讀性。、可讀性。 v3 3、高效率與低存儲(chǔ)量。、高效率與低存儲(chǔ)量。 6.2算法策略v6.2.1 6.2.1 窮舉法

6、窮舉法v問題問題1 1： 有一把鎖和一串鑰匙（共有有一把鎖和一串鑰匙（共有1010把鑰匙），怎樣把鑰匙），怎樣找出所有開這把鎖的鑰匙？找出所有開這把鎖的鑰匙？窮舉法窮舉法又稱列舉法、枚舉法，是蠻力策略的具體又稱列舉法、枚舉法，是蠻力策略的具體體現(xiàn)，是一種簡(jiǎn)單而直接地解決問題的方法。其體現(xiàn)，是一種簡(jiǎn)單而直接地解決問題的方法。其基本思想是逐一列舉問題所涉及的所有情形，并基本思想是逐一列舉問題所涉及的所有情形，并根據(jù)問題提出的條件檢驗(yàn)?zāi)男┦菃栴}的解，哪些根據(jù)問題提出的條件檢驗(yàn)?zāi)男┦菃栴}的解，哪些應(yīng)予排除。應(yīng)予排除。窮舉法窮舉法的的特點(diǎn)特點(diǎn)是算法設(shè)計(jì)比較簡(jiǎn)單，解的可能為有是算法設(shè)計(jì)比較簡(jiǎn)單，解的可能為

7、有限種，一一列舉問題所涉及的所有情形。限種，一一列舉問題所涉及的所有情形。例如：例如：在在QQQQ上，上，OicqPassOverOicqPassOver這個(gè)工具窮舉用戶的口這個(gè)工具窮舉用戶的口令，它根據(jù)機(jī)器性能最高可以每秒測(cè)試令，它根據(jù)機(jī)器性能最高可以每秒測(cè)試2000020000個(gè)口個(gè)口令，如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯令，如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯。 窮舉法運(yùn)用于一些經(jīng)典問題窮舉法運(yùn)用于一些經(jīng)典問題1 1、百錢百雞問題、百錢百雞問題中國古代算書張丘建的中國古代算書張丘建的算經(jīng)算經(jīng)中有一道著名的百雞問題：公中有一道著名的百雞問題：公雞每只值雞每只值5 5 文錢，母雞每

8、只值文錢，母雞每只值3 3 文錢，而文錢，而3 3 只小雞值只小雞值1 1 文錢?，F(xiàn)在文錢。現(xiàn)在用用100 100 文錢買文錢買100 100 只雞，問：這只雞，問：這100 100 只雞中，公雞、母雞和小雞各只雞中，公雞、母雞和小雞各有多少只？有多少只？這個(gè)問題流傳很廣，解法很多，但從現(xiàn)代數(shù)學(xué)觀點(diǎn)來看，實(shí)際這個(gè)問題流傳很廣，解法很多，但從現(xiàn)代數(shù)學(xué)觀點(diǎn)來看，實(shí)際上是一個(gè)求不定方程整數(shù)解的問題。解法如下：設(shè)公雞、母雞、小上是一個(gè)求不定方程整數(shù)解的問題。解法如下：設(shè)公雞、母雞、小雞分別為雞分別為x x、y y、z z 只，由題意得：只，由題意得：用窮舉法求解，對(duì)每組求得滿足等式方程組的值，從而找到

9、百用窮舉法求解，對(duì)每組求得滿足等式方程組的值，從而找到百錢百雞的解。錢百雞的解。031003331201100335100 mod,/zzyxzyxzyxv 用用窮舉窮舉算法解決問題，通?？梢詮膬蓚€(gè)方面進(jìn)行分析：算法解決問題，通?？梢詮膬蓚€(gè)方面進(jìn)行分析：1 1、問題所涉及的情況：?jiǎn)栴}所涉及的情況有哪些，情況的、問題所涉及的情況：?jiǎn)栴}所涉及的情況有哪些，情況的種數(shù)可不可以確定。把它描述出來。種數(shù)可不可以確定。把它描述出來。2 2、答案需要滿足的條件：分析出來的這些情況，需要滿足、答案需要滿足的條件：分析出來的這些情況，需要滿足什么條件，才成為問題的答案，把這些條件描述出來。什么條件，才成為問題的

10、答案，把這些條件描述出來。v 由于由于窮舉法窮舉法窮舉的數(shù)據(jù)量過大，效率較低，對(duì)于小規(guī)模的問窮舉的數(shù)據(jù)量過大，效率較低，對(duì)于小規(guī)模的問題還是適用的，但是問題規(guī)模一旦擴(kuò)大，窮舉法就沒有什么題還是適用的，但是問題規(guī)模一旦擴(kuò)大，窮舉法就沒有什么可取性了。一般巧妙和高效算法很少來自窮舉法?？扇⌒粤恕Ｒ话闱擅詈透咝惴ê苌賮碜愿F舉法。6.2.2 6.2.2 回溯法回溯法迷宮游戲迷宮游戲回溯算法回溯算法也叫試探法，是一種選優(yōu)搜索法，按選也叫試探法，是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退步時(shí)，發(fā)現(xiàn)原

11、先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)回溯點(diǎn)”?；厮莘ɑ厮莘ǖ闹笇?dǎo)思想：走不通，就掉頭的指導(dǎo)思想：走不通，就掉頭回溯法回溯法在搜索過程中通過對(duì)約束條件的判定，排在搜索過程中通過對(duì)約束條件的判定，排除錯(cuò)誤答案，提高了搜索效率。除錯(cuò)誤答案，提高了搜索效率。網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲v 網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲是一個(gè)功能強(qiáng)大的自動(dòng)提取是一個(gè)功能強(qiáng)大的自動(dòng)提取網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)下載網(wǎng)頁，是搜索引擎的重要組成部

12、下載網(wǎng)頁，是搜索引擎的重要組成部分。它可以完全不依賴用戶干預(yù)實(shí)現(xiàn)分。它可以完全不依賴用戶干預(yù)實(shí)現(xiàn)網(wǎng)絡(luò)上的自動(dòng)網(wǎng)絡(luò)上的自動(dòng)“爬行爬行”和搜索。和搜索。v 網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲是通過網(wǎng)頁的鏈接地址來尋是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁在抓取網(wǎng)頁的時(shí)候，找網(wǎng)頁在抓取網(wǎng)頁的時(shí)候，網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲采用了采用了深度優(yōu)先深度優(yōu)先策略，策略，深度優(yōu)先深度優(yōu)先是指是指網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲會(huì)從起始頁開始，一個(gè)鏈接會(huì)從起始頁開始，一個(gè)鏈接一個(gè)鏈接跟蹤下去，處理完這條線路一個(gè)鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個(gè)起始頁，繼續(xù)跟蹤之后再轉(zhuǎn)入下一個(gè)起始頁，繼續(xù)跟蹤鏈接。這個(gè)方法有個(gè)優(yōu)點(diǎn)是網(wǎng)絡(luò)爬蟲鏈接。這個(gè)方法有個(gè)優(yōu)點(diǎn)是網(wǎng)絡(luò)爬蟲

13、在設(shè)計(jì)的時(shí)候比較容易。這是一種典在設(shè)計(jì)的時(shí)候比較容易。這是一種典型的回溯算法。型的回溯算法。v回溯法回溯法的本質(zhì)也是一種窮舉法，但與窮舉法相比，的本質(zhì)也是一種窮舉法，但與窮舉法相比，回溯法的回溯法的“聰明聰明”之處在于能適時(shí)之處在于能適時(shí)“回頭回頭”，若再，若再往前走不可能得到解，就回溯，退一步另找線路，往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯與窮舉相這樣可省去大量的無效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題比，回溯更適宜于量比較大，候選解比較多的問題。6.2.3 遞歸法v人們都熟悉一個(gè)民間故事：從前有一座山，山上人們都熟悉

14、一個(gè)民間故事：從前有一座山，山上有一座廟，廟里有一個(gè)老和尚正在給小和尚講故有一座廟，廟里有一個(gè)老和尚正在給小和尚講故事，故事里說，從前有一座山，山上有一座廟，事，故事里說，從前有一座山，山上有一座廟，廟里有一個(gè)老和尚正在給小和尚講故事，故事里廟里有一個(gè)老和尚正在給小和尚講故事，故事里說說。 v所謂所謂遞歸遞歸就是一個(gè)函數(shù)或過程可以直接或間接地調(diào)就是一個(gè)函數(shù)或過程可以直接或間接地調(diào)用自己。用自己。v遞歸遞歸分為分為直接遞歸直接遞歸和和間接遞歸間接遞歸兩種方法。兩種方法。v如果一個(gè)算法直接調(diào)用自己，稱為如果一個(gè)算法直接調(diào)用自己，稱為直接遞歸調(diào)用直接遞歸調(diào)用；v如果一個(gè)算法如果一個(gè)算法A A調(diào)用另一

15、個(gè)算法調(diào)用另一個(gè)算法B B，而算法，而算法B B又調(diào)用又調(diào)用算法算法A A，則此種遞歸稱為，則此種遞歸稱為間接遞歸調(diào)用間接遞歸調(diào)用。德德羅羅斯斯特特效效應(yīng)應(yīng) 1 1、n n！問題！問題階乘可以這樣遞歸地定義成函數(shù)：階乘可以這樣遞歸地定義成函數(shù)：這樣，所有自然數(shù)的階乘就可以通過上面的兩句話表這樣，所有自然數(shù)的階乘就可以通過上面的兩句話表示了。示了。2 2的階乘就是的階乘就是1 12 2；3 3的階乘就是的階乘就是2 2的階乘乘的階乘乘3 3，即，即1 12 23 3不僅如此，人們還可以知道不僅如此，人們還可以知道0 0的階乘是多少，的階乘是多少，1 1的階乘應(yīng)該等于的階乘應(yīng)該等于0 0的階乘乘以

16、的階乘乘以1 1，顯然，顯然0 0的階乘必須是的階乘必須是1 1才才行。行。)0()0()!1(*1!nnnnn)0()0() 1(*1)(nnnfnnf2 2、漢諾塔（、漢諾塔（HanoiHanoi）問題）問題 相傳印度有座大寺廟，它曾被認(rèn)為是宇宙的中心。神廟中放置相傳印度有座大寺廟，它曾被認(rèn)為是宇宙的中心。神廟中放置了一塊上面插有三根長木釘?shù)哪景?，在其中的一根木釘上，由上至下了一塊上面插有三根長木釘?shù)哪景?，在其中的一根木釘上，由上至下放了放?464片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧侶們將侶們將6464片金屬片全部移

17、至另一根木釘上。移動(dòng)規(guī)則只有兩個(gè)：片金屬片全部移至另一根木釘上。移動(dòng)規(guī)則只有兩個(gè)：（1 1）在每次的移動(dòng)中，只能移動(dòng)一片金屬片；）在每次的移動(dòng)中，只能移動(dòng)一片金屬片；（2 2）過程中任意時(shí)刻必須保證金屬片小的在上，大的在下。）過程中任意時(shí)刻必須保證金屬片小的在上，大的在下。v使用使用遞歸遞歸時(shí)必須符合以下三個(gè)條件：時(shí)必須符合以下三個(gè)條件：（1 1）可將一個(gè)問題轉(zhuǎn)化為一個(gè)新的問題，而新問）可將一個(gè)問題轉(zhuǎn)化為一個(gè)新的問題，而新問題的解決方法仍與原問題的解法相同，只不過所處題的解決方法仍與原問題的解法相同，只不過所處理的對(duì)象有所不同而已，即它們只是有規(guī)律的遞增理的對(duì)象有所不同而已，即它們只是有規(guī)律的

18、遞增或遞減?；蜻f減。 （2 2）可以通過轉(zhuǎn)化過程使問題回到對(duì)原問題的求）可以通過轉(zhuǎn)化過程使問題回到對(duì)原問題的求解。解。 （3 3）必須要有一個(gè)明確的結(jié)束遞歸的條件，否則）必須要有一個(gè)明確的結(jié)束遞歸的條件，否則遞歸會(huì)無止境地進(jìn)行下去。遞歸會(huì)無止境地進(jìn)行下去。v遞歸遞歸對(duì)某些問題而言存在重復(fù)調(diào)用，導(dǎo)致算法效率對(duì)某些問題而言存在重復(fù)調(diào)用，導(dǎo)致算法效率不高。不高。6.2.4 分治法v 分治法分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題，分割成的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。v 分治法分治法所能

19、解決的問題一般具有以下幾個(gè)特征：所能解決的問題一般具有以下幾個(gè)特征：（1 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；）該問題的規(guī)模縮小到一定的程度就可以容易地解決；（2 2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3 3）利用該問題分解出的子問題的解可以合并為該問題的解；）利用該問題分解出的子問題的解可以合并為該問題的解；（4 4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。間不包含公共的子問題。 1 1

20、、找出偽幣、找出偽幣v 一個(gè)裝有一個(gè)裝有1 61 6枚硬幣的袋子，枚硬幣的袋子，1 61 6枚硬幣中有一個(gè)是偽造枚硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這枚偽造的硬幣。務(wù)是找出這枚偽造的硬幣。v 為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，比如天平。利用這臺(tái)儀器，可以知道硬幣重量的儀器，比如天平。利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。兩組硬幣的重量是否相同。 方法方法1 1v 任意取任意取1 1枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，枚

21、硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有這那枚為偽幣。最多可能有1515次比較。次比較。 方法方法2 2v 將硬幣分為將硬幣分為8 8組，每組組，每組2 2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有則為偽幣。最多可能有8 8次比較。次比較。 方法方法3 3分析分析v上述三種方法上述三種方法, ,分別需要比較分別需要比較1818次次,8,8次次,4,4次次, ,那么那么形成比較次數(shù)差異的根據(jù)原因在哪里形成比較次數(shù)差異的根據(jù)原因在哪里? ?v方法方法1:1:每枚硬幣都至少進(jìn)行了一次比較每枚硬幣都至少進(jìn)行了一次比較, ,而有一枚而有一枚硬幣

22、進(jìn)行了硬幣進(jìn)行了1515次比較次比較v方法方法2:2:每一枚硬幣只進(jìn)行了一次比較每一枚硬幣只進(jìn)行了一次比較v方法方法3:3:將硬幣分為兩組后一次比較可以將硬幣的將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來的一半范圍縮小到了原來的一半, ,這樣充分地利用了只有這樣充分地利用了只有1 1枚偽幣的基本性質(zhì)。枚偽幣的基本性質(zhì)。v根據(jù)以上比較，第三種方法就是根據(jù)以上比較，第三種方法就是分治法分治法，可以得到，可以得到以下的采用以下的采用分治方法分治方法的結(jié)論：的結(jié)論：1 1、參與比較的硬幣數(shù)量越多，使用該方法來實(shí)現(xiàn)就越、參與比較的硬幣數(shù)量越多，使用該方法來實(shí)現(xiàn)就越快，而且投機(jī)性大大減少；快，而且

23、投機(jī)性大大減少；2 2、解決方法關(guān)鍵在于能將大問題分割成若干小問題；、解決方法關(guān)鍵在于能將大問題分割成若干小問題；3 3、小問題與原有問題是完全類似的。、小問題與原有問題是完全類似的。2 2、二分法、二分法v二分查找二分查找又稱為折半查找，是一種可在有序順序又稱為折半查找，是一種可在有序順序表上實(shí)現(xiàn)的效率比較高的查找算法。是一個(gè)典型表上實(shí)現(xiàn)的效率比較高的查找算法。是一個(gè)典型的的分治算法分治算法。n牛頓二分法牛頓二分法n二分法查找二分法查找v 分治法分治法所能解決的問題一般具有以下幾個(gè)特征：所能解決的問題一般具有以下幾個(gè)特征：（1 1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；）該問題的規(guī)模

24、縮小到一定的程度就可以容易地解決；（2 2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3 3）利用該問題分解出的子問題的解可以合并為該問題的）利用該問題分解出的子問題的解可以合并為該問題的解；解；（4 4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。題之間不包含公共的子問題。思考：求解一元二次方程實(shí)根思考：求解一元二次方程實(shí)根6.2.5 貪心法v 貪心算法貪心算法（又稱貪婪算法）是指，（又稱貪婪算法）是指，在對(duì)問題求解

25、時(shí)，總是做出在當(dāng)前在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的僅是在某種意義上的局部最優(yōu)解。局部最優(yōu)解。v 貪心算法貪心算法不是對(duì)所有問題都能得到不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題它能產(chǎn)生整體最優(yōu)解或者許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。是整體最優(yōu)解的近似解。v 只顧眼前利益，每次都選最好的只顧眼前利益，每次都選最好的1 1、商場(chǎng)找零、商場(chǎng)找零假設(shè)只有假設(shè)只有3 3種面額的幣值，它們的面值分別為種面額

26、的幣值，它們的面值分別為2020元、元、1010元、元、5 5元、和元、和1 1元。現(xiàn)要找給某顧客元?，F(xiàn)要找給某顧客3737元，這時(shí)，售貨員元，這時(shí)，售貨員幾乎不假思索地拿出幾乎不假思索地拿出1 1個(gè)個(gè)2020元、元、1 1個(gè)個(gè)l0l0元、元、1 1個(gè)個(gè)5 5元和元和2 2個(gè)個(gè)1 1元元的錢幣交給顧客。人們不僅能很快決定要拿哪些錢幣，而的錢幣交給顧客。人們不僅能很快決定要拿哪些錢幣，而且與其它找法相比這時(shí)拿出的錢幣的個(gè)數(shù)肯定是最少的且與其它找法相比這時(shí)拿出的錢幣的個(gè)數(shù)肯定是最少的。在這里，收貨員實(shí)際使用了這樣的算法：首先選出一個(gè)。在這里，收貨員實(shí)際使用了這樣的算法：首先選出一個(gè)面值不超過面值不

27、超過3737元的最大面額錢幣（元的最大面額錢幣（2020元），然后從元），然后從3737元中元中減去減去2020元，剩下元，剩下1717元中再選出一個(gè)不超過元中再選出一個(gè)不超過1717元的最大面額元的最大面額錢幣（錢幣（1010元），如此做下去，直到找足元），如此做下去，直到找足3737元。這就是所謂元。這就是所謂的貪心法。的貪心法。2 2、最短距離、最短距離 DijkstraDijkstra算法又稱為單源最短算法又稱為單源最短路徑，所謂單源是在一個(gè)有向路徑，所謂單源是在一個(gè)有向圖中，從一個(gè)頂點(diǎn)出發(fā)，求該圖中，從一個(gè)頂點(diǎn)出發(fā)，求該頂點(diǎn)至所有可到達(dá)頂點(diǎn)的最短頂點(diǎn)至所有可到達(dá)頂點(diǎn)的最短路徑問題。路

28、徑問題。 DijstraDijstra算法是運(yùn)用貪心算法是運(yùn)用貪心的策略，從源點(diǎn)開始，不斷地的策略，從源點(diǎn)開始，不斷地通過相聯(lián)通的點(diǎn)找出到其他點(diǎn)通過相聯(lián)通的點(diǎn)找出到其他點(diǎn)的最短距離的最短距離基本思想是：基本思想是： 設(shè)置一個(gè)頂點(diǎn)的集合設(shè)置一個(gè)頂點(diǎn)的集合s s，并不斷地?cái)U(kuò)充這個(gè)集合，一個(gè)并不斷地?cái)U(kuò)充這個(gè)集合，一個(gè)頂點(diǎn)屬于集合頂點(diǎn)屬于集合s s當(dāng)且僅當(dāng)從源點(diǎn)當(dāng)且僅當(dāng)從源點(diǎn)到該點(diǎn)的路徑已求出。開始時(shí)到該點(diǎn)的路徑已求出。開始時(shí)s s中僅有源點(diǎn)，并且調(diào)整非中僅有源點(diǎn)，并且調(diào)整非s s中點(diǎn)中點(diǎn)的最短路徑長度，找當(dāng)前最短的最短路徑長度，找當(dāng)前最短路徑點(diǎn)，將其加入到集合路徑點(diǎn)，將其加入到集合s s，直，直到終

29、點(diǎn)在到終點(diǎn)在s s中。中。v貪心法貪心法主要有以下兩個(gè)特點(diǎn)：主要有以下兩個(gè)特點(diǎn)： （1 1）貪心選擇性質(zhì)貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未作出的選擇。但不依賴于未作出的選擇。（2 2）最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)：算法中每一次都取得了最優(yōu)解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。則必須滿足全局最優(yōu)解包含局部最優(yōu)解。6.2.6 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)

30、分支，是求解決策過是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。程最優(yōu)化的數(shù)學(xué)方法。2020世紀(jì)世紀(jì)5050年代美國數(shù)學(xué)家貝爾曼（年代美國數(shù)學(xué)家貝爾曼（Rechard Rechard BellmanBellman）等人在研究多階段決策過程的優(yōu)化問題）等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)性原理，把多階段決策過時(shí)，提出了著名的最優(yōu)性原理，把多階段決策過程轉(zhuǎn)化為一系列單階段問題逐個(gè)求解，創(chuàng)立了解程轉(zhuǎn)化為一系列單階段問題逐個(gè)求解，創(chuàng)立了解決多階段過程優(yōu)化問題的新方法決多階段過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。v動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃所處理的對(duì)象是所處理的對(duì)象是多階段決策問題多階段決

31、策問題。v多階段決策問題多階段決策問題，是指這樣的一類特殊的活動(dòng)過，是指這樣的一類特殊的活動(dòng)過程，問題可以分解成若干相互聯(lián)系的階段，在每程，問題可以分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，形成一個(gè)決策序列，該一個(gè)階段都要做出決策，形成一個(gè)決策序列，該決策序列也稱為一個(gè)策略。決策序列也稱為一個(gè)策略。1 1、最短距離、最短距離 DijkstraDijkstra算法又稱為單源最短算法又稱為單源最短路徑，所謂單源是在一個(gè)有向路徑，所謂單源是在一個(gè)有向圖中，從一個(gè)頂點(diǎn)出發(fā)，求該圖中，從一個(gè)頂點(diǎn)出發(fā)，求該頂點(diǎn)至所有可到達(dá)頂點(diǎn)的最短頂點(diǎn)至所有可到達(dá)頂點(diǎn)的最短路徑問題。路徑問題。 基本思想是：基本

32、思想是： 設(shè)置一個(gè)頂點(diǎn)的集合設(shè)置一個(gè)頂點(diǎn)的集合s s，并不斷地?cái)U(kuò)充這個(gè)集合，一個(gè)并不斷地?cái)U(kuò)充這個(gè)集合，一個(gè)頂點(diǎn)屬于集合頂點(diǎn)屬于集合s s當(dāng)且僅當(dāng)從源點(diǎn)當(dāng)且僅當(dāng)從源點(diǎn)到該點(diǎn)的路徑已求出。開始時(shí)到該點(diǎn)的路徑已求出。開始時(shí)s s中僅有源點(diǎn)，并且調(diào)整非中僅有源點(diǎn)，并且調(diào)整非s s中點(diǎn)中點(diǎn)的最短路徑長度，找當(dāng)前最短的最短路徑長度，找當(dāng)前最短路徑點(diǎn)，將其加入到集合路徑點(diǎn)，將其加入到集合s s，直，直到終點(diǎn)在到終點(diǎn)在s s中。中。2 2、背包問題、背包問題背包問題的一個(gè)例子：應(yīng)該選擇哪些盒背包問題的一個(gè)例子：應(yīng)該選擇哪些盒子，才能使價(jià)格盡可能地大，而保持重子，才能使價(jià)格盡可能地大，而保持重量小于或等于量小于

33、或等于15 kg？背包問題背包問題(Knapsack problem)可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。背包問題背包問題0-10-1背包問題的描述是：有背包問題的描述是：有N N件物品和一個(gè)容量件物品和一個(gè)容量為為V V的背包。第的背包。第i i件物品的容量是件物品的容量是cici，價(jià)值是，價(jià)值是wiwi。求解將哪些物品裝入背包可使價(jià)值總和。求解將哪些物品裝入背包可使價(jià)值總和最大。這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種最大。這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有

34、一件，可以選擇放或不放。物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即用子問題定義狀態(tài)：即fivfiv表示前表示前i i件件物品恰放入一個(gè)容量為物品恰放入一個(gè)容量為v v的背包可以獲得的最的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-ci+wi這個(gè)方程的含義是這個(gè)方程的含義是：“將前將前i i件物品放入容量為件物品放入容量為v v的背包中的背包中”這個(gè)子問題，若只考慮第這個(gè)子問題，若只考慮第i i件物品的策略（放或不放），那件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1i-1件物

35、品的問題。件物品的問題。如果不放第如果不放第i i件物品，那么問題就轉(zhuǎn)化為件物品，那么問題就轉(zhuǎn)化為“前前i-1i-1件物品放件物品放入容量為入容量為v v的背包中的背包中”，價(jià)值為，價(jià)值為fi-1vfi-1v；如果放第；如果放第i i件物品件物品，那么問題就轉(zhuǎn)化為，那么問題就轉(zhuǎn)化為“前前i-1i-1件物品放入剩下的容量為件物品放入剩下的容量為v-civ-ci的背包中的背包中”，此時(shí)能獲得的最大價(jià)值就是，此時(shí)能獲得的最大價(jià)值就是fi-1v-cifi-1v-ci再加再加上通過放入第上通過放入第i i件物品獲得的價(jià)值件物品獲得的價(jià)值wiwi。fiv=maxfi-1v,fi-1v-ci+wiv多階段決

36、策問題的多階段決策問題的最優(yōu)化求解目標(biāo)最優(yōu)化求解目標(biāo)是獲取導(dǎo)致問是獲取導(dǎo)致問題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到最優(yōu)解最優(yōu)解。v動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃思想實(shí)質(zhì)是思想實(shí)質(zhì)是分治思想分治思想和和冗余解決冗余解決方法的方法的結(jié)合。結(jié)合。v動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，動(dòng)態(tài)規(guī)劃三要素是的狀態(tài)中產(chǎn)生出來的，所以，動(dòng)態(tài)規(guī)劃三要素是階段、狀態(tài)、決策。階段、狀態(tài)、決策。v動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法多用來計(jì)算最優(yōu)問

37、題，動(dòng)態(tài)規(guī)劃法與多用來計(jì)算最優(yōu)問題，動(dòng)態(tài)規(guī)劃法與分治法的基本思想是一致的，但處理的手法不同分治法的基本思想是一致的，但處理的手法不同。動(dòng)態(tài)規(guī)劃法在運(yùn)用時(shí)，要先對(duì)問題的分治規(guī)律。動(dòng)態(tài)規(guī)劃法在運(yùn)用時(shí)，要先對(duì)問題的分治規(guī)律進(jìn)行分析，找出終結(jié)子問題，以及子問題向父問進(jìn)行分析，找出終結(jié)子問題，以及子問題向父問題歸納的規(guī)則，而算法則直接從終結(jié)子問題開始題歸納的規(guī)則，而算法則直接從終結(jié)子問題開始求解，逐層向上歸納，直到歸納出原問題的解。求解，逐層向上歸納，直到歸納出原問題的解。6.3 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)語言6.3.1 6.3.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述電話是通訊聯(lián)絡(luò)必不可少的工具。如何用計(jì)算機(jī)來實(shí)電話是通

38、訊聯(lián)絡(luò)必不可少的工具。如何用計(jì)算機(jī)來實(shí)現(xiàn)自動(dòng)查詢電話號(hào)碼呢？要求對(duì)于給定的任意姓名，如果現(xiàn)自動(dòng)查詢電話號(hào)碼呢？要求對(duì)于給定的任意姓名，如果該人有電話號(hào)碼，則迅速給出電話號(hào)碼，否則，給出查找該人有電話號(hào)碼，則迅速給出電話號(hào)碼，否則，給出查找不到該人電話號(hào)碼的信息。不到該人電話號(hào)碼的信息。為了提高查找效率，就必須了解待處理對(duì)象之間的關(guān)為了提高查找效率，就必須了解待處理對(duì)象之間的關(guān)系，以及如何存儲(chǔ)和表示這些數(shù)據(jù)。系，以及如何存儲(chǔ)和表示這些數(shù)據(jù)。 電話號(hào)碼經(jīng)過處理，按照拼音排好了順序，每個(gè)電話電話號(hào)碼經(jīng)過處理，按照拼音排好了順序，每個(gè)電話號(hào)碼之間的先后次序就是數(shù)據(jù)元素之間的關(guān)系。號(hào)碼之間的先后次序就是

39、數(shù)據(jù)元素之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是研究這類非數(shù)值處理的程序設(shè)計(jì)問題。就是研究這類非數(shù)值處理的程序設(shè)計(jì)問題。v數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)系稱為結(jié)構(gòu)系稱為結(jié)構(gòu)(Structure)(Structure)。v一般來說包括以下三方面：一般來說包括以下三方面：數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、數(shù)、數(shù)據(jù)的據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的和數(shù)據(jù)的運(yùn)算運(yùn)算。（1 1）數(shù)據(jù)的邏輯結(jié)構(gòu)）數(shù)據(jù)的

40、邏輯結(jié)構(gòu)數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的在計(jì)是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的在計(jì)算機(jī)內(nèi)部是如何算機(jī)內(nèi)部是如何存儲(chǔ)無關(guān)存儲(chǔ)無關(guān)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立獨(dú)立于計(jì)算機(jī)。于計(jì)算機(jī)。v 數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)和和非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯特征是除第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)外，其他線性結(jié)構(gòu)的邏輯特征是除第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼結(jié)點(diǎn)。所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼結(jié)點(diǎn)。非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)

41、點(diǎn)可能有多個(gè)直接前趨和直接后繼。后繼。v 為了進(jìn)一步研究數(shù)據(jù)的邏輯結(jié)構(gòu)，可以將數(shù)據(jù)的邏輯結(jié)構(gòu)分為為了進(jìn)一步研究數(shù)據(jù)的邏輯結(jié)構(gòu)，可以將數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。v 線性結(jié)構(gòu)包括：線性表、棧和隊(duì)列等。線性結(jié)構(gòu)包括：線性表、棧和隊(duì)列等。v 非線性結(jié)構(gòu)包括樹和圖型結(jié)構(gòu)。非線性結(jié)構(gòu)包括樹和圖型結(jié)構(gòu)。（2 2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)( (是研究數(shù)據(jù)是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，是邏輯數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，是邏輯數(shù)據(jù)的存儲(chǔ)映像，

42、它是的存儲(chǔ)映像，它是面向計(jì)算機(jī)面向計(jì)算機(jī)的。的。數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)有四種基本的映像方法：數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)有四種基本的映像方法： 順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 索引存儲(chǔ)結(jié)構(gòu)。索引存儲(chǔ)結(jié)構(gòu)。 散列存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)。 （3 3）數(shù)據(jù)的運(yùn)算）數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，也就是刪除、檢索和排序等與問題相關(guān)的處理。也就是刪除、檢索和排序等與問題相關(guān)的處理。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)通常具有下列一些基本操作：通常具有下列一些基本操作：插入：在數(shù)據(jù)結(jié)構(gòu)的指定位置上添加一個(gè)新結(jié)點(diǎn)。插入：在數(shù)據(jù)結(jié)構(gòu)的指定位置上添加一個(gè)新結(jié)

43、點(diǎn)。刪除：刪去數(shù)據(jù)結(jié)構(gòu)中指定位置的結(jié)點(diǎn)。刪除：刪去數(shù)據(jù)結(jié)構(gòu)中指定位置的結(jié)點(diǎn)。更新：修改數(shù)據(jù)結(jié)構(gòu)中某個(gè)結(jié)點(diǎn)的值。更新：修改數(shù)據(jù)結(jié)構(gòu)中某個(gè)結(jié)點(diǎn)的值。查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足指定條件的結(jié)點(diǎn)及其位置。查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足指定條件的結(jié)點(diǎn)及其位置。排序：按照指定的順序，使結(jié)點(diǎn)重新排列排序：按照指定的順序，使結(jié)點(diǎn)重新排列。6.3.2程序設(shè)計(jì)語言簡(jiǎn)介1 1、程序設(shè)計(jì)概念、程序設(shè)計(jì)概念程序設(shè)計(jì)程序設(shè)計(jì)(Programming)(Programming)是給出解決特定問題程序的是給出解決特定問題程序的過程，是軟件構(gòu)造活動(dòng)中的重要組成部分。過程，是軟件構(gòu)造活動(dòng)中的重要組成部分。程序設(shè)計(jì)是指設(shè)計(jì)、編制、調(diào)試程

44、序的方法和過程。程序設(shè)計(jì)是指設(shè)計(jì)、編制、調(diào)試程序的方法和過程。程序程序= =數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法算法程序設(shè)計(jì)規(guī)范是進(jìn)行程序設(shè)計(jì)的具體規(guī)定。程序設(shè)計(jì)程序設(shè)計(jì)規(guī)范是進(jìn)行程序設(shè)計(jì)的具體規(guī)定。程序設(shè)計(jì)要本著要本著“清晰第一，效率第二清晰第一，效率第二”的風(fēng)格。的風(fēng)格。 v 按照結(jié)構(gòu)性質(zhì)，有按照結(jié)構(gòu)性質(zhì)，有結(jié)構(gòu)化結(jié)構(gòu)化程序設(shè)計(jì)與程序設(shè)計(jì)與非結(jié)構(gòu)化非結(jié)構(gòu)化程序設(shè)計(jì)程序設(shè)計(jì)v 按照用戶的要求，有按照用戶的要求，有過程式過程式程序設(shè)計(jì)與程序設(shè)計(jì)與非過程式非過程式程序設(shè)計(jì)程序設(shè)計(jì) v 按照程序設(shè)計(jì)風(fēng)格，有按照程序設(shè)計(jì)風(fēng)格，有邏輯式邏輯式程序設(shè)計(jì)、程序設(shè)計(jì)、函數(shù)式函數(shù)式程序設(shè)計(jì)程序設(shè)計(jì)、對(duì)象式對(duì)象式程序設(shè)計(jì)

45、。程序設(shè)計(jì)。 v程序設(shè)計(jì)過程包括程序設(shè)計(jì)過程包括分析分析、設(shè)計(jì)設(shè)計(jì)、編碼編碼、測(cè)試測(cè)試、排排錯(cuò)錯(cuò)等階段等階段 2 2、程序設(shè)計(jì)語言、程序設(shè)計(jì)語言v程序設(shè)計(jì)語言程序設(shè)計(jì)語言，通常簡(jiǎn)稱為編程語言，是一組用，通常簡(jiǎn)稱為編程語言，是一組用來定義計(jì)算機(jī)程序的來定義計(jì)算機(jī)程序的語法規(guī)則語法規(guī)則。 v程序設(shè)計(jì)語言包含三個(gè)方面，即程序設(shè)計(jì)語言包含三個(gè)方面，即語法語法、語義語義和和語語用用 v程序設(shè)計(jì)語言程序設(shè)計(jì)按照語言級(jí)別可以分為程序設(shè)計(jì)語言程序設(shè)計(jì)按照語言級(jí)別可以分為低低級(jí)語言級(jí)語言和和高級(jí)語言高級(jí)語言。3 3、面向過程和面向?qū)ο?、面向過程和面向?qū)ο? 4、語言處理程序、語言處理程序5 5、程序設(shè)計(jì)的一般過

46、程、程序設(shè)計(jì)的一般過程（1 1）確定要解決的問題）確定要解決的問題（2 2）分析問題，建立數(shù)學(xué)模型）分析問題，建立數(shù)學(xué)模型（3 3）確定數(shù)據(jù)結(jié)構(gòu)和算法）確定數(shù)據(jù)結(jié)構(gòu)和算法（4 4）編寫程序）編寫程序（5 5）調(diào)試程序）調(diào)試程序（6 6）整理資料，交付使用）整理資料，交付使用6.3.3結(jié)構(gòu)化程序設(shè)計(jì)v結(jié)構(gòu)化程序設(shè)計(jì)，它的基本思想是結(jié)構(gòu)化程序設(shè)計(jì)，它的基本思想是“自頂向下，自頂向下，逐步求精，模塊化，限制使用逐步求精，模塊化，限制使用gotogoto語句語句”和和“單單入口單出口入口單出口”的控制結(jié)構(gòu)。的控制結(jié)構(gòu)。v基于這樣的思想，提出了三種基本結(jié)構(gòu)，由這三基于這樣的思想，提出了三種基本結(jié)構(gòu)，由這三種基本結(jié)構(gòu)組成的程序，就是結(jié)構(gòu)化程序。種基本結(jié)構(gòu)組成的程序，就是結(jié)構(gòu)化程序。v1 1、順序順序結(jié)構(gòu)結(jié)構(gòu)v2 2、分支分支結(jié)構(gòu)結(jié)構(gòu)v3 3、循環(huán)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)