復雜算法的案例教學設計

柳欣 張斌 張波

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

關鍵詞： 數(shù)據(jù)結構; 二叉樹; 案例教學法; 圖解教學法; 對比教學法

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

1 以“求二叉樹寬度”為主題的案例教學設計方案

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

1.1 問題界定與資料獲取

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

1.2 案例構建

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

1.2.1 背景信息

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

1.2.2 案例正文

⑴ 需求討論

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

⑵ 情境分析

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

⑶ 過程描述

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

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

② 分析討論。首先復習層次遍歷算法，然后討論當前問題與層次遍歷之間的關系，得出明確的技術路線。

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

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

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

⑤ 其他解法介紹及比較。我們通過對一道算法閱讀題進行修改，得到另一種解法（以下稱算法2），將其作為對上述案例的補充。算法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所示），最終明確關鍵局部變量Width， LastWidth， CurrWidth的設置是算法2的最大亮點。其中，Width用于存儲迄今為止所發(fā)現(xiàn)的“結點數(shù)量最多”一層的結點數(shù)。LastWidth表示當前層中尚未訪問的結點數(shù)。當對于某一層的遍歷結束而即將進入下一層時，CurrWidth表示下一層中待訪問的結點數(shù)。

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

⑷ 結果呈現(xiàn)

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

1.2.3 問題設計

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

1.2.4 使用說明

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

1.3 案例應用

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

2 結束語

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

參考文獻（References）：

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

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

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

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

[5] 王道論壇組編.2019年數(shù)據(jù)結構考研復習指導[M].北京：電子工業(yè)出版社，2018

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