徐 翀 徐 建

杭州電子科技大學(xué) 浙江杭州 310018

數(shù)據(jù)結(jié)構(gòu)的對象化教學(xué)方式探討與實踐

徐 翀 徐 建

杭州電子科技大學(xué) 浙江杭州 310018

數(shù)據(jù)結(jié)構(gòu)是高等院校計算機(jī)專業(yè)的一門重要的專業(yè)課。就目前普遍采用的面向過程的教學(xué)方式的弊端，提出了進(jìn)行對象化的教學(xué)方式。結(jié)合我院實踐，提出了一系列的教學(xué)步驟，并對此作了分析和探討。

數(shù)據(jù)結(jié)構(gòu)；面向?qū)ο?；模板?/p>

Abstract: Data structure is an important course for computer science major in university. In this paper, the abuse of a commonly used processoriented teaching method has been analyzed; the author proposes the object-oriented teaching methods. Based on the experience of our college,it puts forward a series of teaching procedures then have been analyzed and discussed.

Key words: data structure; object oriented; template class

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)軟件技術(shù)的基礎(chǔ),以數(shù)據(jù)為中心講述問題如何在計算機(jī)程序中得以實現(xiàn),這門課程的理解和掌握,對學(xué)生進(jìn)行數(shù)據(jù)分析、組織及處理能力以及編程能力有著非常深遠(yuǎn)的影響。課程教學(xué)目標(biāo)不僅要培養(yǎng)學(xué)生縝密的邏輯思維和數(shù)據(jù)抽象能力,更要培養(yǎng)學(xué)生在軟件設(shè)計領(lǐng)域科學(xué)的思維方式,將算法理論和編程實踐完美結(jié)合,能夠在工程實際中靈活加以應(yīng)用。因此不斷改進(jìn)數(shù)據(jù)結(jié)構(gòu)的教學(xué)方法,提高數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)質(zhì)量是培養(yǎng)高素質(zhì)軟件人才的迫切要求。

眾所周知,面向?qū)ο蟪绦蛟O(shè)計思想是目前的主流,它首先著眼于應(yīng)用問題所涉及的對象、對象的屬性、操作等,據(jù)此建立類的繼承層次結(jié)構(gòu),實現(xiàn)所應(yīng)完成的功能。在存儲結(jié)構(gòu)的訪問上,只有通過類的成員函數(shù)才能完成,提高了數(shù)據(jù)的安全性。并且這種程序可靠性,可復(fù)用性均比面向過程的程序更為優(yōu)越。在數(shù)據(jù)結(jié)構(gòu)課程中,可體現(xiàn)為主要工作是處理數(shù)據(jù),對于基本的數(shù)據(jù)結(jié)構(gòu)(線性表、棧、隊列、樹、圖),可以將其數(shù)據(jù)元素的類型定義和基本操作封裝在類中,對這些類作概括抽象,建立實例,能幫助學(xué)生加深對數(shù)據(jù)結(jié)構(gòu)整體認(rèn)識,并鍛煉學(xué)生的編程能力,培養(yǎng)好的編程習(xí)慣,從根本上解決學(xué)生不會分析問題,走出不會編程實現(xiàn)的困境。

本文中使用的面向?qū)ο笳Z言為C++,以《二叉樹和圖》這一章節(jié)中的內(nèi)容為例,探討了使用面向?qū)ο蟮慕虒W(xué)方式,在我校經(jīng)實踐取得了不錯的效果。

1 目前主流的數(shù)據(jù)結(jié)構(gòu)教學(xué)方法存在的弊端

目前國內(nèi)高校計算機(jī)專業(yè)的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大多采用面向過程的思想,當(dāng)描述一種數(shù)據(jù)結(jié)構(gòu)時,通常使用抽象數(shù)據(jù)類型(ADT)。而解決一個具體問題時,首先從系統(tǒng)要實現(xiàn)的功能著手,自頂向下,逐步分解來實現(xiàn)相應(yīng)的程序模塊。采用這種思想,該課程側(cè)重點在于具體算法設(shè)計實現(xiàn)上,學(xué)生往往會注重算法而忽略數(shù)據(jù)結(jié)構(gòu)的定義,考慮問題的著眼點放在局部而非整體。另一方面每一個算法是由一個具體問題研究而出,導(dǎo)致程序的可復(fù)用性很差,不是當(dāng)前的程序設(shè)計方法主流。

經(jīng)查閱資料發(fā)現(xiàn),目前國內(nèi)高校采用面向?qū)ο蟮乃枷脒M(jìn)行數(shù)據(jù)結(jié)構(gòu)教學(xué)還不多見,所使用的語言描述工具常是偽代碼指令,學(xué)生往往很困惑,無法調(diào)動學(xué)習(xí)積極性。

通過上面的分析,可以看出我們正面臨著一個問題：如何修正數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)指導(dǎo)思想來適應(yīng)快速發(fā)展的軟件開發(fā)技術(shù),引入面向?qū)ο蟮拿枋龇椒▉碚归_教學(xué)已迫在眉睫。

2 進(jìn)行面向?qū)ο髷?shù)據(jù)結(jié)構(gòu)教學(xué)的步驟

2.1 做好面向?qū)ο蟪绦蛟O(shè)計的教學(xué)前期工作

面向?qū)ο蟪绦蛟O(shè)計,有2個最為重要的思想即封裝和繼承。作為數(shù)據(jù)結(jié)構(gòu)的先修課程,在教學(xué)過程要重點把握好這兩點。

2.1.1 認(rèn)識封裝,學(xué)會用對象來構(gòu)造程序

在培養(yǎng)學(xué)生編程思維時,要能夠首先考慮用什么對象來解決問題,學(xué)會用對象來構(gòu)造程序。

2.1.2 使用繼承,實現(xiàn)代碼重用

使用繼承的方法很好地實現(xiàn)了軟件的可重用性,讓學(xué)生從實例中領(lǐng)悟一般與特殊的關(guān)系,在進(jìn)行開發(fā)程序時,就可以從類庫中選擇類,進(jìn)行繼承功能。

2.2 用模板類的方式實現(xiàn)每種基本數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)課程的主要教學(xué)內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的操作。4大基本數(shù)據(jù)結(jié)構(gòu)分別是集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。在數(shù)據(jù)結(jié)構(gòu)中,更側(cè)重于算法的實現(xiàn),因此對各種數(shù)據(jù)類型通過使用模板,可以只設(shè)計一個類來處理多種類型的數(shù)據(jù),而不必為每一種類型分別創(chuàng)建類,指定一組基于相同代碼但是處理不同類型或類的函數(shù)就可以完成。下面以二叉樹為例構(gòu)建模板類：

在這個模板類中,首先定義了二叉樹結(jié)點BTNode,是一個結(jié)構(gòu)體,包含數(shù)據(jù)域、左孩子指針和右孩子指針。再定義了一個二叉鏈表類BinaryTree,公有函數(shù)中包含了該類的構(gòu)造函數(shù)和析構(gòu)函數(shù),除此還有二叉樹先序中序和后序遍歷等。另預(yù)留了2個create函數(shù)作為接口,作為學(xué)生在學(xué)完后的課程設(shè)計作業(yè)。若要添加操作,只需在類中增加相應(yīng)函數(shù)即可實現(xiàn)。私有函數(shù)是封裝的,通過調(diào)用類中的公有函數(shù)來訪問它。

2.3 用案例加深面向?qū)ο蟮睦斫?/p>

在教學(xué)過程中,講解各種數(shù)據(jù)結(jié)構(gòu)及其算法往往使學(xué)生覺得枯燥無味,很多學(xué)生學(xué)完了數(shù)據(jù)結(jié)構(gòu)后經(jīng)常會發(fā)問：學(xué)習(xí)這種數(shù)據(jù)結(jié)構(gòu)有何用途？或者在現(xiàn)實生活中哪里可以應(yīng)用到？引入案例更能吸引學(xué)生,提高他們的學(xué)習(xí)興趣,因此案例是重要的教學(xué)資源。教師在講授每一種數(shù)據(jù)結(jié)構(gòu)時,首先設(shè)計與現(xiàn)實生活緊密相連的實際問題,讓學(xué)生試著先用面向過程的方式去解決,再由教師用面向?qū)ο蟮姆绞饺ソ鉀Q,從程序編碼的數(shù)量,到重用代碼的便利等多方面進(jìn)行比較,加深對面向?qū)ο蟮睦斫?。如在《圖》這一章中,設(shè)計一個實例為教學(xué)計劃編制問題,若用面向過程的方式來完成,必須要構(gòu)造圖,建立鄰接表作為存儲結(jié)構(gòu),利用基本數(shù)據(jù)結(jié)構(gòu)棧的出棧入棧等操作,最后用拓?fù)涞姆绞酵瓿伞３绦蛩煤瘮?shù)調(diào)用如圖1所示：

圖1 函數(shù)層次關(guān)系圖

而用面向?qū)ο蟮姆绞?因為已經(jīng)將圖的存儲結(jié)構(gòu)和基本操作封裝在一個頭文件中,使用這種數(shù)據(jù)結(jié)構(gòu)時,只需要將相應(yīng)的頭文件包含在程序中,隨用隨調(diào)。這樣可以幫助學(xué)生將所學(xué)知識形成一個完整框架,讓學(xué)生懂得設(shè)計程序不僅要懂得算法,還要讓程序設(shè)計得模塊化,結(jié)構(gòu)化。這正是面向?qū)ο笏枷氲木琛?/p>

2.4 改革課程設(shè)計讓學(xué)生從看懂到會做

課程設(shè)計是培養(yǎng)學(xué)生動手實踐能力的具體體現(xiàn)。配套相應(yīng)的課程設(shè)計讓學(xué)生自行完成,能加深學(xué)生對數(shù)據(jù)結(jié)構(gòu)的理解,使用面向?qū)ο蟮乃枷胱寣W(xué)生真正學(xué)會編程,學(xué)會分析問題,解決問題。我院主要從如下2點進(jìn)行了課程設(shè)計的教學(xué)改革：

2.4.1 梯度命題,循序漸進(jìn)

課程設(shè)計以往是教師根據(jù)實驗指導(dǎo)書布置課題后由學(xué)生完成,部分學(xué)生感到難度很大,無從下手。現(xiàn)階段我們將課程設(shè)計改為驗證型、驗證設(shè)計型、設(shè)計應(yīng)用型多種層次,進(jìn)行梯度命題,分層教學(xué),使得不同層次的學(xué)生各有收獲。針對各種基本數(shù)據(jù)結(jié)構(gòu),教師首先用模板類實現(xiàn),學(xué)生在課程設(shè)計時先用實例驗證程序,在此基礎(chǔ)上,設(shè)計出預(yù)留的一些函數(shù)接口,實現(xiàn)該類的部分功能。最后再針對某一具體問題,由學(xué)生開發(fā)出完整的程序。這是一個由易入難的循序漸進(jìn)的過程,學(xué)生通過驗證型實驗更加牢固掌握基本數(shù)據(jù)結(jié)構(gòu),再由驗證設(shè)計型和設(shè)計應(yīng)用型實驗學(xué)會如何應(yīng)用數(shù)據(jù)結(jié)構(gòu),如何在計算機(jī)中實現(xiàn)存儲,實現(xiàn)各種需求的功能。

如二叉樹部分,教師設(shè)定的驗證型實驗為：給定一棵二叉樹,驗證其先序中序和后序遍歷結(jié)果。在掌握了二叉樹遍歷的基礎(chǔ)上,設(shè)計出模板類中預(yù)留的兩個接口函數(shù)create1和create2。最后,安排設(shè)計型實驗為創(chuàng)建表達(dá)式樹；分別用3種遍歷方式遍歷該樹,比較它與實際的波蘭式、中綴式和逆波蘭式之間的區(qū)別；完成給定表達(dá)式樹的表達(dá)式求值運算。這樣有梯度地安排課程設(shè)計,一方面強化了基本概念,另一方面引導(dǎo)學(xué)生完成更復(fù)雜的設(shè)計。對基礎(chǔ)薄弱的同學(xué)來說,驗證型實驗難度不大,基本都能完成,大大增強了自信；對優(yōu)秀學(xué)生來說,挑戰(zhàn)設(shè)計型實驗更能提高自身的能力。

2.4.2 精編課題,聯(lián)系實際

教師在每一章精編幾道綜合實用課題,從功能定義、系統(tǒng)分析、數(shù)據(jù)抽象、類的定義、代碼實現(xiàn)等方面進(jìn)行指導(dǎo),彌補學(xué)生在學(xué)習(xí)理論知識時不能聯(lián)系實際的情況。我校課程設(shè)計的題目有：學(xué)生成績管理系統(tǒng)(線性表)、地圖四染色問題(棧)、舞伴問題(隊列)、線索二叉樹問題、報文編碼問題(哈夫曼樹)、校園導(dǎo)航問題(圖的最短路徑)、教學(xué)計劃編制(拓?fù)渑判?、文本文件單詞的檢索(查找)、排序綜合問題等,并要求學(xué)生利用類模板完成上述程序。課程設(shè)計的成績由幾個方面綜合決定,包括課題的難易度、完成情況、代碼編寫質(zhì)量等,最后由學(xué)生提交設(shè)計報告進(jìn)行總結(jié)和討論。設(shè)計報告要學(xué)生再“多想一點”,即其他可能存在的求解方法,該設(shè)計的優(yōu)缺點,如何提高時間空間性能等問題。通過總結(jié),學(xué)生對問題有了更加深入全面的理解。

3 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)專業(yè)的重要基礎(chǔ)課程之一,對學(xué)生軟件開發(fā)的過程和習(xí)慣的培養(yǎng)是至關(guān)重要的。在教學(xué)過程中應(yīng)該把面向?qū)ο蟮乃枷肴谌脒M(jìn)去,用類和模板的形式描述數(shù)據(jù)結(jié)構(gòu),讓學(xué)生適應(yīng)快速發(fā)展的軟件開發(fā)技術(shù)。從4個方面討論了如何進(jìn)行面向?qū)ο蠡臄?shù)據(jù)結(jié)構(gòu)教學(xué),在我院經(jīng)過實踐,通過2個學(xué)期的教學(xué),從效果上來看,比前幾屆學(xué)生的動手能力、學(xué)習(xí)積極性上均有了明顯提高,絕大部分的同學(xué)都能順利完成課程設(shè)計并獲得較好成績。

[1] 李睿,林亞平.做中學(xué)—面向?qū)ο蟪绦蛟O(shè)計與數(shù)據(jù)結(jié)構(gòu)課程一體化研究[J].計算機(jī)教育,2008,16：151～152

[2] 馮莉.用OOP探討數(shù)據(jù)結(jié)構(gòu)的教學(xué)思想和方法[J].襄樊學(xué)院學(xué)報,2008,29(8)：74～77

[3] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：清華大學(xué)出版社,2002

Discussion and practice on data structure by object-oriented teaching method

Xu Chong, Xu Jian
Hangzhou dianzi university, Hangzhou, 310018, China

2010-12-16 稿件編號：1012090

徐翀，碩士，講師。徐建，博士，副教授。

杭州電子科技大學(xué)高教科研項目(編號:ZC1017)。