程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)“雙向重構(gòu)”教學(xué)銜接法探討

趙榆琴，楊 健，張曉玲，蘇 鵬

（大理大學(xué) 數(shù)學(xué)與計算機(jī)學(xué)院，云南 大理 671003）

1 背 景

1.1 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計課程的關(guān)系

程序設(shè)計類課程是數(shù)據(jù)結(jié)構(gòu)課程的先修課，它們都是計算機(jī)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)課程的核心思想是通過在現(xiàn)實問題和計算機(jī)之間建立數(shù)學(xué)模型，然后用程序得到現(xiàn)實問題的答案。這要求學(xué)生先對程序有基本的認(rèn)知和程序設(shè)計能力，但是從多年的教學(xué)過程中發(fā)現(xiàn)，學(xué)生在學(xué)完一門程序設(shè)計語言（如C語言）后，緊接著學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)存在難以銜接的困難，主要包括以下幾個問題。

問題一：對數(shù)據(jù)結(jié)構(gòu)、算法和程序3者之間的認(rèn)識不夠；

問題二：簡單算法和復(fù)雜數(shù)學(xué)模型之間的過渡困難；

問題三：從簡單數(shù)據(jù)類型到復(fù)雜數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的過渡困難；

問題四：從編寫簡單程序到復(fù)雜程序的訓(xùn)練不足；

問題五：對算法效率的評價認(rèn)識和實踐不足。

問題二和問題三是由問題一派生出來的，如果能解決問題一，問題二和問題三即能解決。關(guān)于問題四，學(xué)生進(jìn)入數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)后，接觸到大量非數(shù)值類的復(fù)雜問題，對編程能力是一個延續(xù)訓(xùn)練。關(guān)于問題五，數(shù)據(jù)結(jié)構(gòu)的另一個研究重點是算法效率，算法設(shè)計的好壞直接關(guān)系到程序?qū)崿F(xiàn)的正確性和效率。

1.2 基于建構(gòu)主義理論的知識“雙向重構(gòu)”思想

建構(gòu)主義學(xué)習(xí)觀中認(rèn)為，知識并不是對現(xiàn)實的準(zhǔn)確表征，它只是一種假設(shè)和解釋，并不是問題的最終答案。相反，它會隨著人類的進(jìn)步而不斷地被“革命”掉，并隨之出現(xiàn)新的假設(shè)[1]。建構(gòu)主義的學(xué)習(xí)活動觀認(rèn)為，學(xué)習(xí)不是知識由教師向?qū)W生的傳遞，而是學(xué)生建構(gòu)自己的知識的過程[1]。建構(gòu)主義的學(xué)習(xí)觀認(rèn)為，學(xué)生在接觸新的知識之前，是有一定經(jīng)驗的，他們可以依靠經(jīng)驗背景出發(fā)，經(jīng)過知識的重組和擴(kuò)充，重新建構(gòu)知識體系。

在建構(gòu)主義學(xué)習(xí)理論下出現(xiàn)了多種學(xué)習(xí)模式。赫爾巴特等提出，要以問題解決為基礎(chǔ)改革教學(xué)：應(yīng)該讓學(xué)生就學(xué)科內(nèi)容形成問題，具有對知識的好奇，然后再去探索，去尋找答案，解決自己認(rèn)識上的沖突，通過這種活動使學(xué)生建構(gòu)起對知識的理解[1]。皮亞杰認(rèn)為，新經(jīng)驗的進(jìn)入會使原有的經(jīng)驗發(fā)生一定的改變，使它得到豐富、調(diào)整或改造，這就是雙向的建構(gòu)過程[1]。

在這個“雙向重構(gòu)”過程中，學(xué)習(xí)者首先是“正向”地接受新知識，是新知識的堆砌過程；之后，學(xué)習(xí)者通過思考、比較和重組，“逆向”地改變舊知識構(gòu)成的舊的認(rèn)知，是新舊知識發(fā)生融合、發(fā)生質(zhì)變的一個過程。從實現(xiàn)者的角度出發(fā)，“雙向”表示學(xué)習(xí)不再是教師把知識簡單地教授給學(xué)生的單向傳遞過程，學(xué)習(xí)者不是被動接收信息刺激，而是主動地接受新知識，重新建構(gòu)新認(rèn)知結(jié)構(gòu)的過程?！爸貥?gòu)”指的是學(xué)生不一定按照教師的單向傳遞思路重建教師已經(jīng)建構(gòu)好的知識體系，而是可以重構(gòu)出新的、具有創(chuàng)新性的認(rèn)知體系。

2 程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)課程的知識對比

程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)課程之間相輔相成，兩門課程所講述的內(nèi)容，有很多知識點具有相關(guān)性和延續(xù)性。以C程序設(shè)計課程為例，對比兩門課程講述內(nèi)容見表1。

對比表1中兩門課程的內(nèi)容，可以看出：①程序設(shè)計課程的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)；②數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容是程序設(shè)計課程的深入和延續(xù)；③程序設(shè)計課程內(nèi)容（知識）可以作為學(xué)生的“原有經(jīng)驗”構(gòu)建數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容（知識），即“新的經(jīng)驗”或“新的知識體系”。

3 基于“雙向重構(gòu)”思想的數(shù)據(jù)結(jié)構(gòu)、算法和程序的遞進(jìn)學(xué)習(xí)模型

數(shù)據(jù)結(jié)構(gòu)課程最重要的內(nèi)容就是要讓學(xué)生理解數(shù)據(jù)結(jié)構(gòu)、算法和程序之間的關(guān)系。有了這個前提，學(xué)生才能不斷地調(diào)整和改組舊知識，構(gòu)建新的知識框架，用新的眼光和思考方式解決越來越復(fù)雜的現(xiàn)實問題。因此，應(yīng)首先基于“雙向重構(gòu)”的思想，建立數(shù)據(jù)結(jié)構(gòu)、算法和程序的模型；其次，根據(jù)這個模型，學(xué)生對新舊知識進(jìn)行對比、拆解、分析和重新組裝；最后，學(xué)生對知識點的理解和實踐從量變到質(zhì)變，重新構(gòu)建數(shù)據(jù)結(jié)構(gòu)、算法和程序的認(rèn)知結(jié)構(gòu)。整個模型分3個遞進(jìn)的子模型：概念模型、邏輯模型和實現(xiàn)模型。

表1 兩門課程的內(nèi)容對比

圖1 概念模型

3.1 數(shù)據(jù)結(jié)構(gòu)、算法和程序的概念模型

數(shù)據(jù)結(jié)構(gòu)、算法和程序在數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計中是3個最重要的概念。圖1所示為3個概念的概念模型。

根據(jù)概念模型，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)與數(shù)據(jù)之間的復(fù)雜關(guān)系，這些關(guān)系可以用數(shù)據(jù)類型進(jìn)行組合或者創(chuàng)造得到；算法仍然是解決問題的方法和步驟，只是步驟更多，邏輯性更強(qiáng)；程序仍然是程序，只是程序的結(jié)構(gòu)和規(guī)模都變得更為復(fù)雜。建構(gòu)這樣一個概念模型還有一個好處，在這個階段，3個重要概念中，只有數(shù)據(jù)結(jié)構(gòu)需要認(rèn)知的更新，從而減輕學(xué)生開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的恐懼心理。

3.2 數(shù)據(jù)結(jié)構(gòu)、算法和程序的邏輯模型

對數(shù)據(jù)結(jié)構(gòu)、算法和程序概念再進(jìn)行深層次的剖析和分解，建立邏輯模型，使得3個概念發(fā)生認(rèn)知重構(gòu)，如圖2所示。

（1）數(shù)據(jù)結(jié)構(gòu)。第一，數(shù)據(jù)結(jié)構(gòu)（在計算機(jī)中的模型）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合[2]。第二，Data Structure（數(shù)據(jù)結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的合體。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示[2]。

（2）算法。在概念模型中，算法是對特定問題求解步驟的一種描述。在邏輯模型中，算法是對數(shù)據(jù)所進(jìn)行的操作的一種描述，其中每一條指令表示一個或多個操作[2]。

（3）程序。在邏輯模型中，也能說明公式“Data Structure + Algorithm=Program”，并且是對概念模型的細(xì)化和驗證。程序應(yīng)該能夠刻畫數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的操作。在邏輯模型中最后出現(xiàn)了ADT（抽象數(shù)據(jù)類型），即告訴學(xué)生，在數(shù)據(jù)結(jié)構(gòu)這門課中，通過研究ADT的定義、表示和實現(xiàn)，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法在計算機(jī)中的表示，然后再將它們寫成程序，從而完成“程序（program）”知識的重構(gòu)。

圖2 邏輯模型

3.3 數(shù)據(jù)結(jié)構(gòu)、算法和程序的實現(xiàn)模型

根據(jù)概念模型和邏輯模型，學(xué)生通過知識重構(gòu)，已經(jīng)明確要在計算機(jī)中通過程序解決實際問題，必須學(xué)習(xí)ADT。接下來，教師就可以告知學(xué)生，如何通過創(chuàng)建好的ADT進(jìn)行具體的實踐。以順序表的操作實現(xiàn)為例，構(gòu)建數(shù)據(jù)結(jié)構(gòu)、算法和程序的實現(xiàn)模型，如圖3所示。

在實現(xiàn)模型中，數(shù)據(jù)的邏輯結(jié)構(gòu)最終由ADT List的定義實現(xiàn)；數(shù)據(jù)的存儲結(jié)構(gòu)最終由線性表的動態(tài)分配順序存儲結(jié)構(gòu)Sqlist，即文件S1.h實現(xiàn)；數(shù)據(jù)的操作最終由順序表Sqlist的操作，即文件A1.h實現(xiàn)。另外，文件C1.h中包含的是類C語言的各種函數(shù)狀態(tài)代碼，文件Main.cpp是程序的主調(diào)函數(shù)。通過實現(xiàn)模型，數(shù)據(jù)結(jié)構(gòu)和算法的概念又進(jìn)行了重構(gòu)，概念更新為具體的組成程序（Program）的各個文件。3個抽象的概念得以實體化。

4 數(shù)據(jù)結(jié)構(gòu)、算法和程序的遞進(jìn)模型的實踐和分析

4.1 數(shù)據(jù)結(jié)構(gòu)、算法和程序的遞進(jìn)模型的實踐

我們通過實例對數(shù)據(jù)結(jié)構(gòu)、算法和程序的遞進(jìn)模型進(jìn)行實踐，如線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將La和Lb歸并為一個新的線性表Lc，且Lc中的元素仍按值非遞減有序排列。根據(jù)實現(xiàn)模型，假設(shè)采用順序表作為存儲方式，要求學(xué)生用C語言或者C++語言，在VC++6.0中實現(xiàn)程序。由于文章篇幅有限，只能列出部分重要程序，程序中有符號“……”，表示此處有省略的程序[3]。

1）依次編輯文件C1.h、S1.h、A1.h和Main.cpp，并放入一個文件夾。

（1）文件C1.h的部分內(nèi)容如下：

#include ……

#define TRUE 1 ……

typedef int Status; // Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等

（2）文件S1.h的內(nèi)容如下：

#define LIST_INIT_SIZE 10 // 線性表存儲空間的初始分配量

圖3 實現(xiàn)模型

2）在VC++6.0中執(zhí)行Main.cpp文件，查看并記錄程序運行結(jié)果，如圖4所示。

圖4 程序運行結(jié)果

4.2 數(shù)據(jù)結(jié)構(gòu)、算法和程序的遞進(jìn)模型的分析

從整個遞進(jìn)模型來看，概念模型在整個數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程中，只需建立一次。它是程序設(shè)計課與數(shù)據(jù)結(jié)構(gòu)課程銜接的簡單過渡，學(xué)生容易理解，在“緒論”一章中就可以給學(xué)生建立。建立邏輯模型的過程是學(xué)生知識納入和認(rèn)知重構(gòu)的過程，這一階段需要教師列舉一些實例，如迷宮、學(xué)生信息管理、交通管理等，以幫助學(xué)生解決數(shù)據(jù)結(jié)構(gòu)、算法和程序之間的關(guān)系（問題一）。這一階段也是1.1節(jié)問題二和問題三的重要過渡階段，教師也應(yīng)在“緒論”一章幫助學(xué)生建立起來。第3個模型可在后序整個數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)過程中。教師每講解一種新的數(shù)據(jù)結(jié)構(gòu)，首先可以重復(fù)邏輯模型，以加深學(xué)生對問題二和問題三的過渡；然后再建立新的實現(xiàn)模型；最后，將問題轉(zhuǎn)換為程序由計算機(jī)給出運行結(jié)果。這一階段是程序設(shè)計課與數(shù)據(jù)結(jié)構(gòu)課銜接的重要實踐階段。根據(jù)實現(xiàn)模型，學(xué)生就能得到從簡單程序到復(fù)雜程序編寫的訓(xùn)練（問題四）。另外，教師還應(yīng)強(qiáng)調(diào)改變ADT的表示即改變數(shù)據(jù)的存儲結(jié)構(gòu)，ADT的實現(xiàn)即對數(shù)據(jù)的操作也要隨之改變，也就是數(shù)據(jù)在不同存儲方式下，解決同一問題的算法也要改變。這樣，可引導(dǎo)學(xué)生分析算法的效率（問題五），如在以上實例中，也可以用鏈?zhǔn)酱鎯Ψ绞浇鉀Q，算法執(zhí)行的效率將有所不同。如果學(xué)生能根據(jù)新舊知識的融合，設(shè)計出新的存儲結(jié)構(gòu)或者算法，則實現(xiàn)了認(rèn)知結(jié)構(gòu)的創(chuàng)新。至此，解決了本文前面1.1節(jié)所提出的5個問題。

5 結(jié) 語

從數(shù)據(jù)結(jié)構(gòu)、算法和程序遞進(jìn)模型可以看出，此模型設(shè)計了這樣一個過程：通過一個具體的實例（現(xiàn)實問題），分析其在計算機(jī)中的表示（數(shù)據(jù)結(jié)構(gòu)），并找到問題的解決方法（算法），最后用程序得到問題的解答。模型將數(shù)據(jù)結(jié)構(gòu)、算法和程序?qū)嶓w化。數(shù)據(jù)結(jié)構(gòu)課程中有很多的現(xiàn)實問題，包括一元多項式的求解、迷宮問題、模式匹配、最小生成樹、最短路徑等，都可以用此模型所描述的過程進(jìn)行學(xué)習(xí)和實踐。從整個遞進(jìn)模型的實踐過程來看，學(xué)生親歷了從數(shù)據(jù)結(jié)構(gòu)到算法、從算法到程序的過程。一方面，學(xué)生再次明確數(shù)據(jù)的邏輯結(jié)構(gòu)與算法的設(shè)計相關(guān)，而數(shù)據(jù)的存儲結(jié)構(gòu)與算法的實現(xiàn)相關(guān)[4]；另一個方面，學(xué)生可以更加清楚算法和程序不等價[5]，完全不必因為沒有學(xué)好程序設(shè)計語言而害怕數(shù)據(jù)結(jié)構(gòu)，反而能夠通過對各種數(shù)據(jù)結(jié)構(gòu)運用遞進(jìn)模型的實踐，增強(qiáng)編程能力。這個模型采用了“雙向重構(gòu)”思想，是學(xué)習(xí)者對新信息的建構(gòu)，同時又包含對原有經(jīng)驗的改造和重組。學(xué)習(xí)過程中需要注意：①教師在“正向”傳遞知識時，應(yīng)了解學(xué)生的基本情況，設(shè)計便于學(xué)生理解和重組的知識；②學(xué)生進(jìn)行“逆向”重組時，多設(shè)計實例和需求供學(xué)生重構(gòu)，爭取做到“教師引導(dǎo)，學(xué)生創(chuàng)新”；③可適當(dāng)引導(dǎo)學(xué)生根據(jù)問題，歸類算法的思想，為后序算法設(shè)計和分析課程打下基礎(chǔ)。