趙福生

(泉州師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 泉州 362000)

《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革的思路與實(shí)踐

趙福生

(泉州師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 泉州 362000)

針對(duì)《數(shù)據(jù)結(jié)構(gòu)》課堂教學(xué)，提出了教學(xué)改革的五點(diǎn)思路，通過實(shí)例對(duì)五點(diǎn)思路進(jìn)行詳細(xì)的分析.在實(shí)際的課堂教學(xué)過程中，不斷實(shí)踐與豐富所提出的五點(diǎn)思路.教學(xué)的結(jié)果表明，教學(xué)改革的五點(diǎn)思路是行之有效的.

數(shù)據(jù)結(jié)構(gòu)；指導(dǎo)思想；面向?qū)ο螅怀橄箢愋?/p>

0 引言

《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)類專業(yè)基礎(chǔ)核心課程，該課程一般安排在大二時(shí)進(jìn)行學(xué)習(xí)，在學(xué)這門課程以前，學(xué)生一般學(xué)過高級(jí)語言程序設(shè)計(jì)、概率論等專業(yè)課程，但面向?qū)ο蟮乃季S仍然沒有得到很好的訓(xùn)練，對(duì)編程語言的理解仍然缺少正確有效的方法，學(xué)生如何學(xué)好《數(shù)據(jù)結(jié)構(gòu)》這門課程缺少方向性的指導(dǎo).本文針對(duì)該課程的學(xué)習(xí)，提出了五點(diǎn)思路：牢牢記住一個(gè)指導(dǎo)思想，采用兩種方法，實(shí)現(xiàn)三個(gè)過程，學(xué)習(xí)四個(gè)方面，掌握五種抽象類型.

1 牢牢記住一個(gè)指導(dǎo)思想

在《數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)過程中，必須牢記如下指導(dǎo)思想：閱讀算法時(shí)，要看到算法中語句表達(dá)的意思，要領(lǐng)悟算法中語句執(zhí)行的過程，要理解算法中語句發(fā)生的操作.

任何語言都是形式化的東西，當(dāng)然包括數(shù)學(xué)語言(數(shù)學(xué)符號(hào))、計(jì)算機(jī)語言、自然語言(英語漢語等).語言都表達(dá)一定的意思，語言背后蘊(yùn)含著豐富的信息.透過語言這種形式化的東西看到語言表達(dá)的意思與蘊(yùn)含的信息，語言作為一堆符號(hào)就不再枯燥.自然語言是人與人交流的一種工具.利用自然語言，人可以表達(dá)豐富多彩的信息.計(jì)算機(jī)語言也是一種語言，計(jì)算機(jī)語言用來完成人與計(jì)算機(jī)的交流，人利用計(jì)算機(jī)語言告訴計(jì)算機(jī)該完成哪些工作，計(jì)算機(jī)也可以通過某些方式告訴人相關(guān)的信息.計(jì)算機(jī)語言的形式化程度高于自然語言低于數(shù)學(xué)語言.計(jì)算機(jī)語言所表達(dá)的語義是唯一的，這不同于自然語言，有時(shí)自然語言所表達(dá)的意思會(huì)產(chǎn)生歧義，計(jì)算機(jī)語言表達(dá)的意思(語義)唯一，一個(gè)語句、一段代碼、一個(gè)模塊、一個(gè)函數(shù)表達(dá)的意思、完成的操作、執(zhí)行的過程都是唯一的.這種唯一性進(jìn)一步說明，閱讀計(jì)算機(jī)語言書寫的算法時(shí)要看到計(jì)算機(jī)語言背后所蘊(yùn)含的編程思想.這一點(diǎn)與計(jì)算機(jī)程序是根據(jù)某個(gè)編程思想來編寫的也完全相符.

在閱讀計(jì)算機(jī)語言(如C語言)書寫的算法時(shí)，要逐步提高分析總結(jié)的能力.先看懂每一個(gè)語句表達(dá)的意思、執(zhí)行的過程、發(fā)生的操作，接下來要總結(jié)出每一段代碼、每一個(gè)模塊、每一個(gè)函數(shù)完成的功能.因此，在教學(xué)過程中，要逐步提高學(xué)生的學(xué)習(xí)能力與總結(jié)能力.在實(shí)際教學(xué)過程中，采用嚴(yán)蔚敏、吳偉民編寫的《數(shù)據(jù)結(jié)構(gòu)》(C語言版)(清華大學(xué)出版社)，[1]該教材比較抽象，里面的代碼不是很完整，每個(gè)函數(shù)里面使用的局部變量沒有相應(yīng)的定義語句，函數(shù)里面調(diào)用的函數(shù)也沒給出相應(yīng)的完整實(shí)現(xiàn)代碼，有些操作函數(shù)只給出函數(shù)的功能介紹沒有給出完整的實(shí)現(xiàn)代碼.[2]教材里面只給出一部分操作函數(shù)的實(shí)現(xiàn)代碼，沒有編寫相關(guān)的主函數(shù)代碼對(duì)操作函數(shù)進(jìn)行調(diào)用，因此不能對(duì)操作函數(shù)的功能進(jìn)行驗(yàn)證，對(duì)操作函數(shù)功能的理解還是比較抽象的.[3]在教學(xué)過程中，筆者編寫了完整的程序代碼并且提前印刷給學(xué)生，這些程序代碼以一種抽象類型在某一存儲(chǔ)結(jié)構(gòu)上的完整實(shí)現(xiàn)為一份資料，里面給出了抽象類型的每個(gè)操作在存儲(chǔ)結(jié)構(gòu)上的完整實(shí)現(xiàn)，里面還編寫了一個(gè)主函數(shù)對(duì)每個(gè)操作函數(shù)進(jìn)行調(diào)用，從而可以對(duì)操作函數(shù)的功能有比較形象的理解，每份資料的后面還給出整個(gè)程序的運(yùn)行結(jié)果，同時(shí)也根據(jù)主函數(shù)的執(zhí)行過程畫出數(shù)據(jù)結(jié)構(gòu)的變化.

在教學(xué)過程中，讓學(xué)生提前閱讀編寫的程序代碼，每次上課時(shí)，都抽出十分鐘左右的時(shí)間檢查學(xué)生的學(xué)習(xí)情況.[4]檢查的形式采用互動(dòng)的方式，通過提問，了解學(xué)生對(duì)程序代碼的理解.提問時(shí)，先讓學(xué)生敘述每個(gè)語句發(fā)生的操作，然后讓學(xué)生逐步概括出每個(gè)模塊表達(dá)的意思，總結(jié)出每個(gè)函數(shù)的功能.讓學(xué)生敘述執(zhí)行過程時(shí)，同時(shí)也讓學(xué)生描述數(shù)據(jù)結(jié)構(gòu)的變化，并且與程序的運(yùn)行結(jié)果結(jié)合起來.每次提問都進(jìn)行評(píng)分并且記錄，作為期末成績的一部分.通過這種方式，可以讓學(xué)生自覺利用本節(jié)的指導(dǎo)思想進(jìn)行學(xué)習(xí)，從而逐步提高學(xué)習(xí)能力與總結(jié)能力.通過提問，還可以深入了解學(xué)生的學(xué)習(xí)情況，增進(jìn)師生之間的情感交流.上課過程中，圍繞本節(jié)的指導(dǎo)思想來展開教學(xué)，先講每個(gè)語句發(fā)生的操作，同時(shí)畫出執(zhí)行的過程，進(jìn)而概括出函數(shù)的功能，最后介紹如何調(diào)用函數(shù).

2 采用兩種方法

在整個(gè)教學(xué)過程中，始終采用兩種方法：實(shí)際例子，結(jié)合算法，進(jìn)行分析；面向?qū)ο?只采用引用形參與動(dòng)態(tài)存儲(chǔ)分配).

數(shù)據(jù)結(jié)構(gòu)的算法是比較抽象的，單單只看算法，理解起來肯定是比較困難的.在閱讀算法時(shí)，找出一個(gè)實(shí)際例子來運(yùn)行算法程序，可以對(duì)每行代碼的功能有更加形象的理解.這個(gè)方法可以更加形象地描述為：把人腦當(dāng)作電腦，來運(yùn)行程序代碼.運(yùn)轉(zhuǎn)完以后，程序代碼的功能會(huì)在腦袋里面留下更深的痕跡.下面以單鏈表的插入操作為例來講述該方法.

(1)Status ListInsert_L(LinkList amp;L,int i,ElemType e)

(2){LinkList p; int j; LinkList s;

(3)p=L; j=0;

(4)while(pamp;amp;jlt;i-1)

(5){p=p-gt;next; j++;}

(6)if(!p||jgt;i-1) return ERROR;

(7)else {s=(LinkList)malloc(sizeof(LNode));

(8)s-gt;data=e;

(9)s-gt;next=p-gt;next;

(0)p-gt;next=s;

(11)return OK;

(12) }

(13) }

該操作函數(shù)的形參i里面的值為插入位置，形參e里面的值為插入元素.插入以前單鏈表已經(jīng)存在，i里面的插入位置有可能太小(i≤0)有可能太大(i≥表長+2)也有可能合法(1≤i≤表長+1).當(dāng)i≤0時(shí)，(3)p指向表頭結(jié)點(diǎn)，j為0，(4)jlt;i-1馬上為假，馬上結(jié)束while循環(huán)，流程轉(zhuǎn)到第(6)行，(6)jgt;i-1為真，返回ERROR，說明插入操作沒有成功.當(dāng)i≥表長+2時(shí)，(3)p指向表頭結(jié)點(diǎn)，j為0，(4)(5)while循環(huán)里面p指針一直往后移，j里面的值一直加1，while循環(huán)結(jié)束時(shí)，p為null，j為表長+1，流程轉(zhuǎn)到第( 6)行，if條件!p為真，返回ERROR，說明插入操作沒有成功.當(dāng)1≤i≤表長+1時(shí)，(3)p指向表頭結(jié)點(diǎn)，j為0，(4)(5)while循環(huán)里面p指針一直往后移，j里面的值一直加1，直到p指向第i-1個(gè)結(jié)點(diǎn)，這時(shí)j為i-1，結(jié)束while循環(huán)，流程轉(zhuǎn)到第(6)行，if條件(!p||jgt;i-1)為假執(zhí)行else部分(7)～(12)，(7)動(dòng)態(tài)分配一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，動(dòng)態(tài)分配完以后把結(jié)點(diǎn)的指針存放在s里面，(8)把形參e里面的插入元素存放在新結(jié)點(diǎn)的data成員里面，(9)使得新結(jié)點(diǎn)的next成員指向第i個(gè)結(jié)點(diǎn)，(10)使得第i-1個(gè)結(jié)點(diǎn)的next成員指向新結(jié)點(diǎn)，(11)返回OK，說明插入操作已經(jīng)成功.該函數(shù)執(zhí)行完以后，函數(shù)的返回值要么為OK要么為ERROR，如果返回值為ERROR，單鏈表的結(jié)構(gòu)沒有變化，如果返回值為OK，單鏈表的結(jié)構(gòu)有變化，增加了一個(gè)新元素.由此我們可以得出ListInsert_L函數(shù)的功能，在單鏈表的第i個(gè)位置上插入一個(gè)新的元素，插入操作有可能成功也有可能不成功.

數(shù)據(jù)結(jié)構(gòu)的傳統(tǒng)教學(xué)只注重算法的具體實(shí)現(xiàn)，沒有采用面向?qū)ο蟮姆椒?如果采用真正的面向?qū)ο笳Z言(如C++語言)來描述數(shù)據(jù)結(jié)構(gòu)，則面向?qū)ο笳Z言的語法格式比較復(fù)雜，使得學(xué)習(xí)者很難透過復(fù)雜的語法格式來掌握蘊(yùn)含的編程思想.因此，在教學(xué)過程中往往采用標(biāo)準(zhǔn)的C語言與引用類型的參數(shù)(簡稱引用形參)來描述數(shù)據(jù)結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)所使用的存儲(chǔ)空間利用malloc、realloc函數(shù)來動(dòng)態(tài)分配，當(dāng)數(shù)據(jù)結(jié)構(gòu)所使用的存儲(chǔ)空間不再需要時(shí)，利用free函數(shù)來釋放.利用malloc、realloc函數(shù)動(dòng)態(tài)分配的存儲(chǔ)空間只有當(dāng)調(diào)用free函數(shù)以后才會(huì)釋放.正因?yàn)橐眯螀⑴c動(dòng)態(tài)存儲(chǔ)分配，才可以在C語言的基礎(chǔ)上采用面向?qū)ο蟮姆椒▉硌芯繑?shù)據(jù)結(jié)構(gòu).可以借助下面的程序代碼來更好地理解什么是面向?qū)ο?

(1)void main()

(2){InitList_L(L);

(3)ListInsert_L(L,1,40); ListInsert_L(L,1,30); ListInsert_L(L,1,20); ListInsert_L(L,1,10);

(4)ListDelete_L(L,1,e);

(5)PriorElem_L(L,30,pre_e);

(6)NextElem_L(L,30,next_e);

(7)GetElem_L(L,2,e);

(8)i=LocateElem_L(L,10,Equal);

(9)s=ListEmpty_L(L);

(10)i=ListLength_L(L);

(11)ClearList_L(L);

(12)DestroyList_L(L);

(13) }

這段代碼里面，可以把單鏈表L看成一個(gè)對(duì)象，在主函數(shù)main里面面向L這么一個(gè)對(duì)象.(2)InitList_L(L);用來初始化L這么一個(gè)對(duì)象，(12)DestroyList_L(L);用來破壞L這么一個(gè)對(duì)象，在初始化(2)與破壞(12)之間就可以調(diào)用單鏈表的任何操作函數(shù).(2)InitList_L(L);函數(shù)的功能相當(dāng)于C++的構(gòu)造函數(shù)，(12)DestroyList_L(L);函數(shù)的功能相當(dāng)于C++的析構(gòu)函數(shù).(2)初始化以后單鏈表為空L=( )，(3)的作用為依次往單鏈表的第1個(gè)位置上插入一個(gè)元素，(3)整行執(zhí)行完以后單鏈表為L=(10,20,30,40).(4)ListDelete_L(L,1,e);的作用為刪除單鏈表L=(10,20,30,40)第一個(gè)位置上的元素，刪除以后，單鏈表為L=(20,30,40)，參數(shù)e里面存放刪除元素10.(5)PriorElem_L(L,30,pre_e);用來求單鏈表L=(20,30,40)里面30的前一個(gè)元素，執(zhí)行完以后，單鏈表沒有變化仍然為L=(20,30,40)，參數(shù)pre_e里面存放20.(6)NextElem_L(L,30,next_e);用來求單鏈表L=(20,30,40)里面30的后一個(gè)元素，執(zhí)行完以后，單鏈表沒有變化仍然為L=(20,30,40)，參數(shù)next_e里面存放40.(7)GetElem_L(L,2,e);用來獲得單鏈表L=(20,30,40)里面的第二個(gè)元素，執(zhí)行完以后，單鏈表沒有變化仍然為L=(20,30,40)，參數(shù)e里面存放30.(8)i=LocateElem_L(L,10,Equal);用來求單鏈表L=(20,30,40)里面與10滿足Equal關(guān)系的第一個(gè)元素的位置，因?yàn)椴淮嬖?，所以?zhí)行完以后i為0.(9)s=ListEmpty_L(L);用來判斷單鏈表L=(20,30,40)是否為空，執(zhí)行完以后s里面的值為FALSE，說明單鏈表非空.(10)i=ListLength_L(L);用來求單鏈表L=(20,30,40)里面元素的個(gè)數(shù)，執(zhí)行完以后i里面的值為3.(11)ClearList_L(L);用來清空單鏈表，使得單鏈表由L=(20,30,40)變?yōu)長=( ).

3 實(shí)現(xiàn)三個(gè)過程

知識(shí)傳遞可以分為三個(gè)過程：第一個(gè)過程，嚴(yán)蔚敏老師為了傳播她的編程思想，把她的編程思想整理成文字，這些文字通過書出版發(fā)行.第二個(gè)過程，學(xué)生拿到出版發(fā)行的書以后，就要閱讀文字，掌握里面蘊(yùn)含的編程思想.第三個(gè)過程，學(xué)生掌握了編程思想以后，就要利用編程思想來編程進(jìn)而解決實(shí)際問題.第一個(gè)過程對(duì)于學(xué)生來說，無須參與.在教學(xué)過程中，要求學(xué)生必須完成第二個(gè)過程與第三個(gè)過程，第二個(gè)過程的要求在“牢牢記住一個(gè)指導(dǎo)思想”里面已經(jīng)有詳細(xì)講解.第三個(gè)過程就是要求學(xué)生經(jīng)常編寫程序，編程工具采用Microsoft Visual Studio 2008，編寫的程序必須是完整可以運(yùn)行的代碼，編寫的內(nèi)容包括每種抽象類型在某一存儲(chǔ)結(jié)構(gòu)上的完整實(shí)現(xiàn)，并且把每種抽象類型封裝成類模板以便以后可以直接拿來使用.基于目前手提電腦已經(jīng)非常普及，實(shí)踐教學(xué)時(shí)，要求學(xué)生每臺(tái)手提電腦都必須安裝Microsoft Visual Studio 2008.C#語言是網(wǎng)絡(luò)上比較流行的一種語言，C#語言吸收C語言、C++語言精華部分隱藏比較復(fù)雜的指針部分.在練習(xí)編程時(shí)，讓學(xué)生逐步利用C#語言來編寫程序，從而為后序課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)，也為日后的軟件開發(fā)做了充分的準(zhǔn)備.Web服務(wù)是網(wǎng)頁開發(fā)的一種中間件，Web服務(wù)有輸入與輸出，Web服務(wù)里面可以封裝復(fù)雜的計(jì)算，可以把圖論部分路徑計(jì)算的程序代碼封裝在Web服務(wù)里面.路徑計(jì)算的Web服務(wù)設(shè)計(jì)完以后，可以通過編程的方式來調(diào)用Web服務(wù)，把圖的相關(guān)信息傳給Web服務(wù)，Web服務(wù)計(jì)算完以后再把計(jì)算結(jié)果傳回來，然后可以通過編程的方式對(duì)計(jì)算結(jié)果進(jìn)行處理.在實(shí)踐教學(xué)中，讓學(xué)生編寫如下問題的Web服務(wù)：最小生成樹，關(guān)鍵路徑，最短路徑，兩點(diǎn)間的所有路徑.

4 學(xué)習(xí)四個(gè)方面

在教學(xué)過程中，要求學(xué)生學(xué)習(xí)以下四個(gè)方面：抽象類型的定義(包括邏輯結(jié)構(gòu)的定義、邏輯算法的定義)；存儲(chǔ)結(jié)構(gòu)；實(shí)現(xiàn)算法；評(píng)價(jià)算法.

本節(jié)以抽象類型線性表為例來講述學(xué)習(xí)的四個(gè)方面.抽象類型線性表里面可以有0個(gè)元素，也可以有1個(gè)2個(gè)3個(gè)4個(gè)……元素，除了第一個(gè)元素以外，每個(gè)元素都有一個(gè)直接前驅(qū)，除了最后一個(gè)元素以外，每個(gè)元素都有一個(gè)直接后繼，可以在線性表的任何位置進(jìn)行插入元素刪除元素.線性表的邏輯操作如下：初始化操作InitList，破壞操作DestroyList，清空操作ClearList，判斷空操作ListEmpty，求表長操作ListLength，獲得元素GetElem，定位元素LocateElem，求前驅(qū)元素PriorElem，求后繼元素NextElem，插入操作ListInsert，刪除操作ListDelete，遍歷操作ListTraverse.

抽象類型線性表的存儲(chǔ)結(jié)構(gòu)可以有七種：順序表，單鏈表，雙鏈表，循環(huán)單鏈表鏈表指針指向表頭，循環(huán)雙鏈表鏈表指針指向表頭，循環(huán)單鏈表鏈表指針指向表尾，循環(huán)雙鏈表鏈表指針指向表尾.

針對(duì)每種抽象類型的每種存儲(chǔ)結(jié)構(gòu)，可以根據(jù)抽象類型邏輯操作的要求與功能，寫出每種邏輯操作算法的完整實(shí)現(xiàn).

每種邏輯操作算法設(shè)計(jì)完以后，要從時(shí)間復(fù)雜度空間復(fù)雜度兩個(gè)方面對(duì)算法進(jìn)行分析，從而判斷有沒有更優(yōu)的算法設(shè)計(jì).下面以單鏈表的插入操作ListInsert_L為例，來評(píng)價(jià)算法，程序代碼在“2采用兩種方法”這一小節(jié)里面.該算法的問題規(guī)模為插入元素以前單鏈表的元素個(gè)數(shù)n，分三種情況來分析時(shí)間復(fù)雜度，①i里面的插入位置太小(i≤0)，這時(shí)算法執(zhí)行所需要的時(shí)間T(n)為一個(gè)固定值，不隨問題規(guī)模n的增大而增大，因此時(shí)間復(fù)雜度為T(n)=O(1)；②i里面的插入位置太大(i≥表長+2)，這時(shí)while循環(huán)體會(huì)執(zhí)行n+1次，因此時(shí)間復(fù)雜度為T(n)=O(n)；③i里面的插入位置合法(1≤i≤表長+1)，最好情況i為1，while循環(huán)體執(zhí)行0次，最壞情況i為表長+1，while循環(huán)體執(zhí)行n次，平均情況while循環(huán)體執(zhí)行n/2次，i里面的插入位置為各個(gè)合法值的概率相等，因此可以求平均情況下的時(shí)間復(fù)雜度，從而估算算法執(zhí)行時(shí)間的增長率，時(shí)間復(fù)雜度為T(n)=O(n).該算法所需要的輔助存儲(chǔ)空間S(n)為一個(gè)固定值，不隨問題規(guī)模n的增大而增大，因此空間復(fù)雜度為S(n)=O(1).

在教學(xué)過程中，對(duì)于每種抽象類型，都給出具體的存儲(chǔ)結(jié)構(gòu)，并且針對(duì)存儲(chǔ)結(jié)構(gòu)來編寫操作算法，最后從時(shí)間復(fù)雜度空間復(fù)雜度對(duì)操作算法進(jìn)行分析.

5 掌握五種抽象類型

《數(shù)據(jù)結(jié)構(gòu)》中主要的抽象類型有五種：線性表，棧，隊(duì)列，樹，圖.

線性表的邏輯結(jié)構(gòu)定義、邏輯算法定義在上一小節(jié)已經(jīng)講過.線性表的存儲(chǔ)結(jié)構(gòu)總共有七種，針對(duì)每種存儲(chǔ)結(jié)構(gòu)都編寫了一份資料，每份資料里面都包括邏輯算法的完整實(shí)現(xiàn)、對(duì)算法進(jìn)行調(diào)用的主函數(shù)、整個(gè)程序的運(yùn)行結(jié)果、程序運(yùn)行過程中數(shù)據(jù)結(jié)構(gòu)的變化(用圖表示).在編寫資料時(shí)，不同份資料里面同一個(gè)算法的第一行(也就是同個(gè)操作函數(shù)的第一行)使用相同的函數(shù)名、相同的形參、相同的返回值類型，對(duì)算法進(jìn)行調(diào)用的主函數(shù)也相同，因此程序的運(yùn)行結(jié)果也相同.從這七份資料可以更好地理解線性表是一種抽象類型.在編寫源代碼時(shí)，用到賦值形參函數(shù)指針變量.

(1)void Visit(ElemTypeamp; e)

(2) {printf("%d ",e);}

(3)void Add(ElemTypeamp; e)

(4) {e++;}

(5)void ListTraverse_L(LinkListamp; L,void (* visit)(ElemTypeamp; e))

(6){LNode* p; p=L-gt;next;

(7)while(p!=NULL) {(* visit)(p-gt;data); p=p-gt;next;}

(8) }

(9)ListTraverse_L(L,Visit);

(10)ListTraverse_L(L,Add);

第(9)行第二個(gè)實(shí)參Visit為一個(gè)函數(shù)名，代表第(1)行Visit函數(shù)的入口地址，第(9)行調(diào)用第(5)行的ListTraverse_L函數(shù)，流程轉(zhuǎn)到第(5)行，第(5)行的visit是賦值形參函數(shù)指針變量，另外開辟存儲(chǔ)空間，接收實(shí)參Visit傳過來的函數(shù)入口地址，接收完以后，形參visit指向第(1)行的Visit函數(shù)，指向以后，第(7)行的(* visit)(p-gt;data);相當(dāng)于調(diào)用第(1)行的Visit函數(shù)，也就是相當(dāng)于Visit(p-gt;data);.第(9)行ListTraverse_L(L,Visit);整行的作用為：在ListTraverse_L函數(shù)里面，利用while循環(huán)，依次把單鏈表的每個(gè)元素作為實(shí)參調(diào)用第(1)行的Visit函數(shù)從而顯示每個(gè)元素的值，第(9)行調(diào)用ListTraverse_L函數(shù)以前以后，單鏈表的結(jié)構(gòu)沒有變化.第(10)行ListTraverse_L(L,Add);整行的作用為：依次把單鏈表每個(gè)元素的值加1，調(diào)用函數(shù)以前以后，單鏈表發(fā)生變化.[4]

抽象類型棧邏輯結(jié)構(gòu)的定義為：棧里面可以有0個(gè)元素，也可以有1個(gè)2個(gè)3個(gè)4個(gè)……元素，除了第一個(gè)元素以外，每個(gè)元素都有一個(gè)直接前驅(qū)，除了最后一個(gè)元素以外，每個(gè)元素都有一個(gè)直接后繼，只能在棧頂位置插入元素(入棧)刪除元素(出棧).抽象類型棧的邏輯操作如下：初始化操作InitStack，破壞操作DestroyStack，清空操作ClearStack，判斷空操作StackEmpty，求元素個(gè)數(shù)操作StackLength，獲得棧頂元素操作GetTop，入棧操作Push，出棧操作Pop，遍歷棧操作StackTraverse.在編寫源代碼時(shí)，抽象類型棧的存儲(chǔ)結(jié)構(gòu)采用兩種：順序棧、鏈?zhǔn)綏?在這一章里面，給出了利用棧的一個(gè)例子：把遞歸函數(shù)轉(zhuǎn)換成非遞歸函數(shù).

抽象類型隊(duì)列邏輯結(jié)構(gòu)的定義為：隊(duì)列里面可以有0個(gè)元素，也可以有1個(gè)2個(gè)3個(gè)4個(gè)……元素，除了第一個(gè)元素以外，每個(gè)元素都有一個(gè)直接前驅(qū)，除了最后一個(gè)元素以外，每個(gè)元素都有一個(gè)直接后繼，只能在隊(duì)尾插入元素(入隊(duì))，只能在隊(duì)頭刪除元素(出隊(duì)).抽象類型隊(duì)列的邏輯操作如下：初始化操作InitQueue，破壞操作DestroyQueue，清空操作ClearQueue，判斷空操作QueueEmpty，求元素個(gè)數(shù)操作QueueLength，獲得隊(duì)頭元素操作GetHead，入隊(duì)操作EnQueue，出隊(duì)操作DeQueue，遍歷隊(duì)列操作QueueTraverse.在編寫源代碼時(shí)，抽象類型隊(duì)列的存儲(chǔ)結(jié)構(gòu)只采用鏈?zhǔn)疥?duì)列.鏈?zhǔn)疥?duì)列編寫完以后，就可以直接使用，使用時(shí)，把隊(duì)列元素?fù)Q成實(shí)際的數(shù)據(jù)類型即可.

樹這一章的知識(shí)點(diǎn)可以概括為：二叉樹、二叉排序樹、線索二叉樹、平衡二叉樹、線索二叉排序樹、線索平衡二叉樹、平衡二叉排序樹、線索平衡二叉排序樹、孩子兄弟樹.對(duì)于二叉排序樹，每個(gè)結(jié)點(diǎn)的關(guān)鍵字，總大于左子樹所有結(jié)點(diǎn)的關(guān)鍵字，總小于右子樹所有結(jié)點(diǎn)的關(guān)鍵字.線索二叉樹是在結(jié)點(diǎn)沒有左孩子或者沒有右孩子的情況下加上線索得來的.平衡二叉樹的每個(gè)結(jié)點(diǎn)左子樹的高度與右子樹的高度最多相差1.在樹這一章里面，總共編寫了9份資料.

圖的知識(shí)點(diǎn)包括：創(chuàng)建圖，遍歷圖，深度優(yōu)先生成樹，廣度優(yōu)先生成樹，連通分量，強(qiáng)連通分量，最小生成樹，拓?fù)渑判?，關(guān)鍵路徑，最短路徑.[5]

[1] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)：C語言版[M]．北京：清華大學(xué)出版社，2003:18-39．

[2] 趙福生.最短路徑的教學(xué)[J].福建電腦,2011(6):213-214.

[3] 戴傳江.研究型理工科高校人文素質(zhì)教育的創(chuàng)新[J].四川文理學(xué)院學(xué)報(bào)，2012(2):150-153.

[4] 吳開騰,覃燕梅.提高“數(shù)值分析”課程教學(xué)有效性的策略[J].內(nèi)江師范學(xué)院學(xué)報(bào)，2011(4)：76-78 .

[5] 王 猛,覃燕梅,吳開騰.論程序設(shè)計(jì)教學(xué)中的習(xí)慣養(yǎng)成理念[J].內(nèi)江師范學(xué)院學(xué)報(bào),2011(8)：83-88.

[責(zé)任編輯鄧杰]

MethodandPracticeinTeachingReformofDataStructureCourse

ZHAO Fu-sheng

(Mathematics and Computer Science School of Quanzhou Normal University,Quanzhou Fujian 362000,China)

Five suggestions of teaching reform are put forward and analyzed in detail with examples. The the ideas are practiced and perfected in the classroom teaching. The teaching results show that the teaching reform is effective.

DataStructure;guiding ideology;object-oriented;abstract type.

2013-04-09

趙福生(1980—),男，福建泉州人.助教,碩士，主要從事軟件與算法研究.

G642

A

1674-5248(2013)05-0124-05