應(yīng)用型本科計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)探討

裴大容

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

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

中圖分類號：G424? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? 文章編號：1009-3044（2018）35-0155-03

1 概述

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

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

2 教學(xué)過程把控

教學(xué)過程的把控，主要針對學(xué)生的特點(diǎn)和課程的特點(diǎn)，從以下三個(gè)方面來進(jìn)行：

2.1 抽象概念具象化

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

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

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

#define MAXSIZE 100

typedef? int? DataType;

typedef? ?struct

{DataType? ?data[MAXSIZE];

int? length;}

SqList;

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

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

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

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

2.2 算法實(shí)例化

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

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

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

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

比如有針對性的設(shè)計(jì)2個(gè)多項(xiàng)式A和B：

A=3+5X+8X99

B=7-5X+4X3

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

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

運(yùn)算過程如下：

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

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

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

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

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

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

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

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

2） 當(dāng)原有2個(gè)鏈表都未空時(shí)，即p和q都不為空時(shí)：

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

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

4） 釋放那個(gè)無用頭結(jié)點(diǎn);

整個(gè)算法結(jié)束。

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

2.3 強(qiáng)調(diào)復(fù)習(xí)

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

3 教學(xué)效果

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

參考文獻(xiàn)：

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

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

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

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