摘要:本文針對(duì)困擾“數(shù)據(jù)結(jié)構(gòu)”課程教與學(xué)的幾個(gè)問題，作者根據(jù)自己的認(rèn)識(shí)和多年的實(shí)際教學(xué)經(jīng)驗(yàn)，進(jìn)行深入淺出的分析和論述，以其對(duì)提高課程的認(rèn)識(shí)和興趣、牢固掌握課程知識(shí)及其靈活運(yùn)用、提高利用計(jì)算機(jī)解決問題的能力具有很好的指導(dǎo)作用。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);抽象數(shù)據(jù)類型;教學(xué)

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

1數(shù)據(jù)結(jié)構(gòu)是如何發(fā)展起來的

什么是計(jì)算機(jī)科學(xué)?從20世紀(jì)60年代以來一直有爭(zhēng)議，一部分人認(rèn)為計(jì)算機(jī)科學(xué)的核心是“信息結(jié)構(gòu)的轉(zhuǎn)換”，即側(cè)重強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu);另一部分人則認(rèn)為計(jì)算機(jī)科學(xué)的核心是算法的學(xué)問，即側(cè)重強(qiáng)調(diào)了算法的。我們不去評(píng)判，但應(yīng)該說從宏觀來看計(jì)算機(jī)科學(xué)是研究信息表示和信息處理的科學(xué)，即信息在計(jì)算機(jī)中的表示和信息加工處理是計(jì)算機(jī)科學(xué)研究的主要范疇。

隨著計(jì)算機(jī)科學(xué)技術(shù)的進(jìn)步，計(jì)算機(jī)的硬件技術(shù)和軟件技術(shù)都有了飛速的發(fā)展，計(jì)算機(jī)應(yīng)用也已經(jīng)滲透到了社會(huì)的各個(gè)領(lǐng)域，信息是當(dāng)今社會(huì)的重要資源。在計(jì)算機(jī)應(yīng)用的發(fā)展過程中，出現(xiàn)了以下幾個(gè)突出的變化:

(1) 計(jì)算機(jī)由最初的單一科學(xué)計(jì)算到現(xiàn)在的幾乎無所不能。計(jì)算機(jī)的早期任務(wù)是科學(xué)計(jì)算，隨著計(jì)算機(jī)的發(fā)展，幾乎所有工作都離不開計(jì)算機(jī)。

(2) 計(jì)算機(jī)加工處理的對(duì)象由數(shù)值型變?yōu)閿?shù)值型和非數(shù)值型。現(xiàn)在計(jì)算機(jī)所能加工處理的信息的種類越來越多。

(3) 計(jì)算機(jī)處理的數(shù)據(jù)量由小變?yōu)榇蟆⒃俚骄薮?如海量存儲(chǔ)、計(jì)算)。這一點(diǎn)從人們對(duì)存儲(chǔ)器無止境的追求就可以看出。

(4) 數(shù)據(jù)之間的關(guān)系由簡(jiǎn)單變復(fù)雜、再到很復(fù)雜?，F(xiàn)在計(jì)算機(jī)解決一個(gè)復(fù)雜問題不僅數(shù)據(jù)量大而且數(shù)據(jù)之間的關(guān)系越來越復(fù)雜。

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

2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

很多教科書都了強(qiáng)調(diào)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義，但是，都站的高度太高，學(xué)生體會(huì)不到，很多學(xué)生在被問到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用時(shí)，都知道這課很重要，計(jì)算機(jī)專業(yè)都開設(shè)，考研究生必考等，至于對(duì)專業(yè)能力培養(yǎng)有什么用，很少有學(xué)生說清楚，甚至有些教師也說不清楚，只是簡(jiǎn)單地告訴學(xué)生很重要，要好好學(xué)。

下面看一個(gè)簡(jiǎn)單的例子，它很直觀、很貼切的說明了數(shù)據(jù)結(jié)構(gòu)的重要性。

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

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

如果把這個(gè)問題繼續(xù)擴(kuò)大到學(xué)校的圖書館，想想幾百萬冊(cè)書雜亂地堆在圖書館里，那么借閱等管理幾乎是不可能的了。而現(xiàn)實(shí)是，圖書館里的書都是按一定規(guī)律組織的，這種規(guī)律就是利用了書本身的數(shù)據(jù)特性，即數(shù)據(jù)結(jié)構(gòu)。

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

因此，數(shù)據(jù)結(jié)構(gòu)是問題數(shù)據(jù)信息本身固有的一種特性(與計(jì)算機(jī)無關(guān))，通過分析、研究、發(fā)現(xiàn)這些特性，然后在計(jì)算機(jī)求解該問題時(shí)能利用這些特性，從而提高加工處理的效率。

3抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系

很多人認(rèn)為數(shù)據(jù)結(jié)構(gòu)內(nèi)容很雜、很多，包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法等，難理清楚，不利于學(xué)習(xí)和掌握。其中一個(gè)重要的原因就是數(shù)據(jù)結(jié)構(gòu)本身是脫離計(jì)算機(jī)的，但是又要在計(jì)算機(jī)中用。即數(shù)據(jù)結(jié)構(gòu)是邏輯上的，研究的目的是要讓計(jì)算機(jī)解決問題時(shí)利用它，所以要把數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)起來(存儲(chǔ)數(shù)據(jù)并存儲(chǔ)關(guān)系)，這就是存儲(chǔ)結(jié)構(gòu)。但是存起來不是目的，目的是求解問題，需要對(duì)問題數(shù)據(jù)實(shí)施一系列操作(以期產(chǎn)生預(yù)期結(jié)果)，這就是算法。

抽象數(shù)據(jù)類型是對(duì)問題進(jìn)行抽象建模的一個(gè)結(jié)果，它抽象并刻畫出問題的數(shù)據(jù)及關(guān)系(數(shù)據(jù)結(jié)構(gòu))，抽象并描述出實(shí)施在數(shù)據(jù)結(jié)構(gòu)上的一系列操作?？梢钥闯?，數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型的重要組成部分，因此，從抽象數(shù)據(jù)類型的觀點(diǎn)來研究數(shù)據(jù)結(jié)構(gòu)是最合適的(筆者建議“數(shù)據(jù)結(jié)構(gòu)”課程改為“抽象數(shù)據(jù)類型及實(shí)現(xiàn)”)。

計(jì)算機(jī)求解一個(gè)問題，實(shí)際上就是一個(gè)抽象數(shù)據(jù)類型的計(jì)算機(jī)實(shí)現(xiàn)[2]，包括以下兩個(gè)階段。

(1) 抽象定義階段:分析問題，給出問題的抽象數(shù)據(jù)類型定義。該階段包括分析問題的數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系，描述出數(shù)據(jù)結(jié)構(gòu)，定義出實(shí)施在數(shù)據(jù)結(jié)構(gòu)上的操作。

(2) 實(shí)現(xiàn)階段:在計(jì)算機(jī)上實(shí)現(xiàn)抽象數(shù)據(jù)類型。該階段包括:①數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，即在計(jì)算機(jī)中把數(shù)據(jù)及結(jié)構(gòu)存儲(chǔ)起來(既要存儲(chǔ)元素也要存儲(chǔ)關(guān)系)——選擇存儲(chǔ)結(jié)構(gòu);②操作的具體實(shí)現(xiàn)，即設(shè)計(jì)出各個(gè)操作的具體步驟——算法設(shè)計(jì)。

從這里可以看出，數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)求解問題過程中很重要的一部分，由此也可以看出數(shù)據(jù)結(jié)構(gòu)的重要性。

高級(jí)語言中有很多預(yù)定義類型，其中數(shù)組、字符串也是。在數(shù)據(jù)結(jié)構(gòu)中介紹它們，是要了解它們的原始邏輯模型，也就是說數(shù)組、字符串抽象數(shù)據(jù)類型在高級(jí)語言中都已經(jīng)給予了實(shí)現(xiàn)。高級(jí)語言中的其他數(shù)據(jù)類型也一樣，它們也有自己的抽象數(shù)據(jù)類型原始模型?？梢赃@么認(rèn)為，現(xiàn)實(shí)世界里最常用的一些原始抽象模型，因?yàn)橛猛緩V泛都已經(jīng)(確定了存儲(chǔ)結(jié)構(gòu))實(shí)現(xiàn)了，變成了預(yù)定義類型。從這里可以看出數(shù)據(jù)類型和抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的內(nèi)在聯(lián)系。

4內(nèi)容組織及講授方法

“數(shù)據(jù)結(jié)構(gòu)”的開章篇必須要講清楚數(shù)據(jù)結(jié)構(gòu)是如何產(chǎn)生的、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性，對(duì)于重要的概念不僅僅是學(xué)習(xí)其定義，更重要的是理清楚它們之間的關(guān)系、聯(lián)系，特別是抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法等概念。筆者認(rèn)為應(yīng)該在“問題—抽象—抽象數(shù)據(jù)類型—實(shí)現(xiàn)”這個(gè)大模式下來組織、教授和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容一般包括三部分內(nèi)容:三種基本數(shù)據(jù)結(jié)構(gòu)、最常用和最重要的操作(查找、分類)、典型應(yīng)用。

4.1基本數(shù)據(jù)結(jié)構(gòu)

有些教科書把數(shù)據(jù)結(jié)構(gòu)分為四種[3]，即把集合也列為一種基本數(shù)據(jù)結(jié)構(gòu)，筆者認(rèn)為是不合適的。因?yàn)閿?shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)元素及元素之間關(guān)系的合稱，集合中數(shù)據(jù)元素之間沒有關(guān)系，因此它不應(yīng)該算是一種數(shù)據(jù)結(jié)構(gòu)。

三種基本數(shù)據(jù)結(jié)構(gòu)按照“抽象—實(shí)現(xiàn)”的線路進(jìn)行課程內(nèi)容的組織和講授。包括三大部分。(1)抽象數(shù)據(jù)類型的定義。包括數(shù)據(jù)結(jié)構(gòu)(即數(shù)據(jù)及其邏輯特性)、定義的操作。(2)抽象數(shù)據(jù)類型的實(shí)現(xiàn)。包括數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)(即存儲(chǔ)結(jié)構(gòu))、操作的實(shí)現(xiàn)(算法設(shè)計(jì))。(3)典型應(yīng)用舉例，利用實(shí)現(xiàn)的抽象數(shù)據(jù)類型解決現(xiàn)實(shí)應(yīng)用中的問題。

4.1.1線性數(shù)據(jù)結(jié)構(gòu)

線性數(shù)據(jù)結(jié)構(gòu)是簡(jiǎn)單但是重要的數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)結(jié)構(gòu)中都占有很大的內(nèi)容篇幅。在教授和學(xué)習(xí)中必須抓住共同點(diǎn)、側(cè)重點(diǎn)。線性數(shù)據(jù)結(jié)構(gòu)的共同點(diǎn)是元素之間都是具有線性關(guān)系，因一些特殊性產(chǎn)生了一些特殊的線性數(shù)據(jù)結(jié)構(gòu)。

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

(2) 棧和隊(duì)列:數(shù)據(jù)元素?zé)o特殊限制，但是插入、刪除操作限制在兩端進(jìn)行。這樣，這兩種線性數(shù)據(jù)結(jié)構(gòu)就具有了“先進(jìn)先出”、“先進(jìn)后出”的操作特征，具有非常重要的應(yīng)用價(jià)值。

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

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

(5) 數(shù)組:特殊在元素可以參與多個(gè)線性關(guān)系。如果元素只參與一個(gè)線性關(guān)系就是一維數(shù)組，它和一般的線性表相同。參與的線性關(guān)系的個(gè)數(shù)就是數(shù)組的維數(shù)。由于數(shù)組數(shù)據(jù)結(jié)構(gòu)中元素參與多個(gè)線性關(guān)系，數(shù)組上定義的操作很少，實(shí)現(xiàn)時(shí)一般都是采用順序存儲(chǔ)結(jié)構(gòu)。有些書上說數(shù)組不是線性數(shù)據(jù)結(jié)構(gòu)，筆者認(rèn)為是不正確的。

4.1.2二叉樹結(jié)構(gòu)

樹結(jié)構(gòu)的重點(diǎn)是二叉樹數(shù)據(jù)結(jié)構(gòu)。它有一些重要的性質(zhì)，同時(shí)，由于邏輯結(jié)構(gòu)復(fù)雜了，用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)就變困難，即用物理上的相鄰來存儲(chǔ)層次關(guān)系比較困難了，所以才有了二叉樹的順序存儲(chǔ)方式，存儲(chǔ)位置上的i/2、2*i、2*i+1表示出了層次關(guān)系(一個(gè)前驅(qū)、2個(gè)后繼。表示線性關(guān)系時(shí)是i、i+1，一個(gè)前驅(qū)、一個(gè)后繼)。

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

線索二叉樹是一個(gè)難點(diǎn)，在學(xué)習(xí)時(shí)很多時(shí)候都省略了，但是，這種思想對(duì)于分析和解決問題是很重要的。線索是記錄了元素之間的線性關(guān)系，這種線性關(guān)系是依賴與遍歷方式的，因此線索二叉樹和遍歷是分不開的。講授和學(xué)習(xí)時(shí)應(yīng)該重點(diǎn)放在:

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

(2) 如何記錄線索?

(3) 如何使用線索?

(4) 如何建立線索?

在數(shù)據(jù)結(jié)構(gòu)中有一些特殊的二叉樹，它們具有各自的特點(diǎn)和特殊的應(yīng)用[4]，應(yīng)該把它們歸到一起來講授和學(xué)習(xí)。包括:

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

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

(3) 如何創(chuàng)建和維護(hù)?

4.1.3圖結(jié)構(gòu)

圖結(jié)構(gòu)是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，從它的數(shù)據(jù)結(jié)構(gòu)定義可以看出，其數(shù)據(jù)元素之間的關(guān)系很難用明確的數(shù)學(xué)形式化描述出來。圖結(jié)構(gòu)的存儲(chǔ)是圖操作算法實(shí)現(xiàn)的基礎(chǔ)，是圖結(jié)構(gòu)的重點(diǎn)。由于邏輯關(guān)系的復(fù)雜，無法用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，簡(jiǎn)單的鏈?zhǔn)浇Y(jié)構(gòu)雖然可以很容易的存儲(chǔ)圖結(jié)構(gòu)，但是很不實(shí)用。圖結(jié)構(gòu)的存儲(chǔ)更多地是采用了靈活的存儲(chǔ)方式，這些方式的共同點(diǎn)是:先存儲(chǔ)數(shù)據(jù)元素，再存儲(chǔ)(表示)關(guān)系。存儲(chǔ)數(shù)據(jù)元素一般用連續(xù)地址空間，由于在這里僅僅是存儲(chǔ)元素，所以元素在存儲(chǔ)時(shí)順序是任意的，但是一旦存儲(chǔ)起來，元素就有個(gè)位置，這個(gè)位置就是元素在圖中的位置(很多教科書中沒有講清楚)。元素存儲(chǔ)后，就可以存儲(chǔ)關(guān)系了。因?yàn)橹挥性卮娣藕?，才能說清楚元素與元素之間的關(guān)系。存儲(chǔ)關(guān)系可以采用鄰接矩陣、鄰接表等。

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

圖結(jié)構(gòu)在現(xiàn)實(shí)中有很重要的應(yīng)用，例如最小生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑等。在大的工程應(yīng)用中AOV和AOE兩種圖十分重要，AOV是解決大工程中關(guān)系復(fù)雜的各個(gè)子活動(dòng)的施工調(diào)度順序問題，即通過分析活動(dòng)之間的優(yōu)先關(guān)系，保證各個(gè)子活動(dòng)順利施工而不會(huì)有矛盾;在確定各個(gè)子活動(dòng)能有一個(gè)合理調(diào)度順序的基礎(chǔ)上，AOE是解決工程的施工時(shí)間問題，即通過分析各個(gè)子活動(dòng)的持續(xù)時(shí)間計(jì)算(預(yù)測(cè))出工程的工期。分析AOV是分析AOE的前提，例如，如果AOV里有環(huán)，各個(gè)子活動(dòng)就不能合理進(jìn)行調(diào)度，工期就是無窮大。現(xiàn)在隨著工程越來越大、越來越復(fù)雜，AOV、AOE分析工具也越來越重要。

4.2重要操作

在每種數(shù)據(jù)結(jié)構(gòu)上都有一些常用的操作，其中查找和分類是最常用、最重要的兩個(gè)操作，因此數(shù)據(jù)結(jié)構(gòu)中把這兩個(gè)重要操作的算法分別進(jìn)行了單獨(dú)的介紹。這兩部分內(nèi)容的學(xué)習(xí)和前面三種基本數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)不一樣。

4.2.1查找

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

4.2.2分類

對(duì)于分類操作，目前分為兩大類:基于“比較”的分類方法和基于“非比較”的分類方法。其中大部分方法屬于前者[5]?；凇氨容^”的分類方法又可以按照分類過程中實(shí)施的基本操作分為下面幾類:

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

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

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

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

基于“非比較”的分類方法不多，常見的有計(jì)數(shù)分類、基數(shù)分類等。

對(duì)于各種分類方法，應(yīng)該掌握基本思想、特點(diǎn)、性能，特別是要掌握每種方法的適用場(chǎng)景以及可能的改進(jìn)策略，這樣就可以在實(shí)際應(yīng)用中選擇比較合適的方法來實(shí)現(xiàn)分類操作。

5結(jié)語

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

參考文獻(xiàn):

[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學(xué)出版社，1997.

[2] 許卓群，楊冬青. 數(shù)據(jù)結(jié)構(gòu)與算法[M]. 北京:高等教育出版社，2004.

[3] 殷人昆. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學(xué)出版社，2007.

[4] 李紅衛(wèi). 探索“數(shù)據(jù)結(jié)構(gòu)”教學(xué)改革[J]. 計(jì)算機(jī)教育，2007(14):48-50.

[5] 張銘，許卓群，唐世渭，等. 數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)體系和教學(xué)實(shí)踐[J]. 計(jì)算機(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

(編輯:彭遠(yuǎn)紅)