數(shù)據(jù)結(jié)構(gòu)課程教學(xué)方法研究

【摘 要】 數(shù)據(jù)結(jié)構(gòu)是信息管理與計(jì)算機(jī)等相關(guān)專業(yè)重要的核心課程，為取得良好的教學(xué)效果，本文設(shè)計(jì)了數(shù)據(jù)結(jié)構(gòu)課程的算法與內(nèi)容體系，分析了教學(xué)難點(diǎn)及有效的講授方法，對提高數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)質(zhì)量具有重要的借鑒意義。

【關(guān)鍵詞】 數(shù)據(jù)結(jié)構(gòu)；課程教學(xué)；教學(xué)方法

【中圖分類號】 G643.2 【文獻(xiàn)標(biāo)識碼】 A 【文章編號】 2095-3089（2017）17-000-02

1.引言

1.1數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展趨勢

1968年開始將數(shù)據(jù)結(jié)構(gòu)課程作為信息管理與計(jì)算機(jī)專業(yè)的核心課程，經(jīng)歷了多次的內(nèi)容調(diào)整與教學(xué)改革。第一階段（1968-1995）以結(jié)構(gòu)化的算法教學(xué)為主；第二階段（1996-2009左右）基于網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)結(jié)構(gòu)算法軟件系統(tǒng)與多媒體教學(xué)課件；第三階段（2010-現(xiàn)在）基于大數(shù)據(jù)環(huán)境下的結(jié)構(gòu)化與非結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)算法與網(wǎng)絡(luò)教學(xué)。隨著信息化的發(fā)展，迫切要求學(xué)生對數(shù)據(jù)結(jié)構(gòu)算法細(xì)節(jié)的深入掌握，并根據(jù)算法邏輯步驟快速編寫程序。

1.2數(shù)據(jù)結(jié)構(gòu)課程在信息管理類專業(yè)所處的位置

數(shù)據(jù)結(jié)構(gòu)是信息管理類專業(yè)（計(jì)算機(jī)應(yīng)用、信息科學(xué)、信息管理等相關(guān)專業(yè)）的專業(yè)基礎(chǔ)課。其前趨課程包括：數(shù)學(xué)、計(jì)算機(jī)組成原理、離散數(shù)學(xué)、圖論、算法語言、高級語言程序設(shè)計(jì)、網(wǎng)絡(luò)技術(shù)、數(shù)據(jù)庫原理等；后繼課程包括：編譯原理、操作系統(tǒng)、數(shù)據(jù)倉庫與數(shù)據(jù)挖掘、網(wǎng)絡(luò)技術(shù)與應(yīng)用、決策支持系統(tǒng)等。因此，數(shù)據(jù)結(jié)構(gòu)是信息管理類專業(yè)一門承上啟下的重要課程，為取得良好的教學(xué)效果，應(yīng)注重理論概念與對應(yīng)算法的統(tǒng)一、算法思想與上機(jī)編程的統(tǒng)一。換句話說，為學(xué)生講授一種如何學(xué)好數(shù)據(jù)結(jié)構(gòu)的新方法，即讓學(xué)生了解如何將客觀世界問題在計(jì)算機(jī)外部的表示方式（即邏輯表示方法），客觀世界問題在計(jì)算機(jī)內(nèi)部的存儲方式（物理存儲方式），以及如何對該問題進(jìn)行計(jì)算的方法，是學(xué)好這門課的關(guān)鍵。

2.數(shù)據(jù)結(jié)構(gòu)課程的重點(diǎn)與內(nèi)容體系

2.1數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)重點(diǎn)

數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)重點(diǎn)主要包括：（1）抽象數(shù)據(jù)類型定義與形式化表示，對應(yīng)算法的描述、在計(jì)算機(jī)外部的邏輯表示及其對應(yīng)的計(jì)算機(jī)內(nèi)部的物理表示；（2）抽象數(shù)據(jù)類型對應(yīng)實(shí)際問題的解決方案；（3）線性表、非線性表、數(shù)組、棧與隊(duì)列、樹型、圖形等數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算；（4）經(jīng)典算法的邏輯，如：Hanoi塔的遞歸、樹的遞歸、圖的遞歸；（5）嵌套算法；（6）查找和特殊查找方法；（7）排序的各類方法。

2.2數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)教學(xué)內(nèi)容特點(diǎn)將算法分為線性、非線性數(shù)據(jù)結(jié)構(gòu)及其對應(yīng)算法（如圖1）。

3.數(shù)據(jù)結(jié)構(gòu)課程的難點(diǎn)及講授方法

從圖1可知，數(shù)據(jù)結(jié)構(gòu)課程的知識體系包含大量的解決客觀世界實(shí)際問題的數(shù)學(xué)建模方法即算法，如何快速掌握大量的數(shù)據(jù)結(jié)構(gòu)算法，并快速編寫程序。

3.1掌握數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)要領(lǐng)

（1）梳理數(shù)據(jù)結(jié)構(gòu)課程的算法與內(nèi)容體系。了解知識點(diǎn)的概念、術(shù)語、客觀世界問題的數(shù)學(xué)模型，確定當(dāng)前問題屬于樹、圖、表、字符等哪種數(shù)據(jù)結(jié)構(gòu)形式。之后，按照所選擇的數(shù)據(jù)結(jié)構(gòu)的ADT（抽象數(shù)據(jù)類型）進(jìn)行定義和運(yùn)算；然后，選擇適合的算法，注意算法的時(shí)間復(fù)雜度和空間復(fù)雜度；除此，熟練掌握一門高級程序語言的設(shè)計(jì)方法及程序?qū)崿F(xiàn)。

（2）掌握數(shù)據(jù)結(jié)構(gòu)算法的核心技巧。以講授“線性表的插入與刪除算法”為例，主要包括兩部分內(nèi)容：①找到插入（或刪除）點(diǎn)后，進(jìn)行插入（或刪除）操作；②插入操作則需要將插入點(diǎn)到表尾所有元素進(jìn)行移動。如在第i個(gè)數(shù)據(jù)元素之前進(jìn)行插入操作，則將表中第i個(gè)數(shù)據(jù)元素到第n個(gè)數(shù)據(jù)元素（表長為n）一起進(jìn)行移動到第i+1到第n+1數(shù)據(jù)元素對應(yīng)的存儲位置中。因此，移動元素的算法成為插入或刪除算法的核心，解決方式是將復(fù)雜算法進(jìn)行分段分解。一般的劃分方法是：1）程序（算法）的初始條件部分；2）程序（算法）的主體部分，重點(diǎn)的內(nèi)容是程序（算法）的核心語句部分；3）程序的結(jié)果處理部分。

3.2數(shù)據(jù)結(jié)構(gòu)難點(diǎn)的掌握方法

數(shù)據(jù)結(jié)構(gòu)課程算法的難點(diǎn)主要包括：順序線性表的插入和刪除算法的主體功能—竄動數(shù)據(jù)元素和插入刪除操作；棧與隊(duì)列的特殊操作規(guī)律及應(yīng)用；棧與遞歸過程，廣義表、樹、圖等算法都屬于遞歸問題；串的壓縮與非緊湊存儲的特點(diǎn)等。

（1）學(xué)習(xí)遞歸程序（過程）的技巧。含有遞歸過程的算法有：Hanoi塔，迷宮問題，N！計(jì)算，F(xiàn)ibonacci數(shù)，Ackman函數(shù)，廣義表、樹和圖的遞歸算法等。如果掌握不好將影響數(shù)據(jù)結(jié)構(gòu)課程的整個(gè)進(jìn)度。由于遞歸的運(yùn)行離不開棧，因此，在閱讀遞歸過程中，需要巧妙地將算法的運(yùn)行與棧的參數(shù)保存及傳遞結(jié)合起來。通過經(jīng)典的Hanoi塔遞歸程序（算法）的詳細(xì)講解，解剖這樣一個(gè)具有代表性的遞歸過程的復(fù)雜運(yùn)行過程，使學(xué)生在本課程后續(xù)章節(jié)的遞歸算法（如：廣義表、樹、圖等遞歸算法）的學(xué)習(xí)中起到舉一反三效果。

（2）掌握關(guān)于圖的復(fù)雜算法。首先要清楚圖的特征即引起圖復(fù)雜的原因—圖中的頂點(diǎn)是任意的。首先要在圖中確定第一個(gè)訪問的頂點(diǎn)；對無向圖需要在程序中規(guī)定其當(dāng)前訪問頂點(diǎn)、其第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)；然后，根據(jù)圖中頂點(diǎn)之間的任意關(guān)系，在訪問時(shí)需設(shè)定一個(gè)Visited（v）的訪問標(biāo)志來確定當(dāng)前的訪問狀態(tài)，之后才能進(jìn)行圖的深度優(yōu)先搜索等操作。

（3）將邏輯流程圖和圖示法相結(jié)合掌握和理順?biāo)惴?。首先展出程序（算法）的主體語句；然后從這些主體語句中找出其核心語句。以順序線性表插入算法為例，先找出插入語句；再繼續(xù)理解實(shí)現(xiàn)該操作的基本條件和初始條件，定位到竄動和插入之前的語句；然后，再擴(kuò)展到算法（程序）的其他幾個(gè)重要的核心語句。將上述操作采用流程圖和圖示法相結(jié)合的方式來解釋（圖2）。

（4）對重點(diǎn)算法、經(jīng)典算法應(yīng)采用理論與實(shí)際相結(jié)合的教學(xué)模式。受到課時(shí)的限制，要選擇重要知識點(diǎn)進(jìn)行上機(jī)實(shí)踐，主要包括：棧的應(yīng)用、特性與規(guī)律；模式串匹配的改進(jìn)算法即KMP算法；建立Huffman樹及編碼；最優(yōu)二叉樹的存儲理論及編碼；拓?fù)渑判蛩惴ǖ拇鎯Y(jié)構(gòu)及實(shí)際應(yīng)用；經(jīng)典的排序和查找方法等。

4.小結(jié)

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)應(yīng)始終圍繞“數(shù)據(jù)結(jié)構(gòu)課程的算法與內(nèi)容體系”展開（如圖1）。通過數(shù)據(jù)結(jié)構(gòu)的概念算法與應(yīng)用，找出代表性算法的共性規(guī)律，從數(shù)據(jù)的概念、術(shù)語、數(shù)據(jù)結(jié)構(gòu)類型、對應(yīng)的算法及應(yīng)用等各個(gè)環(huán)節(jié)進(jìn)行講授。采用流程圖和圖示法相結(jié)合的方法模擬計(jì)算機(jī)執(zhí)行程序是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的高效方式。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，2012.12.

[2]陳燕，曹妍，賈紅雨，李曄.數(shù)據(jù)結(jié)構(gòu)（C語言版）.科學(xué)出版社，2016.8.

[3]殷人昆.數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）.清華大學(xué)出版社，2017.4.endprint