王錦程 宋述燕

摘要:面向?qū)ο蟪绦蛟O(shè)計(jì)與各門專業(yè)課程,如“計(jì)算機(jī)基礎(chǔ)”、“操作系統(tǒng)”、“數(shù)據(jù)結(jié)構(gòu)”、“算法設(shè)計(jì)”、“編譯原理”等都是融會(huì)貫通、密切相關(guān)的。因此在程序設(shè)計(jì)課程的教學(xué)環(huán)節(jié)中,逐步滲透各專業(yè)課的基本知識(shí),運(yùn)用適當(dāng)而生動(dòng)的教學(xué)案例,將專業(yè)知識(shí)融入到程序設(shè)計(jì)中,將有助于學(xué)生從更深層次上理解相關(guān)原理和概念,提高學(xué)習(xí)的信心和興趣,建立程序設(shè)計(jì)的思維方式。本文從程序設(shè)計(jì)的過程出發(fā),通過實(shí)例教學(xué)的方式論證了這種教學(xué)方法。

關(guān)鍵詞:高級(jí)程序設(shè)計(jì);專業(yè)課程;教學(xué)

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

“高級(jí)程序設(shè)計(jì)”是一門重要的計(jì)算機(jī)專業(yè)課程,目的是通過對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)思想的把握,培養(yǎng)學(xué)生掌握用計(jì)算機(jī)分析問題、解決問題的思維方式。但是由于該課程內(nèi)容非常抽象,且實(shí)踐性特別強(qiáng),對(duì)于初學(xué)者來說難度較大。同時(shí)由于課時(shí)限制,Console控制臺(tái)環(huán)境下的簡單實(shí)例難以體現(xiàn)出面向?qū)ο蟮膬?yōu)勢,基于語法的講解讓人感到乏味,許多學(xué)生覺得程序設(shè)計(jì)本身枯燥、難懂,高深莫測。以至于課程結(jié)束時(shí),大部分同學(xué)對(duì)語法實(shí)現(xiàn)沒有問題,但面對(duì)實(shí)際問題卻不知道如何下手。如何在短時(shí)間內(nèi)建立學(xué)生的興趣,培養(yǎng)解決實(shí)際問題的能力,是工科教學(xué)中永恒的話題。

計(jì)算機(jī)的課程體系本身是一個(gè)整體,所有課程的結(jié)合都是為了理解并充分利用計(jì)算機(jī)這一現(xiàn)代化工具。在教學(xué)中,將各門課程分開是為了簡化,但在理解時(shí)仍應(yīng)將相關(guān)概念、應(yīng)用領(lǐng)域相結(jié)合。在教學(xué)中我們發(fā)現(xiàn),學(xué)生們剛開始接觸程序設(shè)計(jì)時(shí),對(duì)變量定義、指針分配、數(shù)組訪問等的理解就比較困難。他們知道用變量來存取數(shù)據(jù),但很少關(guān)心這個(gè)數(shù)據(jù)究竟存放在內(nèi)存的什么地方,為什么指針必須先初始化才能使用。這時(shí),不妨給學(xué)生講授一些內(nèi)存訪問的基本知識(shí),讓他們建立起變量、指針與地址的對(duì)應(yīng)關(guān)系?，F(xiàn)在的問題是,教師對(duì)于程序設(shè)計(jì)多是從語法上加以講解,對(duì)于程序的運(yùn)行效率、應(yīng)用領(lǐng)域、編程風(fēng)格極少涉及,許多概念都是在后續(xù)專業(yè)課的學(xué)習(xí)后才逐步理解,這給程序設(shè)計(jì)的初學(xué)者帶來了很大的障礙。如果在教學(xué)中以面向?qū)ο蟮膽?yīng)用為基礎(chǔ),以程序設(shè)計(jì)為主線,在重點(diǎn)介紹程序設(shè)計(jì)方法的同時(shí)將各門專業(yè)課知識(shí)融入其中,將會(huì)使學(xué)生從程序設(shè)計(jì)應(yīng)用的視角來理解這些專業(yè)概念,從而在解決實(shí)際問題時(shí)靈活應(yīng)用;消除對(duì)程序設(shè)計(jì)課程的枯燥感,達(dá)到事半功倍的效果。

1 “高級(jí)程序設(shè)計(jì)”的課程定位

隨著電子技術(shù)和芯片設(shè)計(jì)工藝的發(fā)展,計(jì)算機(jī)硬件一直按照摩爾定律發(fā)展,每18個(gè)月翻一番,處理速度越來越快,價(jià)格成本越來越低,從價(jià)值不菲、主要用于科學(xué)研究的大型計(jì)算機(jī)到現(xiàn)在人們?nèi)粘９ぷ魃钪须S處可見的個(gè)人PC。程序設(shè)計(jì)的目的就是為了充分利用這一現(xiàn)代化的工具,可靠、高效地完成任務(wù),因此程序設(shè)計(jì)其實(shí)是一種人機(jī)交互的方式,簡言之,就是用計(jì)算機(jī)能夠“理解”的語言,告訴它去執(zhí)行某項(xiàng)任務(wù)。當(dāng)然,這個(gè)“理解”需要編譯器的支持,將高級(jí)程序設(shè)計(jì)的語法描述進(jìn)行編譯、連接等,變成計(jì)算機(jī)硬件能夠執(zhí)行的機(jī)器碼,具體編譯的細(xì)節(jié)在編譯原理課程中有重點(diǎn)的介紹。

程序設(shè)計(jì)是一種語言表達(dá),目的是為了人與計(jì)算機(jī)之間的溝通。因此程序設(shè)計(jì)通常有兩方面的特點(diǎn):對(duì)于程序設(shè)計(jì)者,希望能夠精練、高效地說明問題;對(duì)于計(jì)算機(jī),希望語言描述準(zhǔn)確,不會(huì)出現(xiàn)二義性。通過程序設(shè)計(jì)解決一個(gè)具體問題時(shí),大致需要經(jīng)過下列步驟:首先從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型,然后設(shè)計(jì)出解此數(shù)學(xué)模型的算法(Algorithm),該算法與數(shù)據(jù)結(jié)構(gòu)密切相關(guān),最后編寫程序、進(jìn)行測試、調(diào)整優(yōu)化直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題,從中提取操作的對(duì)象,并找出這些操作對(duì)象之間的關(guān)系,然后用數(shù)學(xué)的語言加以描述。

另外,用程序設(shè)計(jì)解決問題時(shí),需要充分、高效地利用現(xiàn)有的計(jì)算機(jī)資源。對(duì)于匯編語言程序設(shè)計(jì)來說,通常直接編寫底層的硬件驅(qū)動(dòng)及管理程序訪問資源;對(duì)于C+ +面向?qū)ο蟮某绦蛟O(shè)計(jì)來說,通常立足于計(jì)算機(jī)硬件、操作系統(tǒng)的基礎(chǔ)之上,在編寫用戶應(yīng)用程序,如常用的各類工具軟件、Office系列等時(shí),通常借助操作系統(tǒng)提供的API(application programming interface)函數(shù)來訪問資源,如用Create Window()來創(chuàng)建一個(gè)窗口,用getchar()來獲取鍵盤上的一個(gè)按鍵值等。操作系統(tǒng)的作用是管理全部的硬件資源、軟件資源及數(shù)據(jù)資源,并提供相關(guān)的API函數(shù)為程序設(shè)計(jì)者調(diào)用。

2操作系統(tǒng):計(jì)算機(jī)資源的管家

計(jì)算機(jī)可以管理哪些資源呢?操作系統(tǒng)告訴我們,總共要管理4種資源:(1)CPU資源:進(jìn)程管理,處理機(jī)調(diào)度;(2)內(nèi)存資源:存儲(chǔ)管理;(3)I/O接口資源:外部設(shè)備管理;(4)文件資源:文件管理。如果需要訪問計(jì)算機(jī)資源,通常利用操作系統(tǒng)所提供的豐富的API函數(shù)來實(shí)現(xiàn),而無需寫驅(qū)動(dòng)程序直接對(duì)資源進(jìn)行訪問,應(yīng)用程序?qū)Σ僮飨到y(tǒng)的函數(shù)調(diào)用過程如圖1 所示。

箭頭①表示操作系統(tǒng)能夠管理系統(tǒng)資源,控制輸入輸出設(shè)備的工作,如文件存取、輸出顯示、聲卡發(fā)聲等;箭頭②表示操作系統(tǒng)能夠感知輸入設(shè)備的狀態(tài)變化,如鼠標(biāo)移動(dòng)、鍵盤按下,并且能夠感知鼠標(biāo)移動(dòng)的方向,具體按下的鍵值。設(shè)計(jì)應(yīng)用程序需要利用輸入輸出設(shè)備或其他計(jì)算機(jī)資源時(shí),并不是由應(yīng)用程序直接訪問,而是借助操作系統(tǒng)。箭頭③表示程序設(shè)計(jì)時(shí)可以通知操作系統(tǒng)執(zhí)行某個(gè)具體的動(dòng)作,如操作系統(tǒng)能夠控制聲卡發(fā)出聲音,但它并不知道應(yīng)該何時(shí)發(fā)出何種聲音,需要通過程序設(shè)計(jì)告知操作系統(tǒng)。箭頭④表示操作系統(tǒng)能夠?qū)⑤斎朐O(shè)備或其他資源的變化傳遞給應(yīng)用程序。如用戶在某個(gè)程序活動(dòng)時(shí)按了一下鍵盤,操作系統(tǒng)能夠馬上感知這一事件,但并不決定如何作出反應(yīng),而是將這一事件轉(zhuǎn)交給應(yīng)用程序,由應(yīng)用程序決定執(zhí)行何種反應(yīng)。

理解了操作系統(tǒng)和應(yīng)用程序的關(guān)系后,對(duì)于面向?qū)ο蟪绦蛟O(shè)計(jì)中如何調(diào)用現(xiàn)有計(jì)算機(jī)資源或創(chuàng)建新的應(yīng)用,就有了十分明晰的思路。

3算法:程序設(shè)計(jì)的靈魂

在程序設(shè)計(jì)中,運(yùn)行效率通常是一個(gè)決定性的指標(biāo),而程序運(yùn)行是否高效,很大程度上取決于能否編寫出高效的算法。比如在游戲世界中,一只妖怪盯上了目標(biāo),并且它足夠聰明,會(huì)選擇一條最短路徑向目標(biāo)殺過去。為什么這只妖怪那么聰明?這就是尋找最短路徑算法的魔力。

算法是指完成某個(gè)特定任務(wù)所需要的具體步驟和方法。在程序設(shè)計(jì)領(lǐng)域,算法表現(xiàn)為一系列解決問題的清晰指令,對(duì)一定規(guī)范的輸入,能夠在有限時(shí)間內(nèi)獲得所要求的輸出,中國古代的珠算口決及其執(zhí)行規(guī)則就是算法的雛形。算法是計(jì)算機(jī)處理信息的本質(zhì),因?yàn)槌绦蚓褪怯盟惴ǜ嬖V計(jì)算機(jī)按照確切的步驟執(zhí)行指定的任務(wù),如計(jì)算職工的薪水或打印學(xué)生的成績單等。程序設(shè)計(jì)中的算法應(yīng)用通常分成三個(gè)階段:分析問題、設(shè)計(jì)算法和實(shí)現(xiàn)算法。

算法設(shè)計(jì)的基本方法有遞推法、遞歸法、窮舉法、分治法、迭代法等。目前被設(shè)計(jì)出來而且應(yīng)用廣泛的算法有很多,如演化算法、蟻群算法、貪婪算法、遺傳算法和一些常用的排序算法等,每一種算法都對(duì)應(yīng)著多種不同的應(yīng)用。如在同一個(gè)動(dòng)畫頁面中,近處的對(duì)象會(huì)擋住遠(yuǎn)處的對(duì)象,可以通過對(duì)不同的對(duì)象進(jìn)行坐標(biāo)排序,然后按由遠(yuǎn)到近的順序排放而實(shí)現(xiàn)。常用的排序算法有四種:選擇排序、插入排序、冒泡排序和快速排序。下面是N個(gè)元素的冒泡算法C++程序?qū)崿F(xiàn)。

template < class T >

void bub_sort( T a[], int n )

{

int i,j,last;

i = n - 1;

while( i > 0 )

{

last = 0;

for( j = 0; j < i; j++ )

{

if( a[j+1] < a[j] )

{

T temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

last = j;

}

}

i = last;

}

}

算法中將每個(gè)元素想象成一個(gè)泡泡,從最底部的元素開始,將各相鄰的元素進(jìn)行比較,若下面的元素大于上面的元素時(shí),則把它們的值進(jìn)行交換,即較大的元素“往上冒泡”。如此循環(huán)N-1次,即可實(shí)現(xiàn)從大到小的排序。

當(dāng)然,算法只是解決某類問題的步驟或方法,同一個(gè)算法可用不同的程序設(shè)計(jì)語言實(shí)現(xiàn),而且能夠根據(jù)不同的應(yīng)用目標(biāo)加以約束和優(yōu)化。算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)密切相關(guān),算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率,在面向?qū)ο蟮某绦蛟O(shè)計(jì)中,二者是一個(gè)整體,不可分割。

4數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)資源的管家

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。討論數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在該類數(shù)據(jù)上執(zhí)行的算法才有意義,通常情況下,精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來最優(yōu)效率的算法。不同種類的數(shù)據(jù)結(jié)構(gòu)適合于不同種類的應(yīng)用,而部分甚至專門用于特定的作業(yè)任務(wù)。在程序設(shè)計(jì)中,根據(jù)不同的應(yīng)用需要,可以選擇不同的數(shù)據(jù)結(jié)構(gòu)。

如果有一堆相似數(shù)據(jù)需要管理,通常會(huì)選擇線性表。如單位人員的記錄、游戲世界里的道具包。線性表一般分為數(shù)組與鏈表兩類。數(shù)組里的元素以連續(xù)的內(nèi)存空間存放,因此可以用內(nèi)存地址檢索到對(duì)應(yīng)的數(shù)據(jù)元素,訪問元素很方便。但如果要進(jìn)行插入/刪除數(shù)據(jù)元素,就要做一些內(nèi)存移動(dòng),效率比較低。而鏈表的數(shù)據(jù)元素存放在任意的物理內(nèi)存位置,相鄰的元素以指針作為“鏈扣”串連起來,可以更高效的插入/刪除數(shù)據(jù)元素。

隊(duì)列和堆?？赡苁鞘褂妙l率最高的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列是一種“先進(jìn)先出(first-in first-out, FIFO)”的數(shù)據(jù)結(jié)構(gòu)。就好像是在銀行里排隊(duì),排在前面的先服務(wù)。因此順序執(zhí)行的任務(wù)可以從一端依次壓進(jìn)任務(wù)隊(duì)列里,要做任務(wù)時(shí)依次從另一端取出,哪個(gè)任務(wù)先接到就先做哪個(gè)任務(wù)。也許有些任務(wù)報(bào)酬更高,如果最求報(bào)酬最大化,就需要使用優(yōu)先級(jí)隊(duì)列。在插入元素時(shí),優(yōu)先級(jí)高的元素插入隊(duì)列前面,把任務(wù)的報(bào)酬設(shè)成優(yōu)先級(jí)數(shù)據(jù)就可以了。

堆棧是一種“先進(jìn)后出”的數(shù)據(jù)結(jié)構(gòu)。就好像是疊盤子,疊在最上面的盤子最先拿來使用。比如Word中的“撤消”按鈕,使用戶在編輯誤操作時(shí)不必驚慌,因?yàn)椤俺废惫δ芸梢猿废暗牟僮?。只要把用戶的操作壓入棧?撤消操作就是從棧中彈出最近發(fā)生的操作,可以很方便地實(shí)現(xiàn)這個(gè)功能。

此外,樹型結(jié)構(gòu)和圖形結(jié)構(gòu)也是比較常用的、非線性的數(shù)據(jù)結(jié)構(gòu)。樹的實(shí)現(xiàn)與應(yīng)用比線性數(shù)據(jù)結(jié)構(gòu)復(fù)雜,但其應(yīng)用很廣泛,如Windows操作系統(tǒng)的文件管理。圖形結(jié)構(gòu)可以用于地圖數(shù)據(jù)的管理等。

5數(shù)據(jù)庫:智能化的大倉庫

在程序設(shè)計(jì)當(dāng)中,具有各種數(shù)據(jù)結(jié)構(gòu)的變量或?qū)ο笫遣豢扇鄙俚脑?。如果?shù)據(jù)量比較小,直接使用內(nèi)存變量或文件存儲(chǔ)就可以了,但在當(dāng)前信息化的環(huán)境中,數(shù)據(jù)量通常是海量的,為了加快對(duì)數(shù)據(jù)的操作與訪問,同時(shí)保護(hù)數(shù)據(jù)的安全性,必須借助專門的工具,這就是數(shù)據(jù)庫。嚴(yán)格地說,數(shù)據(jù)庫是按照數(shù)據(jù)結(jié)構(gòu)組織、存儲(chǔ)和管理數(shù)據(jù)的倉庫。

例如,在企事業(yè)單位的日常管理工作中,常常要把本單位職工的基本情況(職工號(hào)、姓名、年齡、性別、籍貫、工資、簡歷等)存放在表中,這張表就是數(shù)據(jù)庫的一個(gè)基本元素,可以通過不同的“視角”加以查看。如果建立了包含相關(guān)信息的多個(gè)表,我們就擁有了一個(gè)“數(shù)據(jù)倉庫”。在應(yīng)用程序的設(shè)計(jì)中,可以模擬現(xiàn)實(shí)世界,為不同的人員劃分相應(yīng)的權(quán)限,使他們可以根據(jù)需要隨時(shí)在權(quán)限范圍內(nèi)處理數(shù)據(jù),如查詢某職工的基本情況,添加新進(jìn)的職工信息等。此外,在財(cái)務(wù)管理、生產(chǎn)管理中、倉庫管理時(shí),也可以建立眾多的數(shù)據(jù)庫,以實(shí)現(xiàn)財(cái)務(wù)、倉庫、生產(chǎn)的自動(dòng)化管理。

6結(jié)語

計(jì)算機(jī)的課程體系是實(shí)現(xiàn)完整應(yīng)用的一個(gè)整體,獨(dú)立的程序設(shè)計(jì)教學(xué)會(huì)使學(xué)生對(duì)許多概念的理解發(fā)生混淆,造成實(shí)際應(yīng)用的偏差。本文論述了將相關(guān)的專業(yè)課程概念融入C++程序設(shè)計(jì)的教學(xué)過程中,增強(qiáng)學(xué)生對(duì)程序設(shè)計(jì)概念的理解,并根據(jù)需要靈活應(yīng)用。當(dāng)然,面向?qū)ο蟮某绦蛟O(shè)計(jì)也是一門實(shí)踐性很強(qiáng)的課程,學(xué)生對(duì)所有概念的理解及應(yīng)用必須通過上機(jī)操作,在程序設(shè)計(jì)中不斷磨練才能提高。

參考文獻(xiàn):

[1] 劉建華. 計(jì)算機(jī)語言類課程教學(xué)模式初探[J]. 高教論壇,2005,2(1):91-93.

[2] 鄭莉,董淵,張瑞豐. C++語言程序設(shè)計(jì)[M]. 北京:清華大學(xué)出版社,2005.

[3] 陳渝譯. 操作系統(tǒng):精髓與設(shè)計(jì)原理[M]. 北京:電子工業(yè)出版社,2006.

[4] 王曉東. 算法設(shè)計(jì)與分析[M]. 北京:清華大學(xué)出版社,2008.

[5] 寧正元,王秀麗. 算法與數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學(xué)出版社,2006.

[6] 何玉潔. 數(shù)據(jù)庫管理與編程技術(shù)[M]. 北京:清華大學(xué)出版社,2006.