本章學(xué)習(xí)目標(biāo)了解數(shù)據(jù)結(jié)構(gòu)與算法的基本概念；了解幾種基本數(shù)據(jù)結(jié)構(gòu)；掌握算法的結(jié)構(gòu)以及描述方法；熟練掌握算法的流程圖表示，能熟練的繪制算法流程圖。4.1算法概念算法：解決一個問題而采取的方法和步驟。算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系緊密，在算法設(shè)計時先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，而在討論某一種數(shù)據(jù)結(jié)構(gòu)時也必然會涉及相應(yīng)的算法。著名的計算機(jī)科學(xué)家尼古拉斯·沃斯曾提出：程序設(shè)計=數(shù)據(jù)結(jié)構(gòu)+算法。算法的性質(zhì)

一個成熟的算法應(yīng)該具有以下六個特性：算法名稱：就是給算法命名，每個算法都應(yīng)該有一個名字，在C語言中，算法名通常就是函數(shù)名。輸入：算法可能會有若干個輸入。輸出：算法至少有一個或多個輸出，表示算法運(yùn)算的結(jié)果。有效性：算法的每一步都有確定的含義，計算可以進(jìn)行操作和運(yùn)算的。正確性：是指算法的結(jié)果必須正確，能夠解決相應(yīng)問題的。有限性：一個算法必須在執(zhí)行有窮步驟之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。算法的結(jié)構(gòu)C語言是一種結(jié)構(gòu)化的程序語言。任何復(fù)雜的算法都可以由順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組成。1、順序結(jié)構(gòu)，是簡單的線性結(jié)構(gòu)，程序在執(zhí)行過程中是按語句的先后順序來執(zhí)行的。2、分支結(jié)構(gòu)，程序在執(zhí)行過程中，會根據(jù)條件的不同有選擇的執(zhí)行不同的功能。3、循環(huán)結(jié)構(gòu)，程序在執(zhí)行過程中，在一定的時間段內(nèi)或一定的條件下，重復(fù)地執(zhí)行某個功能，直到時間已到或條件不再滿足。數(shù)據(jù)結(jié)構(gòu)概念

數(shù)據(jù)是計算機(jī)處理符號的總稱。數(shù)據(jù)可以是數(shù)值型，也可以是非數(shù)值型。數(shù)值數(shù)據(jù)主要有整數(shù)和浮點(diǎn)數(shù)等。數(shù)據(jù)元素之間的關(guān)系稱為“結(jié)構(gòu)”。有4種基本結(jié)構(gòu):集合關(guān)系(無序的松散關(guān)系)；線性關(guān)系(一一對應(yīng)關(guān)系)；樹樹關(guān)系(一對多關(guān)系)；圖關(guān)系(多對多關(guān)系)。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)的邏輯結(jié)構(gòu)和物理存儲結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。數(shù)據(jù)結(jié)構(gòu)類型

根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，數(shù)據(jù)的邏輯結(jié)構(gòu)有4種基本類型:集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是“屬于同一個集合”。由于集合是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此也可用其他數(shù)據(jù)結(jié)構(gòu)來表示。4.2幾種基本數(shù)據(jù)結(jié)構(gòu)

線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其他數(shù)據(jù)元素都是首尾相接的。在實(shí)際應(yīng)用中，線性表的形式有字符串、一維數(shù)組、棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)。4.2幾種基本數(shù)據(jù)結(jié)構(gòu)

棧最大的特點(diǎn)是先進(jìn)后出。是一種特殊的線性表，棧的插人和刪除運(yùn)算限定在的某一端進(jìn)行。允許插人和刪除的一端稱為棧頂，另一端稱為棧底。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素。在如圖所示的棧中，元素以a1，a2，……，an的順序進(jìn)棧，因此棧底元素是a1，棧頂元素是an。不含任何數(shù)據(jù)元素的棧稱為空棧。4.2幾種基本的數(shù)據(jù)結(jié)構(gòu)

隊(duì)列是先進(jìn)先出，隊(duì)列也是一種運(yùn)算受限的線性表，在隊(duì)列中，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。新插入的元素只能添加到隊(duì)尾，被刪除的元素只能是排在隊(duì)頭的元素。4.2幾種基本的數(shù)據(jù)結(jié)構(gòu)

樹形結(jié)構(gòu)廣泛存在于客觀世界中，如人類的族譜，各種社會組織機(jī)構(gòu)，各種事物的分類等，都可以用樹表示。樹在計算機(jī)領(lǐng)域得到了廣泛應(yīng)用，如：操作系統(tǒng)中的目錄結(jié)構(gòu)。簡單地說，一切具有層次關(guān)系或包含關(guān)系的問題都可用樹來描述。4.2幾種基本的數(shù)據(jù)結(jié)構(gòu)圖中的數(shù)據(jù)元素稱為頂點(diǎn)(Vertex)，頂點(diǎn)之間的邏輯關(guān)系用邊來表示。V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。圖中的邊按有無方向分為無向圖和有向圖，無向圖由頂點(diǎn)和邊組成，有向圖由頂點(diǎn)和弧構(gòu)成，如圖所示。如果圖中的邊沒有權(quán)值關(guān)系時，一般定義邊長為1，如果圖中的邊有權(quán)值，則構(gòu)成的圖稱為網(wǎng)圖。4.3算法的描述常用的算法的描述方法有：自然語言、流程圖、偽代碼、PAD圖等。自然語言描述：用日常交流語言直接將算法步驟表述出來。優(yōu)點(diǎn)：簡單，便于人們對算法的閱讀；缺點(diǎn)：文字冗長，容易出現(xiàn)歧義；描述分支和循環(huán)結(jié)構(gòu)不直觀。4.3算法的描述【例4-1】計算并輸出z=x/y的值。自然語言算法描述：S1：輸入變量x，y;S2：判斷y是否為0；S3：如果y=0；則輸出錯誤提示信息；S4：否則計算z=x/y；S5：輸出z；S6：算法結(jié)束。4.3算法的描述【例4-3】求和sum=1+2+3+4+5+……+n，輸出sum的值。算法描述：s1：給定一個大于0的正整數(shù)n的值；s2：定義一個整型變量i，設(shè)其初始值1；s3：定義整型變量sum，其初始值設(shè)置為0；s4：如果i小于等于n，則轉(zhuǎn)到s5，否則轉(zhuǎn)到s8；s5：將sum的值加上i的值后，重新賦值給sum；s6：將i的值加1，重新賦值給i；s7：轉(zhuǎn)到第4步；s8：輸出sum的值；s9：算法結(jié)束。4.3算法的描述流程圖是由流程線和幾何圖形框連接而成的。開始結(jié)束框：代表算法的開始和結(jié)束，每個算法都必須有且僅有一個開始和一個結(jié)束。數(shù)據(jù)框：代表算法中數(shù)據(jù)的輸入或輸出。處理框：表示算法對數(shù)據(jù)的處理，通常為程序的表達(dá)式語句。判斷框：代表算法中的分支情況，判斷條件只有滿足和不滿足兩種情況。流向線：用來連接各個流程圖框，表示算法的流程走向。連接點(diǎn)：當(dāng)同一個算法流程圖在不同頁時，在分割點(diǎn)畫連接點(diǎn)，來連接流程圖。4.3算法的描述順序結(jié)構(gòu)是一種簡單的線性結(jié)構(gòu)，由處理框和流向線組成，根據(jù)流程線所示的方向，按順序執(zhí)行各矩形框的指令。指令A(yù)、指令B、指令C可以是一條指令語句，也可以是多條指令。執(zhí)行順序?yàn)閺纳系较马樞驁?zhí)行:A-B-C。4.3算法的描述分支結(jié)構(gòu)由判斷框、處理框和流向線組成，先要對給定的條件進(jìn)行判斷，根據(jù)條件結(jié)果的真假而分別執(zhí)行不同的處理框，其流程圖的基本形狀有兩種：注：虛線框表示可將分支結(jié)構(gòu)看成一個矩形框。指令A(yù)、指令B可以是一條或多條指令，也可以是分支結(jié)構(gòu)。4.3算法的描述循環(huán)結(jié)構(gòu)同選擇分支結(jié)構(gòu)一樣，循環(huán)結(jié)構(gòu)也是由判斷框、處理框和流向線組成的。但循環(huán)結(jié)構(gòu)是在某個條件為真的情況下，重復(fù)執(zhí)行某個框中的內(nèi)容。循環(huán)結(jié)構(gòu)有兩種基本形態(tài)while型循環(huán)和dowhile型循環(huán)。while型循環(huán)的流程圖如圖所示。執(zhí)行順序?yàn)?先判斷條件，如果條件為真，則執(zhí)行A；然后再進(jìn)入條件判斷，構(gòu)成一個循環(huán)，一但條件為假，則跳出循環(huán)，進(jìn)入下一個結(jié)構(gòu)。問：分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)流程圖有什么區(qū)別？dowhile型循環(huán)的流程圖如圖所示，執(zhí)行順序?yàn)?先執(zhí)行A，再判斷條件，若條件為真，則重復(fù)執(zhí)行A，一旦條件為假，則跳出循環(huán)，進(jìn)入下一個結(jié)構(gòu)。4.3算法的描述注：(1)虛線框表示可將循環(huán)結(jié)構(gòu)看成一個矩形框。(2)指令A(yù)稱為循環(huán)體，可以是一條或多條指令，也可以是其他分支或循環(huán)結(jié)構(gòu)。(3)do_while結(jié)構(gòu)可以轉(zhuǎn)化成while結(jié)構(gòu)。4.3算法的描述循環(huán)結(jié)構(gòu)注意事項(xiàng)：①在循環(huán)體中的指令有可能不只一條，也可能是其他分支或循環(huán)結(jié)構(gòu)；②指令中必須有修改循環(huán)變量值的語句，使得經(jīng)過有限次循環(huán)后，循環(huán)一定能結(jié)東。③while循環(huán)中循環(huán)體語句可能一次都不執(zhí)行，而dowhile循環(huán)體語句則至少執(zhí)行一次。④dowhile循環(huán)可以轉(zhuǎn)化成為while循環(huán)，但while型循環(huán)不一定能轉(zhuǎn)化為dowhile型循環(huán)。將dowhile循環(huán)轉(zhuǎn)化成while循環(huán)，如圖所示。4.3算法的描述【例4-4】計算并輸出z=x/y的值。流程圖表示：4.3算法的描述【例4-6】求和sum=1+2+3+4+5+……+n，輸出sum的值。流程圖表示：4.4算法設(shè)計范例【例4-7】輸入三個整數(shù)a，b，c，找出其中最小值并輸出。自然語言描述：S1：輸入三個整數(shù)a,b,c；S2：比較a和b的值，將a,b中較小的值賦值給min；S3：比較min和c的值，如果c<min，則將c的值賦給min；S4:輸出min；S5:算法結(jié)束。流程圖表示：4.4算法設(shè)計范例【例4-8】輸入一個正整數(shù)n，求出1+1/2+1/3+……+1/n的值。自然語言描述：S1：給定一個大于0的正整數(shù)n的值；S2：定義一個整型變量i，設(shè)其初始值1；S3：定義整型變量sum，其初始值設(shè)置為0；S4：如果i小于等于n，則轉(zhuǎn)到第5步，否則轉(zhuǎn)到第8步；S5：將sum的值加上1/i的值后，重新賦值給sum；S6：將i的值加1，重新賦值給i；S7：轉(zhuǎn)到第4步；S8：輸出