裴大容

摘要：該文主要針對應用型本科計算機專業(yè)的學生特點和數(shù)據(jù)結(jié)構(gòu)課程的特點，通過有針對性的教學過程的把控，來提高數(shù)據(jù)結(jié)構(gòu)課程的教學質(zhì)量。

關(guān)鍵詞：應用性本科;數(shù)據(jù)結(jié)構(gòu);教學過程

中圖分類號：G424? ? ? 文獻標識碼：A? ? ? 文章編號：1009-3044（2018）35-0155-03

1 概述

數(shù)據(jù)結(jié)構(gòu)課程是計算機專業(yè)一門非常重要的專業(yè)基礎課，學好它為算法設計與分析等后續(xù)課程的學習奠定良好的基礎，同時對軟件設計和開發(fā)能力的提高也有極大的幫助。但由于數(shù)據(jù)結(jié)構(gòu)課程中抽象型概念多且難于理解、知識點多、課內(nèi)課時少等原因，加之應用型本科計算機專業(yè)的學生抽象型概念理解能力較差，分析和總結(jié)問題的能力不強，自學能力較弱等因素，導致了該課程總體學習效果較差。

針對以上問題，本人在教學過程中不斷摸索，通過有針對性地進行教學過程中三方面的把控，使得教學質(zhì)量得以提高。希望對同行們的教學有一定的參考價值。

2 教學過程把控

教學過程的把控，主要針對學生的特點和課程的特點，從以下三個方面來進行：

2.1 抽象概念具象化

數(shù)據(jù)結(jié)構(gòu)中的概念通常都比較抽象，學生難于理解和記憶。只有盡量通過日常生活中的例子或情形來打比方，讓學生好像看到了具體的情形或畫面，這樣才方便他們理解和記憶。

以線性表順序存儲時，順序表的靜態(tài)存儲類型定義為例來講。

此處用c語言來進行描述，順序表類型定義如下：

#define MAXSIZE 100

typedef? int? DataType;

typedef? ?struct

{DataType? ?data[MAXSIZE];

int? length;}

SqList;

如剛講了線性表的含義以及順序存儲的概念后，就直接給出以上類型定義，學生肯定感覺不好理解。原因主要在于三點：第一，前面基礎語言課程學習掌握不扎實，對結(jié)構(gòu)體定義感覺陌生;第二，對typedef語句不熟;第三，剛開始接觸抽象數(shù)據(jù)元素類型DataType，感覺太抽象很別扭;因此總體上導致他們感覺很難，覺得這個定義太抽象不好理解。

此時我們可以在講解時先不把抽象定義給學生看，而是先告訴他們?nèi)我粋€順序表都可以看成由兩部分構(gòu)成：一個數(shù)組和一個表長，然后再盡量找一個現(xiàn)實生活中比較貼切的具象例子來讓學生掌握其定義。

本人以新生入學報到為例來講。在新生報到時，學院領導肯定很關(guān)心學生的報到情況。我們按學生報到的時間先后順序來依次登記這些學生信息（為簡單起見，學生信息僅記錄姓名項），就構(gòu)成了一張學生報到登記表。把每個學生看成一個數(shù)據(jù)元素，那這些同類型數(shù)據(jù)元素的集合，就構(gòu)成了一個線性表。而存儲這些學生的信息剛好可以用一個數(shù)組來實現(xiàn)。注意：數(shù)組的大小必須要足夠大到可以裝下所有可能報到的學生，所以應比預錄人數(shù)適當增大。到目前為止，已經(jīng)來報到的學生通過登記表可以一目了然了，但學校領導除了關(guān)心具體哪些同學已經(jīng)來報到之外，還關(guān)心學生報到率的問題。而學生報到率可以通過實際報到人數(shù)來計算得到，所以在登記報到情況時，除了要登記已到同學的姓名，還要另外登記一個已到學生人數(shù)。那學生人數(shù)如何登記呢？一種方法是在存儲學生信息的數(shù)組中加一個序號分量，但n個同就需要增加n個整型變量的存儲空間;另一種方法是設置一個整形計數(shù)累加器變量，初值置為0，來一個學生就自增1，只需1個整型變量的存儲空間;相較這2種方法，肯定第2種設置一個整形變量的方法更好，因為節(jié)約存儲空間。由此例顯而易見一個順序表定義時需要2塊內(nèi)容：一塊是存儲學生信息的數(shù)組，另一塊是表示實際人數(shù)的表長。然后再告訴學生對任何一個順序表的定義都需要含這2部分內(nèi)容，即：存儲數(shù)據(jù)元素值的數(shù)組和表示元素個數(shù)的表長;此時，再把順序表類型定義的代碼給他們看并加以適當講解，學生就很容易理解和記憶順序表的類型定義了。以后再提及線性表順序表類型定義時，他們就會聯(lián)想到新生入學報到登記信息的情形，很快想到由數(shù)組和表長2部分構(gòu)成。

因此，我們要盡量把一些抽象化的概念通過日常生活中的例子或現(xiàn)象來進行描述，讓他們產(chǎn)生畫面感，以便理解和記憶。

2.2 算法實例化

算法講解前，盡量先演示典型實例，然后由點及面總結(jié)出算法思想，最后講算法的實現(xiàn)代碼。這樣學生就不會覺得算法實現(xiàn)晦澀難懂了。

對于應用型本科計算機專業(yè)的學生來說，他們的數(shù)學基礎不是特別好，直接講算法時他們很難跟上思路;教材上的算法一般都是用類c或類pascal語言寫的偽代碼，再加之以前程序設計語言基礎不太扎實，所以看代碼時覺得很難理解。如果帶入具體數(shù)值的有針對性的特例，他們能看到詳細的計算或求解過程并且能理解這個過程，再稍加總結(jié)，最后轉(zhuǎn)換為代碼，這個時候他們就能理解了。

以線性表應用中稀疏一元多項式求和的算法為例來講，其中一元多項式按冪指數(shù)遞增的方式寫，比如3+4x+6x100。假設用鏈式存儲結(jié)構(gòu)實現(xiàn)，因順序存儲相對來說容易實現(xiàn)。

首先在講解算法之前，應設計一個特例，必須把求和過程中各種可能遇到的情況都考慮進去，包括：指數(shù)項不同時的情況以及指數(shù)項相同時系數(shù)項之和為0和不為0的情況;因遇到不同情況時，要做不同的處理。

比如有針對性的設計2個多項式A和B：

A=3+5X+8X99

B=7-5X+4X3

因為多項式的每一項都可以看成由系數(shù)項和指數(shù)項2個分量構(gòu)成，所以我們可以把2個多項式分別表示成（（3，0），（5，1），（8，99））和（（7，0），（-5，1），（4，3））;由線性表的定義可知，這2個多項式可以看成2個按冪指數(shù)遞增的線性表?，F(xiàn)在按鏈式存儲結(jié)構(gòu)畫出多項式A和B對應的含頭結(jié)點的2個鏈表La和Lb，如圖1所示。其中每個結(jié)點由指數(shù)項（expn）、系數(shù)項（coef）和next指針域3部分構(gòu)成。

此時讓學生回顧，數(shù)學中對一元多項式求和的方法，他們會說出如下規(guī)則：首先比較指數(shù)項：指數(shù)項相同時，系數(shù)項求和;和為零時忽略，和不為零時，生成對應的一項放到求和表達式中;指數(shù)項不同時，按指數(shù)項從低到高的順序分別放到求和表達式中即可;實質(zhì)上用計算機實現(xiàn)一元多項式求和算法也是利用這樣的思路，只不過要考慮到存儲細節(jié)的問題還要刪除原有鏈表中的部分結(jié)點。

運算過程如下：

初始狀態(tài)：分別設置2個移動指針p和q，分別指向La和Lb的第1個數(shù)據(jù)元素結(jié)點，即：p=La→next，q=Lb→next;同時令求和的鏈表用Lc表示，此處借助現(xiàn)有的La的頭結(jié)點生成一個空鏈（借助Lb也同樣可行），用r表示其移動指針（也是其尾指針），此時指向La的頭結(jié)點，即：Lc=La，r=La;因求和后的數(shù)據(jù)元素項按冪指數(shù)遞增，所以采用尾插法來生成新鏈表Lc。當前狀態(tài)如圖2所示。

第1步：比較當前2個指針p和q所指向的結(jié)點的指數(shù)項，都為0相同，系數(shù)項求和3+7=10≠0，所以此時只需修改當前2個結(jié)點中任一結(jié)點的系數(shù)項作為新的尾結(jié)點插入新鏈表中即可。假設選取當前p所指向的結(jié)點進行修改插入新鏈表Lc尾結(jié)點后面，同時r尾指針后，然后p指針后移;即：p→coef=10，r→next=p，p=p→next;因當前q所指向的結(jié)點已經(jīng)用過無效了，應釋放，q也應后移;但應注意順序，先定位要刪除的結(jié)點（假設借助一個移動指針s），然后q后移，即：s=q，q=q→next;此時狀態(tài)如圖3所示;最后刪除結(jié)點，free（s）;得到結(jié)果如圖4所示：

第2步：再繼續(xù)比較當前p和q所指向的結(jié)點，因指數(shù)項相同，但系數(shù)項之和為0，所以新鏈表Lc中不增加新結(jié)點， p和q指針后移。但后移前應先分別定位到原來p和q所指向的結(jié)點，用第1步中刪除結(jié)點的方法進行相同處理。結(jié)果如圖5所示：

第3步：依然比較當前p和q所指向結(jié)點的指數(shù)項，因q所指向的結(jié)點的指數(shù)項小，所以應將q所指的結(jié)點作為新的尾結(jié)點插入到新鏈表Lc中，尾指針r后移， q指針后移。即：r→next=q，r=r→next，q=q→next;結(jié)果如圖6所示：

第4步：因q=NULL，表示q所指向的鏈表已完，此時只需將p所指的結(jié)點作為新鏈表Lc當前尾結(jié)點的下一個結(jié)點即可，即r→next=p，此時新鏈表Lc生成完畢。

但還應注意一個問題，Lb所指向的頭結(jié)點無用了也必須要釋放，即free（Lb）。至此整個運算過程結(jié)束。結(jié)束時的狀態(tài)如圖7所示。

針對以上計算過程，總結(jié)出一般稀疏一元多項式求和的算法思想如下：

1） 初始化：置Lc為帶頭結(jié)點的空鏈表，同時設置移動指針p，q分別指向原有的2個多項式鏈表La和Lb的第一個數(shù)據(jù)元素結(jié)點;設移動指針r指向Lc的頭結(jié)點;

2） 當原有2個鏈表都未空時，即p和q都不為空時：

比較p和q所指向結(jié)點的指數(shù)項，如相同時：判斷其系數(shù)項之和是否為0;為0，則應刪除相應結(jié)點，且p和q均后移;不為0，則應修改其中一個結(jié)點的系數(shù)項為求和后的值，加入新鏈表Lc后面作為最新的尾結(jié)點，且尾指針r后移;再刪除另外一個已經(jīng)無用的結(jié)點，且p和q都后移。（結(jié)合剛才實現(xiàn)過程，提醒學生注意刪除時操作順序，應先定位刪除結(jié)點，然后指針后移，最后刪除結(jié)點，否則容易斷鏈）;當指數(shù)項不同時，則應先把指數(shù)項小的結(jié)點加入新鏈表Lc后面作為最新的尾結(jié)點，且尾指針r和該指針均后移;

3） 重復步驟（2），直到某個鏈表為空時，把指向另一個非空鏈表的移動指針作為新鏈表Lc尾指針r→next的值;

4） 釋放那個無用頭結(jié)點;

整個算法結(jié)束。

然后再講解完整的算法實現(xiàn)，此時學生結(jié)合剛才的運算過程就很容易弄懂算法，也能很快分析出時間復雜度等。此類情況不再贅述。

2.3 強調(diào)復習

強調(diào)復習從兩個方面來進行。第一個：因應用型本科學生自學能力較差，所以只能強調(diào)課后復習，通過有目的性布置作業(yè)和上機實驗題有效地促進他們復習，達到對課堂內(nèi)容的消化理解吸收;另一個，在講課的過程中當用到以前學過的相關(guān)知識點時，有針對性的適當復習，達到溫故而知新的目的。比如講鏈棧生成算法時，要用到頭插法生成單鏈表的知識點，所以首先復習下頭插法的特點和算法中的關(guān)鍵語句;然后再強調(diào)鏈棧和單鏈表的區(qū)別，在鏈棧中頭指針top直接指向鏈表的第一個數(shù)據(jù)元素結(jié)點;這樣鏈棧生成算法在此基礎上很輕松就可以學會。因此強調(diào)復習，對知識的理解、掌握和銜接特別重要。

3 教學效果

通過近4年教學結(jié)果觀察，采用該法后，教學效果有較明顯的改進，學生興趣也有較大的提高，算法設計和分析能力也有一定的提高。

參考文獻：

[1] 王寧寧. 中日工科院校應用型本科人才培養(yǎng)模式比較研究[D].哈爾濱理工大學，2016.

[2] 陳宇文. 注重源程序在《數(shù)據(jù)結(jié)構(gòu)》課程中的重要性[J].高教論壇，2004（2）：73-75.

[3] 汪軍， 周鳴爭. 《數(shù)據(jù)結(jié)構(gòu)》課程教學方法的改革與實踐[J].蘭州工業(yè)高等?？茖W校學報，2004，11（3）：19-21.

[通聯(lián)編輯：張薇]