第7章 數(shù)據(jù)結構與算法

第07章e7d195523061f1c01da5a1f0837ac25283df40ff0a16bfd61AE6AB84AD7EB485CA8019BF267F2027DE2BF09650313B56A435BB3664F8B916CA3777391AC088C283181605E184D6D6879568EB73EB808A103F0784C8DFC3E9CDD14B61FDDA6A8A6237D2DFE3BBAEC8979D824A43E015648F6CB3D1F8D3E352A4BDC9925C075CFF312C4A0BE75FDF5C數(shù)據(jù)結構與算法大學計算機基礎Fundamentalsofuniversitycomputerscience課前導讀2

本章將從數(shù)據(jù)結構的基本概念開始，由淺入深地介紹數(shù)據(jù)結構、算法的基本概念、常用算法、程序、程序設計、程序設計的基本控制結構、常用的程序設計語言等知識，通過程序設計的實例介紹，讓讀者了解程序設計的基本方法和步驟。通過本章的學習，讀者應了解程序設計的基本控制結構，并對程序設計的基本方法和步驟有一個初步的認識。e7d195523061f1c01da5a1f0837ac25283df40ff0a16bfd61AE6AB84AD7EB485CA8019BF267F2027DE2BF09650313B56A435BB3664F8B916CA3777391AC088C283181605E184D6D6879568EB73EB808A103F0784C8DFC3E9CDD14B61FDDA6A8A6237D2DFE3BBAEC8979D824A43E015648F6CB3D1F8D3E352A4BDC9925C075CFF312C4A0BE75FDF5C內容導航第07章7.2算法的基本概念7.3常用算法7.4程序設計7.1數(shù)據(jù)結構7.1.1數(shù)據(jù)結構概述

數(shù)據(jù)結構是計算機存儲、組織數(shù)據(jù)的方式。

據(jù)結構有兩個要素：一是數(shù)據(jù)元素的集合，通常記為d；二是d上的關系，它反映了數(shù)據(jù)元素之間的關系，通常記為s。一個數(shù)據(jù)結構可以表示成：b=(d，s)式中，b表示數(shù)據(jù)結構。用s反映d中各數(shù)據(jù)元素之間的關系。數(shù)據(jù)結構研究的對象是數(shù)據(jù)的邏輯結構和數(shù)據(jù)的物理結構。7.1.1數(shù)據(jù)結構概述1．數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構是反映數(shù)據(jù)元素之間的邏輯關系的數(shù)據(jù)結構，是從操作對象抽象出來的數(shù)據(jù)模型，與它們真正在計算機中的存儲位置無關。

b=（d,s） d={春季，夏季，秋季，冬季}

s={（春季，夏季）,（夏季，秋季），（秋季，冬季），（冬季，春季）}根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間關系的復雜程度，一般將數(shù)據(jù)結構分為兩大類型：線性結構和非線性結構。7.1.1數(shù)據(jù)結構概述2．數(shù)據(jù)的物理結構數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內的存儲形式。由于數(shù)據(jù)元素在計算機內存儲的位置關系可能與邏輯關系不同，因此為了表示存放在計算機內的各數(shù)據(jù)元素之間的邏輯關系，在數(shù)據(jù)的存儲結構中，不僅要存放各數(shù)據(jù)元素的信息，還要存放各數(shù)據(jù)元素之間的前驅和后繼的關系信息。一種數(shù)據(jù)的邏輯結構根據(jù)需要可以表示成多種存儲結構。常用的存儲結構有順序存儲結構、鏈式等存儲結構。7.1.2數(shù)組

數(shù)組是指由相同數(shù)據(jù)類型的元素組成的一個有序序列。數(shù)組名表示整個數(shù)組，組成數(shù)組的各個元素稱為數(shù)組分量，也稱為數(shù)組元素；用于區(qū)分數(shù)組的各個元素的數(shù)字編號稱為下標。7.1.2數(shù)組

1．一維數(shù)組一維數(shù)組是最簡單的數(shù)組，只有一個下標，其邏輯結構是線性表。要使用一維數(shù)組，需經(jīng)過定義、初始化和引用等過程。在C語言中inta[5];表示定義了一含有5個整型元素的一維數(shù)組a，該數(shù)組的邏輯結構如圖所示。a[0]a[1]a[2]a[3]a[4]7.1.2數(shù)組

2．二維數(shù)組

與一維數(shù)組對應，二維數(shù)組有兩個下標，分別表示行、列信息。在C語言中intb[3][3];表示定義了由3行、3列共9個整型元素組成的二維數(shù)組b。不同的語言對二維數(shù)組的物理存儲是不一樣的，分為行序為主的存放（即按行的順序一行一行地存放）和列序為主的存放（即按列的順序一列一列地存放）。下圖所示為該數(shù)組的邏輯結構。b[0][0]b[0][1]b[0][2]b[1][0]b[1][1]b[1][2]b[2][0]b[2][1]b[2][2]7.1.3鏈表在鏈式存儲方式中，要求每個節(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中，指針用于指向該節(jié)點的前一個或后一個節(jié)點等。鏈表分為單鏈表和雙向鏈表等。7.1.3鏈表

1．單鏈表單鏈表是僅有一個數(shù)據(jù)域和一個指針域。單鏈表的節(jié)點結構示意圖如圖所示。

數(shù)據(jù)域data存放節(jié)點值的數(shù)據(jù)域；指針域next存放節(jié)點的直接后繼地址（位置）。7.1.3鏈表

2．雙向鏈表在某些應用中，對線性鏈表中的每個節(jié)點設置兩個指針：一個稱為左指針，用以指向其前驅節(jié)點；另一個稱為右指針，用以指向其后繼節(jié)點。這樣的鏈表稱為雙向鏈表，如圖所示。

7.1.3鏈表

2．雙向鏈表數(shù)據(jù)域data存放節(jié)點的數(shù)據(jù)域；指針域prior存放節(jié)點的直接前驅地址（位置）；指針域next存放節(jié)點的直接后繼地址（位置）。有多個節(jié)點經(jīng)過指針域鏈接后的示意圖如圖所示。

7.1.4棧

1．棧的基本概念棧是一種特殊的線性表，是限定只在一端進行插入和刪除的線性表。在棧中，一端是封閉的，既不允許插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時為空棧。

7.1.4棧

2．棧的基本運算棧的基本運算有3種：入棧、退棧和讀棧頂元素。①入棧。入棧是指在棧頂位置插入一個新元素。②退棧。退棧是指取出棧頂元素并賦給一個指定的變量。③讀棧頂元素。讀棧頂元素是指將棧頂元素賦給一個指定的變量。

7.1.5隊列隊列是只允許在一端進行刪除，在另一端進行插入的順序表。通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。隊列需要用兩個指針進行管理：一個是隊頭指針，指向隊頭元素；另一個是隊尾指針，指向下一個入隊元素的存儲位置。7.1.6樹和二叉樹

1．樹的定義樹是由n（n≥0）個有限節(jié)點組成的一個具有層次關系的集合。把它叫作“樹”，是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。任意一棵非空樹是由根節(jié)點和若干棵子樹構成的，由一個集合及在該集合上定義的一種關系組成。集合中的元素稱為樹的節(jié)點，所定義的關系稱為父子關系。父子關系在樹的節(jié)點之間建立了一個層次結構。在這種層次結構中有一個節(jié)點具有特殊的地位，這個節(jié)點稱為該樹的根節(jié)點，或者稱為樹根。7.1.6樹和二叉樹

2．樹的基本概念根：在樹結構中，沒有前驅的節(jié)點只有一個，即樹的根，如圖中的A。在樹中位于最上層。

父節(jié)點：在樹結構中，每一個節(jié)點只有一個前驅，稱為父節(jié)點。如圖7.11中的B是F的父節(jié)點。

子節(jié)點：每一個節(jié)點可以有多個后繼，稱為該節(jié)點的子節(jié)點。如圖中的E和F是B的子節(jié)點，H是F的子節(jié)點。

葉子節(jié)點：沒有后繼的節(jié)點稱為葉子節(jié)點。圖7.11中的C、E、H、G均為葉子節(jié)點。7.1.6樹和二叉樹

2．樹的基本概念度：在樹結構中，一個節(jié)點所擁有的子節(jié)點的個數(shù)稱為該節(jié)點的度，所有節(jié)點中最大的度稱為樹的度。圖7.11中，根節(jié)點A的度為3，節(jié)點B的度為2，葉子節(jié)點C的度為0。因此，該樹的度為3。

深度：定義一棵樹的根節(jié)點所在的層次為1，其他節(jié)點所在的層次等于它的父節(jié)點所在的層次加1。樹的最大層次稱為樹的深度。圖中，根節(jié)點A在第1層，節(jié)點B、C、D在第2層，節(jié)點E、F、G在第3層，H在第4層，所以該樹的深度為4

子樹：在樹結構中，以某一個子節(jié)點為根構成的樹稱為該節(jié)點的一棵子樹。圖7.11中，B子樹，包含節(jié)點有B、E、F、H。7.1.6樹和二叉樹3．二叉樹在二叉樹中，每一個節(jié)點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個節(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個節(jié)點可以只有左子樹，也可以只有右子樹，如圖所示。7.1.6樹和二叉樹二叉樹具有以下4個性質

性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個節(jié)點。

性質2：深度為m的二叉樹最多有2m-1個節(jié)點。性質3：在任意一棵二叉樹中，度為0的節(jié)點（即葉子節(jié)點）總是比度為2的節(jié)點多一個。

性質4：具有n個節(jié)點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數(shù)部分。7.1.7圖

1．圖的定義圖是由頂點的有窮非空集合和頂點之間邊的集合組成的。圖中每一條邊的兩個頂點互為鄰接點。如果圖中的每條邊是有方向的，則稱該圖是有向圖，如上圖所示。有向圖中的邊也稱為弧，通常用尖括號表示。如果圖中的每條邊是沒有方向的，則稱該圖是無向圖，如下圖所示。無向圖中的邊均為頂點的無序對，通常用圓括號表示。7.1.7圖

2．圖的遍歷圖的遍歷是指從圖中某一頂點出發(fā)訪問圖中的每一個頂點，且每個頂點僅被訪問一次。圖的遍歷方法有兩種：一種是深度優(yōu)先搜索遍歷（Depth-FirstSearch，DFS），另一種是廣度優(yōu)先搜索遍歷（Breadth-FirstSearch，BFS）。e7d195523061f1c01da5a1f0837ac25283df40ff0a16bfd61AE6AB84AD7EB485CA8019BF267F2027DE2BF09650313B56A435BB3664F8B916CA3777391AC088C283181605E184D6D6879568EB73EB808A103F0784C8DFC3E9CDD14B61FDDA6A8A6237D2DFE3BBAEC8979D824A43E015648F6CB3D1F8D3E352A4BDC9925C075CFF312C4A0BE75FDF5C內容導航第07章7.3常用算法7.4程序設計7.1數(shù)據(jù)結構7.2算法的基本概念7.2算法

算法是程序設計的精髓，可以把它定義成在有限步驟內求解某一問題所使用的一組定義明確的規(guī)則。在計算機科學中，算法要用計算機算法語言描述，算法代表用計算機解一類問題的精確、有效的方法。通俗點說，就是計算機解題的過程。

在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。

7.2.1算法的概念算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算，是對解題方案的準確與完整的描述。對算法的學習包括5個方面的內容。（1）設計算法。（2）表示算法。（3）確認算法。（4）分析算法。（5）驗證算法。7.2.2算法的特征算法應該具有以下5個重要的特征：（1）確定性。每一種運算必須有確定的意義。（2）可行性。算法中有待實現(xiàn)的運算都是基本的。（3）輸入。一個算法可能有多個輸入。（4）輸出。一個算法會產(chǎn)生一個或多個輸出。（5）有窮性。一個算法會在執(zhí)行了有限步的運算后終止。7.2.3算法的描述

算法是解題方法的精確描述。描述算法的工具對算法的質量有很大的影響。（1）自然語言（2）偽碼（3）流程圖（4）N-S結構圖7.2.3算法的描述

（1）自然語言

自然語言就是日常使用的語言，可以使用中文，也可以使用英文。用自然語言描述的算法，通俗易懂，但是文字冗長，準確性不好，易于產(chǎn)生歧義性。因此，一般情況下不提倡用自然語言來描述算法。

（2）偽碼

偽碼不是一種現(xiàn)實存在的編程語言。使用偽碼的目的是為了使被描述的算法可以容易地以任何一種編程語言實現(xiàn)。它可能綜合使用多種編程語言中語法、保留字，甚至會用到自然語言。因此，偽代碼必須結構清晰，代碼簡單，可讀性好，并且類似自然語言。7.2.3算法的描述7.2.3算法的描述

（3）流程圖

流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形的框來代表各種不同性質的操作，用流程線來指示算法的執(zhí)行方向。符

號

符

號

名

稱

含

義

起止框

表示算法的開始或結束

輸入/輸出框

表示輸入/輸出操作

處理框

表示對框內的內容進行處理

判斷框

表示對框內的條件進行判斷

流向線

表示算法的流動方向

連接點

表示兩個具有相同標記的“連接點”相連

表7.1流程圖的常用符號7.2.3算法的描述

（4）N-S結構圖N-S圖用一個大矩形框來表示算法，它是算法的一種結構化描述方法，是一種適合于結構化程序設計的流程圖e7d195523061f1c01da5a1f0837ac25283df40ff0a16bfd61AE6AB84AD7EB485CA8019BF267F2027DE2BF09650313B56A435BB3664F8B916CA3777391AC088C283181605E184D6D6879568EB73EB808A103F0784C8DFC3E9CDD14B61FDDA6A8A6237D2DFE3BBAEC8979D824A43E015648F6CB3D1F8D3E352A4BDC9925C075CFF312C4A0BE75FDF5C內容導航第07章7.4程序設計7.1數(shù)據(jù)結構7.2算法的基本概念7.3常用算法7.2.3算法的描述

（4）N-S結構圖N-S圖用一個大矩形框來表示算法，它是算法的一種結構化描述方法，是一種適合于結構化程序設計的流程圖7.3常用算法

任何復雜的算法，都可以由順序結構、選擇（分支）結構和循環(huán)結構這3種基本結構組成，因此，構造一個解決問題的具體方法和步驟的時候，也僅以這3種基本結構作為“建筑單元”，遵守3種基本結構的規(guī)范，基本結構之間可以相互包含，但不允許交叉，不允許從一個結構直接轉到另一個結構的內部。

7.3.1算法概述算法是程序設計的精髓，它的定義是在有限步驟內求解某一問題所使用的一組定義明確的規(guī)則。在計算機科學中，算法要用計算機語言來描述，算法代表用計算機解一類問題的精確、有效的方法和步驟，即計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。因此算法設計與實現(xiàn)是計算思維訓練的重要抓手。7.3.2累加求和算法定義一個變量s（往往初值為0）作為累加器使用，再定義一個變量用來保存加數(shù)。一般在累加算法中的加數(shù)都是有規(guī)律可循的，可結合循環(huán)程序來實現(xiàn)。求1+2+3+…+100的累加和。設累加器s專門存放累加的結果，初值為0，加數(shù)用變量t表示。當t=1時，s的值應為0+1=1，即s=0+1=s+t（執(zhí)行語句s=s+t）。當t=2時，s的值應為1+2=3，即s=1+2=s+t（執(zhí)行語句s=s+t）。當t=3時，s的值應為3+3=6，即s=3+3=s+t（執(zhí)行語句s=s+t）。當t=4時，s的值應為6+4=10，即s=6+4=s+t（執(zhí)行語句s=s+t）?！攖=100時，累加器s=s+100=1+2+3+…+99+100=5050（執(zhí)行語句s=s+t）。不難看出，t的值從1變化到100的過程中，累加器均執(zhí)行同一個操作s=s+t7.3.2累加求和算法求解此類問題的基本步驟可以概括如下。①定義代表和的變量s，定義代表第n項的變量t。②令s=0。③構建循環(huán)體，一般情況下為s=s+t。④構建循環(huán)條件，根據(jù)問題的具體要求，選用相應的循環(huán)語句。⑤輸出累加和s的值。7.3.3連乘求積算法設一個變量p，作為累乘器使用，初值一般為1；設一個變量k用來保存每次需要乘的乘數(shù)，在循環(huán)體中執(zhí)行p=p*k的語句即可。求10！=1×2×3×…×10的結果。設乘法器p，初值為1，設變量k存放乘數(shù)。當k=1時，p=p×k=1×1=1。當k=2時，p=p×k=1×2=2。當k=3時，p=p×k=2×3=6?！攌=10時，p=p×k=1×2×3×…×9×10。因此，在k的值從1變化到10的過程中，乘法器均執(zhí)行同一個操作p=p×k。7.3.3連乘求積算法求解此類問題的基本步驟可以概括如下。①定義代表乘積的變量p，定義代表第n項的變量k。②令p=1。③構建循環(huán)體，一般情況下為p=p×k。④構建循環(huán)條件，根據(jù)問題的具體要求，選用相應的循環(huán)語句。⑤輸出乘積p的值。7.3.4求最值算法在N個數(shù)中求最大值和最小值的思路是：定義一個變量，假設為max，用來存放最大值，再定義一個變量，假設為min，用來存放最小值。一般先將N個數(shù)中的第1個數(shù)賦予max和min作為初始值，然后將剩下的每個數(shù)分別同max、min比較——如果比max大，將該數(shù)賦予max；如果比min小，將該數(shù)賦予min。也就是說，讓max中總是存放當前的最大數(shù)，讓min中總是存放當前的最小值，這樣當所有數(shù)都比較完時，在max中存放的就是最大數(shù)，在min中存放的就是最小數(shù)。7.3.4求最值算法求解此類問題的基本步驟可以概括如下。①定義x代表N個數(shù)中的一個數(shù)。②定義一個存放最大值的變量max，定義一個存放最小值的變量min。③分別令max=所有數(shù)據(jù)中的第1個數(shù)，min=所有數(shù)據(jù)中的第1個數(shù)。④構建循環(huán)體，然后將x與max比較，如果x比max大，令max=x；將x與min比較，如果x比min小，令min=x。⑤構建循環(huán)條件，根據(jù)問題的具體要求，選用相應的循環(huán)語句。⑥輸出max和min的值。7.3.5排序所謂排序，就是將一組相同類型的記錄序列調整為按照元素關鍵字有序（遞增或遞減）的記錄序列。例如，將學生記錄按學號排序、上體育課時按照身高從高到低排隊、考試成績從高分到低分排列、電話簿中的聯(lián)系人姓名按照字母順序排列、電子郵件列表按照日期排序等。7.3.5排序

冒泡法排序方法的算法描述是：

第1趟排序對全部n個記錄R1，R2，…，Rn自左向右順次兩兩比較，如果Rk大于Rk+1（其中，k=1，2，…，n?1），則交換兩者內容，第1趟排序完成后Rn成為序列中的最大記錄；

第2趟排序對序列前n?1個記錄采用同樣的比較和交換方法，第2趟排序完成后Rn?1成為序列中僅比Rn小的次大的記錄；

第3趟排序對序列前n?2個記錄采用同樣的處理方法；如此做下去，最多做n?1趟排序，整個序列就排序完成了。7.3.5排序冒泡法排序原始數(shù)據(jù) 44、33、25、19R[1]，R[2]，R[3]，R[4]第1趟 44、33、25、19

33、44、25、19

33、25、44、19

33、25、19、44R[1]，R[2]，R[3] 第2趟 33、25、19

25、33、19

25、19、33R[1]，R[2] 第3趟 25、19

19、25排序后的數(shù)據(jù) 19、25、33、447.3.5排序冒泡法排序的基本步驟。定義數(shù)組r存放待排序的n個數(shù)。①定義變量i表示比較的趟數(shù)，定義變量j表示每一趟比較的次數(shù)，定義變量temp作為交換時的臨時變量。②利用循環(huán)把n個數(shù)送給數(shù)組元素。③i=0。④構建循環(huán)體（控制趟數(shù)，共n?1趟）。j=0。構建循環(huán)體（控制每一趟比較的次數(shù)，從0變化到n?1?i）。將r[j]和r[j+1]比較，如果r[j]比r[j+1]大，令r[j]與r[j+1]互換值，即temp=r[j]，r[j]=r[j+1]，r[j+1]=temp。⑤構建循環(huán)條件，根據(jù)問題的具體要求，選用相應的循環(huán)語句。⑥利用循環(huán)輸出排序后的數(shù)組元素。7.3.6查找

查找也稱為檢索，是在較大的數(shù)據(jù)集中找出或定位某些數(shù)據(jù)的過程，即在大量的信息中尋找一個特定的信息元素。在計算機中進行查找的方法是根據(jù)表中的記錄的組織結構確定的，被用于查找的數(shù)據(jù)元素的屬性一般稱為關鍵字。

順序查找也稱為線性查找，是一種最簡單的查找方法，可用于有序列表，也可用于無序列表。7.3.6查找

查找也稱為檢索，是在較大的數(shù)據(jù)集中找出或定位某些數(shù)據(jù)的過程，即在大量的信息中尋找一個特定的信息元素。在計算機中進行查找的方法是根據(jù)表中的記錄的組織結構確定的，被用于查找的數(shù)據(jù)元素的屬性一般稱為關鍵字。

順序查找也稱為線性查找，是一種最簡單的查找方法，可用于有序列表，也可用于無序列表。其基本思想是：從查找表（數(shù)據(jù)結構線性表）的一端開始，順序掃描線性表，依次將掃描到的節(jié)點關鍵字同給定值key相比較，如果當前掃描到的節(jié)點關鍵字同key相等，則表示查找成功；如果掃描結束后，沒有找到關鍵字等于key的節(jié)點，表示查找失敗。7.3.6查找假設順序查找表存儲在一維數(shù)組，目標數(shù)據(jù)有100個，這些數(shù)據(jù)是無序的，分別存放在一維數(shù)組R[1]，…，R[100]中?，F(xiàn)要求查找這些數(shù)據(jù)里有沒有值為key的數(shù)據(jù)元素，如果找到，就給出其所在的位置；如果沒有找到，則給出相應提示信息。算法描述如下。SqSearch(key)設初始查找位置k為1；當k≤100且R[k]≠key時 //位置向后移動，直到找到或k越界

k=k+1；如果k≤100，

returnk； //返回數(shù)據(jù)元素所在的位置否則

return0； //沒有找到，返回07.3.7統(tǒng)計統(tǒng)計算法一般用于求解特定值問題。輸入一串字符，統(tǒng)計其中的字母個數(shù)、數(shù)字個數(shù)和其他字符的個數(shù)。分析：要統(tǒng)計滿足指定要求的字符個數(shù)，應定義相應變量作為計數(shù)器，初值為0，每找到符合條件的字符，將指定計數(shù)器的值加1。本題需要定義3個計數(shù)器n1、n2、n3，分別統(tǒng)計字母、數(shù)字和其他字符的個數(shù)，初值均為0。對字符串中的字符逐個判斷，如果是字母，n1執(zhí)行加1操作；如果是數(shù)字，n2加1；否則n3加1。7.3.7統(tǒng)計歸納出求解此類問題的基本步驟如下。①定義代表所有統(tǒng)計要求的計數(shù)器變量（有幾項統(tǒng)計要求，就有幾個計數(shù)器變量）。②令所有計數(shù)器變量的初值為0。③構建循環(huán)體，當滿足指定的計數(shù)要求時，就將相應的計數(shù)器的值加1（執(zhí)行類似于n=n+1的操作）。④構建循環(huán)條件，根據(jù)問題的具體要求，選用相應的循環(huán)語句。⑤輸出所有計數(shù)器的值。e7d195523061f1c01da5a1f0837ac25283df40ff0a16bfd61AE6AB84AD7EB485CA8019BF267F2027DE2BF09650313B56A435BB3664F8B916CA3777391AC088C283181605E184D6D6879568EB73EB808A103F0784C8DFC3E9CDD14B61FDDA6A8A6237D2DFE3BBAEC8979D824A43E015648F6CB3D1F8D3E352A4BDC9925C075CFF312C4A0BE75FDF5C內容導航第07章7.1數(shù)據(jù)結構7.2算法的基本概念7.3常用算法7.4程序設計7.3.7統(tǒng)計程序的概念非常普遍。簡單地說，程序可以看作是對一系列動作的執(zhí)行過程的描述。隨著計算機的出現(xiàn)和普及，“程序”已經(jīng)成了計算機領域的專有名詞。計算機程序是指為了得到某種結果而由計算機等具有信息處理能力的裝置執(zhí)行的代碼化指令序列。也可以這樣說，程序就是由一條條代碼組成的，這樣的一條條代碼各自代表著不同的命令，這些命令結合起來，組成了一個完整的工作系統(tǒng)。程序的性質目的性：程序必須有一個明確的目的。分步性：程序給出了解決問題的步驟。有限性：解決問題的步驟必須是有限的。如果有無窮多個步驟，那么在計算機上就無法實現(xiàn)。可操作性：程序總是實施各種操作于某些對象的，它必須是可操作的。有序性：解題步驟不是雜亂無章地堆積在一起，而是要按一定順序排列的。這是最重要的一點。7.4.1程序設計的概念那么要讓計算機處理一個問題（程序設計），需要經(jīng)過哪些步驟呢？建立數(shù)學模型。確定算法（算法設計）。編寫源程序。程序調試。整理資料。7.4.2結構化程序設計的基本原則人們從多年來的軟件開發(fā)經(jīng)驗中發(fā)現(xiàn)，任何復雜的算法，都可以由順序結構、選擇結構和循環(huán)結構這3種基本結構組成，因此，在構造一個解決問題的具體方法和步驟的時候，也僅以這3種基本結構作為“建筑單元”，遵守3種基本結構的規(guī)范，基本結構之間可以相互包含，但不允許交叉，不允許從一個結構直接轉到另一個結構的內部。正因為整個算法都是由3種基本結構組成的，就像用模塊構建的一樣，所以結構清晰，易于正確性驗證，易于糾錯。這種方法就是結構化方法，遵循這種方法的程序設計，就是結構化程序設計。7.4.2

結構化程序設計的基本原則（1）模塊。當把要開發(fā)的一個較大規(guī)模的軟件，依照功能需要，采用一定的方法（例如，結構化方法）劃分成一些較小的部分時，這些較小的部分就稱為模塊，也叫作功能模塊。（2）模塊化設計。通常把以功能模塊為設計對象，用適當?shù)姆椒ê凸ぞ邔δK的外部（各有關模塊之間）與模塊內部（各成分之間）的邏輯關系進行確切的描述稱為模塊化設計。7.4.2結構化程序設計的原則（1）自頂向下。

考慮總體，后考慮細節(jié)。（2）逐步求精。（3）模塊化。（4）限制使用GoTo語句。7.4.2面向對象的程序設計面向對象的程序設計（ObjectOrientedProgramming，OOP）。在面向對象的程序設計風格中，會將一個問題分解為一些相互關聯(lián)的子集，每個子集內部都包含了相關的數(shù)據(jù)和函數(shù)。同時，會以某種方式將這些子集分為不同等級，而一個對象就是已定義的某個類型的變量。與傳統(tǒng)的結構化分析與設計技術相比，面向對象技術具有許多明顯的優(yōu)點，主要體現(xiàn)在以下3個方面。（1）可重用性。（2）可維護性。（3）表示方法的一致性。7.4.3程序設計的基本控制結構

結構化程序設計提出了順序結構、選擇（分支）結構和循環(huán)結構3種基本程序結構。

一個程序無論大小都可以由3種基本結構搭建而成。7.4.3程序設計的基本控制結構順序結構要求程序中的各個操作按照它們出現(xiàn)的先后順序執(zhí)行。這種結構的特點是：程序從入口點開始，按順序執(zhí)行所有操作，直到出口點處。其流程圖如圖10.3所示。7.4.3程序設計的基本控制結構1．兩路分支選擇結構兩路分支選擇是指根據(jù)判斷結構入口點處的條件來決定下一步的程序流向。如果條件為真則執(zhí)行語句組1，否則執(zhí)行語句組2。

但不論選擇了哪一條分支執(zhí)行，最后流程都一定到達結構的出口點處，其流程圖如圖10.4所示。圖10.4兩路分支選擇結構的流程圖7.4.3程序設計的基本控制結構1．兩路分支選擇結構實際使用過程中可能會遇到只有一條有執(zhí)行的兩分支，此時最好將這些語句放在條件為真的執(zhí)行語句中，如右側圖所示。在有些地方，這個結構稱為是單分支結構。單分