大學(xué)信息技術(shù)基礎(chǔ)：第6章 軟件設(shè)計基礎(chǔ)

1、第6章 軟件設(shè)計基礎(chǔ)n主要內(nèi)容：l6.1 6.1 算法與程序算法與程序l6.2 6.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)l6.3 6.3 程序設(shè)計方法程序設(shè)計方法l* *6.4 6.4 軟件工程軟件工程n本章小結(jié)n思考與練習(xí)n6.1.1 算法的基本概念l1.什么是算法u通俗點說，算法就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。u計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機應(yīng)用系統(tǒng)中的軟件，都必須用一個個具體的算法來實現(xiàn)。l2.算法的特征u（1）可行性針對實際問題設(shè)計的算法，人們總是希望能夠得到滿意的結(jié)果。6.1 算法與程序u（2）確定性算

2、法的確定性，是指算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。u（3）有窮性算法的有窮性，是指算法必須能在有限的時間內(nèi)做完，即算法必須能在執(zhí)行有限個步驟之后終止。u（4）輸入通常，算法中的各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這是算法執(zhí)行的起點或是依據(jù)。u（5）輸出一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。6.1 算法與程序n6.1.2 算法的表示l1.自然語言u自然語言是人們?nèi)粘Ｋ玫恼Z言，如漢語、英語、德語等。l2.傳統(tǒng)流程圖u流程圖是描述算法的常用工具，可以很方便地表示順序、選擇和循環(huán)結(jié)構(gòu)，因此流程圖可

3、以表示任何程序的邏輯結(jié)構(gòu)。u美國國家標(biāo)準(zhǔn)化協(xié)會ANSI規(guī)定了如下一組圖形符號來表示算法。(見課本P144)6.1 算法與程序u例3 用傳統(tǒng)流程圖描述求1+2+3+100之和的算法。如圖6-1所示。 6.1 算法與程序圖圖6-1 傳統(tǒng)流程圖傳統(tǒng)流程圖l3.N-S圖u主要特點是不帶有流向線，整個算法完全寫在一個大矩形框中，這種流程圖被稱為N-S圖。N-S圖特別適合于結(jié)構(gòu)化程序設(shè)計。u圖6-2給出了N-S圖中各種基本的結(jié)構(gòu)圖框，其中(a)表示順序結(jié)構(gòu)，(b)表示選擇結(jié)構(gòu)，(c)表示當(dāng)型循環(huán)結(jié)構(gòu)，(d)表示直到型循環(huán)結(jié)構(gòu)。6.1 算法與程序u例4 用N-S圖描述求1+2+3+ +100之和的算法。如圖

4、6-3所示。6.1 算法與程序l4.偽代碼u偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。u例5 用偽代碼描述求1+2+3+ +100之和的算法。Begin/*算法開始*/ X=1 Y=2 while （Y=100）do/*循環(huán)執(zhí)行，直到條件不成立為止*/ XX+Y YY+1 Print X/*輸出結(jié)果*/End/*算法結(jié)束*/6.1 算法與程序l5.計算機程序設(shè)計語言u因此用自然語言、流程圖和偽代碼等語言描述的算法最終還必須轉(zhuǎn)換為具體的計算機程序設(shè)計語言編寫的程序。u算法和程序是有區(qū)別的。算法是對解題步驟（過程）的描述，可以與計算機無關(guān)；而程序是利用某種計算機語言對算法

5、的具體實現(xiàn)。n6.1.3 算法設(shè)計的基本方法l1.列舉法u列舉法又稱為窮舉法或枚舉法，其基本思想是：根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的?.1 算法與程序l2.歸納法u歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。l3.遞推法u所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。l4.遞歸法u這種將問題逐層分解的過程，實際上并沒有對問題進(jìn)行求解，而只是當(dāng)解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合，直至最終解決原問題，這就是遞歸的基本思想。u遞歸分為直接遞歸與間接遞歸兩種

6、。6.1 算法與程序u遞推與遞歸的實現(xiàn)方法是大不一樣的，遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果；而遞歸則是從算法本身到達(dá)遞歸邊界而后進(jìn)行回歸的。l5.分治法u所謂分治法，就是對問題分而治之。盡可能地把復(fù)雜問題分解為若干較小的問題，找出各個較小問題的解之后，再組合成整個問題的解。l6.回溯法u通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到了問題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方法稱為回溯法。6.1 算法與程序n6.1.4 算法的評價l1.正確性u正確性是指算法的執(zhí)行結(jié)果應(yīng)該滿足預(yù)先規(guī)定的功能和性能要求。 l2.

7、可讀性u一個算法應(yīng)該思路清晰、層次分明、簡單明了、易讀易懂。l3.健壯性u算法的健壯性指的是，算法應(yīng)對非法輸入的數(shù)據(jù)做出恰當(dāng)反映或進(jìn)行相應(yīng)處理。l4.復(fù)雜性6.1 算法與程序u算法的復(fù)雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。 u算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。n6.1.5 程序與程序設(shè)計語言l1.程序u為需要求解的問題設(shè)計好的算法，用程序設(shè)計語言表達(dá)出來后，就得到程序。u計算機程序包含兩方面的內(nèi)容：對象及對象之間的關(guān)系；描述對這些對象進(jìn)行處理的加工規(guī)則。l2.程序設(shè)計語言u程序設(shè)計是根據(jù)特定的問題，使用某種程序設(shè)計語言，設(shè)計計算機執(zhí)行的指令序列。6.1 算法與程序u（1）機器

8、語言u為編寫計算機所能理解的程序，人們最早使用的語言是機器語言。u（2）匯編語言u匯編語言是用助記符來表示每一條機器指令。u由匯編語言編寫的源程序必須經(jīng)過翻譯轉(zhuǎn)變成機器語言程序，計算機才能識別和執(zhí)行。u（3）高級語言u高級語言同人類的自然語言和數(shù)學(xué)表達(dá)方式相當(dāng)接近，其功能更強、可讀性更好、編程也更加方便。u高級語言處理程序有編譯程序和解釋程序兩種。6.1 算法與程序l3.程序與算法、數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系u算法是處理問題的方法和步驟，數(shù)據(jù)結(jié)構(gòu)是算法要處理的數(shù)據(jù)構(gòu)造的邏輯表示形式，最后問題的解由計算機程序給出。u程序的構(gòu)成是和數(shù)據(jù)結(jié)構(gòu)不可分割的。u算法思想決定了程序的質(zhì)量和性能，好的算法可大大提高程

9、序運行的效率，減少時間和空間復(fù)雜性。u算法是建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的，未確定對數(shù)據(jù)如何操作就無法決定如何構(gòu)造數(shù)據(jù)。6.1 算法與程序圖圖6-5 編譯型語言處理程序功能示意圖編譯型語言處理程序功能示意圖n數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下3個方面的問題：l數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。l在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。l對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。n6.2.1 數(shù)據(jù)結(jié)構(gòu)的基本概念l 1.數(shù)據(jù)u數(shù)據(jù)是描述客觀事物的所有能輸入到計算機中并被計算機程序處理的符號的總稱。6.2 數(shù)據(jù)結(jié)構(gòu)l2.數(shù)據(jù)元素u數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機中通常作為一

10、個整體加以考慮和處理。u作為某種處理，其中的數(shù)據(jù)元素一般具有某種共同特征。l3.數(shù)據(jù)對象u數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。l4.數(shù)據(jù)類型u數(shù)據(jù)類型是一個值的集合和定義在這個值的集合上的一組操作的總稱。6.2 數(shù)據(jù)結(jié)構(gòu)l5.數(shù)據(jù)結(jié)構(gòu)u數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一定關(guān)系的數(shù)據(jù)元素的集合以及定義在其上的操作。u（1）數(shù)據(jù)的邏輯結(jié)構(gòu)u所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。u在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系，這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前件與后件關(guān)系來

11、描述。u一個數(shù)據(jù)結(jié)構(gòu)可以用二元組表示，也可以直觀地用圖形表示。6.2 數(shù)據(jù)結(jié)構(gòu)u在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的圓表示，一般稱之為數(shù)據(jù)結(jié)點，簡稱為結(jié)點。u例6-8和例6-9的數(shù)據(jù)結(jié)構(gòu)可以用圖形來表示，如圖6-6和圖6-7所示。u在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點；沒有后件的結(jié)點稱為終端結(jié)點。6.2 數(shù)據(jù)結(jié)構(gòu)圖圖6-6 一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示圖圖6-7 家庭成員關(guān)系數(shù)據(jù)結(jié)構(gòu)的圖形表示家庭成員關(guān)系數(shù)據(jù)結(jié)構(gòu)的圖形表示u（2）數(shù)據(jù)的存儲結(jié)構(gòu)u數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。u為了表示存放在計算機存

12、儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系，在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接和索引等。u（3）對數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的操作u為了在計算機上解決具體問題，數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為如何表示數(shù)據(jù)、如何組織數(shù)據(jù)，以及如何對它們進(jìn)行操作。u以下給出對數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的幾個基本操作：6.2 數(shù)據(jù)結(jié)構(gòu)插入刪除 更新查找排序遍歷l6.線性結(jié)構(gòu)與非線性結(jié)構(gòu)u根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。6.2 數(shù)據(jù)結(jié)構(gòu)6.2 數(shù)據(jù)結(jié)構(gòu)n6.2.2

13、 線性結(jié)構(gòu)l1.線性表u（1）線性表的概念u這些數(shù)據(jù)元素之間除了在表中的排列次序即先后次序不同外，沒有其他的聯(lián)系，這一類的表屬于線性表。u從數(shù)據(jù)結(jié)構(gòu)的角度出發(fā)，線性表是n（n0）個數(shù)據(jù)元素組成的有限序列，記為：（al，a2，an）u（2）線性表的存儲結(jié)構(gòu)u在計算機中存儲線性表，最簡單的方法是順序存儲。u線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：6.2 數(shù)據(jù)結(jié)構(gòu)u線性表中所有元素所占的存儲空間是連續(xù)的。u線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。l2.棧u棧（stack）實際上也是線性表，它是一種限定只在線性表的一端進(jìn)行插入與刪除操作的特殊的線性表。u在棧中，允許插入與刪除的一端稱為

14、棧頂，而不允許插入與刪除的另一端稱為棧底。u如圖6-8所示，即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。u往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素稱為出棧運算。6.2 數(shù)據(jù)結(jié)構(gòu)l3.隊列u隊列（Queues）也是一種操作受限的線性表，要加入的元素總是插入到線性表的末尾，并且又總是從線性表的頭部取出（刪除）元素。圖圖6-8 棧的示意圖棧的示意圖u隊列又稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表，它體現(xiàn)了“先來先服務(wù)”的原則。u在計算機系統(tǒng)中，隊列的思想常用于操作系統(tǒng)的資源調(diào)度。l4.線性鏈表u在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點由兩部分組成，一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部

15、分用于存放指針，稱為指針域。 6.2 數(shù)據(jù)結(jié)構(gòu)圖圖6-9 具有具有6個元素的隊列示意圖個元素的隊列示意圖6.2 數(shù)據(jù)結(jié)構(gòu)u在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。u鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。u在線性鏈表中，用一個專門的指針Head指向線性鏈表中第一個數(shù)據(jù)元素的結(jié)點。6.2 數(shù)據(jù)結(jié)構(gòu)n6.2.3 非線性結(jié)構(gòu)l1.樹形結(jié)構(gòu)u樹（Tree）是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，在這類結(jié)構(gòu)中，元素之間存在著明顯的分支和層次關(guān)系。6.2 數(shù)據(jù)結(jié)構(gòu)圖圖6-13 學(xué)校行政關(guān)系

16、結(jié)構(gòu)樹學(xué)校行政關(guān)系結(jié)構(gòu)樹6.2 數(shù)據(jù)結(jié)構(gòu)u（1）樹的定義樹是由一個或多個結(jié)點組成的有限集合，如圖6-14所示。樹結(jié)構(gòu)的特點是：必有一個特定的稱為根的結(jié)點，根的每個分支稱為子樹，子樹也是一棵樹。圖圖6-14 樹型結(jié)構(gòu)樹型結(jié)構(gòu) 圖圖6-15 兩棵不同的二叉樹兩棵不同的二叉樹u（2）二叉樹二叉樹的特點是：樹中的每個結(jié)點最多只有兩棵子樹。二叉樹的子樹有左右之分，稱為左子樹和右子樹。而且子樹的左右次序是重要的，即使在只有一棵子樹的情況下，也應(yīng)分清楚。例如圖6-15是兩棵不同的二叉樹。u（3）二叉樹的遍歷所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點，使每一個結(jié)點都被訪問一次，而且只被訪問一次

17、。樹的遍歷實質(zhì)上是將二叉樹的各個結(jié)點轉(zhuǎn)換成為一個線性序列來表示。二叉樹的遍歷可分為先序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。6.2 數(shù)據(jù)結(jié)構(gòu)l2.圖形結(jié)構(gòu)u“圖”（Graph）是圖形結(jié)構(gòu)的簡稱。u圖結(jié)構(gòu)與表結(jié)構(gòu)、樹結(jié)構(gòu)的不同之處表現(xiàn)在結(jié)點之間的關(guān)系上，圖是一種更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖中，任意兩個元素中均有可能相關(guān)。u一個圖由有限的頂點（Vertices）和邊（Edge）組成，所以可形式化地用G（V，E）代表一個圖。u圖6-16中的每一個小圓圈代表圖的一個頂點，這個圖有4個頂點，頂點之間有5條邊。因為圖中的邊都沒有方向箭頭，只是表示頂點間的關(guān)系，所以稱為“無向圖”。圖6-17當(dāng)

18、然就應(yīng)該稱作“有向圖”了。6.2 數(shù)據(jù)結(jié)構(gòu)6.2 數(shù)據(jù)結(jié)構(gòu)圖圖6-16 無向圖無向圖 圖圖6-17 有向圖有向圖n6.3.1 程序設(shè)計的一般過程l1.問題描述u程序設(shè)計的最終目的是為了利用計算機求解某一特定問題，因此程序設(shè)計面臨的首要任務(wù)是得到問題的完整和確切的定義。l2.算法設(shè)計u解題過程都是由一定的規(guī)則、步驟組成的，這種規(guī)則就是算法。u為了描述算法，可以使用多種方法。常用的有自然語言、傳統(tǒng)流程圖、NS流程圖、偽代碼和計算機語言等。l3.代碼編制6.3 程序設(shè)計方法u問題定義和算法描述已經(jīng)為程序設(shè)計規(guī)劃好了藍(lán)本，下一步就是用真正的計算機語言表達(dá)了。u有人說代碼編制的過程是算法到計算機語言程序

19、的翻譯過程。l4.調(diào)試運行u通過“編譯程序”或“解釋程序”使人們編寫的程序能夠最終得到執(zhí)行的工作方式，稱為程序的編譯方式和解釋方式。u編譯方式是指將用高級語言編寫好的程序，經(jīng)編譯程序翻譯，形成可由計算機執(zhí)行的機器指令程序的過程。u解釋方式則是將用高級語言編寫好的程序逐條解釋，解釋一句立即執(zhí)行一句，然后再解釋下一句。l5.編寫程序文檔6.3 程序設(shè)計方法u文檔記錄程序設(shè)計的算法、實現(xiàn)以及修改的過程，保證程序的可讀性和可維護(hù)性。n6.3.2 結(jié)構(gòu)化程序設(shè)計l1.結(jié)構(gòu)化程序的基本結(jié)構(gòu)與設(shè)計思想u按照結(jié)構(gòu)化程序設(shè)計的觀點，任何算法功能都可以通過由程序模塊組成的三種基本程序結(jié)構(gòu)（即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循

20、環(huán)結(jié)構(gòu)）的組合來實現(xiàn)。u結(jié)構(gòu)化設(shè)計思想是以模塊化設(shè)計為中心，將待開發(fā)的軟件系統(tǒng)劃分為若干個相互獨立的模塊（圖6-18），一個模塊可以是一條語句、一段程序、一個函數(shù)等。u按照結(jié)構(gòu)化設(shè)計方法設(shè)計出的程序具有結(jié)構(gòu)清晰、可讀性好、易于修改和容易驗證的優(yōu)點。6.3 程序設(shè)計方法6.3 程序設(shè)計方法圖圖6-18 結(jié)構(gòu)化設(shè)計思想是以模塊化設(shè)計為中心結(jié)構(gòu)化設(shè)計思想是以模塊化設(shè)計為中心l2.結(jié)構(gòu)化程序設(shè)計的基本原則u結(jié)構(gòu)化程序設(shè)計的基本原則是采用“自頂向下，逐步求精”的程序設(shè)計方法和“單入口單出口”的控制結(jié)構(gòu)，并限制使用goto語句，因為會破壞程序的結(jié)構(gòu)化，降低程序的可讀性。u首先從問題本身開始，找出解決問題的

21、基本思路，并將其用結(jié)構(gòu)化框圖表示出來。u其次對框圖中的那些比較抽象的、用文字描述的程序模塊做進(jìn)一步的分析細(xì)化，每次細(xì)化的結(jié)果仍用結(jié)構(gòu)化框圖表示。u最后，對如何求解問題的所有細(xì)節(jié)都弄清楚了，便可以根據(jù)這些框圖直接寫出相應(yīng)的程序代碼。6.3 程序設(shè)計方法u先進(jìn)行“頂層設(shè)計”，如圖6-19所示，把要做的三部分工作分別用A、B、C表示。u這三部分還不夠具體，要進(jìn)一步細(xì)化。A部分可以細(xì)化為如圖6-20所示。先輸入n，然后將1輸入給x1，2輸入給x2，1000輸入給X1000。B部分可以細(xì)化為如圖6-21所示。6.3 程序設(shè)計方法圖圖6-19 頂層設(shè)計流程圖頂層設(shè)計流程圖 圖圖6-20 對對A的細(xì)化的細(xì)化

22、u圖6-20中的B1與B2不能再分了。B1處理的方法是：使x1=0，即哪個數(shù)不是素數(shù)，就使它等于0，以后把不等于0的數(shù)打印出來就是所求的素數(shù)表。B3中的循環(huán)體內(nèi)以D標(biāo)志的部分還要進(jìn)一步細(xì)化，對D細(xì)化為如圖6-22所示。6.3 程序設(shè)計方法圖圖6-21 對對B的細(xì)化的細(xì)化 圖圖6-22 對對D的細(xì)化的細(xì)化u圖6-22中的E部分還不夠具體，再進(jìn)一步細(xì)化為如圖6-23所示。u圖6-23中的F部分又細(xì)化為如圖6-24所示。因為首先要判斷某一個xj是否已被去掉，如已被去掉則不必考慮被xi除。至此，已不能也不需要再分解了。6.3 程序設(shè)計方法圖圖6-23 對對E的細(xì)化的細(xì)化 圖圖6-24 對對F的細(xì)化的細(xì)

23、化u再對圖6-19中的C部分進(jìn)行細(xì)化，如圖6-25所示。u對圖6-25中的G部分進(jìn)行細(xì)化，如圖6-26所示。u至此，已將圖6-19分解成為最基本的操作了，將以上這些圖合起來就得到了總的流程圖。6.3 程序設(shè)計方法圖圖6-25 對對C的細(xì)化的細(xì)化 圖圖6-26 對對G的細(xì)化的細(xì)化n6.3.3 面向?qū)ο蟪绦蛟O(shè)計l結(jié)構(gòu)化程序設(shè)計方法雖已得到了廣泛的使用，但有兩個問題仍未得到很好的解決。u一是結(jié)構(gòu)化程序設(shè)計主要是面向過程的，模塊分割主要針對控制流，仍然還含有與人的思維方式不協(xié)調(diào)的地方。u二是該方法在實現(xiàn)中只突出了實現(xiàn)功能的操作方法，而被操作的數(shù)據(jù)處于實現(xiàn)功能的從屬地位，即程序模塊和數(shù)據(jù)結(jié)構(gòu)是松散地耦合

24、在一起。l面向?qū)ο蟮姆纸馔怀稣鎸嵤澜绾统橄蟮膶ο螅紤]的是做什么（What to do）。它將大量的工作由相應(yīng)的對象來完成，程序員在應(yīng)用程序中只需說明要求對象完成的任務(wù)。6.3 程序設(shè)計方法l面向?qū)ο蟮某绦蛟O(shè)計給軟件的發(fā)展帶來了以下益處：u（1）符合人們習(xí)慣的思維方法，便于分析復(fù)雜而多變的問題。u（2）易于軟件的維護(hù)和功能的增減。u（3）可重用性好，能用繼承的方式減少程序開發(fā)所花的時間。u（4）與可視化技術(shù)相結(jié)合，改善了工作界面。6.3 程序設(shè)計方法l1.面向?qū)ο蟮囊恍┗靖拍頻（1）類（class）u類是創(chuàng)建對象實例的模板，是同種對象的集合與抽象，它包含所創(chuàng)建對象的屬性描述和行為特征的定義。

25、l（2）對象（object）u對象是面向?qū)ο蟪绦蛟O(shè)計的核心。u在面向?qū)ο蟮某绦蛟O(shè)計中，對象的概念就是對現(xiàn)實世界中實體的模型化（圖6-27），它是代碼和數(shù)據(jù)的組合，同樣具有自己的狀態(tài)和行為。u 屬性屬性用來表示對象的特性。6.3 程序設(shè)計方法u 方法方法是對對象的各種操作。6.3 程序設(shè)計方法圖圖6-27 對象的概念就是對現(xiàn)實世界中實體的模型化對象的概念就是對現(xiàn)實世界中實體的模型化u 事件對象的事件是指由系統(tǒng)事先設(shè)定的、能被對象識別和響應(yīng)的動作。事件過程：當(dāng)在對象上發(fā)生了事件后，應(yīng)用程序就要處理這個事件，而處理的步驟就是事件過程。事件驅(qū)動：在傳統(tǒng)的面向過程的應(yīng)用程序中，應(yīng)用程序自身控制了代碼的執(zhí)

26、行順序，即代碼的執(zhí)行是從第一行開始，隨著程序流程執(zhí)行代碼的不同部分。l2.面向?qū)ο蟪绦蛟O(shè)計的特點u（1）抽象抽象就是忽略一個主題中與當(dāng)前目標(biāo)無關(guān)的那些方面，以便更充分地注意與當(dāng)前目標(biāo)有關(guān)的方面。面向?qū)ο蟮能浖O(shè)計而言，抽象包括兩個方面，一是數(shù)據(jù)抽象，二是行為（操作與方法）抽象。6.3 程序設(shè)計方法u（2）封裝將數(shù)據(jù)（屬性）和操作數(shù)據(jù)的過程（方法）銜接起來，構(gòu)成一個具有類的對象的描述稱為封裝。封裝一方面通過數(shù)據(jù)抽象，把相關(guān)信息結(jié)合在一起，另一方面簡化了接口。封裝保證了模塊具有較好的獨立性，使得程序維護(hù)修改較為容易。u（3）繼承表示類之間相似性的機制。也就是可以從一個類生成另一個類，派生類（也稱子

27、類）繼承了父類和祖先類的數(shù)據(jù)和操作。u（4）多態(tài)性多態(tài)性是指同一命名方法提供了多態(tài)性結(jié)果，也就是當(dāng)同樣的消息被不同的對象接受時，導(dǎo)致完全不同的行為。6.3 程序設(shè)計方法n本章論述的主要內(nèi)容以“數(shù)據(jù)結(jié)構(gòu)+算法=程序”為主線展開。算法是求解問題的方法和步驟。構(gòu)成算法有兩個要素，即基本操作和控制結(jié)構(gòu)。算法要在計算機上實現(xiàn)，必須轉(zhuǎn)化為某種計算機語言描述的程序。高級程序設(shè)計語言都提供有描述算法控制結(jié)構(gòu)的三種基本結(jié)構(gòu)和完成操作的各種語句，同時也提供各種數(shù)據(jù)類型供程序設(shè)計人員組織程序中的數(shù)據(jù)。但任何語言所提供的數(shù)據(jù)類型都是有限的，遠(yuǎn)遠(yuǎn)不能滿足實際問題求解的需要，因此我們需要研究數(shù)據(jù)結(jié)構(gòu)，以便合理有效地組織實

28、際問題涉及的全部數(shù)據(jù)并交給程序處理。本章小結(jié)n數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及對數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的操作。數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)（線性表、棧、隊列等）與非線性結(jié)構(gòu)（樹、圖等）兩大類，在解決實際問題時選擇合適的數(shù)據(jù)結(jié)構(gòu)，可以把用戶從數(shù)據(jù)存儲細(xì)節(jié)（如存儲單元和地址）中解脫出來，以更方便有效的方法訪問數(shù)據(jù)。程序設(shè)計就是把算法和數(shù)據(jù)結(jié)構(gòu)融為一體，用最少的代價開發(fā)出最好的程序的技術(shù)和方法學(xué)。常用的程序設(shè)計方法主要有結(jié)構(gòu)化程序設(shè)計、面向?qū)ο蠹夹g(shù)、軟件工程方法等。程序編制完畢，需要調(diào)試程序和測試程序，以發(fā)現(xiàn)程序中的錯誤并糾正之。本章小結(jié)n一、思考題l1.什么是算法？算法的特征和基本設(shè)計方法有哪些？l2.請給出表示算法的幾種基本方法。l3.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的存儲結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)包含哪兩個要素？l4.什么是線性表？什么是棧？棧和隊列的區(qū)別是什