章麗玲

（湖北第二師范學院 計算機學院，武漢 430205）

1 引言

當前，新工科教育已成為教育界的熱門話題。新工科教育的核心是培養(yǎng)面向新興產(chǎn)業(yè)和新經(jīng)濟需求的工程實踐能力強、創(chuàng)新能力強，能夠解決復雜工程應用問題且具備國際競爭力的高素質(zhì)復合型“新工科人才”。[1]程序設計能力是新興產(chǎn)業(yè)如人工智能、大數(shù)據(jù)等的核心能力，它是衡量計算機類專業(yè)學生必備的基礎技能，是檢驗計算機相關專業(yè)畢業(yè)生質(zhì)量的重要標準。[2]如何培養(yǎng)具備解決復雜問題的程序設計能力的新工科人才，是目前高校計算機專業(yè)教學改革的重點和難點。

數(shù)據(jù)結(jié)構(gòu)是計算機及相關專業(yè)的專業(yè)基礎課，在整個課程教育體系中起到奠基的作用。該課程學習的好壞直接影響學生的程序設計水平和編程實踐能力，并對后續(xù)課程的學習產(chǎn)生深遠的影響。[3]然而數(shù)據(jù)結(jié)構(gòu)課程的特點是知識點多，算法抽象不易理解，大多數(shù)學生對數(shù)據(jù)結(jié)構(gòu)的學習有畏難情緒，導致學生學習的信心和動力不足。本文構(gòu)建以學生為中心，以教師為主導的啟發(fā)式教學。[4]通過教學設計，采用“讀、仿、改、創(chuàng)”的模式，由淺入深進階式引導學生掌握數(shù)據(jù)結(jié)構(gòu)相關算法。為了激發(fā)學生學習興趣和學習動力，在教學過程中，精心設計教學問題，引導學生主動思考。通過思路引導、舉一反三等方式，讓學生真正吃透算法，并能靈活運用算法，做到“授人以漁”。

2 教學設計

傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)課程看重算法思路的講解，算法大多以偽代碼的形式描述，[5]對學生是否能夠編程實踐通過沒有要求，導致學生只懂算法原理，不能學以致用，更不能基于某個算法進行擴展。最好的辦法是設計符合學生認知規(guī)律的方式來組織教學，由淺入深進階式引導學生掌握數(shù)據(jù)結(jié)構(gòu)核心原理與算法。本文設計的啟發(fā)式教學模型如圖1所示，模型中“讀、仿、改、創(chuàng)”四階段圍繞提高程序設計能力這個目標進行。四階段內(nèi)容相輔相成，互為前提，形成教學閉環(huán)。讀：讀懂程序代碼，分析算法的時間復雜度、空間復雜度。仿：模仿，仿照，在讀懂源程序的基礎上，能夠模仿編寫相似的程序，做到觸類旁通、舉一反三。改：改寫，是在模仿程序的基礎上，能夠完成相似算法的擴展，提高算法的應用。創(chuàng)：創(chuàng)造，創(chuàng)新，是在改寫的基礎上，有所領悟，思維升華。由于代碼是靜止的，程序只有運行才有生命。因此，在教學過程中，采用程序驅(qū)動的方式[6]，要求學生對每一個算法都能編程實踐通過，理論聯(lián)系實際，才能真正提高學生的程序設計能力。

圖1 啟發(fā)式教學模型

3 教學實踐

現(xiàn)以順序表的應用舉例說明。順序表，顧名思義是采用順序存儲結(jié)構(gòu)，而順序存儲結(jié)構(gòu)的主要特征是，所有的元素按照其邏輯順序依次存儲到對應指定存儲位置開始的一塊連續(xù)的存儲空間中，[7]最大的優(yōu)點是可以隨機存儲；缺點是為了保證其邏輯順序不變，在插入、刪除等操作的時候，往往伴隨大量的移動操作，如果移動操作頻繁，往往會降低程序效率。因此，在講解順序表的應用的時候，需要跟學生講透徹——提高順序表算法效率的核心因素，是盡量地減少移動操作。

實例：請設計一個盡可能高效的算法，按要求將順序表分成兩部分，即以順序表L 第一個元素為分界線（基準），將所有大于等于它的元素移到該基準的后面，將所有小于它的元素移到基準的前面。[7]假設元素類型ElemType為int整形，算法要求如圖2所示：

圖2 算法要求示意圖

針對這個實例，老師首先提問：“請問，能否用‘重建法’實現(xiàn)，為什么呢？”引導學生思考。根據(jù)學生的回答情況，老師對“重建法”的特點給出總結(jié)，解析為什么不能用“重建法”的原因。由于算法要求盡可能高效，要求算法的時間復雜度和空間復雜度盡可能低，而重建法，其核心思路是采用賦值的方法按要求將數(shù)據(jù)拷貝到一個新的順序表中，因其空間復雜度為O（n），不符合高效算法的要求，接著給出高效算法思路。為了提高效率，減少移動操作，引入兩個偽指針i和j。i指向順序表的第一個元素，j指向順序表的最后一個元素。以第一個元素為基準，j從右向左找一個小于等于基準的元素x，i從左向右找一個大于基準的元素，將兩者交換，直到i大于或等于j。

3.1 讀算法

引導學生認真讀算法的每一條語句，理解算法的設計思路、算法的邏輯執(zhí)行步驟，分析算法的時間復雜度、空間復雜度。算法的代碼如下：

通讀上面的算法，理解算法的思路。該算法首先把基準元素L-＞data[0]保存到臨時變量tmp中，然后給兩個偽指針i，j附初值，i=0。i的初始值為順序表的最小下標，j=L-＞length-1，j的初始值為順序表的最大下標，j從右向左找一個小于基準元素，i從左向右找一個大于基準的元素，然后將兩個元素交換，直到i＜j為假，循環(huán)結(jié)束。將L-＞data[0]與L-＞data[i]交換，通過分析，該算法的時間復雜度為O（n），空間復雜度為O（1），性能優(yōu)于重建法。為了提高學生的編程能力，要求學生在DevC++編程環(huán)境中，在main（）函數(shù)調(diào)用該算法，并給出相關的數(shù)據(jù)實例測試通過，測試數(shù)據(jù)為：3 8 2 7 1 5 3 4 6 0。測試顯示運行結(jié)果如下圖3所示：

圖3 實例1運行結(jié)果

3.2 仿算法

通過讀算法，學生能夠理解算法的思路，但還不會靈活運用。因此，第二步就是引導學生模仿算法，即在原算法的基礎上作很小的擴充調(diào)整，目的是指導學生能夠?qū)λ惴ㄋ悸愤M行靈活運用，做到舉一反三。

調(diào)整一。如果把題目的要求改為：將所有的奇數(shù)移動到偶數(shù)之前。調(diào)整后，編程的整體思路不變，同樣設置兩個偽指針i，j。j的初始值為順序表的最大下標，j從右向左找一個奇數(shù)元素；i的初始值為順序表的最小下標，i從左向右找一個偶數(shù)元素，然后將兩個元素交換，直到i＜j。算法的整體框架不變，無需設置臨時變量tmp，只需要將判斷條件改為判斷是奇數(shù)還是偶數(shù)即可。修改部分的代碼如下：

同樣要求學生通過DevC++編程環(huán)境編譯通過，給出盡量多的測試用例測試通過。

舉一反三。可以把基準設計為任何整數(shù)x，不再固定為順序表的第一個元素，也不固定為奇數(shù)或偶數(shù)。如要求學生調(diào)整算法使所有小于x（任意值）的元素放在所有大于等于x 的元素的前面，按照實際的要求將順序表分為兩部分。通過仿算法，學生可以掌握類似相似的問題，發(fā)散了學生編程思維，提高學生編程實踐能力。

3.3 改算法

原算法的思路只涉及到將一個順序表拆分為兩個部分，如果把算法要求改為將順序表拆分為符合條件的三部分，引導學生思考。如何修改算法才能實現(xiàn)呢？以荷蘭國旗問題為例：設有一個條塊序列，每個條塊為紅（0）、白（1）、藍（2）三種顏色中的一種。[8]設計一個盡可能高效的算法，使得這些條塊即按紅、白、藍的順序排成荷蘭國旗圖案，假設該序列采用順序表存儲。

思路引導。拆分兩部分需要用2個偽指針，那么拆分三部分需要3個偽指針，用不同的偽指針指向不同的區(qū)間，偽指針i，j，k。初始的時候，i=-1，j=0，k=L-＞length。將0～i 表示0 區(qū)間（紅色），k～n-1 表示2 區(qū)間（藍色），中間部分為1區(qū)間（白色）。i和j指針從左往右移，k指針從右往左移，指針j從頭開始掃描順序表L中的所有元素。針對j所指向的元素，如果j指向元素0：說明它屬于前部，i增1（擴大0元素區(qū)間），將i、j位置的元素交換，j++。j指向元素2：說明它屬于后部，k減1（擴大2元素區(qū)間），將j、k位置的元素交換，此時j位置的元素可能還要交換到前部，所以j不前進。j指向元素1：說明它屬于中部，保持不動，j++。

程序代碼如下：

思路擴展?？梢詫⒑商m國旗問題擴充到任一順序表，按照一定的條件將順序表劃分三個區(qū)間，而不是固定為相同的元素。解決的思路與上面類似，程序的框架不變，只需要修改中間的判斷條件即可。

舉一反三。問題：就地循環(huán)位移，設將n（n＞1）個整數(shù)存放在一維數(shù)組R中。設計僅用O（1）輔助空間，將數(shù)組R 中保存的序列循環(huán)左移p（0＜p＜n）個位置，即將R 中的數(shù)據(jù)由（X0，X1…..Xn-1）變換為（Xp，Xp+1，…..Xn-1，X0，X1，……Xp-1）。

由于要求O（1）的輔助空間，因此仍然不能用“重建法”，需要引導學生如何減少移動的操作。

算法思路如下：

1：將數(shù)組R（X0，X1…，Xn-1）看成順序表，將其分成兩部分（X0，X1，……，Xp-1）和（Xp，Xp+1，…..，Xn-1）。

2：分別對這兩部分中的元素進行原地逆置，中間結(jié)果為（Xp-1，Xp-2，......X1，X0），（Xn-1，Xn-2，......Xp-1，Xp）

3：再對整個數(shù)組進行逆置，最終實現(xiàn)算法要求，結(jié)果為（Xp，Xp+1，…..Xn-1，X0，X1……Xp-1）。

該題思路的核心是數(shù)組逆置，而數(shù)組逆置算法同樣可以采用上面類似的順序表的算法思路，即設計兩個偽指針i，j，i的初始值為數(shù)組的起始下標，j的初始值為數(shù)組的最大下標，i和j對應的元素循環(huán)交換，i從左往右移，j從右往左移，循環(huán)條件為i＜j。詳細代碼如下：

最后同樣需要在編程環(huán)境中實現(xiàn)通過。

分析該算法的時間復雜度為O（n），空間復雜度為O（1），屬于高效的算法。

3.4 創(chuàng)新

在前面讀、仿、改的基礎上，最后的目標是引導學生對所學到的和所領悟的知識進行歸納和總結(jié)，形成自己的知識體系，并且能夠在所悟的基礎上進行創(chuàng)新，提高自己的思維創(chuàng)新能力。如上文讀的實例中，引導學生進一步優(yōu)化算法，讀算法中調(diào)用了交換函數(shù)，而一次交換函數(shù)，需要執(zhí)行3 次賦值操作，能否直接賦值呢？要求學生回答，而結(jié)果肯定是可以的，因為基準已經(jīng)暫存在臨時變量tmp中，可以采用賦值語句，從而進一步提高運行效率。代碼修改非常簡單，只需將while循環(huán)體內(nèi)部改為下面的代碼即可。

改進后算法的思路其實就是經(jīng)典算法“快速排序”的一趟劃分過程。[9]如果需要對n個元素的順序表進行遞增排序，需要對產(chǎn)生的兩部分分別重復上述過程，這就是典型的遞歸的分而治之的思想，即將大的問題分解為兩個相似的小問題，直到每個小問題內(nèi)只有一個元素或空為止。簡而言之，每趟使表的第一個元素放入適當?shù)奈恢?，將表劃分為兩個子表，對子表按遞歸方式繼續(xù)這種劃分，直至劃分的子表的長為1或0。將上述算法作簡單的修改，就是經(jīng)典的快速排序算法了。

通過DevC++編程環(huán)境編譯通過，采用原先的測試數(shù)據(jù)，運行結(jié)果快速排序算法結(jié)果如圖4：

圖4 綜合運行結(jié)果

最后對快速排序進行簡單的算法分析，最好的情況是每一次劃分都將n 個元素劃分為兩個長度差不多的子區(qū)間，這樣的遞歸樹的高度為O（log2n）。而每一趟劃分的時間復雜度為O（n），因此，此算法的時間復雜度為O（nlog2n），空間復雜度為O（log2n）。相對于簡單的冒泡排序，其算法的平均復雜度從O（n2）提高到O（nlog2n），算法的效率得到提高[10]。

總結(jié)順序表進行拆分的應用實例，不管是以某一個數(shù)為基準，還是按照某種特征進行拆分，為了減少移動操作的次數(shù)，都可以設置兩個偽指針。一個指向順序表的初始位置，一個指向順序表的末尾位置。通過比較兩個指針對應的值進行相關的操作。采用這種方法，可以提高順序表的運行效率。通過對算法的總結(jié)歸納，使學生漸漸形成了對復雜問題進行分而治之的思維方式，對今后類似的算法設計都有很大的幫助。

4 小結(jié)

上文以順序表的應用為實例，在教學中采用理論與實踐相結(jié)合的方式，通過“讀、仿、改、創(chuàng)”四個階段由淺入深循序漸進地進行啟發(fā)式教學。這種教學模式和方法可推廣到其他的典型數(shù)據(jù)結(jié)構(gòu)，如單鏈表、二叉樹和圖等。通過問題導入、思路引導、思維擴展的方式，引導學生思考，使學生能夠做到舉一反三，觸類旁通，提高了學生學習動力，挖掘了學生的學習潛能。通過“改”和“創(chuàng)”兩個步驟，引導學生進行思維升華，學會歸納和總結(jié)，并進行創(chuàng)新。采用程序驅(qū)動的方式，提高了學生學習的成就感，促進了學生的程序設計能力和編程實踐能力的提高。

5 成果展示

通過20級計科兩個班進行教學實踐，對照19級計科兩個班學生期末成績，采用算法設計題得分率和期末成績平均分進行比較分析。比較結(jié)果如表1所示，從表一數(shù)據(jù)可以看出，算法設計題1、算法設計題2和期末平均分的增長率均超過了10%。另外，在剛剛公示的第十三屆藍橋杯軟件設計大賽全國決賽獲獎名單中，20級學生在本次全國總決賽中，共獲一等獎1項，二等獎3項，三等獎3項，優(yōu)秀獎6項，創(chuàng)造了近年來最佳成績。由此可知，按照“讀、仿、改、創(chuàng)”四個階段進行啟發(fā)式教學，提高了學生的程序設計能力。該教學方法不僅適合《數(shù)據(jù)結(jié)構(gòu)》課程，同時也適應所有的程序設計類課程，具有一定的推廣價值。

表1 19計科和20計科數(shù)據(jù)結(jié)構(gòu)成績對照表