“數據結構”中基本教學案例的研究

摘要:本文闡明了“數據結構”教學過程中應用案例的重要性，并對示例案例進行詳細的分析、設計;描述了如何進行案例教學的全過程;最后將案例研究應用于實際教學中，結合實驗教學展示了通過數據結構案例進行教學的一個實例。

關鍵詞:數據結構;教學案例;實驗教學

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

1案例分析

針對“數據結構”課程教學中的各個章節，我們根據案例針對的基本數據結構不同分成了不同的基本案例，教學中使用基本案例的作用是加深學生對基本數據結構的理解和數據結構使用方法的認識。

以鏈表[3]為例，鏈表是“數據結構”課程中學習的一個基本數據結構，這種結構簡單而且適用范圍廣，但要想學會、學好卻是一項艱巨的任務，學生往往在學習過程中會感覺明白了理論，但不會應用實踐。針對這個問題，我們提出了通過鏈表應用案例進行教學，采用的案例即為超長大整數的運算。

1.1大整數存儲結構分析

此例中的長整數不是LONG型數據，而是遠遠多于計算機可用基本數據類型存儲的超長的整數運算。一般情況下為了能在計算機中進行運算，必須將這個長整數進行拆分，拆分成符合計算機存儲規則的數。為了遵守整數的四則運算規則，拆分后的數據又必須統一進行運算，于是就想到能否將拆分的數據通過一定的方式連接起來，自定義一些運算，以已知的四則運算為基礎，可以對長整數進行運算。鏈表恰恰就是可以將若干數據連接到一起的一種數據結構，于是我們就想到了使用鏈表來完成這個功能。又因為數據在輸入的時候習慣是從高位向低位逐位輸入，而運算的過程中是從低位向高位進行逐位運算，輸出又反過來，從高位向低位逐位輸出。鑒于此可以考慮使用雙向鏈表來實現數據的存儲結構。

1.2大整數的運算分析

按照習慣性的數據輸入方法和計算機中實際整型數據的存儲容量，可以采用四位一組進行數據存儲。大整數加減法只要逐位進行加減，當有進位或者借位的時候在高一結點位上加入進位或者借位一起運算即可。大整數的乘法和除法[4-5]較為復雜，要涉及分治算法等更深入的內容，在數據結構案例教學中不進行介紹，有興趣的讀者可以參考文獻[4]、[5]。

2案例設計

2.1存儲結構設計

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

Typedef struct DuLNode{

ElemTypedata;//數據

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

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

}DuLNode，*DuLinkList;

而這個雙向鏈表也就是案例中要使用的存儲結構[6]，使用雙向鏈表有利于超長整數加減法運算的順利進行。

2.2操作設計

大整數要從鍵盤進行輸入，所以需要雙向鏈表的插入操作;當減法運算完成后，可能結果會小于任何一個大整數的長度，此時在輸出結果前可能會用到結點的刪除運算。具體過程參見參考文獻[1]，不再贅述。

2.3運算過程設計

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

3案例教學實例

教學中學生學習了線性表基本邏輯結構和鏈式存儲結構后相關理論后，可以根據情況適當地進行實踐，加深學生對鏈表的理解，提高其掌握鏈表結構進行程序設計的能力。在引導學生進行程序設計的時候，可以在教學中使用案例演示系統進行輔助教學。首先讓學生對案例的運行情況進行直觀的動畫式了解，然后對執行過程中對應的是什么程序代碼要有清楚的認識，最后對運行存儲器中變量值的變化情況能夠理解并掌握。比如要講解大整數運算這個案例，通過教學演示系統首先演示數據的輸入存儲過程，如圖3所示。

界面會將輸入數據構建雙向鏈表的過程展示出來，并且右側的代碼區會以紅色代碼的形式展示對應界面上正在執行代碼的情況，右下側的變量區展示當前變量的變化情況。這個界面類似于調試程序界面，不過比調試過程更直觀，更容易理解和操作。

輸入完成后，進行運算過程的演示，逐結點逐位進行加法或者減法操作，進位或者借位單獨處理后進入運算的過程，以期得到完整的結果，如圖4所示。

通過案例的演示，學生會對運算過程有了直觀的了解，結合在課堂上學習的理論知識，學生就能夠對大整數運算有一個總體的認識，并且知道用什么數據結構，用什么樣的算法程序去實現這個運算過程。教學演示中還有許多其他的界面，這里不一一列舉了。教學過程中除了演示部分外還會著重介紹算法的設計思路、實現原理以及實現過程，真正讓學生學懂、學會，并能夠自覺地去應用學習的結果。

4總結與展望

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

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

參考文獻:

[1] 楊桂芝. “數據結構”教學方法探索與實踐[J]. 計算機教育，2007(6):7-9.

[2] 王江濤.《數據結構》教學研究和體會[J]. 科技信息:學術版，2006(03):134.

[3] 嚴蔚敏，吳偉民. 數據結構(C語言版)[M]. 北京:清華大學出版社，2004:27-38.

[4] 高峰，王玉柱，桑林瓊，等. 大整數乘除運算在PC機上的實現[J]. 后勤工程學院學報，2007(01):57-59.

[5] 英昌盛，周喜龍. 大整數乘法的數據結構及算法選擇探究[J]. 長春工業大學學報:自然科學版，2008，29(2):205-207.

[6] 李建學，李光元，吳春芳. 數據結構課程設計案例精編[M]. 北京:清華大學出版社，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

(編輯:姚彥如)