復(fù)雜算法的案例教學(xué)設(shè)計

柳欣 張斌 張波

摘? 要： 當(dāng)前，將案例教學(xué)運(yùn)用于數(shù)據(jù)結(jié)構(gòu)教學(xué)的研究尚存在設(shè)計過程不詳細(xì)、缺少針對問題設(shè)置的分析、教學(xué)案例簡單等不足。為此，提出面向復(fù)雜算法的案例教學(xué)設(shè)計方案。新方案符合“問題界定-數(shù)據(jù)獲取-案例構(gòu)建-案例應(yīng)用”的四階段教學(xué)案例開發(fā)框架。為了實現(xiàn)多個遞進(jìn)的能力培養(yǎng)教學(xué)目標(biāo)，在教學(xué)過程的各環(huán)節(jié)設(shè)置了引導(dǎo)性、分析性和開放性問題。此外，還討論了圖解教學(xué)法和對比教學(xué)法在案例教學(xué)過程中的綜合運(yùn)用。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu); 二叉樹; 案例教學(xué)法; 圖解教學(xué)法; 對比教學(xué)法

中圖分類號：G642? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? 文章編號：1006-8228（2020）02-109-04

A case teaching design scheme for complex algorithms

Liu Xin1，2， Zhang Bin1，2， Zhang Bo3

（1. School of Information Engineering， Shandong Youth University of Political Science， Jinan， Shandong 250013， China;

2. Key Laboratory of Information Security and Intelligent Control in Universities of Shandong （Shandong Youth University of Political Science）;

3. School of Information Science and Engineering， University of Jinan）

Abstract： At present， there are still many shortcomings in the research on the case teaching for data structure course， which are mainly manifested in the following aspects， such as the lack of a detailed design process， the absence of analysis of the raising of problem， the adoption of simple teaching cases， and etc. To solve these problems， a case teaching design scheme for complex algorithms is proposed. The new scheme conforms to the four-stage teaching case development framework of “problem definition， data acquisition， case construction and case application”. In order to achieve the teaching objective of multiple progressive ability building， analytical and open questions are designed in all aspects of the teaching process. In addition， the comprehensive application of graphic teaching method and comparative teaching method is also discussed.

Key words： data structure; binary tree; case teaching method; graphical teaching method; comparative teaching method

0 引言

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)與技術(shù)專業(yè)的核心專業(yè)基礎(chǔ)課程。該課程在計算機(jī)學(xué)科中處于承上啟下的核心地位，且可視為信息處理、人工智能、數(shù)據(jù)庫等課程的重要基礎(chǔ)[1]。該課程有理論性強(qiáng)、算法執(zhí)行過程抽象等特點，使得傳統(tǒng)教學(xué)方式難以取得理想效果。為此，許多院校在課程教學(xué)中引入了案例教學(xué)法。譚定英等人[2]以“哈夫曼算法的應(yīng)用”為例介紹了案例教學(xué)的實施過程。鄭馨等人[3]設(shè)計了基于貪吃蛇游戲的案例，且要求學(xué)生分別利用四種存儲結(jié)構(gòu)來實現(xiàn)。我們認(rèn)為已有研究成果尚存在以下不足：①所提供的教學(xué)案例主題較為簡單，或者設(shè)計過程不夠詳細(xì);②缺少問題設(shè)置舉例以及必要性分析;③教學(xué)手段較為單一，缺少與其他教學(xué)方法的配合;④案例教學(xué)實施步驟并不一致，也缺乏有關(guān)案例開發(fā)的基本框架等規(guī)律性問題的總結(jié)與分析;⑤缺少圍繞具有一定難度的高級主題（如復(fù)雜算法）進(jìn)行案例教學(xué)設(shè)計的討論，無法提升學(xué)生的思維層次，不能滿足創(chuàng)新思維培養(yǎng)的教學(xué)需要。

1 以“求二叉樹寬度”為主題的案例教學(xué)設(shè)計方案

我們選取二叉樹算法教學(xué)中的高級主題——“求二叉樹寬度”問題進(jìn)行教學(xué)案例設(shè)計，且設(shè)計過程遵循錢明輝等人[4]的“問題界定-數(shù)據(jù)獲取-案例構(gòu)建-案例應(yīng)用”四階段教學(xué)案例開發(fā)框架。新的教學(xué)案例設(shè)計可視為該框架在工程實踐類問題教學(xué)方面的具體應(yīng)用。

1.1 問題界定與資料獲取

樹型結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)課程的核心內(nèi)容，并且涉多個基于二叉樹的復(fù)雜算法。本案例的研究對象是“求二叉樹寬度”的算法設(shè)計問題，該問題本身屬于二叉樹層次遍歷算法（簡稱層次遍歷算法）的應(yīng)用范疇。本案例需要研究的問題是：通過詳細(xì)分析算法設(shè)計的過程，使學(xué)生理解并掌握借助層次遍歷求二叉樹寬度的技術(shù)，進(jìn)而領(lǐng)會層次遍歷算法的高級應(yīng)用。同時掌握根據(jù)現(xiàn)實應(yīng)用需要為算法選擇合適存儲結(jié)構(gòu)的方法。本案例的內(nèi)容來自于權(quán)威考研復(fù)習(xí)教材和在考研答疑過程中收集到的歷年考研復(fù)習(xí)題目。

1.2 案例構(gòu)建

以下我們從背景信息、案例正文、問題設(shè)計和使用說明四個方面來詳細(xì)設(shè)計。

1.2.1 背景信息

問題提出的背景是解決課程中有關(guān)層次遍歷算法具體應(yīng)用的教學(xué)難點問題。案例選擇的背景是為了求二叉樹的寬度，需要在執(zhí)行過程和底層存儲結(jié)構(gòu)層面對層次遍歷算法做出擴(kuò)展。其理論依據(jù)是層次遍歷算法、二叉鏈表存儲結(jié)構(gòu)、順序隊列存儲結(jié)構(gòu)的入隊和出隊操作。案例選擇依據(jù)是求二叉樹寬度的算法是層次遍歷算法的重要應(yīng)用。

1.2.2 案例正文

⑴ 需求討論

二叉樹T的寬度定義為：當(dāng)T為空時，寬度為0;當(dāng)T為非空時，取結(jié)點數(shù)最多的那層結(jié)點數(shù)作為T的寬度。需要解決的問題是設(shè)計求T寬度的算法。盡管可以利用層次遍歷算法對T進(jìn)行掃描，并且記錄每層的結(jié)點數(shù)。但是，層次遍歷算法將二叉樹視為整體，并未在層次切換時進(jìn)行停頓或做出判定。主要困難是如何在每層掃描開始時重新進(jìn)行結(jié)點計數(shù)，并且在層次切換之前將本層結(jié)點數(shù)與此前遇到的最大層次結(jié)點數(shù)進(jìn)行比較。

⑵ 情境分析

盡管利用層次遍歷算法無法求出二叉樹的寬度，但是求二叉樹寬度的過程一定蘊(yùn)含著層次遍歷算法的執(zhí)行框架。同時，層次遍歷算法的底層存儲結(jié)構(gòu)為順序?；蜴?zhǔn)綏?。該結(jié)構(gòu)同樣為求二叉樹寬度提供了必要的結(jié)點信息。由此可見，為了求二叉樹的寬度，需要修改層次遍歷算法，使其在進(jìn)行層次切換之前將結(jié)點的層號加1。同時，通過擴(kuò)展底層存儲結(jié)構(gòu)，使得能算法在掃描過程中將結(jié)點的層號寫入底層存儲結(jié)構(gòu)，從而為今后通過二次掃描求出二叉樹的寬度奠定基礎(chǔ)。

⑶ 過程描述

案例教學(xué)過程分以下步驟具體展開。

① 問題引入。通過該環(huán)節(jié)，引入二叉樹寬度的定義。

② 分析討論。首先復(fù)習(xí)層次遍歷算法，然后討論當(dāng)前問題與層次遍歷之間的關(guān)系，得出明確的技術(shù)路線。

③ 底層存儲結(jié)構(gòu)的遴選與擴(kuò)展。我們選擇順序隊列作為層次遍歷算法的存儲結(jié)構(gòu)。為了保存結(jié)點的層次編號，需要在順序隊列的結(jié)構(gòu)體定義中增加成員數(shù)組level[][5]。

④ 算法執(zhí)行過程的圖解展示。為了可視化地展示教師的思維，我們采用特定的二叉樹作為實例，并且以邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)相結(jié)合的方式展示算法的執(zhí)行過程。假設(shè)有一棵基于二叉鏈表結(jié)構(gòu)的二叉樹，且根結(jié)點指針為b。該二叉樹含有6個結(jié)點，且結(jié)點B，C，…，F(xiàn)的指針分別表示為pB，pC，…，pF。算法的執(zhí)行過程分為兩個階段。在第一階段，算法執(zhí)行層次遍歷，并且將所訪問結(jié)點的指針和層次編號保存至隊列。圖1展示了算法在“層次遍歷結(jié)束后”的情景（左圖是基于存儲結(jié)構(gòu)的展示，右圖是基于邏輯結(jié)構(gòu)的展示）。

在第二階段，利用雙重while循環(huán)對底層隊列的成員數(shù)組Qu.level[]進(jìn)行“從左至右”的掃描。通過該過程，確定具有最大結(jié)點數(shù)的層次，而該層的結(jié)點數(shù)就是二叉樹的寬度。

⑤ 其他解法介紹及比較。我們通過對一道算法閱讀題進(jìn)行修改，得到另一種解法（以下稱算法2），將其作為對上述案例的補(bǔ)充。算法2的主要代碼如下所示。

[ InitQueue（Q）;EnQueue（Q，bt）;

Width=1;LastWidth=1;CurrWidth=0;

while（Empty（Q）！=0）{

while（LastWidth！=0）{

DlQueue（Q，p）;visit（p->data）;

if（p->lchild）{EnQueue（Q，p->lchild）;CurrWidth++;}

if（p->rchild）{EnQueue（Q，p->rchild）;CurrWidth++;}

if（CurrWidth>Width）Width=CurrWidth;

LastWidth--;? ? }

LastWidth=CurrWidth;CurrWidth=0;} ]

通過必要的注釋以及圖解（如圖2所示），最終明確關(guān)鍵局部變量Width， LastWidth， CurrWidth的設(shè)置是算法2的最大亮點。其中，Width用于存儲迄今為止所發(fā)現(xiàn)的“結(jié)點數(shù)量最多”一層的結(jié)點數(shù)。LastWidth表示當(dāng)前層中尚未訪問的結(jié)點數(shù)。當(dāng)對于某一層的遍歷結(jié)束而即將進(jìn)入下一層時，CurrWidth表示下一層中待訪問的結(jié)點數(shù)。

⑥ 課后思考與拓展練習(xí)。教師布置課后思考題，從而鞏固課堂教學(xué)效果。

⑷ 結(jié)果呈現(xiàn)

除了培養(yǎng)學(xué)生算法設(shè)計和算法閱讀能力之外，我們的另一個目標(biāo)是通過引入對比教學(xué)法，加深學(xué)生對于兩個算法核心設(shè)計思想的理解。具體做法是，教師從存儲結(jié)構(gòu)、算法執(zhí)行、算法設(shè)計技巧和底層隊列結(jié)構(gòu)操作的角度進(jìn)行示范對比（如表1所示），引導(dǎo)學(xué)生深入思考，進(jìn)而潛移默化地影響學(xué)生的思維方式。

1.2.3 問題設(shè)計

為了在案例教學(xué)過程中創(chuàng)設(shè)情境、鼓勵學(xué)生積極思考，以及引導(dǎo)討論的方向，我們在過程描述部分各步驟中設(shè)置了多個問題（如表2）。同時要求這些問題涵蓋引導(dǎo)性、分析性和開放性三種類型[6]。其中，引導(dǎo)性問題旨在引導(dǎo)學(xué)生回顧知識，促進(jìn)達(dá)成理解與掌握知識的能力培養(yǎng)目標(biāo);分析性問題旨在培養(yǎng)學(xué)生設(shè)計和分析算法的能力;開放性問題旨在培養(yǎng)創(chuàng)新思維，形成解決實際問題的能力。

1.2.4 使用說明

本案例的適用對象是計算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生。適用課程是數(shù)據(jù)結(jié)構(gòu)及后續(xù)進(jìn)階類課程。問題設(shè)計圍繞對層次遍歷算法的擴(kuò)展而展開，使學(xué)生理解并掌握相關(guān)擴(kuò)展技術(shù)。

1.3 案例應(yīng)用

首先，明確教學(xué)目標(biāo)及所含知識點。然后，針對每一個知識點，從案例情節(jié)、分析思路和理論依據(jù)的角度進(jìn)行流程設(shè)計，從而實現(xiàn)教學(xué)目標(biāo)。限于篇幅，省略了具體的流程設(shè)計。

2 結(jié)束語

本文研究了在數(shù)據(jù)結(jié)構(gòu)課程中教師圍繞復(fù)雜算法進(jìn)行案例教學(xué)設(shè)計的問題。在案例教學(xué)實施過程中，始終遵循以問題為導(dǎo)向的原則，以掌握知識、培養(yǎng)算法設(shè)計與分析的能力和解決實際問題的能力為逐級遞進(jìn)的目標(biāo)，在教學(xué)過程的各個階段，精心設(shè)置有針對性的問題。通過將圖解教學(xué)法和對比教學(xué)法融合于案例教學(xué)過程，實現(xiàn)了直觀展示教師思維和影響學(xué)生思維方式的效果。本文案例的特點是講授兩個復(fù)雜算法，它們分別側(cè)重于對算法的設(shè)計能力和閱讀能力的培養(yǎng)。通過對算法進(jìn)行多角度的對比，有利于促進(jìn)學(xué)生思維方式的提升與鍛造。

參考文獻(xiàn)（References）：

[1] 張銘，耿國華，陳衛(wèi)衛(wèi)，等.數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)實施方案[J].中國大學(xué)教學(xué)，2011.3：56-60

[2] 譚定英，陳平平，劉慧玲.以問題為中心的案例教學(xué)法在數(shù)據(jù)結(jié)構(gòu)與算法課程中的應(yīng)用[J].計算機(jī)教育，2013.12：50-53

[3] 鄭馨，江克勤，程玉勝.貪吃蛇游戲在線性數(shù)據(jù)結(jié)構(gòu)中的案例教學(xué)[J].安慶師范大學(xué)學(xué)報（自然科學(xué)版），2018.24（4）：117-119，128

[4] 錢明輝，李天明，舒詩雅，等.教學(xué)案例開發(fā)框架模型的構(gòu)建及其應(yīng)用[J].管理案例研究與評論，2018.11（2）：210-220

[5] 王道論壇組編.2019年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)[M].北京：電子工業(yè)出版社，2018

[6] 嚴(yán)玲，陳雨薇，鄧嬌嬌.以問題為導(dǎo)向的工作坊實踐教學(xué)實施方式研究[J].現(xiàn)代大學(xué)教育，2016.5：94-103