基礎(chǔ)編程的思考方法

焦 華

（貴州商學(xué)院，貴州 貴陽(yáng) 550014）

0 引言

傳說(shuō)著名的瑞士計(jì)算機(jī)科學(xué)家尼克拉斯·沃思（Nicklaus Wirth）是憑借一句話獲得圖靈獎(jiǎng)的，這句話就是眾所周知的著名公式：“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，即程序包含了對(duì)數(shù)據(jù)的描述和對(duì)操作的描述兩個(gè)方面——計(jì)算機(jī)的操作對(duì)象和操作步驟。[1]比如已知三角形的三個(gè)邊a、b、c，用海倫公式求三角形的面積。數(shù)據(jù)的描述是a、b、c、p、s；算法的簡(jiǎn)單描述如下（為簡(jiǎn)單起見(jiàn)，這里假定輸入的a、b、c滿足兩邊之和大于第三邊）：

Wirth公式對(duì)計(jì)算機(jī)科學(xué)的影響程度類似于物理學(xué)中愛(ài)因斯坦的質(zhì)能方程“E=MC2”——一個(gè)公式揭示了程序的本質(zhì)。事實(shí)上這個(gè)公式是 Wirth在1976年寫(xiě)的一本名著的書(shū)名——《Algorithms +Data Structures = Programs》。Wirth被譽(yù)為 PASCAL之父，同時(shí)也是好幾種編程語(yǔ)言的主設(shè)計(jì)師，結(jié)構(gòu)化程序設(shè)計(jì)的思想方法也是Wirth在上世紀(jì)70年代提出的。“頂層設(shè)計(jì)→逐步求精→模塊實(shí)現(xiàn)”在當(dāng)時(shí)的程序設(shè)計(jì)領(lǐng)域引發(fā)了一場(chǎng)革命，具有里程碑的意義，完全改變了人們對(duì)編程的思維方式。世界的復(fù)雜性與人類思維的局限性使得結(jié)構(gòu)化編程方法是解決這一矛盾的有力工具！擴(kuò)展的Wirth公式是：“算法+數(shù)據(jù)結(jié)構(gòu)+結(jié)構(gòu)化程序設(shè)計(jì)方法+語(yǔ)言工具=結(jié)構(gòu)化程序”。因此 1984年獲得的圖靈獎(jiǎng)是對(duì) Wirth一系列重大貢獻(xiàn)的回報(bào)[2]。

應(yīng)當(dāng)說(shuō)Wirth公式貫穿了過(guò)程化程序設(shè)計(jì)始終，可以將所有的知識(shí)點(diǎn)都串起來(lái)。比如C語(yǔ)言程序設(shè)計(jì)包含的內(nèi)容有：程序設(shè)計(jì)及C語(yǔ)言、算法——程序的靈魂、順序結(jié)構(gòu)程序設(shè)計(jì)、分支結(jié)構(gòu)程序設(shè)計(jì)、循環(huán)結(jié)構(gòu)程序設(shè)計(jì)、用函數(shù)實(shí)現(xiàn)模塊化程序設(shè)計(jì)、利用數(shù)組處理批量數(shù)據(jù)、善于利用指針、結(jié)構(gòu)體與共用體、對(duì)文件的輸入輸出。可以看出，這些內(nèi)容都包含于擴(kuò)展的Wirth公式中。

未來(lái)有眾多的不確定性但不容置疑的是大數(shù)據(jù)時(shí)代已經(jīng)到來(lái)，大數(shù)據(jù)的世界是程序的世

界！Wirth公式指出，算法是程序的靈魂，從而大數(shù)據(jù)的世界就是算法的世界！因此有必要對(duì)基礎(chǔ)編程的核心——Wirth公式蘊(yùn)含的思想加以梳理，相關(guān)概念和內(nèi)容進(jìn)行再認(rèn)識(shí)。

1 W irth公式中相關(guān)概念的重述與再認(rèn)識(shí)

計(jì)算機(jī)有硬件與軟件之分，軟件是程序和程序文檔的總稱，計(jì)算機(jī)的本質(zhì)是“執(zhí)行程序的機(jī)器”。由于 Wirth公式揭示了程序的本質(zhì)，在此重溫其相關(guān)術(shù)語(yǔ)和內(nèi)容[3]。

算法（Algorithm）通俗地講，是解決問(wèn)題的方法與步驟；在數(shù)學(xué)中，算法通常是指遵照一定的規(guī)則解決某一類問(wèn)題明確的且有效的步驟；在計(jì)算機(jī)科學(xué)中，算法是指解題方案的既準(zhǔn)確又完整的描述，是一系列清晰指令的有限序列。算法應(yīng)當(dāng)具備正確性、有窮性、可讀性、健壯性、人機(jī)交互性等特征。

數(shù)據(jù)（Data）是客觀事物的符號(hào)表示，計(jì)算機(jī)科學(xué)里是指能輸入至計(jì)算機(jī)且被計(jì)算機(jī)程序加工處理的符號(hào)的總稱。

數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位，計(jì)算機(jī)程序通常將它作為一個(gè)整體加以處理和考慮。

數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指數(shù)據(jù)元素自身特征以及它們之間的相互關(guān)系（結(jié)構(gòu)）。它有四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖或網(wǎng)狀結(jié)構(gòu)。

數(shù)據(jù)類型（Data Type）是與數(shù)據(jù)結(jié)構(gòu)密切有關(guān)的概念，最先出現(xiàn)在計(jì)算機(jī)高級(jí)語(yǔ)言中，用來(lái)刻畫(huà)程序操作對(duì)象的特性。它是一個(gè)值的集合以及定義在該值集上一組操作的總稱。

算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系：算法依賴于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)關(guān)系到算法的選擇與效益。因此很多時(shí)候是先確定數(shù)據(jù)結(jié)構(gòu)，再確定算法。

程序（Program）是一組計(jì)算機(jī)能識(shí)別和執(zhí)行的指令序列。編寫(xiě)程序的人稱為程序員，編寫(xiě)程序的活動(dòng)或過(guò)程稱為程序設(shè)計(jì)。

類比實(shí)例 1：一盤(pán)已做好的美味菜肴比作一個(gè)程序，菜譜中需要的食材、佐料相當(dāng)于數(shù)據(jù)結(jié)構(gòu)，菜譜中的操作流程相當(dāng)于算法，廚師相當(dāng)于程序員，烹飪的過(guò)程相當(dāng)于程序設(shè)計(jì)。

類比實(shí)例 2：一座已建好的雄偉建筑比作一個(gè)程序，建筑中需要的鋼筋、水泥、磚瓦等建材相當(dāng)于數(shù)據(jù)結(jié)構(gòu)，動(dòng)工之前的建筑物設(shè)計(jì)圖相當(dāng)于算法，設(shè)計(jì)師及建筑工人相當(dāng)于程序員，從動(dòng)工到完工驗(yàn)收的過(guò)程相當(dāng)于程序設(shè)計(jì)。

在擴(kuò)展的Wirth公式中，如果將“數(shù)據(jù)結(jié)構(gòu)+語(yǔ)言工具”比作人體的組織、器官，那么“算法+結(jié)構(gòu)化程序設(shè)計(jì)方法”則是人的思想、靈魂。你可以用你的思想去支配你身體的各器官隨意運(yùn)動(dòng)。深入下去就是哲學(xué)中物質(zhì)與意識(shí)的關(guān)系。

2 用流程圖表示算法

程序的概念從“指令序列”轉(zhuǎn)到“算法+數(shù)據(jù)結(jié)構(gòu)”，兩者并不矛盾，而是為解決問(wèn)題必經(jīng)的具體化歷程。比如線性方程組的求解要用到初等行變換算法；而職工工資收入的高低排列要用到排序算法。算法的表示就是解決具體問(wèn)題的思路描述[4]。

算法的表示（描述）方法有：自然語(yǔ)言、流程圖、N—S結(jié)構(gòu)圖、PAD問(wèn)題分析圖、偽代碼、計(jì)算機(jī)語(yǔ)言等。實(shí)際上用計(jì)算機(jī)語(yǔ)言表示算法就已經(jīng)是源程序了。

最早描述算法應(yīng)當(dāng)是自然語(yǔ)言，雖然這種方式通俗易懂但容易出現(xiàn)歧義，且描述分支和循環(huán)極不方便，于是人們發(fā)明了流程圖。這是用一些圖框來(lái)表示各種操作，圖形表示的算法既直觀形象又易于理解。

實(shí)例1：判定2000——2500年中每一個(gè)年份是否是閏年，并將結(jié)果輸出。

算法的流程圖如下：

一級(jí)算法：

圖1 判定閏年的一級(jí)算法流程圖[5]Fig.1 Flow chart of first order algorithm for judging leap year

二級(jí)求精：

圖2 判定閏年的細(xì)化流程圖Fig.2 A thinning flow chart for judging leap year

其實(shí)二級(jí)求精流程圖可以簡(jiǎn)化、不需要分支嵌套，故意復(fù)雜化是編程訓(xùn)練的需要。

實(shí)例 2：歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)正整數(shù)a，b的最大公約數(shù)。

歐幾里得算法的流程圖如下[6]：

3 程序（流程）的三種基本結(jié)構(gòu)

在傳統(tǒng)的流程圖中是用流程線來(lái)指明各框的執(zhí)行順序，對(duì)流程線的使用無(wú)限制，于是亂麻一樣的“面條算法”出現(xiàn)了。為解決這一問(wèn)題，Bohra和Jacopini在1966年提出了三種基本結(jié)構(gòu)——順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，用這三種基本結(jié)構(gòu)作為基本單元去搭建的算法稱為結(jié)構(gòu)化算法。可以證明無(wú)論多么復(fù)雜的流程都可以用三種基本結(jié)構(gòu)排列、組合、嵌套得到（所有非結(jié)構(gòu)化算法可轉(zhuǎn)化為結(jié)構(gòu)化算法）。色彩學(xué)上的三色理論，是指紅、綠、藍(lán)這三種顏色相互獨(dú)立，但自然界的任何色彩都可以由三種顏色按不同的比例混合而成。順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)相互獨(dú)立，雖然人類開(kāi)發(fā)的程序千千萬(wàn)萬(wàn)，但任何程序都可用這三種基本結(jié)構(gòu)搭建得到，如同俄羅斯方塊游戲中用七種不同形狀的構(gòu)件去搭建城墻一樣[7]。

圖3 歐幾里德算法流程圖Fig.3 Flow chart of euclid algorithm

順序結(jié)構(gòu)強(qiáng)調(diào)流程的次序，先做什么后做什么很重要，次序不能顛倒。比如一個(gè)大學(xué)生早晨起床后要做的事：穿衣→洗臉?biāo)⒀馈頃?shū)包→食堂吃飯→教室上課。如果次序改變?yōu)椋合茨標(biāo)⒀馈┮隆程贸燥垺厮奚嵴頃?shū)包→教室上課。這將是糟糕的順序。自然與社會(huì)中的時(shí)間次序、空間次序、事件次序可以舉出很多例子。

選擇結(jié)構(gòu)也稱為分支結(jié)構(gòu)，在多種選擇（分支）中只能取一種，如同在多岔路口你只能走其中的一條。“選擇比努力更重要”表達(dá)的就是一旦選定將無(wú)法更改，這世界從來(lái)沒(méi)有“后悔藥”，“機(jī)會(huì)”錯(cuò)過(guò)就不再有了。

循環(huán)結(jié)構(gòu)也稱為重復(fù)結(jié)構(gòu)，是指反復(fù)執(zhí)行某一部分操作。循環(huán)是天體宇宙的法則。地球每天都在孤獨(dú)地旋轉(zhuǎn)：自轉(zhuǎn)一圈24小時(shí)，形成白天黑夜的交替；公轉(zhuǎn)一圈365天，形成春夏秋冬的輪回。生活在地球上的人類也因此“日出而作，日落而棲”地重復(fù)，感受春花秋月的浪漫、夏日冬雪的無(wú)奈……。

“順序不能倒、選擇是唯一、循環(huán)有條件”是三種基本結(jié)構(gòu)必須遵循的原則，三種基本結(jié)構(gòu)是自然和社會(huì)的法則。在計(jì)算機(jī)科學(xué)中，我們只要定義了三種基本結(jié)構(gòu)的圖形表示，任何復(fù)雜問(wèn)題的算法都可由這三種圖形排列、組合、嵌套得到[8]。

值得一提的是另一種非主流的觀點(diǎn)認(rèn)為：流程不是三種而是四種基本結(jié)構(gòu)，它將函數(shù)的調(diào)用回返也作為一種基本結(jié)構(gòu)，這種思考方式可理解為函數(shù)的調(diào)用回返是和順序、選擇、循環(huán)一樣，都是相當(dāng)重要的結(jié)構(gòu)。

4 用N—S結(jié)構(gòu)圖和PAD問(wèn)題分析圖表示算法

N—S結(jié)構(gòu)圖也稱為盒圖，是由美國(guó)學(xué)者I.Nassi和 B.Shneiderman于1973年提出的一種在流程圖中完全去除流程線，所有算法寫(xiě)在一個(gè)矩形框內(nèi)，在框內(nèi)還可以包含其他從屬于它的框，即大框套小框、框框排列的形式表達(dá)算法。命名為N-S結(jié)構(gòu)流程圖是紀(jì)念這兩位學(xué)者的（用兩個(gè)人姓名的頭一個(gè)字母組成）。N—S結(jié)構(gòu)圖特別能表達(dá)“自頂向下、逐步細(xì)化、模塊化”的編程思想，與中國(guó)古代哲學(xué)“太極生兩儀、兩儀生四象；四象生八卦、八卦定乾坤。”是相通的[9]。

實(shí)例2歐幾里得算法的N—S結(jié)構(gòu)圖如下：

圖4 歐幾里德算法的N—S結(jié)構(gòu)圖Fig.4 N - S structure diagram of euclid algorithm

PAD問(wèn)題分析圖[problem analysis diagram]是日本日立公司二村良彥等人于 1973年提出的一種表示算法的圖形工具。其優(yōu)點(diǎn)是PAD圖是二維樹(shù)形結(jié)構(gòu)，從上到下的各部分是流程執(zhí)行順序，而從左往右的展開(kāi)則代表層次關(guān)系。它的特點(diǎn)是結(jié)構(gòu)清晰、易于閱讀、結(jié)構(gòu)化程度高。最左邊縱線是程序的主干線，對(duì)應(yīng)于程序第一層結(jié)構(gòu)，之后每增加一層，PAD圖就向右擴(kuò)展一條縱線，縱線數(shù)就是程序?qū)哟螖?shù)。程序執(zhí)行時(shí)是從PAD圖最左邊主干線的上端結(jié)點(diǎn)開(kāi)始，從上而下、自左往右依次執(zhí)行，最后終止于最左主干線[2]。

實(shí)例2歐幾里得算法的PAD問(wèn)題分析圖如下：

圖5 歐幾里德算法的PAD問(wèn)題分析圖Fig.5 PAD problem analysis diagram of euclid algorithm

偽代碼是使用自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之間的文字及符號(hào)來(lái)表示算法。軟件從業(yè)人員一般習(xí)慣使用偽代碼，這是由于復(fù)雜而龐大的問(wèn)題，畫(huà) N—S結(jié)構(gòu)圖或PAD問(wèn)題分析圖很費(fèi)事，使用偽代碼不受約束、自由自在。偽代碼還有容易轉(zhuǎn)化為真代碼（源程序）的優(yōu)勢(shì)，但表達(dá)的流程不清晰、不直觀、尤其對(duì)分支與循環(huán)描述困難。

傳統(tǒng)流程圖、N—S結(jié)構(gòu)圖、PAD問(wèn)題分析圖是基礎(chǔ)編程的基本功！是學(xué)習(xí)程序設(shè)計(jì)必經(jīng)的思維訓(xùn)練歷程！

5 結(jié)構(gòu)化程序設(shè)計(jì)方法

結(jié)構(gòu)化程序設(shè)計(jì)是用工程的方法設(shè)計(jì)程序。其基本思想就是“自頂向下、逐步細(xì)化、模塊化編程”，是將問(wèn)題的求解從抽象逐步具體化的過(guò)程。在模塊化分工完成后，即把一個(gè)大任務(wù)分解為若干個(gè)子任務(wù)后，對(duì)每一個(gè)子任務(wù)（小模塊）的編碼則是“自下而上、逐步積累”的過(guò)程。類比例子是設(shè)計(jì)房屋，先要“自頂向下、逐步細(xì)化”作整體規(guī)劃、確定建筑物方案……有了設(shè)計(jì)圖之后，施工階段則是一磚一瓦“自下而上、逐步積累”完成的[2]。

實(shí)例3：輸入兩個(gè)自然數(shù)a與b，求出它們的最大公約數(shù)和最小公倍數(shù)。

C語(yǔ)言是函數(shù)式的語(yǔ)言，它的特點(diǎn)決定了它是最容易實(shí)現(xiàn)結(jié)構(gòu)化編程的優(yōu)秀語(yǔ)言。在C語(yǔ)言中對(duì)一個(gè)較復(fù)雜的規(guī)模較大的問(wèn)題編程時(shí)，代碼通常由一個(gè)主函數(shù)和若干個(gè)其它函數(shù)組成。一個(gè)函數(shù)就是一個(gè)程序模塊。主函數(shù)可調(diào)用其它函數(shù)，其它函數(shù)也可相互調(diào)用，但主函數(shù)只能被操作系統(tǒng)調(diào)用。同一函數(shù)可被一個(gè)或多個(gè)函數(shù)調(diào)用任意多次（“代碼重用”）。函數(shù)必須先定義后使用，函數(shù)之間的關(guān)系是相互獨(dú)立的、地位是平行的。和“組裝汽車”、“組裝電腦”相類似，結(jié)構(gòu)化編程就是“組裝程序”，而函數(shù)就是“組裝程序”的部件。

下面的函數(shù)調(diào)用回返的樹(shù)型模塊圖（方向向右的樹(shù)，可旋轉(zhuǎn)改變方向。）可反映復(fù)雜程序的結(jié)構(gòu)脈絡(luò)。

圖6 逐步細(xì)化的N—S結(jié)構(gòu)圖Fig.6 A gradually refined N - S structure diagram

圖7 函數(shù)調(diào)用回返的樹(shù)型模塊圖Fig.7 Tree module diagram of function call return

上圖中注意函數(shù)調(diào)用的層次、調(diào)用回返的順序。箭頭旁的數(shù)字代表順序號(hào)，調(diào)用回返過(guò)程形成一個(gè)個(gè)閉合回路。從抽象到具體可看下面的簡(jiǎn)化的實(shí)例[2]：

實(shí)例 4：圖書(shū)館管理系統(tǒng)樹(shù)型模塊圖（方向向下的樹(shù)，可旋轉(zhuǎn)改變方向。）

實(shí)例 5：C語(yǔ)言程序設(shè)計(jì)內(nèi)容樹(shù)型模塊圖（方向向下的樹(shù)，可旋轉(zhuǎn)改變方向。）

模塊化編程從設(shè)計(jì)到實(shí)現(xiàn)就象從“庖丁解牛”到“全牛宴”，是編程學(xué)習(xí)者必經(jīng)的心路歷程。語(yǔ)法和算法是貫穿程序設(shè)計(jì)語(yǔ)言的兩條線索，這兩條線索交織在一起，構(gòu)成計(jì)算機(jī)高級(jí)語(yǔ)言編程的結(jié)構(gòu)體系。在此只牽出程序的靈魂——算法的線索，這是所有高級(jí)語(yǔ)言的共性。至于語(yǔ)法各種高級(jí)語(yǔ)言各有千秋[10]。

圖8 圖書(shū)館管理系統(tǒng)樹(shù)型模塊圖Fig.8 The tree model diagram of the library management system

圖9 C 語(yǔ)言程序設(shè)計(jì)內(nèi)容樹(shù)型模塊圖Fig.9 C language program design content tree module diagram

大數(shù)據(jù)的世界是程序的世界、人工智能的世界也是程序的世界，所以在此探討、提煉基礎(chǔ)編程的思考方法很有必要，因?yàn)檫@是通向未來(lái)的必經(jīng)之路。

[1] 焦華. C/C++編程中典型案例分析與思路拓展[J]. 《電腦與信息技術(shù)》2017-6.

[2] 譚浩強(qiáng). C程序設(shè)計(jì)(第四版)[M]. 清華大學(xué)出版社2010年.

[3] 梅創(chuàng)社. C語(yǔ)言程序設(shè)計(jì)[M]. 北京理工大學(xué)出版社2010年.

[4] 施鍵蘭, 黃文秀, 楊立娟. C語(yǔ)言程序設(shè)計(jì)教學(xué)探討[J]. 軟件, 2013, 34(1): 171-172.

[5] 姜蘊(yùn)莉. 以興趣為導(dǎo)向的高職院校《c#程序設(shè)計(jì)》教學(xué)改革探討[J]. 軟件, 2014, 35(10): 87-90.

[6] 施鍵蘭, 黃文秀. 程序設(shè)計(jì)類課程中的教改研究[J]. 軟件,2016, 37(3): 34-35.

[7] 陳強(qiáng). C#編程新手自學(xué)手冊(cè)[M]. 機(jī)械工業(yè)出版社2012年.

[8] 郭旭靜, 周麗娜, 尚佳棟, 等. 一種可編程實(shí)現(xiàn)的Ramanujan 和計(jì)算方法[J]. 新型工業(yè)化, 2013, 3(2): 61-70.

[9] 唐建中, 陳曉亮. 可編程電液比例系統(tǒng)控制器[J]. 新型工業(yè)化, 2013, 3(9): 99-105.

[10] 焦華. C編程教學(xué)導(dǎo)入線索分析[J]. 《電腦知識(shí)與技術(shù)》2017-4.