“數據結構”教學中的關聯教學法探索

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

摘 要： “數據結構”是計算機科學與技術專業的一門核心課程，是一門理論與實踐相結合的課程。學生對這門課程的學習往往不能將前后知識相關聯并用于解決實際問題，對此提出在教學過程中從表達式求值及遍歷二叉樹出發，引導學生將該知識點與進化計算相關聯。延伸出數學函數所對應的二叉樹生成算法，二叉數求值算法，二叉樹繪圖算法，并將二叉樹表達的樹形結構編碼用于進化計算，從而實現產品的外觀造型設計。教學結果證明，該關聯教學法可以很好地提高學生的自主創新能力。

關鍵詞： 自主創新； 數據結構； 二叉樹； 進化計算

中圖分類號：G40 文獻標志碼：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 引言

數據結構[1]是計算機專業的專業基礎課，屬于主干和核心課程。數據結構的學習目的是讓學生理解和掌握各種數據結構的定義及基本操作的實現，理解和掌握典型算法的基本思想、算法設計方法和計算算法的時間復雜度。使學生通過學習，掌握經典算法的編程方法和技巧，提高編程能力。這門課程的學習，不僅鞏固了前導課程（如程序設計、離散數學等）知識，而且為后續課程（如算法設計與分析、人工智能、計算機圖形學）的學習提供了基礎[4]。

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

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

1 表達式求值

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

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

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

2 遍歷二叉樹

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

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

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

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

3 基于樹形結構的進化計算技術

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

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

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

圖2 樹結構編碼的進化計算的交叉操作

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

移除的子樹][A]

圖3 樹結構編碼的進化計算的變異操作

將基于樹形結構編碼的進化計算技術用于輔助設計領域，可以構造出奇異、夢幻、各種美輪美奐的圖形和形狀[5]，如圖4所示。

圖4 基于進化計算的輔助設計環境

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

4 二叉樹生成算法

算法1 生成數學函數的二叉樹表示（CreateBiTree）

輸入：S表示數學函數對應的字符串，low表示字符串的起點，high表示字符串的終點。

輸出：tr表示數學函數對應的二叉樹。

{ if （low和high位置上的左右括號配對出現）

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

自左至右找出S串中low到high之間優先級最高的操作符，記為

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

if （Oper存在） {

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

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

//遞歸調用建立右子樹

}

tr=new CBiTree；

tr->data=Oper；

}

5 樹形結構編碼的交叉和變異算法

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

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

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

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

int len1=TraversTree（tr1）； //求出第一棵二叉樹目前的節點個數

int len2=TraversTree（tr2）； //求出第二棵二叉樹目前的節點個數

int sel1=rand（）%len1+1； //隨機產生交叉點

int sel2=rand（）%len2+1； //隨機產生交叉點

//以下進行交叉操作

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

TreeSelect（tr2，parent2，sel2，flag2）；

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

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

}

6 基于二叉樹的求值算法

算法3 利用二叉樹求解數學函數的值（CalByTree）

輸入：tr表示數學函數對應的二叉樹，x表示自變量的取值。

輸出：f表示函數的值。

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

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

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

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

}

7 二叉樹所對應的三維圖形的顯示算法

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

輸入：tr表示數學函數對應的二叉樹，low和high表示自變量的取值范圍，density表示曲線的平滑度。

輸出：屏幕上圖形顯示結果。

{ 將low與high之間分成density份，對每一份求值置入數組

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 ）； //構造圓柱體

Save（my_body）； //顯示圖形

}

8 改進的二叉樹遍歷算法

算法5 從二叉樹結構出發構建字符串表示的表達式（ReConstruct）

輸入：tr表示數學函數所對應的二叉樹。

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

{ temp=tree->data；

if （temp是操作數） 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的優先級

if （rtemp是操作符）

if （level（rtemp，0）

//比較rtemp與temp的優先級

if （lflag） //子樹的優先級低于根結點，需要加括號

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

else //子樹的優先級高于根結點

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

if （rflag）

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

else

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

return temp；

}

9 結束語

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].清華大學出版社，2011.

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

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

24-27

[4] 許自龍.關于《數據結構》的教學實踐和體會[J].信息技術教學與研

究，2012.4：120-121

[5] 高麗萍，劉弘.支持創新設計的多Agent系統[J].計算機應用研究，

2003.10：18-21