“數(shù)據(jù)結(jié)構(gòu)”教學(xué)中的關(guān)聯(lián)教學(xué)法探索

高麗萍 鄧桂英 曹春萍 胡德敏 李銳

摘 要： “數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心課程，是一門理論與實(shí)踐相結(jié)合的課程。學(xué)生對(duì)這門課程的學(xué)習(xí)往往不能將前后知識(shí)相關(guān)聯(lián)并用于解決實(shí)際問題，對(duì)此提出在教學(xué)過程中從表達(dá)式求值及遍歷二叉樹出發(fā)，引導(dǎo)學(xué)生將該知識(shí)點(diǎn)與進(jìn)化計(jì)算相關(guān)聯(lián)。延伸出數(shù)學(xué)函數(shù)所對(duì)應(yīng)的二叉樹生成算法，二叉數(shù)求值算法，二叉樹繪圖算法，并將二叉樹表達(dá)的樹形結(jié)構(gòu)編碼用于進(jìn)化計(jì)算，從而實(shí)現(xiàn)產(chǎn)品的外觀造型設(shè)計(jì)。教學(xué)結(jié)果證明，該關(guān)聯(lián)教學(xué)法可以很好地提高學(xué)生的自主創(chuàng)新能力。

關(guān)鍵詞： 自主創(chuàng)新； 數(shù)據(jù)結(jié)構(gòu)； 二叉樹； 進(jìn)化計(jì)算

中圖分類號(hào)：G40 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）05-54-03

Exploration in the associated teaching methods during the data structure teaching process

Gao Liping， Deng Guiying， Cao Chunping， Hu Demin， Li Rui

（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： Data Structure is one of the core courses of computer science specialty. It's a course requiring the combination of the theory and practice. During the learning process of this course， students tend to pay more attention to the mastery of the teaching materials， while lacking the ability to combine the knowledge front and behind to solve the practical problems. A demand to guide the students to relate the knowledge of the expression evaluation and the binary tree traversing with the evolutionary computation is introduced. It extends the binary tree creation algorithm， binary tree evaluation algorithm and the binary tree drawing algorithm which mathematical functions are corresponded. The tree structure is used to enhance computation and to achieve the appearance design of products. The teaching results show that the associated teaching methods can improve the students' capacity for independent innovation to some extent.

Key words： independent innovation； data structure； binary tree； evolutionary computation

0 引言

數(shù)據(jù)結(jié)構(gòu)[1]是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課，屬于主干和核心課程。數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)目的是讓學(xué)生理解和掌握各種數(shù)據(jù)結(jié)構(gòu)的定義及基本操作的實(shí)現(xiàn)，理解和掌握典型算法的基本思想、算法設(shè)計(jì)方法和計(jì)算算法的時(shí)間復(fù)雜度。使學(xué)生通過學(xué)習(xí)，掌握經(jīng)典算法的編程方法和技巧，提高編程能力。這門課程的學(xué)習(xí)，不僅鞏固了前導(dǎo)課程（如程序設(shè)計(jì)、離散數(shù)學(xué)等）知識(shí)，而且為后續(xù)課程（如算法設(shè)計(jì)與分析、人工智能、計(jì)算機(jī)圖形學(xué)）的學(xué)習(xí)提供了基礎(chǔ)[4]。

計(jì)算機(jī)專業(yè)的本科生在畢業(yè)之后往往選擇從事IT領(lǐng)域的研發(fā)工作，而目前大型企業(yè)往往對(duì)應(yīng)聘者的創(chuàng)新能力有較高的期望值。公司在決定是否接納應(yīng)聘者之前，通常需要對(duì)應(yīng)聘者進(jìn)行電話或者面試，而面試的主要內(nèi)容則來源于實(shí)際問題中所抽象出來的分支問題。應(yīng)聘者需要在給定時(shí)間內(nèi)針對(duì)具體問題，進(jìn)行相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，并基于所選擇的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行算法設(shè)計(jì)及效率分析。這就要求應(yīng)聘者除了具有扎實(shí)的課本知識(shí)，還要能夠靈活運(yùn)用所學(xué)知識(shí)解決實(shí)際問題。因此，在授課過程中，教師除了講解課本知識(shí)外，還應(yīng)該對(duì)各種問題求解進(jìn)行引申與延展，以促進(jìn)學(xué)生創(chuàng)新思維能力的開發(fā)。

本文從“表達(dá)式求值”及“遍歷二叉樹”知識(shí)點(diǎn)出發(fā)，延伸出樹形結(jié)構(gòu)的進(jìn)化計(jì)算技術(shù)，提出在二者之間通過二叉樹生成、二叉樹進(jìn)化操作、二叉樹求值、二叉樹繪圖、二叉樹遍歷等進(jìn)行關(guān)聯(lián)，從而在理論與實(shí)踐之間構(gòu)架一座橋梁。實(shí)驗(yàn)證明，該方法對(duì)于提高學(xué)生的自主創(chuàng)新能力具有十分重要的意義。

1 表達(dá)式求值

表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)最基本的問題，它的實(shí)現(xiàn)往往采用“算符優(yōu)先法”。例如4+2*3-10/5的計(jì)算順序?yàn)椋?+2*3-10/5=4+6-10/5=10-10/5=10-2=8。首先算法會(huì)比較+和*的優(yōu)先級(jí)，發(fā)現(xiàn)*的優(yōu)先級(jí)高于+，故首先執(zhí)行2*3的運(yùn)算，得到4+6-10/5這個(gè)表達(dá)式，之后再進(jìn)行+和-的優(yōu)先級(jí)比較，發(fā)現(xiàn)+的優(yōu)先級(jí)高于-，故執(zhí)行4+6的運(yùn)算，得到10-10/5這個(gè)表達(dá)式，此后再進(jìn)行-和/的優(yōu)先級(jí)比較，發(fā)現(xiàn)-的優(yōu)先級(jí)低于/的，故執(zhí)行10/5的運(yùn)算，得到10-2的表達(dá)式，最后算出最終結(jié)果為8。

從以上分析中可以看出，任何一個(gè)表達(dá)式都是由操作數(shù)和操作符組成，在表達(dá)式求值過程中通過不斷地比較相鄰兩個(gè)運(yùn)算符之間的優(yōu)先級(jí)，來確定參加運(yùn)算的運(yùn)算數(shù)，并需要存儲(chǔ)臨時(shí)計(jì)算結(jié)果。這個(gè)過程可以通過定義操作符優(yōu)先矩陣，并控制操作符及操作數(shù)棧的入棧和出棧順序來實(shí)現(xiàn)。

在算符優(yōu)先法中，主要通過堆棧這個(gè)數(shù)據(jù)結(jié)構(gòu)完成對(duì)表達(dá)式的求值，且僅適用于雙目運(yùn)算符，無(wú)法提供對(duì)單目運(yùn)算符（如sin，cos，exp等）的支持，并且也不能支持對(duì)表達(dá)式的自由變更。

2 遍歷二叉樹

二叉樹的遍歷分為前序、中序和后序遍歷。前序遍歷按照“根結(jié)點(diǎn)-左子樹-右子樹”的順序完成對(duì)二叉樹的訪問；中序遍歷按照“左子樹-根結(jié)點(diǎn)-右子樹”的順序完成對(duì)二叉樹的訪問；后序遍歷按照“左子樹-右子樹-根結(jié)點(diǎn)”的順序完成對(duì)二叉樹的訪問。如圖1所示的二叉樹，經(jīng)過中序遍歷后，得到的中序序列為：a+b*c-d-e/f。

[a] [b][c] [d] [e] [f] [+] [-] [*] [/] [-]

圖1 表達(dá)式a+b*（c-d）-e/f的二叉樹

該二叉樹結(jié)構(gòu)能夠支持表達(dá)式的自由變換，但當(dāng)需要通過遍歷生成所需要的表達(dá)式時(shí)，卻沒有根據(jù)運(yùn)算符的優(yōu)先級(jí)加括號(hào)，因此會(huì)產(chǎn)生與原表達(dá)式不一致的狀態(tài)。例如圖1所產(chǎn)生的表達(dá)式a+b*c-d-e/f與原表達(dá)式a+b*（c-d）-e/f含義不同。

3 基于樹形結(jié)構(gòu)的進(jìn)化計(jì)算技術(shù)

進(jìn)化計(jì)算[2]是模擬自然界生物進(jìn)化過程的計(jì)算模型。它依據(jù)適者生存、優(yōu)勝劣汰的進(jìn)化規(guī)則對(duì)包含可能解的群體反復(fù)進(jìn)行遺傳操作（交叉、變異、選擇），不斷產(chǎn)生新的個(gè)體。

進(jìn)化計(jì)算可以采用多種編碼方式：二進(jìn)制編碼、實(shí)數(shù)編碼及樹形編碼。一棵用數(shù)學(xué)表示的二叉樹是一個(gè)數(shù)學(xué)操作數(shù)及數(shù)學(xué)操作符的有限節(jié)點(diǎn)集，該集或者是空集，或者是由根及兩棵互不相交的，稱為左、右子樹的二叉樹組成。二叉樹的中序遍歷序列是一個(gè)合法的數(shù)學(xué)表達(dá)式。樹的節(jié)點(diǎn)可以是終端節(jié)點(diǎn)（操作數(shù)）或者是中間節(jié)點(diǎn)（操作符）。操作數(shù)可以是變量，也可以是常量，操作符包括基本運(yùn)算符+，2，3，/，^，基本數(shù)學(xué)函數(shù)sqrt（），exp（），log（），三角函數(shù)sin（），cos（），tan（），asin（），acos（），atan（）以及雙曲函數(shù)sinh（），cosh（），tanh（），asinh（），acosh（），atanh（）等。例如圖1所示的二叉樹就是個(gè)體a+b*（c-d）-e/f所對(duì)應(yīng)的樹形結(jié)構(gòu)編碼?；跇湫尉幋a的交叉和變異操作如圖2和圖3所示。

[A][B][A][B]

圖2 樹結(jié)構(gòu)編碼的進(jìn)化計(jì)算的交叉操作

[A][移除的子樹][用新子樹替換

移除的子樹][A]

圖3 樹結(jié)構(gòu)編碼的進(jìn)化計(jì)算的變異操作

將基于樹形結(jié)構(gòu)編碼的進(jìn)化計(jì)算技術(shù)用于輔助設(shè)計(jì)領(lǐng)域，可以構(gòu)造出奇異、夢(mèng)幻、各種美輪美奐的圖形和形狀[5]，如圖4所示。

圖4 基于進(jìn)化計(jì)算的輔助設(shè)計(jì)環(huán)境

在講解完二叉樹遍歷這部分內(nèi)容時(shí)，首先跟同學(xué)一起回顧二叉樹求值的內(nèi)容，之后，給出支持進(jìn)化的輔助設(shè)計(jì)環(huán)境，以引發(fā)學(xué)生對(duì)這二者之間相互關(guān)聯(lián)的探索興趣。通過討論得出如下結(jié)論：要能夠支持樹形結(jié)構(gòu)編碼的進(jìn)化計(jì)算，首先我們需要設(shè)計(jì)相應(yīng)的算法，將給定的表達(dá)式轉(zhuǎn)化成二叉樹表示，支持交叉和變異操作，之后能根據(jù)給定的變量值進(jìn)行表達(dá)式求值，并根據(jù)求得的值進(jìn)行圖形顯示，最后通過遍歷得到字符串結(jié)構(gòu)的表達(dá)式形式。

4 二叉樹生成算法

算法1 生成數(shù)學(xué)函數(shù)的二叉樹表示（CreateBiTree）

輸入：S表示數(shù)學(xué)函數(shù)對(duì)應(yīng)的字符串，low表示字符串的起點(diǎn)，high表示字符串的終點(diǎn)。

輸出：tr表示數(shù)學(xué)函數(shù)對(duì)應(yīng)的二叉樹。

{ if （low和high位置上的左右括號(hào)配對(duì)出現(xiàn)）

脫括號(hào)（low++；high--）；

自左至右找出S串中l(wèi)ow到high之間優(yōu)先級(jí)最高的操作符，記為

Oper，Oper在S中的位置記為k。

if （Oper存在） {

tr->left=CreateBiTree（s，low，k-1）；//遞歸調(diào)用建立左子樹

tr->right=CreateBiTree（s，k+Oper.Length（）+1，high）；

//遞歸調(diào)用建立右子樹

}

tr=new CBiTree；

tr->data=Oper；

}

5 樹形結(jié)構(gòu)編碼的交叉和變異算法

算法2 基于二叉樹的交叉和變異算法（TreeCross）

輸入：tr1，tr2分別代表兩顆待執(zhí)行交叉或變異操作的二叉樹。

輸出：tr1，tr2分別代表執(zhí)行交叉或變異之后的二叉樹。

{ if（tr1==NULL||tr2==NULL） return；

int len1=TraversTree（tr1）； //求出第一棵二叉樹目前的節(jié)點(diǎn)個(gè)數(shù)

int len2=TraversTree（tr2）； //求出第二棵二叉樹目前的節(jié)點(diǎn)個(gè)數(shù)

int sel1=rand（）%len1+1； //隨機(jī)產(chǎn)生交叉點(diǎn)

int sel2=rand（）%len2+1； //隨機(jī)產(chǎn)生交叉點(diǎn)

//以下進(jìn)行交叉操作

TreeSelect（tr1，parent1，sel1，flag1）； //獲取待交叉節(jié)點(diǎn)的父親結(jié)點(diǎn)，存入parent1；flag1用來記錄tree1是父親結(jié)點(diǎn)的左/右孩子結(jié)點(diǎn)。

TreeSelect（tr2，parent2，sel2，flag2）；

//獲取待交叉節(jié)點(diǎn)的父親結(jié)點(diǎn)，存入parent2；

按照flag1和flag2的4種組合進(jìn)行指針交換操作；

}

6 基于二叉樹的求值算法

算法3 利用二叉樹求解數(shù)學(xué)函數(shù)的值（CalByTree）

輸入：tr表示數(shù)學(xué)函數(shù)對(duì)應(yīng)的二叉樹，x表示自變量的取值。

輸出：f表示函數(shù)的值。

{ if （tr->data不是操作符） return x；

f1=CalByTree（tr->left，x）；

f2=CalByTree（tr->right，x）；

f=Cal（f1，tr->data，f2）；

}

7 二叉樹所對(duì)應(yīng)的三維圖形的顯示算法

算法4 二叉樹所對(duì)應(yīng)的三維圖形顯示（GraphicShow）[3]

輸入：tr表示數(shù)學(xué)函數(shù)對(duì)應(yīng)的二叉樹，low和high表示自變量的取值范圍，density表示曲線的平滑度。

輸出：屏幕上圖形顯示結(jié)果。

{ 將low與high之間分成density份，對(duì)每一份求值置入數(shù)組

Point[density]中；

for （i=0； i

api_solid_cylinder_cone（position（point[i].x，0，0），

position（point[i+1].x，0，0）， point[i].y，point[i].y， point[i+1].y，

NULL，my_body ）； //構(gòu)造圓柱體

Save（my_body）； //顯示圖形

}

8 改進(jìn)的二叉樹遍歷算法

算法5 從二叉樹結(jié)構(gòu)出發(fā)構(gòu)建字符串表示的表達(dá)式（ReConstruct）

輸入：tr表示數(shù)學(xué)函數(shù)所對(duì)應(yīng)的二叉樹。

輸出：字符串所表示的表達(dá)式。

{ temp=tree->data；

if （temp是操作數(shù)） return temp；

if （temp是單目運(yùn)算符） return temp+"（"+ReContruct（tree->right）+"）"；

//如果temp是雙目運(yùn)算符

CString ltemp， rtemp；

Int lflag， rflag；

ltemp=tree->left->data；

rtemp=tree->right->data；

if （ltemp是操作符）

if （level（ltemp，0）

//比較ltemp與temp的優(yōu)先級(jí)

if （rtemp是操作符）

if （level（rtemp，0）

//比較rtemp與temp的優(yōu)先級(jí)

if （lflag） //子樹的優(yōu)先級(jí)低于根結(jié)點(diǎn)，需要加括號(hào)

temp="（"+ReContruct（tree->left）+"）"+temp；

else //子樹的優(yōu)先級(jí)高于根結(jié)點(diǎn)

temp=ReContruct（tree->left）+temp；

if （rflag）

temp=temp+"（"+ReContruct（tree->right）+"）"；

else

temp=temp+ReContruct（tree->right）；

return temp；

}

9 結(jié)束語(yǔ)

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門非常重要的核心課程，擔(dān)負(fù)著構(gòu)架程序設(shè)計(jì)、算法設(shè)計(jì)與分析之間橋梁的重要任務(wù)，所學(xué)知識(shí)是學(xué)生走上社會(huì)崗位所必備的。傳統(tǒng)的授課模式一般以課本知識(shí)為重點(diǎn)，鮮少進(jìn)行基礎(chǔ)知識(shí)與前沿科學(xué)之間的關(guān)聯(lián)和討論。本文從表達(dá)式求值及二叉樹遍歷兩個(gè)知識(shí)點(diǎn)出發(fā)，延伸出數(shù)學(xué)函數(shù)所對(duì)應(yīng)的二叉樹生成算法，二叉樹求值算法，二叉樹繪圖算法，并將二叉樹表達(dá)的樹形結(jié)構(gòu)編碼用于進(jìn)化計(jì)算，從而實(shí)現(xiàn)產(chǎn)品的外觀造型設(shè)計(jì)。課堂教學(xué)效果顯示，該方法對(duì)于提高學(xué)生理論與實(shí)踐的關(guān)聯(lián)能力、提高學(xué)生獨(dú)立思考和解決問題的能力具有十分重要的意義。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].清華大學(xué)出版社，2011.

[2] 王正志，薄濤.進(jìn)化計(jì)算[M].國(guó)防科技大學(xué)出版社，2000.

[3] 楊曉波，陳邦澤.二叉樹的可視化實(shí)現(xiàn)[J].國(guó)際IT傳媒品牌，2011.32：

24-27

[4] 許自龍.關(guān)于《數(shù)據(jù)結(jié)構(gòu)》的教學(xué)實(shí)踐和體會(huì)[J].信息技術(shù)教學(xué)與研

究，2012.4：120-121

[5] 高麗萍，劉弘.支持創(chuàng)新設(shè)計(jì)的多Agent系統(tǒng)[J].計(jì)算機(jī)應(yīng)用研究，

2003.10：18-21