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

1、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義和作用董建寅 羅遠(yuǎn)（上海金融學(xué)院信息管理系，）引言 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)是否是一門純數(shù)學(xué)課程？它在專業(yè)課程體系中起什么樣的作用？許多學(xué)生學(xué)完后也茫然一片，為此我們很有必要探討一下學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意思和作用。眾所周知，計(jì)算機(jī)科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。數(shù)據(jù)是計(jì)算機(jī)化的信息，它是計(jì)算機(jī)可以直接處理的最基本和最重要的對象。無論是進(jìn)行科學(xué)計(jì)算或數(shù)據(jù)處理、過程控制以及對文件的存儲和檢索及數(shù)據(jù)庫技術(shù)應(yīng)用等，都是對數(shù)據(jù)進(jìn)行加工處理的過程。因此，要設(shè)計(jì)出一個結(jié)構(gòu)好效率高的程序，必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的存儲表示，并利用這些特性和關(guān)系設(shè)計(jì)出相應(yīng)的算法和程

2、序。1 學(xué)習(xí)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)的意義數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、計(jì)算機(jī)信息管理與應(yīng)用專業(yè)，電子商務(wù)等專業(yè)的基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計(jì)算機(jī)來解決實(shí)際問題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語言是難以應(yīng)付當(dāng)前眾多復(fù)雜的課題。要想有效地使用計(jì)算機(jī)、充分發(fā)揮計(jì)算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實(shí)基礎(chǔ)，對于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、軟件工程、編譯原理、人工智能、圖視學(xué)等都是十分有益的。2 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)的目的主要是處理數(shù)值

3、計(jì)算問題。當(dāng)我們使用計(jì)算機(jī)來解決一個具體問題時，一般需要經(jīng)過下列幾個步驟：首先要從該具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)或選擇一個解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行調(diào)試、測試，直至得到最終的解答。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型的線性方程組，可以使用迭代算法來求解。由于當(dāng)時所涉及的運(yùn)算對象是簡單的整型、實(shí)型或布爾類型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力是集中于程序設(shè)計(jì)的技巧上，而無須重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計(jì)算問題越來越顯得重要。據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值計(jì)算性問題占用了85%以上的機(jī)器時間。這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法

4、用數(shù)學(xué)方程式加以描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。下面所列舉的就是屬于這一類的具體問題。例1：圖書館信息檢索系統(tǒng)。當(dāng)我們根據(jù)書名查找某本書有關(guān)情況的時候；或者根據(jù)作者或某個出版社查找有關(guān)書籍的時候，或根據(jù)書刊號查找作者和出版社等有關(guān)情況的時候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動檢索。由此，可以在圖書館信息檢索系統(tǒng)中建立一張按書刊號順序排列的圖書信息表和分別按作者、書名、出版社順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是圖書信息檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某

5、個特定要求（如給定書名）對圖書館藏書信息文件進(jìn)行查詢。諸如此類的還有學(xué)生信息查詢系統(tǒng)、商場商品管理系統(tǒng)、倉庫物資管理系統(tǒng)等。在這類文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對象之間通常存在著的是一種簡單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。 書刊號書名作者出版社書架編號7-302-02368-3數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)p302-419-25-301-00128-1線性代數(shù)李志中復(fù)旦大學(xué)k203-048-17-309-01408-2數(shù)據(jù)結(jié)構(gòu)蔡子經(jīng)高校出版社p302-428-55-303-01654-3線性代數(shù)趙堅(jiān)清華大學(xué)k205-046-26-506-04314-2離散數(shù)學(xué)左孝凌復(fù)旦大學(xué)t-304

6、-056-27-406-03416-1數(shù)據(jù)結(jié)構(gòu)李有亮上海教育出版社p302-433-47-406-01256-2計(jì)算機(jī)組成顧浩清華大學(xué)w306-224-26-507-1離散數(shù)學(xué)楊文杰高校出版社t-306-433-57-408-2計(jì)算機(jī)組成顧浩上海教育出版社w-305-036-6(a)圖書信息數(shù)據(jù)結(jié)構(gòu)1，3，6線性代數(shù)2，4離散數(shù)學(xué)5，8計(jì)算機(jī)組成7，9(c)書名索引表蔡子經(jīng) 3顧浩 7，9李志中 2李有亮 6嚴(yán)蔚敏1楊文杰 8左孝凌5趙堅(jiān) 4(b)作者索引表清華大學(xué)1,4,7復(fù)旦大學(xué)2,5高校出版社3,8上海教育出版社6,9(d)出版社索引表 圖1.1圖書館信息檢索例2：八皇后問題。在八皇后問

7、題中，處理過程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進(jìn)行試探，每試探一步形成一個新的狀態(tài)，整個試探過程形成了一棵隱含的狀態(tài)樹。如圖1.2所示（為了描述方便，將八皇后問題簡化為四皇后問題）?；厮莘ㄇ蠼膺^程實(shí)質(zhì)上就是一個遍歷狀態(tài)樹的過程。在這個問題中所出現(xiàn)的樹也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計(jì)算的問題中。圖1.2 四皇后問題中隱含的狀態(tài)樹例3：教學(xué)計(jì)劃編排問題。一個教學(xué)計(jì)劃包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒有次序要求。即有些課程之間有先修和

8、后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個課程之間的次序關(guān)系可用一個稱作圖的數(shù)據(jù)結(jié)構(gòu)來表示，如圖1.3所示。有向圖中的每個頂點(diǎn)表示一門課程，如果從頂點(diǎn)vi到vj之間存在有向邊，則表示課程i必須先于課程j進(jìn)行。由以上三個例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如線性表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計(jì)算機(jī)處理對象的特性，將實(shí)際問題中所涉及的處理對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。與此同時，通過算法訓(xùn)練來提高學(xué)生的思維能力，通過程序設(shè)

9、計(jì)的技能訓(xùn)練來促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。課程編號課程名稱先修課程C1程序設(shè)計(jì)基礎(chǔ)無c2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2, C5C4匯編語言C1C5C程序設(shè)計(jì)語言C1C6計(jì)算機(jī)圖形學(xué)C3，C4，C5C7接口技術(shù)C4C8數(shù)據(jù)庫原理C3，C10C9編譯原理C4 ,C5C10操作系統(tǒng)C3c9圖1.3 教學(xué)計(jì)劃編排問題的數(shù)據(jù)結(jié)構(gòu)表示課程之間優(yōu)先關(guān)系的有向圖c10c7c8c6c5c4c3c1c23數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計(jì)算機(jī)硬件和軟件有十分密切的關(guān)系，它是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)專業(yè)的核心課程，是高級程序設(shè)計(jì)語言、操作系統(tǒng)、編譯原理、數(shù)據(jù)庫、人工智能、圖

10、視學(xué)等課程的基礎(chǔ)。同時，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。 方面 層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲結(jié)構(gòu)算法評價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析圖1.4 數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容體系數(shù)據(jù)結(jié)構(gòu)課程重在討論軟件開發(fā)過程中的方案設(shè)計(jì)階段、同時設(shè)計(jì)編碼和分析階段的若干基本問題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個層次的五個“要素”，如圖1.4所示。數(shù)據(jù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過分解可以劃分出數(shù)據(jù)的三個層次；再通過抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過分解將處理要求劃分

11、成各種功能，再通過抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個方面的結(jié)合使我們將問題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)。這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。熟練地掌握這兩個過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。結(jié)束語：數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國外是從1968年才開始的，但在此之前其有關(guān)內(nèi)容已散見于編譯原理及操作系統(tǒng)之中。20世紀(jì)60年代中期，美國的一些大學(xué)開始設(shè)立有關(guān)課程，但當(dāng)時的課程名稱并不叫數(shù)據(jù)結(jié)構(gòu)。1968年美國唐.歐.克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計(jì)算機(jī)程序設(shè)計(jì)技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們越來越重視數(shù)據(jù)結(jié)構(gòu)。從70年代中期到80年代，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢，越來越被人們所重視。參考資料1 數(shù)據(jù)結(jié)構(gòu)（C語言版） 嚴(yán)蔚敏 編（著） 清華大學(xué)出版社；