跟蹤法在數據結構教學中的創新應用

摘 要:《數據結構》是我國本科及高職院校計算機專業教學中一門重要的專業基礎課程，而現階段普遍采用傳統教學方法并沒有取得良好的教學效果。利用來源于實際軟件生產的跟蹤法進行數據結構教學，效果顯著，事半功倍。

關鍵詞:跟蹤法 數據結構教學

中圖分類號:G642文獻標識碼:A文章編號:1674-098X(2012)01(a)-0135-03

《數據結構》是我國本科及高職院校計算機專業教學中一門重要的專業基礎課程，通常在學生系統的學習完一門計算機高級語言課程之后開設。《數據結構》的主要內容是向學生介紹如何在計算機內部組織數據、存儲數據以及利用這些數據解決現實生產、生活中的具體問題。眾所周知，利用計算機編程解決客觀世界中存在的具體問題需要完成兩個階段的工作，第一個階段是將問題域中的問題在解域中進行描述，也就是將客觀世界中的問題在計算機內進行描述，這涉及到客觀世界數字化過程中大量數據的組織與存儲，需要程序設計者掌握數據間的邏輯結構和存貯結構的知識;第二個階段是設計合理的步驟處理數據解決問題，需要程序設計者掌握數據處理算法的知識。完成這兩個階段工作所需要的專業知識均包含在《數據結構》課程中，因而學生學習《數據結構》課程效果的好壞直接決定了學生專業素質的高低以及解決實際問題能力的強弱，因此《數據結構》課程也幾乎成為各種層次的選拔考試和招聘考試的必考課程。然而對于如此重要的一門課程，在教學上卻長時間找不到一種有效方法能夠讓學生既易于理解晦澀的理論，又對經典算法印象深刻，這不能不說是計算機專業教學的一種悲哀。

《數據結構》是程序設計的方法學，應重點培養學生的邏輯思維能力，使學生的思維方式逐漸與計算機的運行特點相適應，從而使學生設計出有利于在計算機上實現的算法。為此，教學工作者應充分利用教材中提供的經典算法，在長期的講解教學過程中潛移默化的影響學生，最終實現教學教學目標。傳統的教學方法在對算法例題的講解方式上存在重大偏差，只側重講解算法中包含多少個順序結構、多少個選擇結構、多少個循環結構以及每個組成部分的功能，而這些組成部分的功能是如何實現的卻鮮有涉及。這種教學方法一方面使數據結構教學流于程式化、表面化，最終退化為計算機程序語言教學，另一方面使學生對經典算法例題只知其然而不知其所以然，逐漸對課程喪失興趣，滋生畏學、厭學情緒，加劇教與學的矛盾。有鑒于數據結構傳統教學方法的缺陷，高校教師開始積極探索，對其進行改進。隨著黨和政府對教育事業投資的日趨加大，電化教學設備在高校教學中逐漸普及使用，于是數據結構教學工具由粉筆加黑板演變成教師機加投影儀，教師手中的教案變成了多媒體教學課件，但這種教學工具上的變革沒有改變數據結構傳統教學方法中對經典算法例題的講解方式，學生在對新的教學設備產生短暫興趣后依然畏學、厭學，教學矛盾沒有緩解，沒有從根本上解決問題。我作為一名高校基層教師，常年承擔《數據結構》課程的教學任務，在教學實踐中幾經摸索，終于找到一種我稱其為跟蹤法的行之有效教學方法，既能夠激發學生的學習興趣、增進學生對所學經典算法的理解，又能夠盡快使學生的思維方式貼近計算機，使《數據結構》課程的教學效果獲得大幅改觀。

《數據結構》課程采用跟蹤法教學的主導思想就是通過向學生跟蹤展示算法執行過程中核心變量和關鍵數據結構的變化以及它們之間的關聯來揭示計算機在解決問題時的行為模式，從而使學生把握計算機思維特點。在整個教學過程中通過對大量算法例題的跟蹤，不斷強化這種思維方式，使學生適應這種思維方式，最終能夠應用這種思維方式獨立思考，編寫出有利于上機實現的實用算法。

跟蹤法是經過生產檢驗的有助于人把握程序和算法執行過程的有效方法。在軟件生產過程中，系統設計人員設計的算法在經過程序員實現(即按算法編程)后，程序員編寫的程序需要上機編譯、測試和調試，如果發現程序的執行結果與預期結果不一致，則說明程序中包含邏輯錯誤。為了確定發生邏輯錯誤的準確位置，程序員需要監視程序執行過程中的每個環節，而監視程序執行過程的方法就是跟蹤程序中核心變量和關鍵數據結構的變化。程序流程每向前推進一步，核心變量和關鍵數據結構的值都會發生變化，如果在某一步推進后核心變量和關鍵數據結構的值發生了預期外的變化，則說明這一步的推進有問題，其對應的程序段也就是邏輯錯誤發生的地方。經過生產實踐的檢驗證明，這種跟蹤核心變量和關鍵數據結構的方法是一種有效的、高效的方法，它能夠幫助程序員正確理解算法，準確把握程序的執行動態，精確定位邏輯錯誤的發生地點。在長期的生產實踐過程中，軟件生產者利用跟蹤法驗證自己生產的算法和程序;在教學實踐過程中，我逆向使用跟蹤法，使學生更加迅速、深刻的理解經典算法例題，大大提高了教學效率、效果。

利用跟蹤法進行《數據結構》課程的教學，操作簡便易行。使用跟蹤法講解經典算法可分兩步操作，第一步是確定核心變量和關鍵數據結構以及促使二者的值發生變化的驅動變量，第二步是展示核心變量和關鍵數據結構的變化過程，揭示計算機解決實際問題時的行為模式。以跟蹤三元組表保存稀疏矩陣進行轉置運算為例，演示跟蹤法教學過程。假設現有矩陣A=，A轉置后成為矩陣B，即B=。完成此運算的C語言偽碼算法如下:

# define smax 20

typedef struct

{ int i ， j ， v;

}node; /*三元組類型定義*/

typedef struct

{ int m ， n ， t;

node data[smax];

}spmatrix; /*三元組表類型定義*/

spmatrix *transmat (a) /*矩陣轉置*/

spmatrix *a;

{ int ano，bno，col;

spmatrix *b;

b=malloc(sizeof(spmatrix));

b->m=a->n;

b->n=a->m;

b->t=a->t;

if(b->t > 0)

{ bno=0;

for(col=0;col < a->n;col++)

for(ano=0;ano < a->t;ano++)

{ if(a->data[ano].j==col)

{ b->data[bno].i=a->data[ano].j;

b->data[bno].j=a->data[ano].i;

b->data[bno].v=a->data[ano].v;

bno++;

}

}

}

return b;

}

1 確定核心變量和關鍵數據結構

矩陣轉置算法中包含的變量眾多，但對理解算法執行過程起到關鍵作用的是兩個三元組表a、b和一個表示對a表進行列序掃描的變量col，而兩個三元組表中起核心作用的是保存矩陣元素的整形數組域data。通過分析，我們確定了該算法的核心變量和關鍵數據結構為a->data域、b->data域和變量col。

2 展示核心變量和關鍵數據結構的變化過程

在轉置運算實施之前，矩陣A保存在三元組表a中，其核心a->data域狀態為(表1)。

矩陣B尚未生成，保存B矩陣的三元組表b的核心b->data域狀態為(表2)。

在以列序掃描A矩陣并完成轉置的過程中，當col值為0，即掃描A矩陣的第0列時，找到兩個非零元素，將其轉置填充到B矩陣的三元組表中。b->data域狀態變為(表3)。

當col值為1，即掃描A矩陣的第1列時，找到兩個非零元素，將其轉置填充到B矩陣的三元組表中。b->data域狀態變為(表4)。

當col值為2，即掃描A矩陣的第2列時，找到一個非零元素，將其轉置填充到B矩陣的三元組表中。b->data域狀態變為(表5)。

當col值為3，即掃描A矩陣的第3列時，找到一個非零元素，將其轉置填充到B矩陣的三元組表中。b->data域狀態變為(表6)。

此時A矩陣所有各列掃描完畢，A矩陣完成轉置并將結果保存在b三元組表中，b->data域的最終狀態為(表7)。

經過跟蹤后，學生得以準確把握該算法的執行脈絡，知其然，知其所以然，理解深刻，印象持久。

綜上所述，教師應用跟蹤法進行《數據結構》課程教學，可以使教學內容真正觸及算法執行的本質，避免流于算法流程表面，退化為計算機程序語言教學，同時能夠大幅增強教學效果，提高教學效率，是一種值得推廣的教學方法。