李鳳榮 劉嘉洋

摘 要 數(shù)據(jù)結(jié)構(gòu)是研究計(jì)算機(jī)科學(xué)和工程的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與專業(yè)技術(shù)專業(yè)及相關(guān)專業(yè)的核心課程之一，學(xué)好該課程不僅對(duì)后續(xù)課程的學(xué)習(xí)有很大幫助，而且對(duì)開發(fā)有效利用計(jì)算機(jī)資源的程序極為有益。

關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 二叉樹 算法

中圖分類號(hào)：G424文獻(xiàn)標(biāo)識(shí)碼：A

計(jì)算機(jī)是進(jìn)行數(shù)據(jù)處理的工具，數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的各種組織形式以及建立在這些結(jié)構(gòu)之上的各種運(yùn)算算法的實(shí)現(xiàn)，它不僅為用計(jì)算機(jī)語(yǔ)言進(jìn)行程序設(shè)計(jì)提供了方法性的理論指導(dǎo)，還在更高的層次上總結(jié)了程序設(shè)計(jì)的常用方法和常用技巧。

1教學(xué)目標(biāo)剖析

1.1課程性質(zhì)

數(shù)據(jù)結(jié)構(gòu)是一門承上啟下的課程，前期課程：計(jì)算機(jī)基礎(chǔ)，C語(yǔ)言，后期課程：算法設(shè)計(jì)與分析、操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)原理、軟件工程……。

1.2教學(xué)目標(biāo)剖析

數(shù)據(jù)結(jié)構(gòu)課程是研究各種數(shù)據(jù)模型在內(nèi)存中的存儲(chǔ)方法及實(shí)現(xiàn)方法，只要是程序，無(wú)不是以數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)。通過(guò)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程獲得經(jīng)典數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法的思想、方法、技術(shù)。學(xué)習(xí)過(guò)程就像思維體操，潛移默化中提高程序設(shè)計(jì)和計(jì)算思維能力。所以，理解并掌握基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典的算法，培養(yǎng)算法設(shè)計(jì)和分析能力，培養(yǎng)計(jì)算思維能力，培養(yǎng)數(shù)據(jù)結(jié)構(gòu)和算法的運(yùn)用能力是這門課的教學(xué)目標(biāo)。

1.3教學(xué)內(nèi)容設(shè)計(jì)

在教學(xué)設(shè)計(jì)上緊扣大綱，涵蓋全部知識(shí)點(diǎn)（考研、面試）;強(qiáng)調(diào)基礎(chǔ)提煉基礎(chǔ)性內(nèi)容，讓學(xué)生在這門課程涉及的相關(guān)領(lǐng)域內(nèi)，打下終身學(xué)習(xí)的知識(shí)基礎(chǔ)、技術(shù)基礎(chǔ)和思維基礎(chǔ);因材施教對(duì)人的公平以及對(duì)人才的公平，對(duì)某些知識(shí)點(diǎn)進(jìn)行適當(dāng)?shù)臄U(kuò)充和提高，可用于選講，可用于部分同學(xué)的講授，也可用于學(xué)生自學(xué)或課外閱讀;抽象分層兼顧概念層和實(shí)現(xiàn)層，既強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)的基本概念和原理方法，又注重?cái)?shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)和實(shí)際運(yùn)用;呈上啟下抓住關(guān)鍵點(diǎn)。

1.4課程結(jié)構(gòu)設(shè)計(jì)

我們將課程分成兩條線讓學(xué)生更好的理解：第一條線從線性表→?！?duì)列→串→數(shù)組→樹→二叉樹→圖;第二條線從邏輯結(jié)構(gòu)→映射計(jì)算機(jī)中的表示→存儲(chǔ)結(jié)構(gòu)→運(yùn)算實(shí)現(xiàn)→算法設(shè)計(jì)。只有掌握了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)表示方法，才能在此之上設(shè)計(jì)更有效的算法。

2數(shù)據(jù)表示的重要性及講授方法

數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序，程序設(shè)計(jì)的關(guān)鍵是數(shù)據(jù)表示和數(shù)據(jù)處理。將現(xiàn)實(shí)世界的問(wèn)題進(jìn)行抽象變成模型化數(shù)據(jù)模型，表示高級(jí)語(yǔ)言層（常量變量、數(shù)據(jù)類型）進(jìn)行翻譯到機(jī)器層（內(nèi)存0、1編碼）。將問(wèn)題（抽象模型+基本思路）的想法（數(shù)據(jù)表示+數(shù)據(jù)處理）編程算法（程序語(yǔ)言+編程環(huán)境）用程序?qū)崿F(xiàn)。

數(shù)據(jù)表示的重要性及講授方法，沒(méi)有數(shù)據(jù)表示，數(shù)據(jù)處理是空中樓閣（頂層算法）。存儲(chǔ)（映像）到內(nèi)存中，由機(jī)外表示轉(zhuǎn)換為機(jī)內(nèi)表示。

2.1變量表示數(shù)據(jù)的理解

通過(guò)順序表的插入實(shí)現(xiàn)體會(huì)數(shù)據(jù)表示的含義，計(jì)算的本質(zhì)就是符號(hào)變換，形式化的計(jì)算機(jī)僅有語(yǔ)法，沒(méi)有語(yǔ)義，如數(shù)據(jù)的插入程序

for （int j = L->length-1; j > i; j--）

L->data[j+1] = L->data[j];

2.2從實(shí)際問(wèn)題抽象的數(shù)據(jù)模型

例如求解兩個(gè)動(dòng)物之間通信的最少翻譯問(wèn)題，來(lái)掌握廣度優(yōu)先遍歷在求解實(shí)際問(wèn)題中的應(yīng)用。假設(shè)動(dòng)物A可以與動(dòng)物B進(jìn)行通信（通信是雙向的），但它不能與動(dòng)物C通信，動(dòng)物C只能與動(dòng)物B通信，所以動(dòng)物A、C之間通信需要?jiǎng)游顱來(lái)當(dāng)翻譯。則兩個(gè)動(dòng)物之間相互通信最少需要多少翻譯。通過(guò)輸入樣本得出輸出結(jié)果。

2.3算法的執(zhí)行結(jié)果

哈夫曼樹具體的構(gòu)造方法，如何實(shí)現(xiàn)使用頻率越高的字符采用越短的編碼。理解在數(shù)據(jù)通信中文字怎樣轉(zhuǎn)換成二進(jìn)制字符0和1的。

3運(yùn)行實(shí)例方法在教學(xué)中的運(yùn)用

3.1運(yùn)行實(shí)例，理解基本思想

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹的數(shù)據(jù)元素，因此必須確定好樹中各元素的存放次序，使得各數(shù)據(jù)元素在這個(gè)存放次序中的相互位置能反映出數(shù)據(jù)元素之間的邏輯關(guān)系。

3.2運(yùn)行實(shí)例，設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)

3.2.1二叉樹順序存儲(chǔ)結(jié)構(gòu)（不用下標(biāo)為0的元素）

typedef? ElemType? SqBTree[MaxSize];

SqBTree bt="#ABD#C#E######F";

其特點(diǎn)：對(duì)于完全二叉樹來(lái)說(shuō)，其順序存儲(chǔ)是十分合適的;對(duì)于一般的二叉樹，特別是對(duì)于那些單分支結(jié)點(diǎn)較多的二叉樹來(lái)說(shuō)是很不合適的，因?yàn)榭赡苤挥猩贁?shù)存儲(chǔ)單元被利用，特別是對(duì)退化的二叉樹（即每個(gè)分支結(jié)點(diǎn)都是單分支的），空間浪費(fèi)更是驚人。在順序存儲(chǔ)結(jié)構(gòu)中，找一個(gè)結(jié)點(diǎn)的雙親和孩子都很容易。

3.2.2二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)用鏈表中的結(jié)點(diǎn)來(lái)存儲(chǔ)。

typedef struct node

{? ?ElemType data;

struct node *lchild， *rchild;

} BTNode;

其特點(diǎn)：除了指針外，二叉鏈比較節(jié)省存儲(chǔ)空間。占用的存儲(chǔ)空間與樹形沒(méi)有關(guān)系，只與樹中結(jié)點(diǎn)個(gè)數(shù)有關(guān);在二叉鏈中，找一個(gè)結(jié)點(diǎn)的孩子很容易，但找其雙親不方便。

3.3運(yùn)行實(shí)例，解決算法的關(guān)鍵問(wèn)題

二叉樹的基本運(yùn)算包括創(chuàng)建二叉樹、查找結(jié)點(diǎn)、求高度、輸出等。

void CreateBTNode（BTNode * &b，char *str）

{? ? ? //由str 二叉鏈b

BTNode *St[MaxSize]， *p;

int top=-1，? k ， j=0;

char ch;

b=NULL;//建立的二叉鏈初始時(shí)為空

ch=str[j];

while （ch！='＼0'）? //str未掃描完時(shí)循環(huán)

{? ? ?switch（ch）

{

case '（'： top++; St[top]=p; k=1; break;//可能有左孩子結(jié)點(diǎn)，進(jìn)棧

case '）'： top--;? break;

case '，'： k=2;? break; //后面為右孩子結(jié)點(diǎn)

……

4數(shù)據(jù)結(jié)構(gòu)中的計(jì)算思維

任何一種思維的形成，都肯定有一定的模式（套路），都需要大量的練習(xí)， 在潛移默化中逐漸形成。思維培養(yǎng)是一個(gè)綜合性的系統(tǒng)工程，把計(jì)算思維的培養(yǎng)構(gòu)建一個(gè)教學(xué)體系，需要思考計(jì)算思維的特征和表現(xiàn)是什么？計(jì)算思維有哪些組成？各組成部分在哪些課程中講授？如何將其貫徹到具體課程的知識(shí)單元中？程序設(shè)計(jì)的過(guò)程訓(xùn)練就像一種思維體操，能夠使思維得到鍛煉，引導(dǎo)思維過(guò)程，在潛移默化中使思維變得更清晰、更有邏輯，程序設(shè)計(jì)關(guān)注的是從實(shí)際問(wèn)題到抽象出解決問(wèn)題的算法，直至編寫程序解決問(wèn)題的整個(gè)思維過(guò)程，這個(gè)過(guò)程正是計(jì)算思維的運(yùn)用過(guò)程。使學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)理解得到升華。

5結(jié)語(yǔ)

數(shù)據(jù)結(jié)構(gòu)是一門應(yīng)用實(shí)踐性非常強(qiáng)的課程，學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)（特別是存儲(chǔ)結(jié)構(gòu)）的基礎(chǔ)上一定要盡可能地多上機(jī)實(shí)習(xí)，通過(guò)較多的實(shí)驗(yàn)把難以理解的抽象概念轉(zhuǎn)化為實(shí)實(shí)在在的能夠在計(jì)算機(jī)上執(zhí)行的程序，這樣才能將所學(xué)知識(shí)和實(shí)際應(yīng)用結(jié)合起來(lái)，吸取算法的設(shè)計(jì)思想和精髓，提高運(yùn)用這些知識(shí)解決實(shí)際問(wèn)題的能力。