也談“數據結構”課程教學的幾個問題

摘要:本文針對困擾“數據結構”課程教與學的幾個問題，作者根據自己的認識和多年的實際教學經驗，進行深入淺出的分析和論述，以其對提高課程的認識和興趣、牢固掌握課程知識及其靈活運用、提高利用計算機解決問題的能力具有很好的指導作用。

關鍵詞:數據結構;抽象數據類型;教學

“數據結構”是計算機科學與技術專業中一門重要的專業基礎課，它不僅是各大學計算機及相關的IT專業的核心課程之一，也是許多高校中非計算機專業的主要選修課程之一[1]。美國ACM和IEEE/CS于2001年制定的《Computing Curricula 2001》課程體系以及我國在2002年結合本國國情制定的《中國計算機科學與技術學科教程2002》都賦予“數據結構”課程極高的地位。但是，在該課程教與學的過程中有幾個核心問題許多教師和學生很模糊，也困擾著該課程的教與學。

1數據結構是如何發展起來的

什么是計算機科學?從20世紀60年代以來一直有爭議，一部分人認為計算機科學的核心是“信息結構的轉換”，即側重強調了數據結構;另一部分人則認為計算機科學的核心是算法的學問，即側重強調了算法的。我們不去評判，但應該說從宏觀來看計算機科學是研究信息表示和信息處理的科學，即信息在計算機中的表示和信息加工處理是計算機科學研究的主要范疇。

隨著計算機科學技術的進步，計算機的硬件技術和軟件技術都有了飛速的發展，計算機應用也已經滲透到了社會的各個領域，信息是當今社會的重要資源。在計算機應用的發展過程中，出現了以下幾個突出的變化:

(1) 計算機由最初的單一科學計算到現在的幾乎無所不能。計算機的早期任務是科學計算，隨著計算機的發展，幾乎所有工作都離不開計算機。

(2) 計算機加工處理的對象由數值型變為數值型和非數值型。現在計算機所能加工處理的信息的種類越來越多。

(3) 計算機處理的數據量由小變為大、再到巨大(如海量存儲、計算)。這一點從人們對存儲器無止境的追求就可以看出。

(4) 數據之間的關系由簡單變復雜、再到很復雜。現在計算機解決一個復雜問題不僅數據量大而且數據之間的關系越來越復雜。

這些變化對計算機提出了更高的要求和挑戰，要應對這些變化和挑戰，人們自然想到的就是發展硬件技術，開發出速度更快、存儲容量更大、性能更高的計算機硬件產品。那么有沒有其他途徑呢?或者說，若硬件水平一定，有沒有可能的其他途徑來適應這個變化呢?回答是肯定的，傳統的經驗告訴我們:將一“大堆雜亂無章”的數據交給計算機處理是很不明智的，加工處理的效率會非常低，有時甚至根本無法進行。于是人們想到，通過研究問題本身，發現問題數據的特性，并讓計算機解決問題時利用問題數據的特性，從而提高計算機解決問題的效率。于是人們提出了研究求解問題的數據及數據之間的關系，產生了數據結構。

2學習數據結構的意義

很多教科書都了強調學習數據結構的意義，但是，都站的高度太高，學生體會不到，很多學生在被問到學習數據結構有什么用時，都知道這課很重要，計算機專業都開設，考研究生必考等，至于對專業能力培養有什么用，很少有學生說清楚，甚至有些教師也說不清楚，只是簡單地告訴學生很重要，要好好學。

下面看一個簡單的例子，它很直觀、很貼切的說明了數據結構的重要性。

一個學生在剛入學時，只發了幾本書，可以隨意地扔在自己的桌子上，要上課時，很容易的就找到上課要用的書;到了大二，書多了，變成了20幾本，還可以隨意的扔在桌子上，當然桌子上很滿、很亂了，要上課時，找到上課用的課本需要的時間就長了很多，但是還可以忍受;如果到了大四，積攢的書達到了50多本或者上百本，估計就忍受不了了，也許可以忍受桌子上的滿和亂，但是可能忍受不了找書花的時間了。要想花少的時間找到想用的書，一種方法是提高眼睛識別力和手找書的速度，另一種方法就是很多同學們做的，把書分類碼放，如數學一類、外語一類、人文一類、專業一類等，桌子上整齊了，更重要的是找到想用的書容易多了，花的時間少了。

例子中，前一種提高眼睛識別力方法就是發展“硬件”技術來提高解決問題的效率，后一種方法就是“數據結構”的作用，利用數據結構(書目信息本身固有的關系)來提高解決問題的效率。

如果把這個問題繼續擴大到學校的圖書館，想想幾百萬冊書雜亂地堆在圖書館里，那么借閱等管理幾乎是不可能的了。而現實是，圖書館里的書都是按一定規律組織的，這種規律就是利用了書本身的數據特性，即數據結構。

需要特別指出的是，“數據結構”這門課程是計算機應用發展到一定程度才產生的，但是數據結構本身是問題的數據固有的，人們用或不用，它都天然存在著。例如，書印刷出來后，書目的數據信息(例如書名、分類等)及關系就固有了，無論是堆在桌子上還是碼放，這種數據信息及關系天然存在著。當碼放書時，可以利用這種關系來碼放，這就是利用了數據結構，帶來的是圖書檢索的高效率。

因此，數據結構是問題數據信息本身固有的一種特性(與計算機無關)，通過分析、研究、發現這些特性，然后在計算機求解該問題時能利用這些特性，從而提高加工處理的效率。

3抽象數據類型與數據結構的關系

很多人認為數據結構內容很雜、很多，包括邏輯結構、存儲結構、算法等，難理清楚，不利于學習和掌握。其中一個重要的原因就是數據結構本身是脫離計算機的，但是又要在計算機中用。即數據結構是邏輯上的，研究的目的是要讓計算機解決問題時利用它，所以要把數據結構在計算機中存儲起來(存儲數據并存儲關系)，這就是存儲結構。但是存起來不是目的，目的是求解問題，需要對問題數據實施一系列操作(以期產生預期結果)，這就是算法。

抽象數據類型是對問題進行抽象建模的一個結果，它抽象并刻畫出問題的數據及關系(數據結構)，抽象并描述出實施在數據結構上的一系列操作。可以看出，數據結構是抽象數據類型的重要組成部分，因此，從抽象數據類型的觀點來研究數據結構是最合適的(筆者建議“數據結構”課程改為“抽象數據類型及實現”)。

計算機求解一個問題，實際上就是一個抽象數據類型的計算機實現[2]，包括以下兩個階段。

(1) 抽象定義階段:分析問題，給出問題的抽象數據類型定義。該階段包括分析問題的數據及數據之間的關系，描述出數據結構，定義出實施在數據結構上的操作。

(2) 實現階段:在計算機上實現抽象數據類型。該階段包括:①數據結構的實現，即在計算機中把數據及結構存儲起來(既要存儲元素也要存儲關系)——選擇存儲結構;②操作的具體實現，即設計出各個操作的具體步驟——算法設計。

從這里可以看出，數據結構是計算機求解問題過程中很重要的一部分，由此也可以看出數據結構的重要性。

高級語言中有很多預定義類型，其中數組、字符串也是。在數據結構中介紹它們，是要了解它們的原始邏輯模型，也就是說數組、字符串抽象數據類型在高級語言中都已經給予了實現。高級語言中的其他數據類型也一樣，它們也有自己的抽象數據類型原始模型。可以這么認為，現實世界里最常用的一些原始抽象模型，因為用途廣泛都已經(確定了存儲結構)實現了，變成了預定義類型。從這里可以看出數據類型和抽象數據類型、數據結構、存儲結構的內在聯系。

4內容組織及講授方法

“數據結構”的開章篇必須要講清楚數據結構是如何產生的、學習數據結構的重要性，對于重要的概念不僅僅是學習其定義，更重要的是理清楚它們之間的關系、聯系，特別是抽象數據類型、數據結構、存儲結構、算法等概念。筆者認為應該在“問題—抽象—抽象數據類型—實現”這個大模式下來組織、教授和學習數據結構。

數據結構的內容一般包括三部分內容:三種基本數據結構、最常用和最重要的操作(查找、分類)、典型應用。

4.1基本數據結構

有些教科書把數據結構分為四種[3]，即把集合也列為一種基本數據結構，筆者認為是不合適的。因為數據結構是數據元素及元素之間關系的合稱，集合中數據元素之間沒有關系，因此它不應該算是一種數據結構。

三種基本數據結構按照“抽象—實現”的線路進行課程內容的組織和講授。包括三大部分。(1)抽象數據類型的定義。包括數據結構(即數據及其邏輯特性)、定義的操作。(2)抽象數據類型的實現。包括數據結構的實現(即存儲結構)、操作的實現(算法設計)。(3)典型應用舉例，利用實現的抽象數據類型解決現實應用中的問題。

4.1.1線性數據結構

線性數據結構是簡單但是重要的數據結構，在數據結構中都占有很大的內容篇幅。在教授和學習中必須抓住共同點、側重點。線性數據結構的共同點是元素之間都是具有線性關系，因一些特殊性產生了一些特殊的線性數據結構。

(1) 一般線性表:數據元素、操作都沒有任何特殊限制。

(2) 棧和隊列:數據元素無特殊限制，但是插入、刪除操作限制在兩端進行。這樣，這兩種線性數據結構就具有了“先進先出”、“先進后出”的操作特征，具有非常重要的應用價值。

(3) 字符串:數據元素限制為字符集，操作沒有限制。但是由于元素的限制，使得操作時的操作對象不再是簡單的單個元素，而通常是連續的一組元素(子串)，這樣使得一些操作的算法不同于其他類似操作，如模式匹配。

(4) 廣義表:數據元素特殊，不再僅僅是單元素，還可以是線性表，即可以嵌套。這樣存儲、操作都要復雜了。

(5) 數組:特殊在元素可以參與多個線性關系。如果元素只參與一個線性關系就是一維數組，它和一般的線性表相同。參與的線性關系的個數就是數組的維數。由于數組數據結構中元素參與多個線性關系，數組上定義的操作很少，實現時一般都是采用順序存儲結構。有些書上說數組不是線性數據結構，筆者認為是不正確的。

4.1.2二叉樹結構

樹結構的重點是二叉樹數據結構。它有一些重要的性質，同時，由于邏輯結構復雜了，用順序存儲結構存儲就變困難，即用物理上的相鄰來存儲層次關系比較困難了，所以才有了二叉樹的順序存儲方式，存儲位置上的i/2、2*i、2*i+1表示出了層次關系(一個前驅、2個后繼。表示線性關系時是i、i+1，一個前驅、一個后繼)。

在二叉樹結構中，最重要的兩個操作是創建二叉樹和遍歷。創建二叉樹又分為一般二叉樹的創建和特殊二叉樹的創建;遍歷實際上就是非線性結構的線性化過程，即把非線性的元素按某種方式輸出為一個線性序列。

線索二叉樹是一個難點，在學習時很多時候都省略了，但是，這種思想對于分析和解決問題是很重要的。線索是記錄了元素之間的線性關系，這種線性關系是依賴與遍歷方式的，因此線索二叉樹和遍歷是分不開的。講授和學習時應該重點放在:

(1) 為什么要引入線索二叉樹?

(2) 如何記錄線索?

(3) 如何使用線索?

(4) 如何建立線索?

在數據結構中有一些特殊的二叉樹，它們具有各自的特點和特殊的應用[4]，應該把它們歸到一起來講授和學習。包括:

(1) 特殊二叉樹是如何定義的(具有什么特征)?

(2) 它的用途是什么(例如哈夫曼樹和哈夫曼編碼、二叉排序樹和查找、堆和堆分類等)?

(3) 如何創建和維護?

4.1.3圖結構

圖結構是最復雜的數據結構，從它的數據結構定義可以看出，其數據元素之間的關系很難用明確的數學形式化描述出來。圖結構的存儲是圖操作算法實現的基礎，是圖結構的重點。由于邏輯關系的復雜，無法用順序存儲結構存儲，簡單的鏈式結構雖然可以很容易的存儲圖結構，但是很不實用。圖結構的存儲更多地是采用了靈活的存儲方式，這些方式的共同點是:先存儲數據元素，再存儲(表示)關系。存儲數據元素一般用連續地址空間，由于在這里僅僅是存儲元素，所以元素在存儲時順序是任意的，但是一旦存儲起來，元素就有個位置，這個位置就是元素在圖中的位置(很多教科書中沒有講清楚)。元素存儲后，就可以存儲關系了。因為只有元素存放后，才能說清楚元素與元素之間的關系。存儲關系可以采用鄰接矩陣、鄰接表等。

圖結構的重要操作包括圖的建立(把圖結構在計算機里存儲起來)和遍歷(非線性結構的元素的一種線性訪問順序)。圖的遍歷是圖的其他操作的重要基礎。

圖結構在現實中有很重要的應用，例如最小生成樹、最短路徑、拓撲排序、關鍵路徑等。在大的工程應用中AOV和AOE兩種圖十分重要，AOV是解決大工程中關系復雜的各個子活動的施工調度順序問題，即通過分析活動之間的優先關系，保證各個子活動順利施工而不會有矛盾;在確定各個子活動能有一個合理調度順序的基礎上，AOE是解決工程的施工時間問題，即通過分析各個子活動的持續時間計算(預測)出工程的工期。分析AOV是分析AOE的前提，例如，如果AOV里有環，各個子活動就不能合理進行調度，工期就是無窮大。現在隨著工程越來越大、越來越復雜，AOV、AOE分析工具也越來越重要。

4.2重要操作

在每種數據結構上都有一些常用的操作，其中查找和分類是最常用、最重要的兩個操作，因此數據結構中把這兩個重要操作的算法分別進行了單獨的介紹。這兩部分內容的學習和前面三種基本數據結構的學習不一樣。

4.2.1查找

對于查找操作，應該掌握每一種查找方法的思想、對查找表的要求、性能、優缺點等。順序查找方法思想簡單，對查找表沒有要求，查找效率比較低;折半查找采用二分的思想，要求查找表必須順序存儲而且有序，查找效率比較高;樹查找的思想類似與折半查找，要求查找表必須是二叉排序樹，查找效率與樹的高度有關，因此就要構造高度小的二叉排序樹，即平衡二叉樹;HASH查找的思想很簡單，怎么存起來的就可以怎么查找出來。但是HASH技術有很強的應用背景，即查找表是取自一個很大的元素值集合的、任意一個小子集。這個應用背景決定了HASH技術的兩個關鍵問題:HASH函數的構造、沖突不可避免及解決沖突的方法。當HASH函數比較好(計算簡單、沖突少)時，HASH查找效率是很高的。當然，反過來，如果HASH函數使得查找效率很低，意味著查出來很難或者幾乎不可能，說明這個元素“隱藏”是很深的，也可以說是安全的，所以在信息安全領域HASH技術也很重要。

4.2.2分類

對于分類操作，目前分為兩大類:基于“比較”的分類方法和基于“非比較”的分類方法。其中大部分方法屬于前者[5]。基于“比較”的分類方法又可以按照分類過程中實施的基本操作分為下面幾類:

(1) 基于“插入”思想的分類方法(簡單插入分類、折半插入分類、二路插入分類、SHELL分類等);

(2) 基于“交換”思想的分類方法(冒泡分類、奇偶交換分類、穿梭分類、快速分類等);

(3) 基于“選擇”思想的分類方法(簡單選擇分類、錦標賽分類、堆分類等);

(4) 基于“歸并”思想的分類方法(二路歸并分類、多路歸并分類等);

基于“非比較”的分類方法不多，常見的有計數分類、基數分類等。

對于各種分類方法，應該掌握基本思想、特點、性能，特別是要掌握每種方法的適用場景以及可能的改進策略，這樣就可以在實際應用中選擇比較合適的方法來實現分類操作。

5結語

講授和學習一門課程，形式上是傳授和掌握知識，本質上應該是達到培養和提高能力的目標。一般說來傳授和學習知識容易，但是如何把知識升華為能力很難，這也是目前教學中存在的突出問題，“為什么要學”很重要，“學了怎么用”更重要，這個看似簡單的目標對教師教學提出了極高要求。對IT教學來說，照本宣科是不行的，沒有親自實踐也是不行的，教師和學生都應該牢記“紙上得來終覺淺，覺知此事要躬行”。

參考文獻:

[1] 嚴蔚敏，吳偉民. 數據結構[M]. 北京:清華大學出版社，1997.

[2] 許卓群，楊冬青. 數據結構與算法[M]. 北京:高等教育出版社，2004.

[3] 殷人昆. 數據結構[M]. 北京:清華大學出版社，2007.

[4] 李紅衛. 探索“數據結構”教學改革[J]. 計算機教育，2007(14):48-50.

[5] 張銘，許卓群，唐世渭，等. 數據結構課程的知識體系和教學實踐[J]. 計算機教育，2004(2):89-91.

Discuss Some Problems about \"Data Structure\" Teaching

DUAN You-xiang， SONG Hui-ying， GONG Fa-ming

(China University of Petroleum， Dongying 257061， China)

Abstract: The problems about “Data Structure” teaching and learning are aimed in this paper. Analysis and discussion are done based on the author’s opinion and practical teaching experience. It benefit to raise awareness and interest in the courses， solid grasp the knowledge and more flexibility in using， and enhance their ability on solving problems with computer .

Key word: Data Structure; abstract data type; teaching

(編輯:彭遠紅)