“數(shù)據(jù)結(jié)構(gòu)”中基本教學(xué)案例的研究

摘要:本文闡明了“數(shù)據(jù)結(jié)構(gòu)”教學(xué)過程中應(yīng)用案例的重要性，并對(duì)示例案例進(jìn)行詳細(xì)的分析、設(shè)計(jì);描述了如何進(jìn)行案例教學(xué)的全過程;最后將案例研究應(yīng)用于實(shí)際教學(xué)中，結(jié)合實(shí)驗(yàn)教學(xué)展示了通過數(shù)據(jù)結(jié)構(gòu)案例進(jìn)行教學(xué)的一個(gè)實(shí)例。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);教學(xué)案例;實(shí)驗(yàn)教學(xué)

近年來的教學(xué)實(shí)踐表明，除了課堂上講解的基本理論外，如何應(yīng)用數(shù)據(jù)結(jié)構(gòu)中學(xué)到的理論進(jìn)行實(shí)踐正是學(xué)生迫切需要掌握的。為此，很多相關(guān)的學(xué)者、老師也進(jìn)行了深入的探討和研究[1-2]。給學(xué)生更多自主學(xué)習(xí)時(shí)間，培養(yǎng)學(xué)生進(jìn)行數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)及分析問題、解決問題的能力是教學(xué)的最終目標(biāo)。目前部分學(xué)生的自主學(xué)習(xí)能力尚達(dá)不到相應(yīng)的水平，尤其是擴(kuò)大招生后，這一問題尤為突出。教學(xué)改革勢在必行，我們將實(shí)例納入教學(xué)范疇，研究如何圍繞基本數(shù)據(jù)結(jié)構(gòu)概念增加一些新的、應(yīng)用型的且是必要的實(shí)例知識(shí)，并且附以部分算法設(shè)計(jì)內(nèi)容，這樣不僅能夠彌補(bǔ)“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中缺乏實(shí)踐所帶來的問題，同時(shí)還可以拓寬學(xué)生的知識(shí)面，增強(qiáng)學(xué)生學(xué)以致用的實(shí)踐能力。

1案例分析

針對(duì)“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中的各個(gè)章節(jié)，我們根據(jù)案例針對(duì)的基本數(shù)據(jù)結(jié)構(gòu)不同分成了不同的基本案例，教學(xué)中使用基本案例的作用是加深學(xué)生對(duì)基本數(shù)據(jù)結(jié)構(gòu)的理解和數(shù)據(jù)結(jié)構(gòu)使用方法的認(rèn)識(shí)。

以鏈表[3]為例，鏈表是“數(shù)據(jù)結(jié)構(gòu)”課程中學(xué)習(xí)的一個(gè)基本數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)簡單而且適用范圍廣，但要想學(xué)會(huì)、學(xué)好卻是一項(xiàng)艱巨的任務(wù)，學(xué)生往往在學(xué)習(xí)過程中會(huì)感覺明白了理論，但不會(huì)應(yīng)用實(shí)踐。針對(duì)這個(gè)問題，我們提出了通過鏈表應(yīng)用案例進(jìn)行教學(xué)，采用的案例即為超長大整數(shù)的運(yùn)算。

1.1大整數(shù)存儲(chǔ)結(jié)構(gòu)分析

此例中的長整數(shù)不是LONG型數(shù)據(jù)，而是遠(yuǎn)遠(yuǎn)多于計(jì)算機(jī)可用基本數(shù)據(jù)類型存儲(chǔ)的超長的整數(shù)運(yùn)算。一般情況下為了能在計(jì)算機(jī)中進(jìn)行運(yùn)算，必須將這個(gè)長整數(shù)進(jìn)行拆分，拆分成符合計(jì)算機(jī)存儲(chǔ)規(guī)則的數(shù)。為了遵守整數(shù)的四則運(yùn)算規(guī)則，拆分后的數(shù)據(jù)又必須統(tǒng)一進(jìn)行運(yùn)算，于是就想到能否將拆分的數(shù)據(jù)通過一定的方式連接起來，自定義一些運(yùn)算，以已知的四則運(yùn)算為基礎(chǔ)，可以對(duì)長整數(shù)進(jìn)行運(yùn)算。鏈表恰恰就是可以將若干數(shù)據(jù)連接到一起的一種數(shù)據(jù)結(jié)構(gòu)，于是我們就想到了使用鏈表來完成這個(gè)功能。又因?yàn)閿?shù)據(jù)在輸入的時(shí)候習(xí)慣是從高位向低位逐位輸入，而運(yùn)算的過程中是從低位向高位進(jìn)行逐位運(yùn)算，輸出又反過來，從高位向低位逐位輸出。鑒于此可以考慮使用雙向鏈表來實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

1.2大整數(shù)的運(yùn)算分析

按照習(xí)慣性的數(shù)據(jù)輸入方法和計(jì)算機(jī)中實(shí)際整型數(shù)據(jù)的存儲(chǔ)容量，可以采用四位一組進(jìn)行數(shù)據(jù)存儲(chǔ)。大整數(shù)加減法只要逐位進(jìn)行加減，當(dāng)有進(jìn)位或者借位的時(shí)候在高一結(jié)點(diǎn)位上加入進(jìn)位或者借位一起運(yùn)算即可。大整數(shù)的乘法和除法[4-5]較為復(fù)雜，要涉及分治算法等更深入的內(nèi)容，在數(shù)據(jù)結(jié)構(gòu)案例教學(xué)中不進(jìn)行介紹，有興趣的讀者可以參考文獻(xiàn)[4]、[5]。

2案例設(shè)計(jì)

2.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)(node)。n個(gè)結(jié)點(diǎn)(ai(1<=i<=n)的存儲(chǔ)映像)鏈結(jié)成一個(gè)鏈表，即為線性表(a1，a2，…，an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。若再增加一個(gè)指針域，另其指向直接前趨，則構(gòu)成雙向鏈表，線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)描述如下:

Typedef struct DuLNode{

ElemTypedata;//數(shù)據(jù)

Struct DuLNode*prior;//指向前趨的指針

Struct DuLNode*next;//指向后繼的指針

}DuLNode，*DuLinkList;

而這個(gè)雙向鏈表也就是案例中要使用的存儲(chǔ)結(jié)構(gòu)[6]，使用雙向鏈表有利于超長整數(shù)加減法運(yùn)算的順利進(jìn)行。

2.2操作設(shè)計(jì)

大整數(shù)要從鍵盤進(jìn)行輸入，所以需要雙向鏈表的插入操作;當(dāng)減法運(yùn)算完成后，可能結(jié)果會(huì)小于任何一個(gè)大整數(shù)的長度，此時(shí)在輸出結(jié)果前可能會(huì)用到結(jié)點(diǎn)的刪除運(yùn)算。具體過程參見參考文獻(xiàn)[1]，不再贅述。

2.3運(yùn)算過程設(shè)計(jì)

大整數(shù)的輸入時(shí)結(jié)點(diǎn)大小可以任意，具體可以由實(shí)際情況來定，這里采用四位數(shù)據(jù)形成鏈表中的一個(gè)結(jié)點(diǎn)。輸入數(shù)據(jù)并且判斷運(yùn)算類型后進(jìn)行具體的加法或者是減法的運(yùn)算，圖1和圖2是加法和減法的運(yùn)算流程，在教學(xué)中教師可以選取其中一個(gè)進(jìn)行詳細(xì)講解，另一個(gè)留待學(xué)生自己學(xué)習(xí)完成。

3案例教學(xué)實(shí)例

教學(xué)中學(xué)生學(xué)習(xí)了線性表基本邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)后相關(guān)理論后，可以根據(jù)情況適當(dāng)?shù)剡M(jìn)行實(shí)踐，加深學(xué)生對(duì)鏈表的理解，提高其掌握鏈表結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)的能力。在引導(dǎo)學(xué)生進(jìn)行程序設(shè)計(jì)的時(shí)候，可以在教學(xué)中使用案例演示系統(tǒng)進(jìn)行輔助教學(xué)。首先讓學(xué)生對(duì)案例的運(yùn)行情況進(jìn)行直觀的動(dòng)畫式了解，然后對(duì)執(zhí)行過程中對(duì)應(yīng)的是什么程序代碼要有清楚的認(rèn)識(shí)，最后對(duì)運(yùn)行存儲(chǔ)器中變量值的變化情況能夠理解并掌握。比如要講解大整數(shù)運(yùn)算這個(gè)案例，通過教學(xué)演示系統(tǒng)首先演示數(shù)據(jù)的輸入存儲(chǔ)過程，如圖3所示。

界面會(huì)將輸入數(shù)據(jù)構(gòu)建雙向鏈表的過程展示出來，并且右側(cè)的代碼區(qū)會(huì)以紅色代碼的形式展示對(duì)應(yīng)界面上正在執(zhí)行代碼的情況，右下側(cè)的變量區(qū)展示當(dāng)前變量的變化情況。這個(gè)界面類似于調(diào)試程序界面，不過比調(diào)試過程更直觀，更容易理解和操作。

輸入完成后，進(jìn)行運(yùn)算過程的演示，逐結(jié)點(diǎn)逐位進(jìn)行加法或者減法操作，進(jìn)位或者借位單獨(dú)處理后進(jìn)入運(yùn)算的過程，以期得到完整的結(jié)果，如圖4所示。

通過案例的演示，學(xué)生會(huì)對(duì)運(yùn)算過程有了直觀的了解，結(jié)合在課堂上學(xué)習(xí)的理論知識(shí)，學(xué)生就能夠?qū)Υ笳麛?shù)運(yùn)算有一個(gè)總體的認(rèn)識(shí)，并且知道用什么數(shù)據(jù)結(jié)構(gòu)，用什么樣的算法程序去實(shí)現(xiàn)這個(gè)運(yùn)算過程。教學(xué)演示中還有許多其他的界面，這里不一一列舉了。教學(xué)過程中除了演示部分外還會(huì)著重介紹算法的設(shè)計(jì)思路、實(shí)現(xiàn)原理以及實(shí)現(xiàn)過程，真正讓學(xué)生學(xué)懂、學(xué)會(huì)，并能夠自覺地去應(yīng)用學(xué)習(xí)的結(jié)果。

4總結(jié)與展望

數(shù)據(jù)結(jié)構(gòu)的使用和算法思想的理解是課程的重點(diǎn)，將抽象的算法執(zhí)行過程以淺顯易懂的方式講解并 在課堂上展現(xiàn)出來，配合以學(xué)生的親身實(shí)踐，將起到事半功倍的學(xué)習(xí)效果。以教學(xué)案例作為一種輔助教學(xué)，用形象生動(dòng)的動(dòng)畫效果和類似于程序單步執(zhí)行的過程，操作簡單、形象生動(dòng)，改善了學(xué)生對(duì)“數(shù)據(jù)結(jié)構(gòu)”課程的學(xué)習(xí)理解和掌握，有助于深刻理解相應(yīng)的算法，有利于培養(yǎng)知識(shí)結(jié)構(gòu)，激發(fā)學(xué)習(xí)興趣，從很大程度上提高學(xué)生的學(xué)習(xí)質(zhì)量和效率。今后的教學(xué)研究中，除了進(jìn)行案例教學(xué)外，我們更應(yīng)該考慮和企業(yè)應(yīng)用問題掛鉤，將實(shí)際項(xiàng)目引入到課堂教學(xué)中，增加知識(shí)的實(shí)用性。

注:本文受2007年度北京信息科技大學(xué)校級(jí)精品課程資助。

參考文獻(xiàn):

[1] 楊桂芝. “數(shù)據(jù)結(jié)構(gòu)”教學(xué)方法探索與實(shí)踐[J]. 計(jì)算機(jī)教育，2007(6):7-9.

[2] 王江濤.《數(shù)據(jù)結(jié)構(gòu)》教學(xué)研究和體會(huì)[J]. 科技信息:學(xué)術(shù)版，2006(03):134.

[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京:清華大學(xué)出版社，2004:27-38.

[4] 高峰，王玉柱，桑林瓊，等. 大整數(shù)乘除運(yùn)算在PC機(jī)上的實(shí)現(xiàn)[J]. 后勤工程學(xué)院學(xué)報(bào)，2007(01):57-59.

[5] 英昌盛，周喜龍. 大整數(shù)乘法的數(shù)據(jù)結(jié)構(gòu)及算法選擇探究[J]. 長春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2008，29(2):205-207.

[6] 李建學(xué)，李光元，吳春芳. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編[M]. 北京:清華大學(xué)出版社，2007:161-166.

Study of Teaching Instance in “Data Structure”

LIU Cheng-xia， DONG Wan， CAI Ying

(Computer School， Beijing Information Technology University， Beijing 100101， China)

Abstract: The importance of teaching instance used in the teaching process of Data Structure is explained in this paper. Detailed analysis and design of one instance are provided. At the end of the paper， a specific demo showing how to use the instance in actual class is brought forth combined with the experimental teaching.

Key words: Data Structure;teaching instance;experiment teaching

(編輯:姚彥如)