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

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

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

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

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

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

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

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