鹿旸++刁明光

摘要：分析了“數(shù)據結構”課程的特點、經典算法的教學和實踐現(xiàn)狀，針對存在的問題，以改進經典算法講解為基礎，討論了如何培養(yǎng)學生的編程思維，并進一步探討了實踐教學的組織和設計。

關鍵詞：數(shù)據結構；經典算法；編程思維

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2017）37-0136-02

“數(shù)據結構”是計算機專業(yè)的一門核心課程。該課程不僅是程序設計的基礎，而且是設計和實現(xiàn)編譯原理、操作系統(tǒng)、數(shù)據庫系統(tǒng)等系統(tǒng)程序和大型應用程序的重要基礎[1]。數(shù)據結構教材以數(shù)據的邏輯結構為主線，依次介紹線性結構和非線性結構。在各種數(shù)據結構介紹時再討論其存儲結構以及相關算法，最后介紹查找和排序算法，知識框架體系完善清晰[2]。教學的突出難點是知識的抽象性和動態(tài)性，尤其涉及大量抽象數(shù)據類型及經典算法。本文是作者九年來的授課小結，從教學方法和經典算法的講解方法入手，進行了教學和實踐的探討。

一、傳統(tǒng)教學方法存在的問題

1.缺乏良好的解題習慣。課程的教學要求之一是訓練學生進行復雜程序設計的技能和培養(yǎng)良好程序設計的習慣，其重要程度決不亞于知識傳授。在學習數(shù)據結構之前，學生學習了C和C++兩門編程語言，但沒有進行系統(tǒng)的訓練，也沒有形成規(guī)范的編程習慣。很多同學拿到題目直接編寫代碼，在寫代碼的過程中邊寫邊想，然后反復修改代碼，造成程序結構混亂、可讀性差、調試困難。尤其在解決大規(guī)模輸入的復雜問題時，更容易造成程序癱瘓。

2.課堂算法講解不透徹。在課程中，各種數(shù)據結構都有相關算法，此外還有查找和排序算法。因此，算法部分占了課程相當大的比例。這其中很多經典算法都極具代表性，使用了大量的編程技巧，這些是算法的精華部分。如果授課教師只對書中的算法進行流程講解，不揭示編程技巧的話，那么學生也只能死記硬背，學習不到算法的精華，對提高編程能力毫無幫助。而且死記硬背的方式也容易讓學生喪失學習的興趣。

3.缺少綜合性實驗題目。通常練習冊中會按照章節(jié)安排實驗題目，題目內容針對本章知識點，針對性強，而且和書上的例題有相似之處。因此，學生在做這些分章節(jié)的小程序時，過度依賴課本中的范例，甚至不假思索，照搬照抄，編程思維得不到很好的鍛煉，而且也體會不到處理大規(guī)模輸入的復雜問題時，數(shù)據結構體現(xiàn)出來的優(yōu)勢。

二、教學方法探索

1.培養(yǎng)良好的分析問題的習慣。如圖1所示，遇到問題時，學生習慣性地直接編碼，并在代碼上不斷修改，沒有良好的編程習慣，往往解決問題事倍功半。在授課過程中，對每一個問題，教師要嚴格按照“抽象數(shù)據對象→分析邏輯關系→選取物理結構→分析解題思路→畫流程圖→分析時間復雜度→多種解法比較→確定解題方案→編寫代碼（可省略）”[3]的思路進行分析和講解，最終完成算法。其中，在“選取物理結構”環(huán)節(jié)，要充分分析操作特征，設計合理的存儲結構服務于后續(xù)算法。在“分析解題思路”和“畫流程圖”環(huán)節(jié)，首先提煉解題步驟，形成流程圖，然后使用編程技巧優(yōu)化流程，重點優(yōu)化循環(huán)結構，并逐步修改流程圖，最終確定。在分析過程中，應啟發(fā)學生的解題思路，鼓勵大家多角度分析問題，提出不同的解決方案，并應一并列出，逐一分析解題步驟和時間復雜度，最后做一比較。這樣，將編程思維從課堂的講授延伸至實踐環(huán)節(jié)的動手操作，鞏固了學習效果。這樣學生不僅對算法印象深刻，更能培養(yǎng)良好的思維習慣，從而真正提高解決問題的能力。

2.強調經典算法中的編程技巧。書中選用算法多為經典算法，其中不乏經過多次優(yōu)化、多次驗證的高效率算法。這些算法在優(yōu)化過程中使用了很多編程技巧。教師在授課過程中，應重點介紹算法的優(yōu)化方法，并引導學生對程序進行自查和優(yōu)化，養(yǎng)成良好的習慣[4]。

以冒泡排序經典算法為例，首先講解算法的思想“依次比較兩兩相鄰記錄，若反序，則交換位置，直至有序”。并且舉例動態(tài)演示。然后讓同學嘗試將操作流程轉換成算法。要求同學設計出流程圖，如果課堂上有條件可以編程序實現(xiàn)。然后選取同學的例子做展示，有如圖2所示算法。

本算法中有兩個循環(huán)結構，應逐個解析。第一個循環(huán)結構表示算法經過n-1趟完成排序，通過舉反例，說明根據輸入數(shù)列不同，排序趟數(shù)也不同，最少一趟就能完成排序，顯然第一個循環(huán)存在冗余。然后引導學生一起改進算法，此循環(huán)要解決的是“結束狀態(tài)”的判定問題，引出編程技巧“狀態(tài)判定問題，通過操作特征找條件”。根據算法的“比較”和“交換”操作特征，分析得出“結束條件”為：經過一趟排序，如果沒有發(fā)生交換操作，就說明已經有序，結束算法。經改進后的第一個循環(huán)如圖3所示。同樣，第二個循環(huán)結構也存在冗余。通過分析，引出編程技巧“范圍劃定問題，通過操作特征找邊界”。經編程技巧優(yōu)化后的程序如圖4所示。最后，比較改進前和改進后算法的時間復雜度，然后給定一個輸入數(shù)列，比較兩個算法的實際運行時間。結果顯示，雖然沒有改變算法的時間復雜度，但通過剔除冗余循環(huán)，縮減了算法的運行時間，提高了執(zhí)行效率。通過對學生程序的優(yōu)化和實驗測試，學生能夠直觀地認識到使用編程技巧的好處，且印象深刻。

類似的例子還有在順序查找算法中，通過使用監(jiān)視哨，簡化while循環(huán)判定條件的編程技巧；線性表GetElem算法中，合并兩個并列循環(huán)的編程技巧等等。配合編程技巧的講解，在實踐環(huán)節(jié)設置題目，進一步強化這些技巧的使用，使學生熟練掌握。學生學習算法的目的是要學會其中的編程技巧，活學活用，這樣才能寫出高效、優(yōu)質的算法。

3.設置綜合型題目。教師應適當設置包含多個知識點且有多種解法的題目，鍛煉學生綜合運用知識解決問題的能力，并給學生留出發(fā)揮創(chuàng)造力的空間。例如“走迷宮問題”，對已知的二維迷宮求通路。學生可以選擇用不同的數(shù)據結構表示迷宮作為程序輸入，然后選擇用深度優(yōu)先或者廣度優(yōu)先遍歷的算法來得到路徑，最后用圖形界面將迷宮顯示出來。再例如“最少換乘次數(shù)”問題，已知地點和公交線路，求某兩地點間的最少換乘次數(shù)。學生需要在問題中抽象出適當?shù)膶ο蠛完P系，將地點和線路表示在圖形結構中，然后可以選擇圖的廣度優(yōu)先遍歷方法，或者改進求單源最短路徑的Dijkstra算法，比較它們，選擇更優(yōu)算法。

在實踐環(huán)節(jié)，可以將學生分為若干個團隊，團隊成員要按照規(guī)范的解題思路提出個人的見解，而后互相比較和討論，最終擇優(yōu)給出完整的解題步驟和算法。這樣，學生在充分的討論過程中，會比較存儲結構的差異和不同算法的性能，進一步鞏固了書本知識，鞏固編程技巧，同時鍛煉了團隊合作能力。

“數(shù)據結構”課程在計算機學科中的地位十分重要，教師在教學過程中應著力培養(yǎng)學生分析和解決問題的能力。這需要教師在授課和實踐環(huán)節(jié)加強編程思維的訓練，并不斷督促，完善自己的教學方法，以達到更優(yōu)的教學質量。

參考文獻：

[1]陳越，何欽銘，馮雁.“數(shù)據結構”綜合性課程設計教學探索與實踐[J].計算機教育，2008，（08）：54-55.

[2]張銘，趙海燕，王騰蛟.北京大學“數(shù)據結構與算法”教學設計[J].計算機教育，2008，（20）：5-11.

[3]孟凡榮，張斌，楊雷.計算思維在數(shù)據結構中的實踐探索[J].教育教學論壇，2015，（10）：117-120.

[4]張乃孝.數(shù)據結構體系分析[J].計算機研究與發(fā)展，1988，（05）：36-40.endprint