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

趙福生

(泉州師范學(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)思路，通過(guò)實(shí)例對(duì)五點(diǎn)思路進(jìn)行詳細(xì)的分析.在實(shí)際的課堂教學(xué)過(guò)程中，不斷實(shí)踐與豐富所提出的五點(diǎn)思路.教學(xué)的結(jié)果表明，教學(xué)改革的五點(diǎn)思路是行之有效的.

數(shù)據(jù)結(jié)構(gòu)；指導(dǎo)思想；面向?qū)ο?；抽象?lèi)型

0 引言

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

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

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

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

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

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

2 采用兩種方法

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

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

(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≥表長(zhǎng)+2)也有可能合法(1≤i≤表長(zhǎng)+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，說(shuō)明插入操作沒(méi)有成功.當(dāng)i≥表長(zhǎng)+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為表長(zhǎng)+1，流程轉(zhuǎn)到第( 6)行，if條件!p為真，返回ERROR，說(shuō)明插入操作沒(méi)有成功.當(dāng)1≤i≤表長(zhǎng)+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，說(shuō)明插入操作已經(jīng)成功.該函數(shù)執(zhí)行完以后，函數(shù)的返回值要么為OK要么為ERROR，如果返回值為ERROR，單鏈表的結(jié)構(gòu)沒(méi)有變化，如果返回值為OK，單鏈表的結(jié)構(gòu)有變化，增加了一個(gè)新元素.由此我們可以得出ListInsert_L函數(shù)的功能，在單鏈表的第i個(gè)位置上插入一個(gè)新的元素，插入操作有可能成功也有可能不成功.

數(shù)據(jù)結(jié)構(gòu)的傳統(tǒng)教學(xué)只注重算法的具體實(shí)現(xiàn)，沒(méi)有采用面向?qū)ο蟮姆椒?如果采用真正的面向?qū)ο笳Z(yǔ)言(如C++語(yǔ)言)來(lái)描述數(shù)據(jù)結(jié)構(gòu)，則面向?qū)ο笳Z(yǔ)言的語(yǔ)法格式比較復(fù)雜，使得學(xué)習(xí)者很難透過(guò)復(fù)雜的語(yǔ)法格式來(lái)掌握蘊(yùn)含的編程思想.因此，在教學(xué)過(guò)程中往往采用標(biāo)準(zhǔn)的C語(yǔ)言與引用類(lèi)型的參數(shù)(簡(jiǎn)稱(chēng)引用形參)來(lái)描述數(shù)據(jù)結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)所使用的存儲(chǔ)空間利用malloc、realloc函數(shù)來(lái)動(dòng)態(tài)分配，當(dāng)數(shù)據(jù)結(jié)構(gòu)所使用的存儲(chǔ)空間不再需要時(shí)，利用free函數(shù)來(lái)釋放.利用malloc、realloc函數(shù)動(dòng)態(tài)分配的存儲(chǔ)空間只有當(dāng)調(diào)用free函數(shù)以后才會(huì)釋放.正因?yàn)橐眯螀⑴c動(dòng)態(tài)存儲(chǔ)分配，才可以在C語(yǔ)言的基礎(chǔ)上采用面向?qū)ο蟮姆椒▉?lái)研究數(shù)據(jù)結(jié)構(gòu).可以借助下面的程序代碼來(lái)更好地理解什么是面向?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ái)初始化L這么一個(gè)對(duì)象，(12)DestroyList_L(L);用來(lái)破壞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(zhǎng)=(10,20,30,40).(4)ListDelete_L(L,1,e);的作用為刪除單鏈表L=(10,20,30,40)第一個(gè)位置上的元素，刪除以后，單鏈表為L(zhǎng)=(20,30,40)，參數(shù)e里面存放刪除元素10.(5)PriorElem_L(L,30,pre_e);用來(lái)求單鏈表L=(20,30,40)里面30的前一個(gè)元素，執(zhí)行完以后，單鏈表沒(méi)有變化仍然為L(zhǎng)=(20,30,40)，參數(shù)pre_e里面存放20.(6)NextElem_L(L,30,next_e);用來(lái)求單鏈表L=(20,30,40)里面30的后一個(gè)元素，執(zhí)行完以后，單鏈表沒(méi)有變化仍然為L(zhǎng)=(20,30,40)，參數(shù)next_e里面存放40.(7)GetElem_L(L,2,e);用來(lái)獲得單鏈表L=(20,30,40)里面的第二個(gè)元素，執(zhí)行完以后，單鏈表沒(méi)有變化仍然為L(zhǎng)=(20,30,40)，參數(shù)e里面存放30.(8)i=LocateElem_L(L,10,Equal);用來(lái)求單鏈表L=(20,30,40)里面與10滿(mǎn)足Equal關(guān)系的第一個(gè)元素的位置，因?yàn)椴淮嬖?，所以?zhí)行完以后i為0.(9)s=ListEmpty_L(L);用來(lái)判斷單鏈表L=(20,30,40)是否為空，執(zhí)行完以后s里面的值為FALSE，說(shuō)明單鏈表非空.(10)i=ListLength_L(L);用來(lái)求單鏈表L=(20,30,40)里面元素的個(gè)數(shù)，執(zhí)行完以后i里面的值為3.(11)ClearList_L(L);用來(lái)清空單鏈表，使得單鏈表由L=(20,30,40)變?yōu)長(zhǎng)=( ).

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

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

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

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

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

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

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

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

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

5 掌握五種抽象類(lèi)型

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

線性表的邏輯結(jié)構(gòu)定義、邏輯算法定義在上一小節(jié)已經(jīng)講過(guò).線性表的存儲(chǔ)結(jié)構(gòu)總共有七種，針對(duì)每種存儲(chǔ)結(jié)構(gòu)都編寫(xiě)了一份資料，每份資料里面都包括邏輯算法的完整實(shí)現(xiàn)、對(duì)算法進(jìn)行調(diào)用的主函數(shù)、整個(gè)程序的運(yùn)行結(jié)果、程序運(yùn)行過(guò)程中數(shù)據(jù)結(jié)構(gòu)的變化(用圖表示).在編寫(xiě)資料時(shí)，不同份資料里面同一個(gè)算法的第一行(也就是同個(gè)操作函數(shù)的第一行)使用相同的函數(shù)名、相同的形參、相同的返回值類(lèi)型，對(duì)算法進(jìn)行調(diào)用的主函數(shù)也相同，因此程序的運(yùn)行結(jié)果也相同.從這七份資料可以更好地理解線性表是一種抽象類(lèi)型.在編寫(xiě)源代碼時(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ù)指針變量，另外開(kāi)辟存儲(chǔ)空間，接收實(shí)參Visit傳過(guò)來(lái)的函數(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)沒(méi)有變化.第(10)行ListTraverse_L(L,Add);整行的作用為：依次把單鏈表每個(gè)元素的值加1，調(diào)用函數(shù)以前以后，單鏈表發(fā)生變化.[4]

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

抽象類(lèi)型隊(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ì)).抽象類(lèi)型隊(duì)列的邏輯操作如下：初始化操作InitQueue，破壞操作DestroyQueue，清空操作ClearQueue，判斷空操作QueueEmpty，求元素個(gè)數(shù)操作QueueLength，獲得隊(duì)頭元素操作GetHead，入隊(duì)操作EnQueue，出隊(duì)操作DeQueue，遍歷隊(duì)列操作QueueTraverse.在編寫(xiě)源代碼時(shí)，抽象類(lèi)型隊(duì)列的存儲(chǔ)結(jié)構(gòu)只采用鏈?zhǔn)疥?duì)列.鏈?zhǔn)疥?duì)列編寫(xiě)完以后，就可以直接使用，使用時(shí)，把隊(duì)列元素?fù)Q成實(shí)際的數(shù)據(jù)類(lèi)型即可.

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

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

[1] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版[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] 吳開(kāi)騰,覃燕梅.提高“數(shù)值分析”課程教學(xué)有效性的策略[J].內(nèi)江師范學(xué)院學(xué)報(bào)，2011(4)：76-78 .

[5] 王 猛,覃燕梅,吳開(kāi)騰.論程序設(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