計(jì)算機(jī)科學(xué)導(dǎo)論-數(shù)據(jù)結(jié)構(gòu)與算法綜述

1、第第5講講 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 理解數(shù)據(jù)結(jié)構(gòu)的概念，理解數(shù)據(jù)結(jié)構(gòu)的邏輯和存儲(chǔ)結(jié)構(gòu)； 理解算法的概念和算法的基本特性，了解算法復(fù)雜度的度量方法； 理解線性數(shù)據(jù)結(jié)構(gòu)，理解順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)方法； 描述棧和隊(duì)列、串和數(shù)組這幾個(gè)線性數(shù)據(jù)結(jié)構(gòu)的概念； 了解非線性的數(shù)據(jù)結(jié)構(gòu)，了解樹、二叉樹以及圖的概念和數(shù)據(jù)結(jié)構(gòu)； 理解排序的概念，描述插入、選擇、氣泡和快速排序的算法； 理解查找的概念，描述順序查找和折半查找的算法，并能夠比較它們 理解遞歸的概念，能夠在實(shí)踐中了解遞歸的應(yīng)用。 教 學(xué) 目目 的的學(xué)學(xué) 習(xí)習(xí) 重重 點(diǎn)點(diǎn) 數(shù)據(jù)結(jié)構(gòu)的基本概念 算法的描述、流程圖的使用以及算法的復(fù)雜度的衡量 順序存

2、儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的方法 棧、隊(duì)列、串和數(shù)組的概念和用法 二叉樹數(shù)據(jù)結(jié)構(gòu) 查詢、排序和遞歸算法第一節(jié)第一節(jié) 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述1. 1. 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述1. 數(shù)據(jù)結(jié)構(gòu)概述1.2 數(shù)據(jù)結(jié)構(gòu)相關(guān)概念基本概念和術(shù)語數(shù)據(jù)元素、結(jié)點(diǎn)、數(shù)據(jù)項(xiàng)、關(guān)鍵字或主關(guān)鍵字、 次關(guān)鍵字、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 特性相同的數(shù)據(jù)元素構(gòu)成的集合中，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱之為數(shù)據(jù)結(jié)構(gòu) 。 Data-Structure=(D,R) 其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。1. 數(shù)據(jù)結(jié)構(gòu)概述1. 數(shù)據(jù)結(jié)構(gòu)概述四類基本的數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集

3、合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)，各元素間沒有直接的關(guān)聯(lián)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的關(guān)系。圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。 123456 例例5-2 5-2 線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)=(D,S)=(D,S) D=1,2,3,4,5,6,7,8,9,10 D=1,2,3,4,5,6,7,8,9,10 S=,S=, , ,1. 數(shù)據(jù)結(jié)構(gòu)概述例5-3 圖形數(shù)據(jù)結(jié)構(gòu)=(D,R) D=1, 2, 3, 4, 5, 6, 7, 8, 9 R=, ,1. 數(shù)據(jù)結(jié)構(gòu)概述 例例5-4 樹形結(jié)構(gòu)樹形

4、結(jié)構(gòu) =（D,R） D=a, b, c, d, e, f, g, h, i, j, k, l R=, ,1. 數(shù)據(jù)結(jié)構(gòu)概述1.3 數(shù)據(jù)結(jié)構(gòu)的分類按數(shù)據(jù)結(jié)構(gòu)的性質(zhì)劃分 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系 （設(shè)計(jì)算法 數(shù)學(xué)模型） 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的映像 （存儲(chǔ)結(jié)構(gòu)，算法的實(shí)現(xiàn)）按數(shù)據(jù)結(jié)構(gòu)的操作來劃分 靜態(tài)結(jié)構(gòu)經(jīng)過操作后，數(shù)據(jù)的結(jié)構(gòu)特征保持不變（如數(shù)組）。 半靜態(tài)結(jié)構(gòu)經(jīng)過操作后，數(shù)據(jù)的結(jié)構(gòu)特性只允許很小變遷（如棧、隊(duì)列）。 動(dòng)態(tài)結(jié)構(gòu)經(jīng)過操作后，數(shù)據(jù)的結(jié)構(gòu)特性變化比較靈活，可隨機(jī)地重新組織結(jié)構(gòu)（如指針）。1. 數(shù)據(jù)結(jié)構(gòu)概述1.3 數(shù)據(jù)結(jié)構(gòu)的分類按數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式來劃分 順

5、序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器的相對位置來表示數(shù)據(jù)元素之 的邏輯關(guān)系。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間 的邏輯關(guān)系 索引存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)結(jié)點(diǎn)的同時(shí)，建立附加 的索引表，索引表 中的每一項(xiàng)稱為索引項(xiàng)，形式為：關(guān)鍵字，地址。 散列存儲(chǔ)結(jié)構(gòu)根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。 說明：四種存儲(chǔ)方法可結(jié)合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。1. 數(shù)據(jù)結(jié)構(gòu)概述1.4 算法及其描述和算法分析1、算法的概念及特征算法: 對問題求解的描述，為解決問題給出的一個(gè)確定的、有限長的操作序列算法具有以下五個(gè)重要的特征： 1）有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束。 2）確切性：算法的每一步驟必須有

6、確切的定義。 3）輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件。 4）輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法沒有實(shí)際意義。 5）可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。1. 數(shù)據(jù)結(jié)構(gòu)概述1.4 算法及其描述和算法分析算法的描述: 1）流程圖 2）偽代碼類程序設(shè)計(jì)語言算法的基本結(jié)構(gòu) :1）順序結(jié)構(gòu) 2）分支結(jié)構(gòu) 3）循環(huán)結(jié)構(gòu)1. 數(shù)據(jù)結(jié)構(gòu)概述1. 數(shù)據(jù)結(jié)構(gòu)概述 算法基本結(jié)構(gòu)示意圖算法基本結(jié)構(gòu)示意圖1.4 算法及其描述和算法分析算法效率衡量方法與準(zhǔn)則 :時(shí)間復(fù)雜度：指算法從開

7、始執(zhí)行到處理結(jié)束所需要的總時(shí)間。 T（n）= O（f(n)）空間復(fù)雜度：指算法從開始執(zhí)行到處理結(jié)束所需的存儲(chǔ)量空間的總和。 S（n）= O（g(n)）1. 數(shù)據(jù)結(jié)構(gòu)概述1. 數(shù)據(jù)結(jié)構(gòu)概述第二節(jié) 線性結(jié)構(gòu)2.1 線性表線性表的定義 線性表是n(n=0)個(gè)數(shù)據(jù)元素的有限序列，表中各個(gè)元素具有相同的屬性，表中相鄰元素間存在“序偶”關(guān)系。 記做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，ai-1稱為ai 的直接前驅(qū)元素，ai+1是ai的直接后繼元素 線性表的長度：表中的元素個(gè)數(shù) n 位序：i稱元素ai在線性表中的位序2. 線性結(jié)構(gòu)2.1 線性表線性表的順序表示和實(shí)現(xiàn) 線性表的

8、順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素，用這種存儲(chǔ)形式存儲(chǔ)的線性表稱其為順序表。 2. 線性結(jié)構(gòu)2.1 線性表線性表的順序表示和實(shí)現(xiàn) 順序表線性表的順序存儲(chǔ)表示 Const LIST_INIT_SIZE=100; (C+規(guī)范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C規(guī)范) Typedef Struct Elemtype * elem;Int length;Intlistsize;Int incrementsize; SqList;2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2.1 線性表線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 鏈表

9、是通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù)元素之間的關(guān)系，對每個(gè)數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼ai+1所在的存貯單元的地址，這兩部分信息組成一個(gè)“節(jié)點(diǎn)”。 2. 線性結(jié)構(gòu)2.1 線性表線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)表示 F 數(shù)據(jù)域（data）和指針域（next） F 存儲(chǔ)表示typedef struct LnodeElemTypedata;Struct Lnode*next;Lnode, *LinkList; 2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)堆棧結(jié)構(gòu)示意圖堆棧結(jié)構(gòu)示意圖2. 線性結(jié)構(gòu)2

10、. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)2. 線性結(jié)構(gòu)第三節(jié) 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)典型的樹結(jié)構(gòu)典型的樹結(jié)構(gòu)3. 非線性結(jié)構(gòu)二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 2.2.二叉樹二叉樹 滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹 滿二叉樹（滿二叉樹（full binary treefull binary tree）：所有結(jié)點(diǎn)度為）：所有結(jié)點(diǎn)度為2 2，葉子結(jié)，葉子結(jié)點(diǎn)在同一層次。點(diǎn)在同一層次。 完全二叉樹（完全二叉樹（complete binary treecomplete binary tree）：一棵深度為）：一棵深度為k k

11、的有的有n n個(gè)節(jié)點(diǎn)的二叉樹，對樹中的節(jié)點(diǎn)按從上至下、從左到右的順序個(gè)節(jié)點(diǎn)的二叉樹，對樹中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為進(jìn)行編號(hào)，如果編號(hào)為i i（1in1in）的節(jié)點(diǎn)與滿二叉樹中編號(hào)）的節(jié)點(diǎn)與滿二叉樹中編號(hào)為為i i的節(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉的節(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。樹。 3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3.2 圖圖圖的定義與相關(guān)概念圖的定義與相關(guān)概念 圖的相關(guān)概念圖的相關(guān)概念弧弧(arc)(arc)、弧頭（終點(diǎn)）、弧尾（起點(diǎn)）：、弧頭（終點(diǎn)）、弧尾（起點(diǎn)）：表示從表示從v v到到w

12、 w的弧的弧 有向圖有向圖(digraph) (digraph) 、無向圖、無向圖(undigraph) (undigraph) 、邊、邊: : (v,w)(v,w)代表代表和和 有向網(wǎng)、無向網(wǎng)：有向網(wǎng)、無向網(wǎng)：帶權(quán)的有向圖和無向圖帶權(quán)的有向圖和無向圖 完全圖（完全圖（complete graphcomplete graph）：邊）：邊e e為為n(n-1)/2n(n-1)/2有向完全圖：弧有向完全圖：弧e e為為n(n-1)n(n-1) 3. 非線性結(jié)構(gòu)3. 非線性結(jié)構(gòu)3 非線性結(jié)構(gòu)一、一、算法概念算法概念二、二、算法結(jié)構(gòu)算法結(jié)構(gòu)三三、算法表示算法表示（流程圖、偽代碼、（流程圖、偽代碼、N-

13、SN-S圖等）圖等）四、四、基本基本算法算法（計(jì)數(shù)，累加，值交換，求最（計(jì)數(shù)，累加，值交換，求最大（?。┲担F舉、迭代、遞推、遞歸）大（小）值，窮舉、迭代、遞推、遞歸） 1.1.算法的定義算法的定義 為解決問題而采取的方法和步驟。（非為解決問題而采取的方法和步驟。（非正式）正式） 算法是一組明確步驟的有序集合，它產(chǎn)算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時(shí)間內(nèi)終止。（正式）生結(jié)果并在有限的時(shí)間內(nèi)終止。（正式） 2. 2. 算法的分類算法的分類計(jì)算機(jī)算法可分為兩大類：計(jì)算機(jī)算法可分為兩大類： 數(shù)值運(yùn)算算法：數(shù)值運(yùn)算算法： 求解數(shù)值求解數(shù)值 非數(shù)值運(yùn)算算法：非數(shù)值運(yùn)算算法： 事務(wù)管理事務(wù)

14、管理例例 1:1: 數(shù)值計(jì)算問題：數(shù)值計(jì)算問題：結(jié)構(gòu)靜力分析計(jì)算結(jié)構(gòu)靜力分析計(jì)算需要解需要解線性線性代數(shù)方程組代數(shù)方程組。例例 2:2: 非數(shù)值計(jì)算問題：非數(shù)值計(jì)算問題：計(jì)算機(jī)對弈計(jì)算機(jī)對弈 算法算法對弈的規(guī)則和策略對弈的規(guī)則和策略 模型模型棋盤及棋盤的格局棋盤及棋盤的格局 3. 3.算法的基本特征算法的基本特征有窮性有窮性：任何算法都會(huì)在有限步后終止；：任何算法都會(huì)在有限步后終止；確定性確定性：算法的每一步都有唯一的含義；：算法的每一步都有唯一的含義；有效性有效性：算法的每一步都可以被執(zhí)行；：算法的每一步都可以被執(zhí)行；有輸入有輸入：可以有多個(gè)輸入，也可能沒有輸：可以有多個(gè)輸入，也可能沒有輸入

15、；入；有輸出有輸出：算法至少有一個(gè)輸出結(jié)果。：算法至少有一個(gè)輸出結(jié)果。 4.4.算法設(shè)計(jì)的原則算法設(shè)計(jì)的原則正確性：正確性：對于一切合法的輸入數(shù)據(jù)都能得對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果。出滿足要求的結(jié)果?？勺x性：可讀性：算法應(yīng)該易理解，便于交流。算法應(yīng)該易理解，便于交流。健壯性：健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)恰當(dāng)當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理。地作出反應(yīng)或進(jìn)行相應(yīng)處理。高效率與低存儲(chǔ)量需求：高效率與低存儲(chǔ)量需求：算法執(zhí)行時(shí)間較算法執(zhí)行時(shí)間較少，算法執(zhí)行所需存儲(chǔ)空間較小。少，算法執(zhí)行所需存儲(chǔ)空間較小。 定義動(dòng)作定義動(dòng)作 確定一系列的步驟，每一步都只完成一確定一

16、系列的步驟，每一步都只完成一個(gè)動(dòng)作。個(gè)動(dòng)作。 精化精化 剔除重復(fù)的步驟；剔除重復(fù)的步驟； 不同的步驟完成的動(dòng)作可能相同，但它不同的步驟完成的動(dòng)作可能相同，但它 們產(chǎn)生的結(jié)果不能相同。們產(chǎn)生的結(jié)果不能相同。 泛化泛化使算法對盡可能多的具體問題具有適應(yīng)性。使算法對盡可能多的具體問題具有適應(yīng)性。5.5.如何設(shè)計(jì)一個(gè)算法如何設(shè)計(jì)一個(gè)算法例例1 1：從一組正整數(shù)中找到最大的數(shù)。從一組正整數(shù)中找到最大的數(shù)。 （正整數(shù)個(gè)數(shù)（正整數(shù)個(gè)數(shù)2 2，3 3， N N）例如, 12, 8; 12, 8, 13; 12, 8, 13, 9; 12, 8, 13, 9, 11, . 方法方法1 1：第一步第一步: : 比

17、較第一個(gè)數(shù)和第二個(gè)數(shù)比較第一個(gè)數(shù)和第二個(gè)數(shù); ;第二步第二步: : 比較第一個(gè)數(shù)和第三個(gè)數(shù)比較第一個(gè)數(shù)和第三個(gè)數(shù); ;第三步第三步: : 比較第二個(gè)數(shù)和第三個(gè)數(shù)比較第二個(gè)數(shù)和第三個(gè)數(shù); ;方法方法2：第一步：第一步：將最大值置為第一個(gè)數(shù)；將最大值置為第一個(gè)數(shù)；第二步：第二步：將第二個(gè)數(shù)和最大值進(jìn)行比較，如果第將第二個(gè)數(shù)和最大值進(jìn)行比較，如果第二個(gè)數(shù)大于最大值，將最大值置為第二個(gè)數(shù)，二個(gè)數(shù)大于最大值，將最大值置為第二個(gè)數(shù)，反之保持最大值不變。反之保持最大值不變。第三步：第三步：將第三個(gè)數(shù)和最大值進(jìn)行比較，如果第將第三個(gè)數(shù)和最大值進(jìn)行比較，如果第三個(gè)數(shù)大于最大值，將最大值置為第三個(gè)數(shù)，三個(gè)數(shù)大于最

18、大值，將最大值置為第三個(gè)數(shù)，反之保持最大值原值不變。反之保持最大值原值不變。第二、第二、三步程三步程序功能序功能相同，相同，程序描程序描述語言述語言相似相似和第二、三步不同和第二、三步不同方法方法3：第零步：第零步：將最大值置為零；將最大值置為零；第一步：第一步：如果當(dāng)前數(shù)大于最大值，那么將最如果當(dāng)前數(shù)大于最大值，那么將最大值置為當(dāng)前數(shù)，否則保留原最大值；大值置為當(dāng)前數(shù)，否則保留原最大值；第二步：第二步：重復(fù)第一步直至所有數(shù)全比較完。重復(fù)第一步直至所有數(shù)全比較完。 任何算法（或程序）都由三種基本結(jié)構(gòu)組成任何算法（或程序）都由三種基本結(jié)構(gòu)組成： 順序結(jié)構(gòu)順序結(jié)構(gòu) 判斷（選擇）結(jié)構(gòu)判斷（選擇）結(jié)構(gòu)

19、 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 任何算法都是上述三種結(jié)構(gòu)的組合。任何算法都是上述三種結(jié)構(gòu)的組合。1. 1. 順序結(jié)構(gòu)順序結(jié)構(gòu)S1S22. 2. 選擇結(jié)構(gòu)選擇結(jié)構(gòu)60N條件條件S1S2Y 雙選擇結(jié)構(gòu)雙選擇結(jié)構(gòu)N條件條件S1Y單選擇結(jié)構(gòu)單選擇結(jié)構(gòu)3. 3. 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)61 條件條件A 塊塊NY直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)條件條件A 塊塊YN 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)三種基本結(jié)構(gòu)的特點(diǎn)：三種基本結(jié)構(gòu)的特點(diǎn)： 一個(gè)入口一個(gè)入口 一個(gè)出口一個(gè)出口 不出現(xiàn)死循環(huán)和死語句不出現(xiàn)死循環(huán)和死語句6263T+I TI10YN1I，0 K, 0 TK10YNT+K T64T+I TI10YN1I，0 K, 0 TK10Y

20、NT+K T死死循循環(huán)環(huán)死死語語句句65用順序結(jié)構(gòu)描述將華氏溫用順序結(jié)構(gòu)描述將華氏溫度度F F轉(zhuǎn)換成攝氏溫度轉(zhuǎn)換成攝氏溫度C C的流的流程。程。算法：算法：C=5/9*（F-32）4. 4. 順序結(jié)構(gòu)設(shè)計(jì)順序結(jié)構(gòu)設(shè)計(jì)順序結(jié)構(gòu)中，按語句的自順序結(jié)構(gòu)中，按語句的自然順序依次執(zhí)行。然順序依次執(zhí)行。開始開始5/9 bb*(F-32)C輸出輸出F F，C C結(jié)束結(jié)束輸入輸入F F66已知三角形的已知三角形的3 3條邊邊長，求條邊邊長，求三角形面積。用順序結(jié)構(gòu)描三角形面積。用順序結(jié)構(gòu)描述求三角形面積的流程。述求三角形面積的流程。開始開始(a+b+c)/2 ss*(s-a)*(s-b)*(s-c) t輸出輸

21、出areaarea結(jié)束結(jié)束輸入輸入a,b,ca,b,careat 用順序結(jié)構(gòu)描述兩個(gè)值用順序結(jié)構(gòu)描述兩個(gè)值（a=1, b=2a=1, b=2）交換的流程）交換的流程 12bca1開始開始1 1a a，2 2b ba bb a 輸出輸出a a，b b結(jié)束結(jié)束a cb ac b2112ab21選擇結(jié)構(gòu)（分支選擇結(jié)構(gòu)（分支結(jié)構(gòu)），根據(jù)選結(jié)構(gòu)），根據(jù)選擇結(jié)構(gòu)中判斷的擇結(jié)構(gòu)中判斷的結(jié)果，選擇執(zhí)行結(jié)果，選擇執(zhí)行相應(yīng)的語句。相應(yīng)的語句。5. 5. 選擇結(jié)構(gòu)及其程序設(shè)計(jì)選擇結(jié)構(gòu)及其程序設(shè)計(jì)開始開始輸出輸出 MAXMAX結(jié)束結(jié)束輸入輸入R,HR MAXH MAXRHYN例例 用選擇用選擇結(jié)構(gòu)結(jié)構(gòu)描述求描述求兩個(gè)

22、數(shù)中兩個(gè)數(shù)中的最大值的流程的最大值的流程例例 用選擇結(jié)構(gòu)描用選擇結(jié)構(gòu)描述檢查某年是否閏述檢查某年是否閏年的流程。年的流程。X X年為閏年滿足下年為閏年滿足下列條件之一：列條件之一：1.N1.N能被能被400400整除整除2.N2.N能被能被4 4整除，但整除，但不能被不能被100100整除整除開始開始輸出輸出 X X YESYES結(jié)束結(jié)束輸入輸入XX被被400整除整除YNX被被4整除整除YNX被被100整除整除YN輸出輸出 X X NONO用選擇結(jié)構(gòu)描述用選擇結(jié)構(gòu)描述檢查某成績級(jí)別檢查某成績級(jí)別的流程。的流程。成績成績N N的級(jí)別：的級(jí)別：A A級(jí)級(jí)-X90-X90B B級(jí)級(jí)90X8090X8

23、0C C級(jí)級(jí)80X6080X60D D級(jí)級(jí)X60X60開始開始輸出輸出 X-X-A A結(jié)束結(jié)束輸入輸入XX 9090YNX 80YNYNX 60輸出輸出 X-X-B B 輸出輸出 X-X-C C輸出輸出 X-X-D D循環(huán)結(jié)構(gòu)：當(dāng)循環(huán)控制條循環(huán)結(jié)構(gòu)：當(dāng)循環(huán)控制條件為真時(shí)反復(fù)執(zhí)行循環(huán)體件為真時(shí)反復(fù)執(zhí)行循環(huán)體中的語句，直到循環(huán)控制中的語句，直到循環(huán)控制條件為假時(shí)為止。條件為假時(shí)為止。開始開始輸出輸出 T T 的值的值結(jié)束結(jié)束輸入輸入KT+K TI+1 II10YN1I，0 T累加器累加器計(jì)數(shù)器計(jì)數(shù)器用循環(huán)結(jié)構(gòu)描述求用循環(huán)結(jié)構(gòu)描述求1010個(gè)個(gè)學(xué)生成績之和的流程學(xué)生成績之和的流程用用T T累計(jì)累計(jì)1

24、010個(gè)學(xué)生的成績（個(gè)學(xué)生的成績（K K），），用用I I記錄累加的次數(shù)記錄累加的次數(shù)（I=1,2,I=1,2,10,10）6.6.循環(huán)結(jié)構(gòu)及其程序設(shè)計(jì)循環(huán)結(jié)構(gòu)及其程序設(shè)計(jì)例例 用循環(huán)結(jié)構(gòu)描述用循環(huán)結(jié)構(gòu)描述求求1010到到100100之間所之間所有不能被有不能被3 3整除的整整除的整數(shù)的流程數(shù)的流程開始開始結(jié)束結(jié)束I+1 II100YN10II不能被不能被3整除整除輸出輸出 IYN對對1010到到100100之間所之間所有數(shù)逐一驗(yàn)證，凡有數(shù)逐一驗(yàn)證，凡滿足滿足“不能被不能被3 3整除整除”的整數(shù)即可輸出。的整數(shù)即可輸出。循環(huán)嵌套結(jié)構(gòu)循環(huán)嵌套結(jié)構(gòu)：一個(gè)循環(huán)結(jié)構(gòu)一個(gè)循環(huán)結(jié)構(gòu)的循環(huán)體中又的循環(huán)體中又

25、出現(xiàn)另一個(gè)循出現(xiàn)另一個(gè)循環(huán)結(jié)構(gòu)。環(huán)結(jié)構(gòu)。 外循環(huán)外循環(huán) 內(nèi)循環(huán)內(nèi)循環(huán)J+1 JI3YN1I輸出IJ21J輸出JI+1 IYNI=1，輸出1 J=1，輸出1 J=2，輸出2I=2，輸出2 J=1，輸出1 J=2，輸出2I=3，輸出3 J=1，輸出1 J=2，輸出274例例 打印邊長為打印邊長為 m m 的正方型的正方型要求：從鍵盤輸入要求：從鍵盤輸入 m m 值，輸出值，輸出 m m 行每行行每行 m m 個(gè)個(gè)* *號(hào)。號(hào)。例：輸入例：輸入 m=4m=4，輸出的圖形如下：，輸出的圖形如下：* * * * * * * * * * * * * * * * * * * * * * * * * * *

26、* *算法：算法：1. 1. 輸入輸入 m m 2. 2. 重復(fù)重復(fù)打印打印 m m 行，每行打印行，每行打印 m m 個(gè)個(gè) * *開始開始結(jié)束結(jié)束輸入輸入MI+1 IIMYN1I 對行循環(huán)對行循環(huán)(I=1,2,，M) 對對I行的各列循行的各列循環(huán)環(huán)(J=1,2,，M)輸出輸出 * * J+1 JJMYN1 J換行換行輸出輸出I行的行的M個(gè)個(gè)* *I=1，J=1 輸出 * * J=2 輸出 * * J=3 輸出 * * J=4 輸出 * * 換行I=2 J=1，2，3，4 * *I=4 J=1，2，3，4 * * * *77例例 從鍵盤輸入從鍵盤輸入n n值，輸出值，輸出n n行用行用* *號(hào)

27、組成等腰三角號(hào)組成等腰三角形。例：輸入形。例：輸入 n=4n=4，輸出的圖形如下：，輸出的圖形如下：* * * * * * * * * * * * * * k=1,n-1=3個(gè)空，2*1-1=1個(gè)* * * * k=2,n-2=2個(gè)空，2*2-1=3個(gè)* * * * * * k=3,n-3=1個(gè)空，2*3-1=5個(gè)* * * * * * * k=4,n-4=0個(gè)空，2*4-1=7個(gè)*共共n n行，其中第行，其中第K K行由行由n-kn-k個(gè)空格個(gè)空格和和2k-12k-1個(gè)個(gè)* *組成組成 分析：分析： 1 1、輸出、輸出 n n 行。行。 2 2、圖形的第、圖形的第 k k 行行(1=(1=k

28、 k=n n) )由由 n n- -k k個(gè)個(gè) 空格空格 和和 2 2k k-1 -1 個(gè)個(gè) * * 組成。組成。算法設(shè)計(jì)：算法設(shè)計(jì)：1.1.輸入輸入 n n; ;2.2.重復(fù)重復(fù)輸出輸出n n行。對于第行。對于第 k k 行，行，每行輸出每行輸出n n- -k k 個(gè)空格個(gè)空格和和 2 2k k-1 -1 個(gè)個(gè)* * 開始開始結(jié)束結(jié)束輸入輸入nk+1 kknYN1k 對行循環(huán)對行循環(huán)(k=1,2,，n)輸出空輸出空J(rèn)+1 JJn-kYN1 J輸出輸出 * * J+1 JJ2k-1YN1 J換行換行 對每個(gè)對每個(gè)k行行各列循環(huán)，各列循環(huán)，輸出輸出n-k個(gè)空個(gè)空格和格和2k-1個(gè)個(gè)* 自然語言自

29、然語言 流程圖流程圖 偽代碼偽代碼 結(jié)構(gòu)圖結(jié)構(gòu)圖 N-SN-S結(jié)構(gòu)圖結(jié)構(gòu)圖 PADPAD結(jié)構(gòu)圖結(jié)構(gòu)圖 計(jì)算機(jī)語言計(jì)算機(jī)語言 用規(guī)定的一系列圖形、流程線和文用規(guī)定的一系列圖形、流程線和文字說明算法中的基本操作和控制流程。字說明算法中的基本操作和控制流程。流程圖包括：流程圖包括： 表示相應(yīng)操作的框；表示相應(yīng)操作的框； 帶箭頭的流程線；帶箭頭的流程線； 框內(nèi)外必要的文字說明?？騼?nèi)外必要的文字說明。1. 1. 流程圖流程圖（1 1）圖形符號(hào)）圖形符號(hào)起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框注釋框注釋框流向線流向線連接點(diǎn)連接點(diǎn)例：求給定半徑例：求給定半徑R R的的圓面積和圓周長。圓面積

30、和圓周長。算法：算法：圓面積圓面積 S=S=* R2 2圓周長圓周長 L=2L=2* *R開始開始輸出輸出 S S、L L的值的值結(jié)束結(jié)束輸入半徑輸入半徑R*R*R S2*R L順序順序（2 2）用流程圖表示算法）用流程圖表示算法例：例：求給定數(shù)求給定數(shù)R R的絕對值。的絕對值。算法算法：|R|= R R|R|= R R0 -R R0-R R0開始開始輸出輸出 S S的值的值結(jié)束結(jié)束輸入輸入RR S-R SR0YN選擇選擇求求 S=1+2+3+.+1000s;s+1ss+2 s.s+100 s0ss+i s(循環(huán)體循環(huán)體)(i=1,2,.,100)例例: : 給定給定K K值，求值，求T=1+

31、2+3+T=1+2+3+K+K。K=5，T=0I=1：T=0+1=1，I=1+1=2I=2：T=1+2=3，I=2+1=3I=3：T=3+3=6，I=3+1=4I=4：T=6+4=10，I=4+1=5I=5：T=10+5=15，I=5+1=60 0 T TT+IT+I T(I=1,2,3,T(I=1,2,3,K)K)開始開始輸出輸出 T T 的值的值結(jié)束結(jié)束輸入輸入KT+I TI+1 IIKYN1I，0 T循循環(huán)環(huán) 由于流程線的任意轉(zhuǎn)向性，傳統(tǒng)流程圖由于流程線的任意轉(zhuǎn)向性，傳統(tǒng)流程圖無法保證自頂向下的程序設(shè)計(jì)，使模塊之間無法保證自頂向下的程序設(shè)計(jì)，使模塊之間的調(diào)用關(guān)系難以表達(dá)。故兩位美國學(xué)者的

32、調(diào)用關(guān)系難以表達(dá)。故兩位美國學(xué)者NassiNassi和和ShneidermanShneiderman于于19731973年提出了無流程線的年提出了無流程線的N-N-S S流程圖流程圖。 2. 2. N NS S流程圖流程圖S1S2流程圖流程圖S1S2N-S流程圖流程圖（1 1）圖形符號(hào)）圖形符號(hào)YNS1 S2 條件條件流程圖流程圖條件條件YNS1 S2N-S流程圖流程圖YN循環(huán)體循環(huán)體 條件條件流程圖流程圖循環(huán)體循環(huán)體循環(huán)條件循環(huán)條件N-S流程圖流程圖流程圖流程圖NY循環(huán)體循環(huán)體 條件條件循環(huán)體循環(huán)體循環(huán)條件循環(huán)條件N NS S流程圖流程圖（2 2）用）用N-SN-S流程圖表示算法流程圖表示算

33、法輸入半徑輸入半徑R輸出輸出 S S、L L的值的值*R*R S2*R L例：求給定半徑例：求給定半徑R R的圓面積和圓周長的圓面積和圓周長開始開始輸出輸出 S S、L L的值的值結(jié)束結(jié)束輸入半徑輸入半徑R*R*R S2*R L順序順序開始開始輸出輸出 S S的值的值結(jié)束結(jié)束輸入輸入RR S-R SR0YN選擇選擇輸入輸入R輸出輸出 S S的值的值R S - R S Y R 0 N例：求給定數(shù)例：求給定數(shù)R R的絕對值的絕對值例例: : 給定給定K K值，求值，求T=1+2+3+T=1+2+3+K+K開始開始輸出輸出 T T 的值的值結(jié)束結(jié)束輸入輸入KT+I TI+1 IIKYN1I，0 T循

34、循環(huán)環(huán)輸入輸入K輸出輸出 T T 的值的值IK 1 1I，0 TT+I TI+1 I 偽代碼是算法的一種類似英語的表示法。偽代碼是算法的一種類似英語的表示法。它是部分英語和部分結(jié)構(gòu)化代碼的組合。它是部分英語和部分結(jié)構(gòu)化代碼的組合。英文代碼部分采用不嚴(yán)格的語法，很容英文代碼部分采用不嚴(yán)格的語法，很容易看懂；易看懂；代碼部分包含基本算法結(jié)構(gòu)（順序、選代碼部分包含基本算法結(jié)構(gòu)（順序、選擇和循環(huán)）的擴(kuò)展形式。擇和循環(huán)）的擴(kuò)展形式。 目前還沒有偽代碼的標(biāo)準(zhǔn)。目前還沒有偽代碼的標(biāo)準(zhǔn)。3. 3. 偽代碼偽代碼偽代碼描述算法的一般組成：偽代碼描述算法的一般組成：算法頭：算法頭：算法的名字。算法的名字。目的、條

35、件和返回值：目的、條件和返回值： 目的目的：有關(guān)算法要做什么的簡短說明：有關(guān)算法要做什么的簡短說明 前置條件前置條件：列出算法所有前驅(qū)條件：列出算法所有前驅(qū)條件 后置條件后置條件：指出算法產(chǎn)生的影響：指出算法產(chǎn)生的影響 返回值返回值：算法返回的結(jié)果或無返回值：算法返回的結(jié)果或無返回值語句序號(hào)：語句序號(hào)：表示語句之間的附屬關(guān)系。表示語句之間的附屬關(guān)系。例：用偽代碼描述在一例：用偽代碼描述在一數(shù)列中找最小值的算法數(shù)列中找最小值的算法Algorithm Algorithm （算法）：（算法）：Finding SmallestFinding SmallestPurposePurpose（目的）：（目的

36、）：在一數(shù)列中找最小值在一數(shù)列中找最小值PrePre（前置條件）：（前置條件）：List of numbersList of numbers（數(shù)列）（數(shù)列）PostPost（后置條件）：（后置條件）：NoneNoneReturnReturn（返回值）：（返回值）：The smallestThe smallest32416a:S3 2 1算法：算法：設(shè)數(shù)列中第一個(gè)數(shù)為最設(shè)數(shù)列中第一個(gè)數(shù)為最小值小值S S，然后用后續(xù)數(shù)依次與，然后用后續(xù)數(shù)依次與S S比較，若比比較，若比S S小，則用該數(shù)替換小，則用該數(shù)替換原原S S的值，全部比較完成后的值，全部比較完成后S S即即最小值。最小值。1.Set sm

37、allest to the first number1.Set smallest to the first number2.Loop(not end of list)2.Loop(not end of list) 2.1 if(next number smallest)2.1 if(next number smallest) 2.1.1 set smallest to next2.1.1 set smallest to next number number 2.2 end if2.2 end if3. end loop3. end loop4. return smallest4. return

38、 smallestEnd Finding SmallestEnd Finding Smallest數(shù)列數(shù)列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值S1. 1. 數(shù)列數(shù)列ai ( i=1,5 )2.2. a1 S, 2 i3. while(i3. while(i5) ) 3.1 if if( (aiS ) then ai S endif 3.2 i+1i end while end while 4.4. return Sreturn S偽代碼不一定按上述嚴(yán)格的格式，且可以偽代碼不一定按上述嚴(yán)格的格式，且可以使用漢字，只要把算法表達(dá)清楚即可。使

39、用漢字，只要把算法表達(dá)清楚即可。數(shù)列數(shù)列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值Ss=a1; i=2;while(iwhile(i=5) ) if( if(ais ) s = ai; i= i+1; return s;return s;數(shù)列數(shù)列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值S4. 4. 計(jì)算機(jī)語言計(jì)算機(jī)語言 計(jì)數(shù)計(jì)數(shù) 累加累加 值交換值交換 求最大（?。┲登笞畲螅ㄐ。┲?窮舉窮舉 迭代迭代 遞推遞推 遞歸遞歸基本思想基本思想首先根據(jù)問題的部分條件預(yù)估計(jì)出答案的范圍首先根據(jù)問題的

40、部分條件預(yù)估計(jì)出答案的范圍在預(yù)估計(jì)的答案范圍內(nèi)，對所有可能的情況逐在預(yù)估計(jì)的答案范圍內(nèi)，對所有可能的情況逐一驗(yàn)證。一驗(yàn)證。若某個(gè)情況使驗(yàn)證符合題目的全部條件，則該若某個(gè)情況使驗(yàn)證符合題目的全部條件，則該情況是本題目的一個(gè)答案。情況是本題目的一個(gè)答案。分析：分析： 假設(shè)假設(shè)a,ba,b分別代表父親和兒子的年齡，分別代表父親和兒子的年齡，x x年后年后a=2ba=2b。根據(jù)人的壽命，根據(jù)人的壽命，x x取值為：取值為：1,2,1,2,150,150 問題問題：父親今年：父親今年3030歲，兒子今年歲，兒子今年6 6歲，在父親有生之歲，在父親有生之年中，多少年后父親的年齡是兒子的年中，多少年后父親的

41、年齡是兒子的2 2倍？倍？算法：算法：1. 1. 考察考察x x可能的范圍：可能的范圍：x=1x=1，2 2，150150；2. 30+x2. 30+xa a, 6+x, 6+xb b3. 3. 若若a=2ba=2b，則輸出，則輸出x x。開始開始結(jié)束結(jié)束輸出輸出a,b,xa,b,xx+1 xx150YN0 xa =2bYN30+x a6+x bX X年后，父親年后，父親和兒子的年齡和兒子的年齡105分析：分析： 對對5 5本書從本書從1 1至至5 5編號(hào)，假設(shè)編號(hào)，假設(shè)a,ba,b兩個(gè)人分別借這兩個(gè)人分別借這5 5本本書中的書中的1 1本。當(dāng)本。當(dāng)a=ia=i時(shí)，表示時(shí)，表示a a借了編號(hào)為

42、借了編號(hào)為i i的書。的書。則則a a、b b的取值范圍為：的取值范圍為：1 = 1 = a a、b= 5b= 5 當(dāng)當(dāng)2 2個(gè)人所借的書的編號(hào)不相同時(shí)（個(gè)人所借的書的編號(hào)不相同時(shí)（a!=ba!=b） ，就是滿足題意的一種借閱方法。就是滿足題意的一種借閱方法。問題問題：小明有：小明有5 5本新書，要借給、兩位小朋友，本新書，要借給、兩位小朋友，若每人每次只能借一本，則可有多少種不同的借法？若每人每次只能借一本，則可有多少種不同的借法？算法：算法：1.1.考察考察a a可能的范圍：可能的范圍：a=1a=1，2 2，3 3，4 4，5 5；2.2.考察考察b b可能的范圍：可能的范圍：b=1b=1，2 2，3 3，4 4，5;5;3.3.驗(yàn)證驗(yàn)證a,ba,b的所有取值，若的所有取值，若a!=ba!=b，則輸出，則輸出a,ba,b。開始開始結(jié)束結(jié)束a+1 aa5YN1a輸出輸出a,ba,bb+1 bb5YN1 ba bYN