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

前言

　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)各專業(yè)以及其他相近專業(yè)的核心課程之一，其研究對(duì)象為問(wèn)題求解方法、程序設(shè)計(jì)方法和典型的數(shù)據(jù)結(jié)構(gòu)算法?！　”緯?shū)根據(jù)現(xiàn)代教育教學(xué)特點(diǎn)，充分考慮到一般本科院校學(xué)校計(jì)算機(jī)及其相關(guān)專業(yè)的現(xiàn)狀，嚴(yán)格遵循教育部計(jì)算機(jī)及相關(guān)專業(yè)研究生考試大綱的要求，吸收國(guó)外教材的一些新思想，既有創(chuàng)新，又兼顧了傳統(tǒng)教材的優(yōu)點(diǎn)。把教師的教學(xué)要求與學(xué)生學(xué)習(xí)、實(shí)際工作需要和進(jìn)一步深造等需求緊密結(jié)合起來(lái)?！　”緯?shū)既考慮數(shù)據(jù)結(jié)構(gòu)的組織方式，又強(qiáng)化算法的實(shí)踐與應(yīng)用。采用自上而下的設(shè)計(jì)方法，從抽象的數(shù)據(jù)結(jié)構(gòu)描述到數(shù)據(jù)結(jié)構(gòu)的組織，再到操作的具體實(shí)現(xiàn)，并通過(guò)實(shí)例說(shuō)明應(yīng)用方法。這種組織方法的目的是：為了使學(xué)生在學(xué)習(xí)過(guò)程中更好地分析研究計(jì)算機(jī)加工數(shù)據(jù)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的操作方法，通過(guò)程序設(shè)計(jì)實(shí)現(xiàn)相應(yīng)的算法，求得相關(guān)問(wèn)題的解，并能掌握算法的時(shí)間分析和空間分析技術(shù)。使學(xué)生通過(guò)實(shí)現(xiàn)算法的復(fù)雜程序訓(xùn)練，編寫(xiě)出結(jié)構(gòu)清晰、正確易讀、符合軟件工程規(guī)范的程序。使教師方便組織教學(xué)內(nèi)容，教學(xué)過(guò)程結(jié)構(gòu)清晰，內(nèi)容循序漸進(jìn)易于講解。　　本書(shū)使用標(biāo)準(zhǔn)C++作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言。采用C++語(yǔ)言中的類(lèi)來(lái)表示抽象數(shù)據(jù)類(lèi)型（ADT）；盡可能用C++的類(lèi)和面向?qū)ο蠼Y(jié)構(gòu)來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的算法。對(duì)基本的數(shù)據(jù)結(jié)構(gòu)采用面向?qū)ο蟮姆椒ǎ瑢?shù)據(jù)與對(duì)象封裝成類(lèi)，以便在其他應(yīng)用程序中直接使用?！　”緯?shū)讀者應(yīng)已經(jīng)修完程序設(shè)計(jì)課程并熟悉標(biāo)準(zhǔn)C++語(yǔ)言，所使用的C++代碼均在VC++編譯器上全部通過(guò)測(cè)試?！　”緯?shū)是多位老師多年來(lái)從事數(shù)據(jù)結(jié)構(gòu)教學(xué)的智慧和經(jīng)驗(yàn)的結(jié)晶，提供了豐富的教學(xué)輔助手段，其配套教材有《數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程》和《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題集》，同時(shí)由清華大學(xué)出版社出版。這些輔助教材為數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)和學(xué)習(xí)提供了有效的保障。數(shù)據(jù)結(jié)構(gòu)前言本書(shū)第1章、第6章和第7章由管致錦編寫(xiě)，第2章～第5章由徐慧編寫(xiě)，第8章和第9章由陳德裕編寫(xiě)，全書(shū)的統(tǒng)稿由管致錦負(fù)責(zé)。杭月芹、顧頎、周建美、丁衛(wèi)平、陳蘇蓉、顧衛(wèi)江、丁紅、章雅娟、周潔、朱穎等對(duì)本書(shū)進(jìn)行了詳細(xì)審閱，并提出了寶貴意見(jiàn)。聶志浪、趙戈杰、凡剛、陳驚雷、禹杰等同學(xué)完成了本書(shū)大部分算法代碼的測(cè)試工作?！　”緯?shū)及其配套教材編寫(xiě)和實(shí)踐過(guò)程歷時(shí)3年，盡管做了大量的努力，也難免存在不妥和錯(cuò)誤之處，懇請(qǐng)讀者予以指正，我們也會(huì)在適當(dāng)時(shí)間進(jìn)行修訂和補(bǔ)充，同時(shí)對(duì)教材中引用和參考的其他同行的文獻(xiàn)資料在此一并致以感謝。

內(nèi)容概要

本書(shū)根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，充分考慮到教師教學(xué)、學(xué)生學(xué)習(xí)與進(jìn)一步深造，以及相關(guān)人員實(shí)際工作需要，在處理好數(shù)據(jù)結(jié)構(gòu)的組織方式和強(qiáng)化算法的實(shí)踐與應(yīng)用的同時(shí)，使學(xué)生通過(guò)實(shí)現(xiàn)算法的復(fù)雜程序訓(xùn)練，編寫(xiě)出結(jié)構(gòu)清晰、正確易讀、符合軟件工程規(guī)范的程序；使教師方便組織教學(xué)內(nèi)容，教學(xué)過(guò)程結(jié)構(gòu)清晰，內(nèi)容循序漸進(jìn)且易于講解。    本書(shū)符合教育部計(jì)算機(jī)及相關(guān)專業(yè)研究生考試大綱對(duì)數(shù)據(jù)結(jié)構(gòu)內(nèi)容的要求。    本書(shū)使用C++作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言。采用C++語(yǔ)言中的類(lèi)來(lái)表示抽象數(shù)據(jù)類(lèi)型(ADT)，用C++的類(lèi)和面向?qū)ο蠼Y(jié)構(gòu)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的算法。所使用的C++代碼在Visual C++編譯器上全部通過(guò)測(cè)試。    為了方便本書(shū)的學(xué)習(xí)和教學(xué)，提供有配套教材《數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程》、《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題集》和相關(guān)的學(xué)習(xí)課件，本系列教材的所有源代碼都可以從清華大學(xué)出版社網(wǎng)站(http：／／www．tup．corn)上免費(fèi)下載。    本書(shū)可作為計(jì)算機(jī)類(lèi)及其相關(guān)專業(yè)的教材，也可供從事計(jì)算機(jī)工程與應(yīng)用的科技工作者參考。

書(shū)籍目錄

第1章 緒論  1.1 數(shù)據(jù)結(jié)構(gòu)的概念    1.1.1 引言    1.1.2 數(shù)據(jù)結(jié)構(gòu)的發(fā)展及其在計(jì)算機(jī)科學(xué)中所處的地位    1.1.3 什么是數(shù)據(jù)結(jié)構(gòu)    1.1.4 有關(guān)概念和術(shù)語(yǔ)  1.2 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型    1.2.1 數(shù)據(jù)類(lèi)型    1.2.2 抽象數(shù)據(jù)類(lèi)型  1.3 算法和算法分析    1.3.1 算法特性    1.3.2 算法描述    1.3.3 算法性能分析與度量第2章 線性表  2.1 線性表的類(lèi)型定義  2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)    2.2.1 線性表的順序存儲(chǔ)    2.2.2 順序表的實(shí)現(xiàn)  2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)    2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)    2.3.2 單鏈表的實(shí)現(xiàn)    2.3.3 其他形式的鏈表  2.4 線性表的其他存儲(chǔ)方法    2.4.1 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較    2.4.2 靜態(tài)鏈表    2.4.3 間接尋址  2.5 線性表應(yīng)用舉例第3章 特殊線性表  3.1 棧    3.1.1 棧的邏輯結(jié)構(gòu)    3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)    3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)    3.1.4 順序棧和鏈棧的比較    3.1.5 棧的應(yīng)用舉例  3.2 隊(duì)列    3.2.1 隊(duì)列的邏輯結(jié)構(gòu)    3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)    3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)    3.2.4 隊(duì)列的應(yīng)用第4章 串及其模式匹配  4.1 串的定義    4.1.1 串的相關(guān)概念    4.1.2 串的抽象數(shù)據(jù)類(lèi)型定義  4.2 串的存儲(chǔ)結(jié)構(gòu)    4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)    4.2.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)    4.2.3 串的索引存儲(chǔ)結(jié)構(gòu)    4.2.4 串的堆存儲(chǔ)  4.3 順序串的實(shí)現(xiàn)    4.3.1 常用C++字符串函數(shù)    4.3.2 串類(lèi)  4.4 串操作舉例  4.5 模式匹配第5章 廣義線性表  5.1 數(shù)組    5.1.1 數(shù)組的定義    5.1.2 數(shù)組的順序存儲(chǔ)   5.2 矩陣的壓縮存儲(chǔ)   5.2.1 特殊矩陣的壓縮存儲(chǔ)    5.2.2 稀疏矩陣的壓縮存儲(chǔ)    5.2.3 稀疏矩陣的運(yùn)算  5.3 廣義表  ……第6章 樹(shù)和二叉樹(shù)第7章 圖第8章 查找第9章 排序參考文獻(xiàn)

章節(jié)摘錄

　　算法（algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)該具有下列特性?！　。?）有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成?！　。?）確定性。算法的每一步必須有確切的定義，無(wú)二義性.算法的執(zhí)行對(duì)應(yīng)著相同的輸入僅有唯一的一條路徑?！　。?）可行性。算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行得以實(shí)現(xiàn)?！　。?）輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合?！　。?）輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，這些輸出同輸入之間存在某種特定的關(guān)系。　　算法的含義與程序十分相似，但又有區(qū)別。一個(gè)程序不一定滿足有窮性。例如操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會(huì)停止，即使沒(méi)有作業(yè)需要處理，它仍處于動(dòng)態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。另一方面，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。算法代表了對(duì)問(wèn)題的解，而程序則是算法在計(jì)算機(jī)上的特定實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來(lái)描述，則它就是一個(gè)程序?！　∷惴ㄅc數(shù)據(jù)結(jié)構(gòu)是相輔相成的。解決某一特定類(lèi)型問(wèn)題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來(lái)體現(xiàn)?！　∫O(shè)計(jì)一個(gè)好的算法通常要考慮以下要求。　?。?）正確性。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求?！　。?）可讀性。一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂?！　。?）健壯性。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至于引起嚴(yán)重后果?！　。?）高效性。有較高的時(shí)間效率并能有效使用存儲(chǔ)空間。

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---