柳欣 張斌 張波

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

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

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

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

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

1.1 問(wèn)題界定與資料獲取

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

1.2 案例構(gòu)建

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

1.2.1 背景信息

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

1.2.2 案例正文

⑴ 需求討論

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

⑵ 情境分析

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

⑶ 過(guò)程描述

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

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

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

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

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

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

⑤ 其他解法介紹及比較。我們通過(guò)對(duì)一道算法閱讀題進(jìn)行修改，得到另一種解法（以下稱算法2），將其作為對(duì)上述案例的補(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;} ]

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

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

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

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

1.2.3 問(wèn)題設(shè)計(jì)

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

1.2.4 使用說(shuō)明

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

1.3 案例應(yīng)用

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

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

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

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

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

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

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

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

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

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