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

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

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

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

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

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

1 表達式求值

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

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

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

2 遍歷二叉樹

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

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

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

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

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

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

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

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

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

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

移除的子樹][A]

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

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

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

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

4 二叉樹生成算法

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

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

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

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

脫括號（low++；high--）；

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

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é)點個數(shù)

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

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

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

//以下進行交叉操作

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

TreeSelect（tr2，parent2，sel2，flag2）；

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

按照flag1和flag2的4種組合進行指針交換操作；

}

6 基于二叉樹的求值算法

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

輸入：tr表示數(shù)學(xué)函數(shù)對應(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 二叉樹所對應(yīng)的三維圖形的顯示算法

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

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

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

{ 將low與high之間分成density份，對每一份求值置入數(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 改進的二叉樹遍歷算法

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

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

輸出：字符串所表示的表達式。

{ temp=tree->data；

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

if （temp是單目運算符） return temp+"（"+ReContruct（tree->right）+"）"；

//如果temp是雙目運算符

CString ltemp， rtemp；

Int lflag， rflag；

ltemp=tree->left->data；

rtemp=tree->right->data；

if （ltemp是操作符）

if （level（ltemp，0）

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

if （rtemp是操作符）

if （level（rtemp，0）

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

if （lflag） //子樹的優(yōu)先級低于根結(jié)點，需要加括號

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

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

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

if （rflag）

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

else

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

return temp；

}

9 結(jié)束語

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

參考文獻：

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

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

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

24-27

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

究，2012.4：120-121

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

2003.10：18-21