數(shù)據(jù)結(jié)構(gòu)概念---中南大學(xué)教程

1、數(shù)據(jù)結(jié)構(gòu)的概念美國(guó)計(jì)算機(jī)科學(xué)家 Don aid Ervin Kn uth首次提出了數(shù)據(jù)結(jié)構(gòu)和算法的概念，并在他所著 的計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第 1卷基本算法中首次較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ) 結(jié)構(gòu)及其操作。隨后，美國(guó)的一些大學(xué)開(kāi)始設(shè)立與數(shù)據(jù)結(jié)構(gòu)相關(guān)的課程。同時(shí)，結(jié)構(gòu)化程序 設(shè)計(jì)逐漸成為當(dāng)時(shí)程序設(shè)計(jì)的主流方法，人們也越來(lái)越重視數(shù)據(jù)結(jié)構(gòu)。各種版本的數(shù)據(jù)結(jié)構(gòu)著作也相繼出現(xiàn)。數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)科學(xué)的一門分支學(xué)科，主要研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象、對(duì)象之間的關(guān)系和操作等。為了編寫出“好”的程序，必須分析待處理對(duì)象 的特性及各處理對(duì)象之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括 3個(gè)層次的5個(gè)“

2、要素”，如表1-1所示。其中的3個(gè)層次分別為 抽象、實(shí)現(xiàn)與評(píng)價(jià)。通過(guò)抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)表示，通過(guò)分解 將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到基本操作的定義。上述兩個(gè) 方面的結(jié)合將問(wèn)題變換為數(shù)據(jù)結(jié)構(gòu)，這是一個(gè)從具體（即具體問(wèn)題）到抽象（即數(shù)據(jù)結(jié)構(gòu)） 的過(guò)程。最后，通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)，而這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過(guò)程。熟練掌握這兩個(gè)過(guò) 程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。在這個(gè)過(guò)程中需要對(duì)不同結(jié)構(gòu)及其實(shí)現(xiàn)的性能進(jìn)行評(píng)價(jià)，從而獲得最佳實(shí)踐方案。實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)算法評(píng)價(jià)不同數(shù)據(jù)

3、結(jié)構(gòu)的比較艮算法分析針對(duì)要處理的問(wèn)題，設(shè)計(jì)最有利于操作系統(tǒng)處理的數(shù)據(jù)結(jié)構(gòu)時(shí)需考慮下列因素。數(shù)據(jù)的數(shù)量。數(shù)學(xué)系統(tǒng)設(shè)計(jì)）.算子關(guān)系 數(shù)據(jù)類型數(shù)據(jù)表示法數(shù)據(jù)的操作 數(shù)據(jù)結(jié)構(gòu)硬件（計(jì)算機(jī)圖1-1數(shù)據(jù)結(jié)構(gòu)的地位代數(shù)系統(tǒng)編碼理論文件系統(tǒng)存儲(chǔ)裝置數(shù)據(jù)存取數(shù)據(jù)組織器組織信息檢索軟件（計(jì)算機(jī)程序設(shè)計(jì)）（2）數(shù)據(jù)的使用次數(shù)和方式。（3）數(shù)據(jù)的性質(zhì)是動(dòng)態(tài)的還是靜態(tài)的。（4）數(shù)據(jù)結(jié)構(gòu)化后需要多大的存儲(chǔ)空間。（5）存取結(jié)構(gòu)化后的數(shù)據(jù)所需花費(fèi)的時(shí)間。（6）是否容易程序化。目前，“數(shù)據(jù)結(jié)構(gòu)”已經(jīng)是計(jì)算機(jī)科學(xué)及相 關(guān)專業(yè)的一門專業(yè)基礎(chǔ)課。它與數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的關(guān)系如圖1-1所示。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是

4、一般程序設(shè)計(jì)的基 礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)以及 數(shù)據(jù)庫(kù)系統(tǒng)等大型程序的基礎(chǔ)。所有的計(jì)算機(jī)系 統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，學(xué)好“數(shù)據(jù)結(jié)構(gòu)”這門課程，對(duì)學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程都是十分有益的。為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)發(fā)展的初期， 人們使用計(jì)算機(jī)的主要目的是處理數(shù)值計(jì)算問(wèn)題。使用計(jì)算機(jī)解決具體問(wèn)題一般需要經(jīng)過(guò)以下幾個(gè)步驟： 首先從具體問(wèn)題抽象出適當(dāng)?shù)臄?shù)學(xué)模型， 然后設(shè)計(jì) 或選擇解此數(shù)學(xué)模型的算法，接著編寫程序并進(jìn)行調(diào)試、測(cè)試，直至得到最終的解答。由于最初涉及的運(yùn)算對(duì)象是簡(jiǎn)單的整型、實(shí)型或布爾型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力集中于程序設(shè)計(jì)的技巧上，而無(wú)需重視數(shù)據(jù)

5、結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟硬件的 發(fā)展，非數(shù)值計(jì)算問(wèn)題顯得越來(lái)越重要。據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值計(jì)算問(wèn)題占用了90%A上的機(jī)器時(shí)間。這類問(wèn)題涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無(wú)法用數(shù)學(xué)方程式加以描述。因此，解決這類問(wèn)題的關(guān)鍵不再是數(shù)學(xué)分析和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)。著名的瑞士計(jì)算機(jī)科學(xué)家沃思(N.Wirth )教授曾提出：算法+數(shù)據(jù)結(jié)構(gòu)=程序程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題設(shè)計(jì)/選擇好的數(shù)據(jù)結(jié)構(gòu)和好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。例1-1 電話號(hào)碼查詢問(wèn)題。編寫一個(gè)查詢某個(gè)私人電話號(hào)碼的程序。要求任意給出的 一個(gè)姓名，若該人有電話號(hào)碼，則迅

6、速找到其電話號(hào)碼；否則指出該人沒(méi)有電話號(hào)碼。要解決此問(wèn)題首先需構(gòu)造一張電話號(hào)碼登記表。表中每個(gè)結(jié)點(diǎn)存放兩個(gè)數(shù)據(jù)項(xiàng)：姓名和電話號(hào)碼。能否寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式。最簡(jiǎn)單的方式是將表中結(jié) 點(diǎn)順序地存儲(chǔ)在計(jì)算機(jī)中。查找時(shí)從頭開(kāi)始依次查對(duì)姓名，直到找出正確的姓名或是遍歷 整個(gè)表均沒(méi)有找到為止。這種查找算法對(duì)一個(gè)有少量私人電話的區(qū)域或許是可行的，但對(duì) 一個(gè)有成千上萬(wàn)私人電話的城市就不適用了。若這張表是按姓氏排列的，則可另建一張姓 氏索引表，采用如圖 1-2所示的存儲(chǔ)結(jié)構(gòu)。查找時(shí)先在左邊的索引表中查對(duì)姓氏，然后根 據(jù)索引表中的地址到右邊的電話號(hào)碼登記表中核查姓名，這樣查找登記表時(shí)就無(wú)

7、需查找其他姓氏的名字了。因此，在這種新的結(jié)構(gòu)上產(chǎn)生的查找算法就更加有效。諸如此類的還有電話自動(dòng)查號(hào)系統(tǒng)、考試查分系統(tǒng)、倉(cāng)庫(kù)庫(kù)存管理系統(tǒng)等。在這類文 檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著一種簡(jiǎn)單的線性關(guān)系。這類數(shù)學(xué) 模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。姓名電話號(hào)碼張二地址張明張 m 李張志a H.坐文 r李真圖1-2電話號(hào)碼的索引存儲(chǔ)例1-2 四皇后問(wèn)題，即在一個(gè) 4 4的棋盤上放置4個(gè)皇后，使得任意兩個(gè)皇后在行、 列和斜方向上都不在一條線上。在四皇后問(wèn)題中，處理過(guò)程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀

8、態(tài)開(kāi)始,一步步地進(jìn)行試探，每試探一步形成一種新的狀態(tài)，整個(gè)試探過(guò)程形成了一棵隱含的狀態(tài)樹(shù)， 如圖1-3所示?；厮莘ㄇ蠼膺^(guò)程實(shí)質(zhì)上就是一個(gè)遍歷狀態(tài)樹(shù)的過(guò)程。在這個(gè)問(wèn)題中所出現(xiàn)的樹(shù)也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計(jì)算的問(wèn)題中。圖1-3四皇后問(wèn)題中隱含的狀態(tài)樹(shù)例1-3田徑賽的時(shí)間安排問(wèn)題。假設(shè)某校的田徑選拔賽共設(shè)6個(gè)項(xiàng)目，即跳高、跳遠(yuǎn)、標(biāo)槍、鉛球、100米短跑和200米短跑，規(guī)定每個(gè)選手至多參加3個(gè)項(xiàng)目的比賽?，F(xiàn)有 5名選手報(bào)名參賽，選手所選擇的項(xiàng)目如表 1-2所示。要求設(shè)計(jì)一個(gè)競(jìng)賽日程安排表，使得在盡可能短的時(shí)間內(nèi)完成比賽。（1）首先選擇一種合適的數(shù)據(jù)結(jié)構(gòu)，如圖1-4所示。圖中頂點(diǎn)代表競(jìng)賽

9、項(xiàng)目，讓代表所連接的兩個(gè)競(jìng)賽項(xiàng)目的比賽時(shí)間不發(fā)生沖突，因此選手選擇的項(xiàng)目中應(yīng)該兩兩有邊相連。（2）競(jìng)賽項(xiàng)目的時(shí)間安排問(wèn)題可以抽象為對(duì)無(wú)向圖進(jìn)行“著色”操作，即用盡可能少的顏色給圖中每個(gè)頂點(diǎn)著色，使得任意兩個(gè)有邊連接的相鄰頂點(diǎn)具有不同的顏色。每一種顏色表示一個(gè)比賽時(shí)間，同一種顏色表示可以安排在同一時(shí)間進(jìn)行比賽。由此可得，只要安排4個(gè)不同的比賽時(shí)間即可。比如，在時(shí)間1比賽跳高（A）和標(biāo)槍（C）,在時(shí)間2比賽跳遠(yuǎn)（B）和鉛球（D）,在時(shí)間3和時(shí)間4分別比賽表1-2參賽選干比賽項(xiàng)目表100 米（E）和 200 米（F）。項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一跳高跳遠(yuǎn)100米馬剛標(biāo)槍鉛球張明標(biāo)槍100米200米李遠(yuǎn)強(qiáng)鉛

10、球200米跳高TV7跳遠(yuǎn)200米K1-4安排競(jìng)賽碩目的數(shù)據(jù)姑杓模型由以上3個(gè)例子可見(jiàn)，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)、圖之類的數(shù)據(jù)結(jié)構(gòu)。相應(yīng)地解決問(wèn)題的一個(gè)關(guān)鍵步驟是設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)表示該 問(wèn)題，然后才能寫出有效的算法。有關(guān)概念和術(shù)語(yǔ)在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，你應(yīng)該先了解一些基本概念和術(shù)語(yǔ)。數(shù)據(jù)（data ）是信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理。它可以是數(shù)值數(shù)據(jù)；也 可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像和語(yǔ)音等。數(shù)據(jù)元素（data element ）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元 素、結(jié)點(diǎn)、頂點(diǎn)和記錄等。一個(gè)數(shù)據(jù)元素可由若

11、干個(gè) 數(shù)據(jù)項(xiàng)（data item ）組成。例如，學(xué)生信息表中的一個(gè)記錄 可以包括學(xué)號(hào)、姓名、性別、籍貫、出生年月和成績(jī)等數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)可以分為兩種：一種 叫做原子項(xiàng)（如學(xué)生的性別、籍貫等），是數(shù)據(jù)處理時(shí)不能再分割的最小單位；另一種叫做組合項(xiàng)（如學(xué)生的成績(jī)，可以再劃分為數(shù)學(xué)、物理和化學(xué)等更小的項(xiàng)）。數(shù)據(jù)對(duì)象（data object ）或數(shù)據(jù)元素類（data element class）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問(wèn)題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），是數(shù)據(jù)元素類的一個(gè)實(shí)例，屬于同一個(gè)數(shù)據(jù)元素類。例如，例1-3中，所有的頂點(diǎn)集合是一個(gè)數(shù)據(jù)元素類，頂點(diǎn) A和頂點(diǎn)B各自代

12、表一個(gè)運(yùn)動(dòng)項(xiàng)目，是該數(shù)據(jù)元素類中的兩個(gè)實(shí)例。數(shù)據(jù)結(jié)構(gòu)（data structure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列4類基本結(jié)構(gòu)。集合結(jié)構(gòu)。其中所有的數(shù)據(jù)元素都屬于同一個(gè)集合。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)，因此也可用其他結(jié)構(gòu)來(lái)表示。線性結(jié)構(gòu)。數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。樹(shù)型結(jié)構(gòu)。數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。圖形結(jié)構(gòu)。數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。圖1-5表示了上述4類基本結(jié)構(gòu)的示意圖。(b)線性結(jié)構(gòu)圖1-54類基本結(jié)構(gòu)由此可知，一個(gè)數(shù)據(jù)結(jié)構(gòu)具有兩個(gè)要素：一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。

13、因此在形式上數(shù)據(jù)結(jié)構(gòu)可以采用一個(gè)二元組來(lái)表示。數(shù)據(jù)結(jié)構(gòu)的形式定義為：Data_Structure= ( D R其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。例如，復(fù)數(shù)可被定義為一種數(shù)據(jù)結(jié)構(gòu)Complex = ( D, R)D = x | x是實(shí)數(shù)R = v x , y > | x , y Dx稱為實(shí)部，y稱為虛部=。研究數(shù)據(jù)結(jié)構(gòu)主要是研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)操作。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)(或映像)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))，它表示數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，即數(shù)據(jù)結(jié)構(gòu)中元素及元素間關(guān)系的表示。操

14、作是數(shù)據(jù)結(jié)構(gòu)對(duì)外表現(xiàn)的行為或方法。1. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的邏輯關(guān)系，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 線性結(jié)構(gòu)的邏輯特征是，若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。例如，線性表、棧、隊(duì)列和串等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。例如，數(shù)組、廣義表、樹(shù)和圖等都是非線性結(jié)構(gòu)。2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一般來(lái)說(shuō)，一個(gè)存儲(chǔ)結(jié)構(gòu)包括以下3個(gè)主要部分。存儲(chǔ)結(jié)點(diǎn)：在不致混淆時(shí)簡(jiǎn)稱為結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。 數(shù)據(jù)元素之間的關(guān)聯(lián)方式表示。附加設(shè)施，如為便于運(yùn)算實(shí)現(xiàn)而設(shè)置的“啞結(jié)點(diǎn)”

15、等。同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。 一般可用以下4種基本存儲(chǔ)方法。(1)順序存儲(chǔ)方法。該方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里， 結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)方法為使用整數(shù)編碼訪問(wèn)數(shù)據(jù)結(jié)點(diǎn)提供了便利。順序存儲(chǔ)結(jié)構(gòu)中沒(méi)有存儲(chǔ)其他附加的信息，所以也稱為緊湊存儲(chǔ)結(jié)構(gòu)。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過(guò)某種線性化的方法實(shí)現(xiàn)順序存儲(chǔ)。(2) 鏈接存儲(chǔ)方法。該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，通常

16、借助于程序語(yǔ)言的指針類型描述。鏈接存儲(chǔ)方法適用于那些需要經(jīng)常進(jìn)行增刪結(jié)點(diǎn)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)。(3) 索引存儲(chǔ)方法。該方法是順序存儲(chǔ)方法的一種推廣，用于大小不等的數(shù)據(jù)結(jié)點(diǎn)的順序存儲(chǔ)。通過(guò)建造一個(gè)由整數(shù)域映射到存儲(chǔ)地址域的函數(shù)，把整數(shù)索引值映射到結(jié)點(diǎn)的存儲(chǔ)地址，從而形成一個(gè)存儲(chǔ)一串指針的索引表，每個(gè)指針指向存儲(chǔ)區(qū)域的一個(gè)數(shù)據(jù)結(jié)點(diǎn)。索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則稱該索引表為稠密索引(dense index )。若一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，則稱該索引表為稀疏索 引(spare in dex)。索引項(xiàng)的一般形式是：關(guān)鍵字地址關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)。稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置，稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。(4) 散列存儲(chǔ)方法。作為索引存儲(chǔ)方法的一種延伸和擴(kuò)展，散列存儲(chǔ)方法利用散列函數(shù) 進(jìn)行索引值的計(jì)算，然后通過(guò)索引表求出結(jié)點(diǎn)的指針地址。以上4種基本存儲(chǔ)方法既可單獨(dú)使用，