《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第1章

第1章緒論1.1軟件的基本概念1.2數(shù)據(jù)結(jié)構(gòu)概述1.3算法與算法分析1.4程序設(shè)計的關(guān)鍵技術(shù)1.5程序設(shè)計的步驟及實(shí)例

1.1軟件的基本概念

從一般意義上講，能夠在計算機(jī)上運(yùn)行的程序都可以稱為軟件。軟件更準(zhǔn)確的定義是利用計算機(jī)本身提供的邏輯功能，合理地組織計算機(jī)的工作流程，簡化或替代人們使用計算機(jī)過程中的各個環(huán)節(jié)，提供給使用者一個便于操作的工作環(huán)境的“程序集”。軟件是邏輯的而不是物理的產(chǎn)品，與硬件相比具有以下完全不同的特征：

(1)軟件是由開發(fā)或工程化而形成的，而不是由傳統(tǒng)意義上的制造產(chǎn)生的。

(2)軟件不會磨損。軟件的故障率隨時間的推移而降低，而硬件的故障率隨時間的推移而增加。

(3)大多數(shù)軟件是自定義的，而不是通過已有的組件組裝而來的。1.1.1軟件應(yīng)用

從某種程度上講，對軟件應(yīng)用給出一個確切的分類是比較困難的。下面給出的一些軟件的應(yīng)用領(lǐng)域，可以看做是一種潛在的應(yīng)用分類：

(1)系統(tǒng)軟件。

(2)實(shí)時軟件。

(3)商業(yè)軟件。

(4)工程和科學(xué)計算軟件。

(5)嵌入式軟件。

(6)個人軟件。

(7)人工智能軟件。1.1.2軟件生存期

1．制定計劃

2．需求分析和定義

3．軟件設(shè)計

4．程序編制

5．軟件測試

6．運(yùn)行/維護(hù)圖1-1軟件生存期模型1.1.3軟件技術(shù)

軟件是由程序、數(shù)據(jù)和文檔組成的。為了開發(fā)高質(zhì)量的軟件，軟件工程師必須遵循一個開發(fā)策略，即軟件過程模型。軟件技術(shù)是指開發(fā)軟件所需的所有技術(shù)的總稱。按照軟件分支學(xué)科的內(nèi)容劃分，軟件技術(shù)包括以下幾個領(lǐng)域：

(1)軟件工程技術(shù)。

(2)程序設(shè)計技術(shù)。

(3)軟件工具環(huán)境技術(shù)。

(4)系統(tǒng)軟件技術(shù)。

(5)數(shù)據(jù)庫技術(shù)。

(6)實(shí)時軟件技術(shù)。

(7)網(wǎng)絡(luò)軟件技術(shù)。

(8)與實(shí)際工作相關(guān)的軟件技術(shù)。1.1.4程序設(shè)計技術(shù)

程序設(shè)計技術(shù)的目標(biāo)是提高程序的質(zhì)量與生產(chǎn)率，最終實(shí)現(xiàn)程序的工業(yè)化生產(chǎn)。影響程序質(zhì)量的因素有很多，如正確性、性能、可靠性、容錯性、易用性、靈活性、可擴(kuò)充性、可理解性、可維護(hù)性和復(fù)用性等。下面所介紹的程序設(shè)計技術(shù)主要是針對規(guī)模小且一個人能夠獨(dú)立完成的程序設(shè)計技術(shù)。程序設(shè)計的主要環(huán)節(jié)有：明確需求、設(shè)計、實(shí)現(xiàn)(即編碼)、測試等，如圖1-2所示。圖1-2程序設(shè)計的主要環(huán)節(jié)

1．明確需求

程序設(shè)計的第一步工作是明確需求，即明確待解決的問題是什么，也稱為問題分析階段。

2．設(shè)計

設(shè)計是把需求轉(zhuǎn)化為程序的最重要的環(huán)節(jié)。設(shè)計的優(yōu)劣在根本上決定了程序的質(zhì)量，它包括程序結(jié)構(gòu)設(shè)計、模塊設(shè)計、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計和用戶界面設(shè)計。

1)結(jié)構(gòu)設(shè)計

結(jié)構(gòu)是程序中最本質(zhì)的內(nèi)容。

(1)結(jié)構(gòu)是對復(fù)雜事物的一種抽象。

(2)結(jié)構(gòu)在一定的時間內(nèi)保持穩(wěn)定。

2)模塊設(shè)計

在程序結(jié)構(gòu)設(shè)計完成后，就已經(jīng)在宏觀上明確了各個模塊具有的功能以及在結(jié)構(gòu)中的位置。我們習(xí)慣地從功能上劃分模塊，并保持“功能獨(dú)立”是模塊化設(shè)計的基本原則，這是因?yàn)楣δ塥?dú)立的模塊可以降低開發(fā)、測試、維護(hù)等階段的代價。但是功能獨(dú)立并不意味著模塊之間保持絕對的孤立，一個系統(tǒng)要完成某項(xiàng)任務(wù)，需要各個模塊相互配合才能實(shí)現(xiàn)，此時模塊之間就要進(jìn)行信息交流。評價模塊設(shè)計優(yōu)劣的三個特征因素是信息隱藏、內(nèi)聚與耦合和封閉—開放性。

(1)信息隱藏。

(2)內(nèi)聚與耦合。

耦合的強(qiáng)度依賴于以下幾個因素：

①一個模塊對另一個模塊的調(diào)用；

②一個模塊向另一個模塊傳遞的數(shù)據(jù)量；

③一個模塊施加到另一個模塊的控制的多少；

④模塊之間接口的復(fù)雜程度。

(3)封閉—開放性。

3)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計

設(shè)計高效率的程序是基于良好的數(shù)據(jù)結(jié)構(gòu)與算法，而不是基于編程小技巧。

人們對常用的數(shù)據(jù)結(jié)構(gòu)與算法的研究已經(jīng)相當(dāng)透徹了，可以歸納出下列設(shè)計原則：

(1)每一種數(shù)據(jù)結(jié)構(gòu)與算法都有其時間、空間的開銷和收益。

(2)與開銷和收益有關(guān)的是時間—空間的權(quán)衡。

(3)程序員應(yīng)該充分地了解一些常用的數(shù)據(jù)結(jié)構(gòu)與算法，避免不必要的重復(fù)設(shè)計工作。

(4)數(shù)據(jù)結(jié)構(gòu)與算法為應(yīng)用服務(wù)。

4)用戶界面設(shè)計

(1)界面的合適性。

(2)界面的風(fēng)格。

(3)界面的廣義美。

3．編碼

編碼(Coding)的任務(wù)是為每個模塊編寫程序，也就是說，將設(shè)計的結(jié)果轉(zhuǎn)換為用某種程序設(shè)計語言編寫的程序，這個程序必須是無錯的，并且要有必要的內(nèi)部文檔和外部

文檔。

4．測試

程序測試是指在受控制的條件下對程序進(jìn)行操作并評價操作結(jié)果的過程。所謂控制條件，應(yīng)包括正常條件與非正常條件。測試是程序的執(zhí)行過程，測試的目的是發(fā)現(xiàn)盡可能多的缺陷。

1.2數(shù)據(jù)結(jié)構(gòu)概述

1.2.1數(shù)據(jù)結(jié)構(gòu)的引入

從提出一個實(shí)際問題到計算機(jī)解出答案，需要經(jīng)歷下列步驟：分析階段、設(shè)計階段、編碼階段和測試維護(hù)階段等。其中，分析階段就是要從實(shí)際問題中提取操作對象以及操作對象之間的關(guān)系。下面舉例說明。

例1-1計算機(jī)管理圖書目錄問題。

要利用計算機(jī)幫助查詢書目，首先必須將書目存入計算機(jī)，那么這些書目如何存放呢？我們既希望查詢時間短，又要求節(jié)省空間。一個簡單的辦法就是建立一張表，每本書的信息只用一張卡片表示，在表中占一行，如表1-1所示。

例1-2

工廠的組織管理問題。

某工廠的組織機(jī)構(gòu)如圖1-3所示。

廠長要通過計算機(jī)了解各個科室及車間的工作和生產(chǎn)情況，于是，將該組織機(jī)構(gòu)抽象成某個結(jié)構(gòu)—樹，如圖1-4所示，它可以表示問題中各數(shù)據(jù)之間的關(guān)系。只要將數(shù)據(jù)按一定的方式存入計算機(jī)中，并對這棵樹遍歷，就能了解廠內(nèi)的整個情況。圖1-3工廠組織機(jī)構(gòu)

圖1-4樹形結(jié)構(gòu)

例1-3

多岔路口交通燈管理問題。

通常，在十字交叉路口只要設(shè)置紅綠兩色的交通燈便可保持正常的交通秩序，但是對于多岔路口，需要設(shè)置幾種顏色的交通燈，既能使車輛相互間不發(fā)生碰撞，又能達(dá)到交通控制的最大流通量呢？圖1-5(a)所示是一個實(shí)際的五岔路口，我們?nèi)绾卧O(shè)置交通燈，即最少應(yīng)設(shè)置幾種顏色的交通燈，才能保證正常的交通秩序？圖1-5五岔路口交通燈管理問題1.2.2數(shù)據(jù)結(jié)構(gòu)的基本概念

計算機(jī)處理的對象是數(shù)據(jù)，那么什么是數(shù)據(jù)呢？簡單地講，數(shù)據(jù)就是客觀事物在計算機(jī)中的表示，它具有可識別性、可加工處理性和可存儲性等特征。數(shù)據(jù)結(jié)構(gòu)所要研究的主要內(nèi)容可以簡要地歸納為以下三個方面：

(1)研究數(shù)據(jù)元素之間固有的客觀聯(lián)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicalStructure)。

(2)研究數(shù)據(jù)在計算機(jī)內(nèi)部的存儲方法，即數(shù)據(jù)的存儲結(jié)構(gòu)(StorageStructure)，又稱物理結(jié)構(gòu)。

(3)研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)上施加有效的操作或處理(算法)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：

(1)線性結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯特征是有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，且所有結(jié)點(diǎn)都最多只有一個直接前趨和一個直接后繼。線性表就是一種典型的線性結(jié)構(gòu)。本書第2章～第4章介紹的數(shù)據(jù)邏輯結(jié)構(gòu)都是線性結(jié)構(gòu)。

(2)非線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點(diǎn)可能有多個直接前趨和直接后繼。例如，樹和圖就是典型的非線性結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本的存儲方法得到。

(1)順序存儲方法。

(2)鏈接存儲方法。

(3)索引存儲方法。

(4)散列存儲方法。

例1-4

抽象數(shù)據(jù)類型復(fù)數(shù)的定義。1.2.3數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計

關(guān)于“計算機(jī)科學(xué)”，從20世紀(jì)60年代以來，一直有兩種觀點(diǎn)。一種觀點(diǎn)認(rèn)為“計算機(jī)科學(xué)是一種基于信息結(jié)構(gòu)轉(zhuǎn)換的科學(xué)”，另一種觀點(diǎn)認(rèn)為“計算機(jī)科學(xué)是算法的學(xué)問”。這兩種觀點(diǎn)從不同的側(cè)面說明了數(shù)據(jù)結(jié)構(gòu)、算法在計算機(jī)科學(xué)中的重要位置。實(shí)際上數(shù)據(jù)結(jié)構(gòu)與算法之間存在著本質(zhì)聯(lián)系，應(yīng)該說，數(shù)據(jù)結(jié)構(gòu)與算法是計算機(jī)科學(xué)的核心。

例1-5

電話號碼查詢問題。

假定要編寫一個程序，查詢某人的電話號碼。對任意給出的一個姓名(假設(shè)不存在重名的情況)，若該人的電話已登記，則要迅速找到其電話號碼；否則指出該人沒有電話。解決此問題的辦法是，首先要構(gòu)造一張電話號碼登記表，表中每個結(jié)點(diǎn)存放兩個數(shù)據(jù)項(xiàng)：姓名和電話號碼。其次，如何組織表中的數(shù)據(jù)是問題的關(guān)鍵，最簡單的方法是將每個人的信息順序存放在表中(如圖1-6所示)，查找時從頭開始依次查找姓名，直到找到相應(yīng)的姓名，或找遍整個表沒有找到為止。但是，這種查找方法不適用于表中內(nèi)容龐大的情況。圖1-6電話號碼查詢中的順序存儲現(xiàn)在我們從數(shù)據(jù)結(jié)構(gòu)的角度考慮，即對圖1-6所示表中信息的組織和存儲重新考慮，將表中的姓名按姓氏排列，并另外再建一張姓氏索引表，其存儲結(jié)構(gòu)如圖1-7所示。圖1-7電話查詢中的索引存儲

例1-6

人事檔案的建立及管理。

假設(shè)要建立一個大學(xué)的教師和學(xué)生檔案，并完成日常的管理(如查詢、插入、刪除等)。教師和學(xué)生檔案的邏輯結(jié)構(gòu)如圖1-8所示(以一系教師和學(xué)生邏輯結(jié)構(gòu)示意)。圖1-8人事檔案

1.3算法與算法分析

1.3.1算法的概念

通俗地講，一個算法就是一種解題方法。更嚴(yán)格地說，算法是由若干條指令組成的有限序列，它必須滿足以下性質(zhì)。

(1)輸入性：具有零個或多個輸入量，即算法開始前對算法給出的初始量。

(2)輸出性：至少產(chǎn)生一個輸出。

(3)有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。

(4)確定性：每條指令的含義必須明確，無二義性。

(5)可行性：每條指令都應(yīng)在有限的時間內(nèi)完成。1.3.2算法分析

求解一個問題，可以有許多種不同的算法，究竟如何評價這些算法的好壞呢？

顯然，選用的算法首先應(yīng)該是“正確的”，其次，還需考慮以下幾個因素：

(1)執(zhí)行算法所消耗的時間。

(2)執(zhí)行算法所消耗的存儲空間，其中主要考慮輔助存儲空間。

(3)算法的可讀性好，易理解，易編碼、調(diào)試。例如，求兩個n階方陣的乘積C?=?A?×?B，其算法描述如下：例如，MatrixMulti算法的時間復(fù)雜度T(n)在n趨向無窮大時，顯然有例如，交換i和j的內(nèi)容。

temp=i;i=j;j=temp;對于較復(fù)雜的算法，我們則可以將其分隔成容易估算的幾個部分，然后利用“O”的求和原則得到整個算法的時間復(fù)雜度。例如，若算法中兩個部分的時間復(fù)雜度分別為T1(n)?=?

(f(n))和T2(n)?=?O(g(n))，則總的時間復(fù)雜度為

T(n)=T1(n)+T2(n)=O(max(f(n),g(n))

若T1(m)?=?O(f(m))，T2(n)?=?O(g(n))，則總的時間復(fù)雜度為

T(m,n)=T1(m)+T2(n)=O(f(m)+g(n))圖1-9幾種常見函數(shù)的增長率類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(SpaceComplexity)S(n)定義為該算法所耗費(fèi)的存儲空間的量度，記做

S(n)?=?O(f(n))

其中，n為問題的規(guī)模。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。

1.4程序設(shè)計的關(guān)鍵技術(shù)

結(jié)構(gòu)化程序設(shè)計中要遵循如下原則：

(1)分解原則。

(2)模塊獨(dú)立性原則。

(3)編碼結(jié)構(gòu)化原則。1.4.1程序結(jié)構(gòu)設(shè)計

1．自頂向下

自頂向下層次結(jié)構(gòu)設(shè)計方法的主要思想是：先設(shè)計第一層(即頂層)，然后步步深入，逐層細(xì)分，逐步求精，直到整個問題可用程序設(shè)計語言明確地描述出來為止。

2．自底向上

自底向上層次結(jié)構(gòu)設(shè)計方法的主要思想：先設(shè)計底層，最后設(shè)計頂層。

這種層次結(jié)構(gòu)設(shè)計方法的優(yōu)點(diǎn)是：由表及里、由淺入深地解決問題。

自底向上層次結(jié)構(gòu)設(shè)計方法的不足之處是：在逐步細(xì)化的過程中可能發(fā)現(xiàn)原來的分解細(xì)化不夠完善。

這種層次結(jié)構(gòu)設(shè)計方法主要用于修改、優(yōu)化或擴(kuò)充一個程序。

3．模塊劃分

模塊劃分的目的是將較復(fù)雜的程序/模塊分解為規(guī)模較小、功能單一的子模塊，以便于把握程序的實(shí)現(xiàn)。為了達(dá)到這個目的，必須深入理解程序/模塊的功能及其應(yīng)用環(huán)境，在此基礎(chǔ)上才能設(shè)計出好的程序。圖1-10程序結(jié)構(gòu)與組成示意圖圖1-11程序的分解示意圖

(1)模塊獨(dú)立性原則。每一個功能模塊都必須是獨(dú)立的，即模塊內(nèi)部的處理與其他模塊的任何信息處理無關(guān)。模塊外部只提供輸入條件和輸出條件，這是與其化模塊之間僅有的聯(lián)系。圖1-12塊間聯(lián)系與塊內(nèi)聯(lián)系示意圖

(2)信息隱蔽原則。程序經(jīng)常被其他程序設(shè)計人員閱讀，在整個生命期中要經(jīng)歷多次修改，程序設(shè)計時如何劃分模塊，才能使將來修改的影響范圍盡量小呢？D.Parnas提出了信息隱蔽原則。根據(jù)信息隱蔽的原則，設(shè)計時應(yīng)列出可能發(fā)生變化的因素，在劃分模塊時將一個可能發(fā)生變化的因素包含在某個模塊的內(nèi)部，使其他模塊與這個因素?zé)o關(guān)。這樣，將來某個因素發(fā)生變化時，我們只需要修改一個模塊就夠了，而其他模塊則不受這個因素的影響。下面用一個例子來解釋信息隱蔽原則：用數(shù)組實(shí)現(xiàn)了一個棧，有十個模塊要對棧做存取操作。

一種設(shè)計方案是將數(shù)組、棧頂、深度等作為全程變量，由各個模塊自行對棧進(jìn)行存取操作，如圖1-13(a)所示，也就是說十個模塊都需了解棧的具體結(jié)構(gòu)細(xì)節(jié)。這個方案的缺點(diǎn)是：如果將來?xiàng)５木唧w結(jié)構(gòu)發(fā)生變化(如深度增加)，那么這十個模塊都必須做相應(yīng)的修改。另一種設(shè)計方案是根據(jù)信息隱蔽的原則，先構(gòu)造兩個模塊Push和Pop，它們分別負(fù)責(zé)對棧做存取操作，十個模塊通過調(diào)用Push和Pop實(shí)現(xiàn)棧操作，如圖1-13(b)所示。此時，棧的具體結(jié)構(gòu)是隱含在Push和Pop兩個模塊內(nèi)部的，其他十個模塊完全不了解這些細(xì)節(jié)，棧對這十個模塊來說是一個抽象的數(shù)據(jù)結(jié)構(gòu)。這個方案的優(yōu)點(diǎn)是：如果將來需要修改棧的具體結(jié)構(gòu)，只須改動Push和Pop兩個模塊就夠了，其余十個模塊完全不受影響。圖1-13模塊對棧的存取操作

(3)重用性原則。軟件的可重用性一直是軟件工程所追求的目標(biāo)之一，人們希望利用標(biāo)準(zhǔn)化的軟件模塊快速地構(gòu)建特定的應(yīng)用系統(tǒng)。軟件開發(fā)的全生命周期都有可重用的價值，包括項(xiàng)目的組織，軟件需求、設(shè)計、文檔、實(shí)現(xiàn)、測試方法和測試用例，都是可以被重復(fù)利用或借鑒的有效資源。軟件代碼的可重用性是最直觀、最容易想到的部分，也是程序員們最樂意追求和有成就感的部分。

4．模塊功能確定和接口定義

在模塊劃分原則的基礎(chǔ)上，可根據(jù)程序的功能對程序進(jìn)行模塊劃分。在模塊劃分時一定要遵循模塊劃分原則和程序的功能要求。

程序具有特定的功能，而程序的功能是由所有模塊的功能經(jīng)過有機(jī)組合來實(shí)現(xiàn)的，因此確定每一個模塊的功能和模塊間的關(guān)系是非常重要的。確定模塊的功能必須與模塊劃分同時考慮。

接口定義是指為了實(shí)現(xiàn)模塊間的相互調(diào)用而約定的調(diào)用協(xié)議，即調(diào)用模塊所應(yīng)遵守的規(guī)則。如圖1-13中的模塊Push，該模塊的輸入是一個有效的X，其操作結(jié)果是將X入棧，那么該模塊的接口可定義為(用C語言給出)：

Output_TypePush(Stack_TypeX);

在調(diào)用該模塊時，應(yīng)采用如下格式：

Stack_Typeinput;

Output_Typeoutput;

output=Push(input);

5．調(diào)用關(guān)系確定

模塊間的調(diào)用關(guān)系是指模塊間調(diào)用的次序。模塊調(diào)用關(guān)系分為遞歸調(diào)用和非遞歸調(diào)用。遞歸調(diào)用是指模塊自身調(diào)用自己；非遞歸調(diào)用是指模塊調(diào)用其他模塊。遞歸調(diào)用分為直接遞歸調(diào)用和間接遞歸調(diào)用,直接遞歸調(diào)用是指模塊直接調(diào)用自身；間接遞歸調(diào)用是指模塊通過其他模塊調(diào)用自身。圖1-14模塊間調(diào)用關(guān)系說明在確定調(diào)用關(guān)系時，應(yīng)根據(jù)程序的處理流程確定模塊間的調(diào)用關(guān)系。實(shí)際上，程序的處理流程與程序中模塊的調(diào)用關(guān)系有著明顯的對應(yīng)關(guān)系。例如，在1.5.2節(jié)將介紹的程序設(shè)計實(shí)例中，查詢請求的處理流程(圖1-18)所對應(yīng)的模塊調(diào)用關(guān)系如圖1-15所示。圖1-15模塊調(diào)用關(guān)系1.4.2模塊設(shè)計

1．輸入到輸出的映射建模

輸入到輸出的映射建模是根據(jù)模塊的功能要求，對輸入進(jìn)行有效的變換，得到期望的輸出結(jié)果。

假設(shè)Compute模塊的功能是求input的平方根，并且沒有現(xiàn)成的平方根函數(shù)，則抽象的映射為

2．?dāng)?shù)據(jù)結(jié)構(gòu)和算法設(shè)計

算法的描述方法有自然語言描述法、類計算機(jī)語言描述法、形式語言描述法和圖示描述法，而使用最普遍的方法是類計算機(jī)語言描述法和圖示描述法。最具代表性的類計算機(jī)語言描述方法是類Pascal語言，而圖示描述法中常用的方法是流程圖。1.4.3良好的編程風(fēng)格

好程序除了滿足必需的要求(如正確性、可靠性、健壯性、高效率等)外，還必須具有好的編程風(fēng)格。好的編程風(fēng)格對于好的程序設(shè)計具有關(guān)鍵性作用，它使程序代碼容易被讀懂。

1．命名

在程序中有大量的變量、常量、宏和函數(shù)等，如何為這些變量和函數(shù)命名？名字用來標(biāo)識某個對象，帶著說明其用途的一些信息。一個名字應(yīng)該是簡練的、容易記憶的，如果可能的話，最好是能夠拼讀的。一個變量的作用域越大，它的名字所攜帶的信息就應(yīng)該越多。因?yàn)槿肿兞靠梢猿霈F(xiàn)在整個程序中的任何地方，所以它們的名字應(yīng)該足夠長，具有足夠的說明性，以便使讀者能夠記得它們的用途。

2．注釋

注釋是幫助程序閱讀的一種手段。好的注釋可用于簡潔地說明程序的突出特征，幫助讀者理解程序。

(1)不要注釋明顯的內(nèi)容。

(2)給函數(shù)和全局?jǐn)?shù)據(jù)加注釋。

(3)不要注釋差的代碼，而應(yīng)重寫代碼。

(4)不要與代碼矛盾。

(5)澄清情況，不要添亂。

3．程序的外觀

1)塊的對齊方式

2)適當(dāng)?shù)目s進(jìn)和空白

一致的縮進(jìn)風(fēng)格會使程序清晰易懂。縮進(jìn)用于描述程序中各部分或語句之間的結(jié)構(gòu)關(guān)系。在嵌套結(jié)構(gòu)中，每個內(nèi)層部分或語句應(yīng)該比外層縮進(jìn)適當(dāng)?shù)目崭?。例如?/p>

for(i++;i<100;field[i++]=‘c’);

field[i]=‘\0’;return0;

該程序段的格式就不好，重新調(diào)整格式如下所示：

for(i++;i<100;i++)

field[i]=‘c’;

field[i]=‘\0’;

return0;

3)用加括號的方式排除二義性

括號表示分組，即使有時并不必要，加了括號也可能把意圖表示得更清楚。在下面的例子里，內(nèi)層括號就不是必需的，但加上也沒有壞處。

if((block_id>=actblks||(block_id<unblocks)))

4)分解復(fù)雜的表達(dá)式

C語言有很豐富的表達(dá)式語法結(jié)構(gòu)和運(yùn)算符，因此很容易把一大堆內(nèi)容寫進(jìn)一個語句中。例如：

*x+=(*xp=(2*k<(n-m)?c[k+1]:d[k--]));

該表達(dá)式雖然很緊湊，但是寫進(jìn)一個語句里的內(nèi)容確實(shí)太多了，把它分解成幾個部分，其含義更容易把握，如下所示：

if(2*k<(n-m))

?

*xp+=c[k+1];

else

?

*xp+=d[k--];如果將其改寫為

if(2*k<(n-m))

?

*xp=c[k+1];

else

?

*xp=d[k--];

?

*x+=*xp;

則更加直觀。

4．一致性和習(xí)慣用法

1)使用一致的縮排和加括號風(fēng)格

縮排可以顯示出程序的結(jié)構(gòu)，那么什么樣的縮排風(fēng)格最好呢？是采用次行風(fēng)格，還是采用行尾風(fēng)格？實(shí)際上，特定風(fēng)格遠(yuǎn)沒有一致性那么重要。

2)為了保持一致性，使用習(xí)慣用法

和自然語言一樣，程序設(shè)計語言也有許多習(xí)慣用法，也就是那些經(jīng)驗(yàn)豐富的程序員的習(xí)慣方式。在學(xué)習(xí)一個語言的過程中，一個主要問題就是逐漸熟悉它的習(xí)慣用法。1.4.4排錯與測試

1．排錯

1)排錯系統(tǒng)

每種語言的編譯系統(tǒng)通常都帶有一個排錯系統(tǒng)。它常常作為整個開發(fā)環(huán)境里的一個組成部分，在這個環(huán)境里集成了有關(guān)程序建立和源代碼編輯、編譯、執(zhí)行和排錯的各種功能。排錯系統(tǒng)使我們能夠以語句或者按函數(shù)的方式分步執(zhí)行程序，在某個特定程序行或者在某個特定條件發(fā)生時停下來等，通常還提供了按照某些指定格式顯示變量值等功能。2)尋找錯誤線索

(1)尋找熟悉的模式。

(2)檢查最近的改動。

(3)取得堆棧軌跡。

(4)鍵入前仔細(xì)讀一讀。

(5)把代碼解釋給別人。

3)寫測試代碼

如果上面的方法都不能幫助定位程序中的錯誤，這時我們可以編寫自己的檢查函數(shù)去測試某些條件，打印出相關(guān)變量的值或者終止程序，如下所示：另外，還可以把對Check的調(diào)用加到程序里可能需要它的地方，如下所示：

Check(“beforesuspect”);

//…suspectcode…

Check(“aftersuspect”);

即使在錯誤排除后，也不要簡單地將Check丟掉，而應(yīng)讓它留在源程序里，將它寫成注釋或者用一個排錯選項(xiàng)來控制它，以便在遇到問題時還可以重新啟用。

2．測試

1)測試代碼的邊界情況

在編寫好一個簡單的代碼段，如一個循環(huán)或一個條件分支語句之后，就應(yīng)該檢查條件所導(dǎo)致的分支是否正確，循環(huán)實(shí)際執(zhí)行的次數(shù)是否正確等。這種工作稱為邊界條件測試，原因是這種檢查是在程序和數(shù)據(jù)的自然邊界上。例如，檢查不存在的或者空的輸入，單個的輸入數(shù)據(jù)項(xiàng)，一個正好填滿了的數(shù)組等。這里要強(qiáng)調(diào)的是：大部分錯誤都出現(xiàn)在邊界上。如果一段代碼出錯，則錯誤最可能是出現(xiàn)在邊界上。

2)測試前置條件和后置條件

通過驗(yàn)證在某段代碼執(zhí)行前所期望的或必須滿足的性質(zhì)(前條件)，執(zhí)行后的性質(zhì)(后條件)是否成立，是防止錯誤發(fā)生的一個方法。保證輸入取值在某個范圍之內(nèi)是前置條件測試的一種常見例子。

3)使用斷言

C語言<assert.h>里提供了一種斷言機(jī)制，它鼓勵給程序加上前/后條件測試。斷言失敗將會終止程序，所以這種機(jī)制通常是保留給某些特殊情況使用的，寫在這里的錯誤是不應(yīng)該出現(xiàn)的，而且是無法恢復(fù)的。

4)防御性的程序設(shè)計

還有一種很有用的技術(shù)，那就是在程序里增加一些代碼，專門處理所有“不可能”出現(xiàn)的情況，也就是處理那些從邏輯上講是不可能發(fā)生的，但是或許(由于其他地方的某些失誤)可能出現(xiàn)的情況。前面討論的在Average里加上檢查數(shù)組長度是否為0或者負(fù)數(shù)就是一個例子。

5)以遞增方式做測試

測試應(yīng)該與程序的構(gòu)造同步進(jìn)行。與逐步推進(jìn)的方式相比，以“大爆炸”方式先寫出整個程序，然后做測試，面臨的困難較多，通常也要花費(fèi)更長時間。寫出程序的一部分并測試，加上一些代碼后再進(jìn)行測試，如此下去，這樣做效果會更好。如果有兩個程序包，且都已經(jīng)寫好并經(jīng)過了測試，那么就把它們直接連接起來測試，看看它們能否在一起工作。

6)弄清所期望的輸出

對于所有測試，都必須知道正確的答案是什么，如果不知道，那么所做的測試就是白白浪費(fèi)時間了。

7)測試自動化

以手工方式做大量測試既枯燥無味又很不可靠，嚴(yán)格意義上的測試總要涉及大量的測試實(shí)例，大量的輸入以及大量的輸出比較，所以測試最好由程序來做，原因是程序不會疲勞，也不會疏忽?；c(diǎn)時間編寫一個簡單程序，用它包裝起所有的測試，這樣我們就可以通過一個按鍵使得測試順利執(zhí)行。

8)測試用例的設(shè)計

所謂測試用例，就是以發(fā)現(xiàn)錯誤為目的而精心設(shè)計的一組測試數(shù)據(jù)。測試一個程序，往往需要一組測試用例。每一個完整的測試用例，不僅包含有被測程序的輸入數(shù)據(jù)，而且還包括用這組數(shù)據(jù)執(zhí)行被測程序后預(yù)期的輸出結(jié)果。每次測試時，都要把實(shí)測的結(jié)果與期望的結(jié)果做比較，若不相符，就表明程序可能存在錯誤。(1)等價分類法。

(2)邊界值分析法。

(3)錯誤猜測法。

(4)因果圖法。

(5)邏輯覆蓋法。

①語句覆蓋。

②判定覆蓋。

③條件覆蓋。

④條件組合覆蓋。

1.4.5程序性能

(1)可維護(hù)性。

(2)可靠性。

(3)效率。

1.5程序設(shè)計的步驟及實(shí)例

1.5.1程序設(shè)計的步驟

程序設(shè)計的步驟如下：

1．明確問題的要求

對要解決的問題，必須通過分析明確題目的要求，列出所有已知量，找出題目的求解范圍、解的精度等。

2．分析問題與問題分解

根據(jù)問題的要求，明確程序應(yīng)具有哪些功能，分析清楚解決問題的流程，以及這些功能如何有效地組織在一起解決問題。

3．設(shè)計程序結(jié)構(gòu)

層次結(jié)構(gòu)是一種主要的程序結(jié)構(gòu)。在結(jié)構(gòu)化程序設(shè)計中，程序?qū)哟谓Y(jié)構(gòu)設(shè)計的依據(jù)是：為了實(shí)現(xiàn)程序的功能需要哪些支持，這些支持與程序的功能要求就構(gòu)成了程序的“一級”程序?qū)哟谓Y(jié)構(gòu)。假設(shè)程序功能要求為G，為了實(shí)現(xiàn)G必須有五個支持(S1，S2，S3，S4，S5)，那么該程序的一級層次結(jié)構(gòu)如圖1-16所示。圖1-16層次結(jié)構(gòu)設(shè)計的基本原理

4．算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計

在程序結(jié)構(gòu)設(shè)計完成之后，需要對其中的每一個模塊進(jìn)行更詳細(xì)的設(shè)計，該設(shè)計過程一般稱為模塊設(shè)計或函數(shù)設(shè)計。

5．編寫程序?qū)崿F(xiàn)

在程序結(jié)構(gòu)框架和所有模塊設(shè)計完成之后，接下來的工作是采用某種程序設(shè)計語言實(shí)現(xiàn)上述設(shè)計。程序?qū)崿F(xiàn)時需要考慮的問題有：選擇程序設(shè)計語言，界面設(shè)計，程序風(fēng)格和實(shí)現(xiàn)程序時的其他細(xì)節(jié)問題。

把整個程序看做一個整體，先全局后局部，自頂向下，一層一層地分解處理，如果某些子問題的算法相同而僅參數(shù)不同，則可以用子程序來表示。

6．調(diào)試運(yùn)行

調(diào)試程序的過程就是排錯的過程，其目的是解決程序中的語法錯誤和明顯的邏輯錯誤。語法錯誤可根據(jù)系統(tǒng)的提示修改。明顯的邏輯錯誤表現(xiàn)為運(yùn)行結(jié)果不正確，對此一般采用的方法是跟蹤程序的運(yùn)行過程，發(fā)現(xiàn)錯誤出現(xiàn)的位置，并做相應(yīng)的修改。

7．測試與結(jié)果分析

測試的目的是發(fā)現(xiàn)調(diào)試時未能發(fā)現(xiàn)的錯誤。一般的方法是給出測試用例，并運(yùn)行程序，分析期望的運(yùn)行結(jié)果與實(shí)際運(yùn)行結(jié)果。如果兩個結(jié)果不一致，則需要分析原因，并改正。

8．寫出程序的文檔

程序的文檔主要用來對程序中的變量、函數(shù)或過程做必要的說明，解釋編程思路，畫出框圖，討論運(yùn)行結(jié)果等。1.5.2程序設(shè)計實(shí)例

1．問題與分析

很多讀者看到該問題后認(rèn)為：問題簡單，容易實(shí)現(xiàn)。實(shí)際情況真是這樣嗎？完全不是。真實(shí)情況是很多學(xué)生在8個小時的實(shí)驗(yàn)時間內(nèi)沒有完成程序設(shè)計。其原因歸納起來有兩條：一是沒有完全理解問題；二是基礎(chǔ)薄弱，面對較大的程序無從下手。圖1-17學(xué)生信息查詢問題的原型

2．問題處理流程與問題分解

圖1-17僅僅說明了問題，并沒有給出具體的處理問題過程，下面將從學(xué)生信息查詢的實(shí)際過程來進(jìn)一步說明處理該問題的流程。

程序的使用者有兩類：一是查詢者；二是維護(hù)者。因此將處理流程分為查詢者流程和維護(hù)者流程。查詢者的使用步驟如下：

(1)啟動查詢過程；

(2)選擇查詢方式；

(3)輸入查詢條件；

(4)根據(jù)查詢條件在學(xué)生信息文件中查詢；

(5)顯示查詢結(jié)果；

(6)結(jié)束本次查詢。

對于查詢者而言，處理問題的流程如圖1-18所示。圖1-18查詢請求的處理流程維護(hù)者的使用步驟如下：

(1)啟動維護(hù)過程；

(2)選擇維護(hù)方式；

(3)輸入維護(hù)內(nèi)容；

(4)根據(jù)維護(hù)方式和維護(hù)內(nèi)容維護(hù)學(xué)生信息文件；

(5)顯示維護(hù)結(jié)果；

(6)結(jié)束本次維護(hù)。

對于維護(hù)者而言，處理問題的流程如圖1-19所示。圖1-19維護(hù)請求的處理流程根據(jù)問題的分析和初步的處理流程，可以將問題分解為兩個子問題：查詢和維護(hù)，如圖1-20所示。圖1-20問題分解假設(shè)經(jīng)過交流得到的查詢功能要求如下：

(1)根據(jù)學(xué)號或姓名能夠完成學(xué)生基本信息及學(xué)生家庭信息等的查詢；

(2)根據(jù)家庭所在地(地址)和系別查詢學(xué)生的基本信息。

經(jīng)過與問題提出人員交流得到的維護(hù)功能要求如下：

(1)根據(jù)學(xué)號修改學(xué)生的信息；

(2)增加一個新學(xué)生的信息；

(3)刪除一個學(xué)生的信息。據(jù)此可以得到維護(hù)的功能包括：修改學(xué)生信息，插入一個新學(xué)生的信息，刪除一個學(xué)生的信息。

根據(jù)上述要求和功能劃分，對問題做進(jìn)一步的分解，其分解的結(jié)果如圖1-21所示。圖1-21對子問題的進(jìn)一步分解根據(jù)問題分解的結(jié)果對問題處理流程進(jìn)一步細(xì)化，得到如圖1-22和圖1-23所示的細(xì)化后的查詢和維護(hù)處理流程。圖1-22細(xì)化后的查詢處理流程圖1-23細(xì)化后的維護(hù)處理流程

3．程序結(jié)構(gòu)

根據(jù)上述分析，整個程序應(yīng)具有兩部分功能：查詢和維護(hù)。現(xiàn)在面臨的問題是如何將兩部分功能集成在一起。

查詢和維護(hù)功能的集成與程序的實(shí)際應(yīng)用模式有關(guān)。程序的應(yīng)用模式有兩種：一種是一體模式，即查詢和維護(hù)功能集中在一個應(yīng)用界面下；另一種模式是分離模式，即查詢和維護(hù)功能分別實(shí)現(xiàn)，且維護(hù)功能采用遠(yuǎn)程或“離線”方式對學(xué)生信息進(jìn)行更新。由于第二種模式需要網(wǎng)絡(luò)方面