程序設計與數據結構“雙向重構”教學銜接法探討

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

（大理大學 數學與計算機學院，云南 大理 671003）

1 背 景

1.1 數據結構與程序設計課程的關系

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

問題一：對數據結構、算法和程序3者之間的認識不夠；

問題二：簡單算法和復雜數學模型之間的過渡困難；

問題三：從簡單數據類型到復雜數據邏輯結構和存儲結構之間的過渡困難；

問題四：從編寫簡單程序到復雜程序的訓練不足；

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

問題二和問題三是由問題一派生出來的，如果能解決問題一，問題二和問題三即能解決。關于問題四，學生進入數據結構的學習后，接觸到大量非數值類的復雜問題，對編程能力是一個延續訓練。關于問題五，數據結構的另一個研究重點是算法效率，算法設計的好壞直接關系到程序實現的正確性和效率。

1.2 基于建構主義理論的知識“雙向重構”思想

建構主義學習觀中認為，知識并不是對現實的準確表征，它只是一種假設和解釋，并不是問題的最終答案。相反，它會隨著人類的進步而不斷地被“革命”掉，并隨之出現新的假設[1]。建構主義的學習活動觀認為，學習不是知識由教師向學生的傳遞，而是學生建構自己的知識的過程[1]。建構主義的學習觀認為，學生在接觸新的知識之前，是有一定經驗的，他們可以依靠經驗背景出發，經過知識的重組和擴充，重新建構知識體系。

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

在這個“雙向重構”過程中，學習者首先是“正向”地接受新知識，是新知識的堆砌過程；之后，學習者通過思考、比較和重組，“逆向”地改變舊知識構成的舊的認知，是新舊知識發生融合、發生質變的一個過程。從實現者的角度出發，“雙向”表示學習不再是教師把知識簡單地教授給學生的單向傳遞過程，學習者不是被動接收信息刺激，而是主動地接受新知識，重新建構新認知結構的過程。“重構”指的是學生不一定按照教師的單向傳遞思路重建教師已經建構好的知識體系，而是可以重構出新的、具有創新性的認知體系。

2 程序設計與數據結構課程的知識對比

程序設計與數據結構課程之間相輔相成，兩門課程所講述的內容，有很多知識點具有相關性和延續性。以C程序設計課程為例，對比兩門課程講述內容見表1。

對比表1中兩門課程的內容，可以看出：①程序設計課程的內容是數據結構課程的基礎；②數據結構課程的內容是程序設計課程的深入和延續；③程序設計課程內容（知識）可以作為學生的“原有經驗”構建數據結構課程內容（知識），即“新的經驗”或“新的知識體系”。

3 基于“雙向重構”思想的數據結構、算法和程序的遞進學習模型

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

表1 兩門課程的內容對比

圖1 概念模型

3.1 數據結構、算法和程序的概念模型

數據結構、算法和程序在數據結構和程序設計中是3個最重要的概念。圖1所示為3個概念的概念模型。

根據概念模型，數據結構是數據與數據之間的復雜關系，這些關系可以用數據類型進行組合或者創造得到；算法仍然是解決問題的方法和步驟，只是步驟更多，邏輯性更強；程序仍然是程序，只是程序的結構和規模都變得更為復雜。建構這樣一個概念模型還有一個好處，在這個階段，3個重要概念中，只有數據結構需要認知的更新，從而減輕學生開始學習數據結構課程的恐懼心理。

3.2 數據結構、算法和程序的邏輯模型

對數據結構、算法和程序概念再進行深層次的剖析和分解，建立邏輯模型，使得3個概念發生認知重構，如圖2所示。

（1）數據結構。第一，數據結構（在計算機中的模型）是相互之間存在一種或多種特定關系的數據元素的集合[2]。第二，Data Structure（數據結構）是數據的邏輯結構和存儲結構的合體。數據的邏輯結構是數據之間的結構關系，是具體關系的抽象。數據的存儲結構是數據結構在計算機內存中的表示[2]。

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

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

圖2 邏輯模型

3.3 數據結構、算法和程序的實現模型

根據概念模型和邏輯模型，學生通過知識重構，已經明確要在計算機中通過程序解決實際問題，必須學習ADT。接下來，教師就可以告知學生，如何通過創建好的ADT進行具體的實踐。以順序表的操作實現為例，構建數據結構、算法和程序的實現模型，如圖3所示。

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

4 數據結構、算法和程序的遞進模型的實踐和分析

4.1 數據結構、算法和程序的遞進模型的實踐

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

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

（1）文件C1.h的部分內容如下：

#include ……

#define TRUE 1 ……

typedef int Status; // Status是函數的類型，其值是函數結果狀態代碼，如OK等

（2）文件S1.h的內容如下：

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

圖3 實現模型

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

圖4 程序運行結果

4.2 數據結構、算法和程序的遞進模型的分析

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

5 結 語

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