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

前言

　　本書是一本系統(tǒng)介紹數(shù)據(jù)結(jié)構(gòu)的教材。在本書的論述過程中會反復(fù)聯(lián)系到計算機(jī)領(lǐng)域的許多重要問題，包括問題求解，算法的分析與設(shè)計、抽象數(shù)據(jù)類型、程序設(shè)計方法、程序設(shè)計語言等內(nèi)容，根據(jù)目前計算機(jī)科學(xué)發(fā)展的情況，本書采用面向?qū)ο蟮乃枷虢M織與課程有關(guān)的內(nèi)容，運(yùn)用C++語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言，其目的是為了保證本書的先進(jìn)性和適用性。　　數(shù)據(jù)結(jié)構(gòu)的一般討論并不依賴于具體的語言，然而，在具體問題求解時，使用什么語言描述數(shù)據(jù)結(jié)構(gòu)會在很大程度上影響程序設(shè)計者的思維方式和方法，選擇一種實用的程序語言作為工作語言，有利于使討論更面向?qū)嶋H應(yīng)用，使參加課程學(xué)習(xí)的學(xué)生不僅可以掌握數(shù)據(jù)結(jié)構(gòu)的抽象概念和性質(zhì)，也有助于了解實現(xiàn)的思想和方法。　　由于程序設(shè)計語言的發(fā)展，適合用來討論數(shù)據(jù)結(jié)構(gòu)的語言越來越多，今天國際上新的數(shù)據(jù)結(jié)構(gòu)教材已經(jīng)不再用偽語言作為工具了，隨著面向?qū)ο蠓椒ǖ膹V泛應(yīng)用，許多學(xué)校已經(jīng)把C++語言定為學(xué)習(xí)計算機(jī)的第一種程序設(shè)計語言，越來越多的教材采用C++作為數(shù)據(jù)結(jié)構(gòu)的教學(xué)語言。　　在本書中，不僅討論了抽象的數(shù)據(jù)結(jié)構(gòu)，而且討論了各種數(shù)據(jù)結(jié)構(gòu)的不同實現(xiàn)方式并對它們進(jìn)行了比較，從中可以看到不同數(shù)據(jù)結(jié)構(gòu)的相互關(guān)系，包括結(jié)構(gòu)上的（邏輯）關(guān)系和實現(xiàn)上的（表示）關(guān)系。采用C++語言和面向?qū)ο蟮姆椒ㄖv解數(shù)據(jù)結(jié)構(gòu)，對這些關(guān)系的討論提供了有力的工具?！　∮捎贑++語言的一些優(yōu)點(diǎn)，特別是它的模板機(jī)制，使我們可以比較清晰地討論具有類型參數(shù)的數(shù)據(jù)結(jié)構(gòu)。例如，我們實現(xiàn)的不是整數(shù)的堆棧，也不是字符串的堆棧，而是一般的具有類型參數(shù)的堆棧。一個實現(xiàn)可以滿足各種程序?qū)τ诙褩５男枰?。這樣學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)不僅更接近那種抽象概念上的數(shù)據(jù)結(jié)構(gòu)，同時也可以直接用到不同類型對象的相同計算過程中去?！　”緯挠懻摿D反映計算機(jī)科學(xué)的最新發(fā)展，用面向?qū)ο蟮姆椒ńM織數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，以抽象數(shù)據(jù)類型的方式定義各種結(jié)構(gòu)的用戶界面，以時間和空間開銷作為評價各種結(jié)構(gòu)使用好壞的主要標(biāo)準(zhǔn)，從簡到繁，系統(tǒng)地介紹各種常用的數(shù)據(jù)結(jié)構(gòu)，強(qiáng)調(diào)不同結(jié)構(gòu)之間的聯(lián)系。書中采用C++語言描述各種類的界面和實現(xiàn)。把面向?qū)ο蟮某绦蛟O(shè)計方法與數(shù)據(jù)結(jié)構(gòu)的主要原理緊密結(jié)合起來，講解過程中還插入大量實例。讀者通過本書的學(xué)習(xí)不僅能掌握數(shù)據(jù)結(jié)構(gòu)的基本原理和基本方法，同時可以把所學(xué)的知識用于實際問題求解的過程之中。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)：C++與面向?qū)ο蟮耐緩剑ㄐ抻啺妫肥?998年6月出版的《數(shù)據(jù)結(jié)構(gòu)——C++與面向?qū)ο蟮耐緩健芬粫男抻啺?它采用面向?qū)ο蟮乃枷虢M織數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，運(yùn)用C什語言作為討論數(shù)據(jù)結(jié)構(gòu)的工作語言。在第一版的基礎(chǔ)上，除對各章的順序及內(nèi)容安排進(jìn)行了進(jìn)一步的調(diào)整之外，還補(bǔ)充了各章的例子、習(xí)題，并增加了若干上機(jī)實習(xí)題，使讀者可以更好地對數(shù)據(jù)結(jié)構(gòu)進(jìn)行學(xué)習(xí)、實踐.在《數(shù)據(jù)結(jié)構(gòu)：C++與面向?qū)ο蟮耐緩剑ㄐ抻啺妫返淖詈筮€附加了一個上機(jī)實習(xí)報告的例子，使其具有較強(qiáng)的實用性?！稊?shù)據(jù)結(jié)構(gòu)：C++與面向?qū)ο蟮耐緩剑ㄐ抻啺妫烦永m(xù)了第一版的風(fēng)格外，內(nèi)容更加充實、完整，，講解更加清楚、透徹?？勺鳛楸究朴嬎銠C(jī)專業(yè)或相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教材，也可作為面向?qū)ο蟪绦蛟O(shè)計課程或C++程序設(shè)計實踐課程的教材和參考書。

書籍目錄

第一章 緒論1.1 問題求解1.1.1 問題1.1.2 問題的分析1.].3 算法的選擇1.1.4 解的精化1.2 數(shù)據(jù)結(jié)構(gòu)1.3 算法1.3.1 算法的設(shè)計1.3.2 算法的分析1.4 抽象數(shù)據(jù)類型1.5 程序設(shè)計方法和語言小結(jié)習(xí)題第二章 C++與面向?qū)ο蟪醪?.1 C++語言對C的基本擴(kuò)充2.1.1 注釋2.1.2 函數(shù)原型說明2.1.3 引用和引用參數(shù)2.1.4 重載2.1.5 缺省參數(shù)2.1.6 變量說明2.1.7 輸入和輸出2.1.8 動態(tài)存儲分配2.1.9 類型定義2.1.10 強(qiáng)制類型轉(zhuǎn)換2.2 對象和類2.3 類的界面描述和實現(xiàn)2.3.1 類的數(shù)據(jù)域2.3.2 對象的行為——成員函數(shù)2.3.3 運(yùn)算符作為成員函數(shù)2.3.4 用構(gòu)造函數(shù)進(jìn)行實例的初始化2.4 普通運(yùn)算符和普通函數(shù)2.4.1 普通運(yùn)算符2.4.2 普通函數(shù)2.4.3 輸入和輸出2.5 類的合成、繼承和多態(tài)性2.5.1 合成2.5.2 繼承2.5.3 多態(tài)性小結(jié)習(xí)題第三章 字符串——數(shù)據(jù)封裝技術(shù)3.1 C語言的字符和字符串3.2 字符串?dāng)?shù)據(jù)抽象的描述和實現(xiàn)3.2.1 字符串類的定義3.2.2 構(gòu)造函數(shù)的定義3.2.3 析構(gòu)函數(shù)3.2.4 基本成員函數(shù)的實現(xiàn)3.2.5 比較運(yùn)算符3.2.6 串連接3.2.7 輸入和輸出3.3 子串3.4 模式匹配3.4.1 簡單字符串匹配3.4.2 Knuth-Morris.Pratt模式匹配算法3.4.3 Boycr－Moom字符串匹配算法小結(jié)習(xí)題第四章 向量——類的重用技術(shù)4.1 模板類4.2 向量的實現(xiàn)4.3 定界向量和枚舉向量、——繼承方式的重用4.3.1 定界向量4.3.2 枚舉向量4.4 排序向量和矩陣——合成方式的重用4.4.1 排序向量和二分法檢索4.4.2 矩陣4.5 向量遍歷器4.5.1 遍歷器的抽象4.5.2 向量遍歷器4.6 向量的排序——模板函數(shù)4.6.1 插入排序4.6.2 起泡排序4.6.3 選擇排序4.6.4 快速排序算法4.7 繼承和多態(tài)的若干討論4.7.1 父類與子類4.7.2 靜態(tài)類型和動態(tài)類型4.7.3 框架和框架類4.7.4 蔽和虛函數(shù)4.7.5 虛遮蔽和非虛遮蔽4.7.6 兩類繼承4.7.7 多態(tài)的主要形式4.7.8 參數(shù)多態(tài)性——?dú)w約4.7.9 切割問題小結(jié)習(xí)題第五章 動態(tài)數(shù)據(jù)結(jié)構(gòu)——鏈表5.1 單鏈表的定義5.1.1 表類5.1.2 鏈類5.2 單鏈表的實現(xiàn)5.2.1 鏈類的實現(xiàn)5.2.2 表類的實現(xiàn)5.3 表遍歷器5.3.1 表遍歷器類5.3.2 表遍歷器類的實現(xiàn)表的應(yīng)用：多項式處理5.4.1 項類5.4.2 多項式類5.5 排序表5.5.1 排序表類5.5.2 排序表類的實現(xiàn)5.5.3 排序表的應(yīng)用——表插入排序5.6 其他鏈表5.6.1 自組織表5.6.2 雙端表5.6.3 循環(huán)表5.6.4 雙鏈表5.7 可利用空間表小結(jié)習(xí)題第六章 棧和隊列6.1 抽象類棧和隊列6.2 棧的實現(xiàn)6.2.1 棧的向量實現(xiàn)6.2.2 棧的鏈表實現(xiàn)6.3 棧的應(yīng)用——表達(dá)式計算6.3.1 后綴表達(dá)式的求值6.3.2 中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換6.4 隊列的實現(xiàn)6.4.1 隊列的向量實現(xiàn)6.4.2 隊列的鏈表實現(xiàn)6.5 隊列的應(yīng)用——農(nóng)夫過河問題小結(jié)習(xí)題第七章 樹和二叉樹7.1 基本概念7.1.1 樹7.1.2 二叉樹山7.1.3 樹與二叉樹的關(guān)系7.2 二叉樹的實現(xiàn)7.2.1 二叉樹結(jié)點(diǎn)類7.2.2 基本二叉樹類7.2.3 可構(gòu)造二叉樹類7.3 二叉樹的周游7.3.1 周游的遞歸實現(xiàn)7.3.2 通過遍歷器實現(xiàn)周游7.3.3 前序周游器類7.3.4 中序周游器類7.3.5 后序周游器類7.3.6 層次周游算法(按寬度方向周游)7.4 二叉樹的向量表示7.4.1 二叉樹向量表示的一種基本方法7.4.2 記錄結(jié)構(gòu)信息的二叉樹向量表示7.5 二叉排序樹7.6 平衡的二叉排序樹7.6.1 AVL樹上的操作7.6.2 AVL樹的設(shè)計與實現(xiàn)7.7 二叉樹的應(yīng)用——哈夫曼樹小結(jié)習(xí)題第八章 優(yōu)先隊列8.1 優(yōu)先隊列的抽象8.2 堆8.3 堆排序8.4 斜堆8.5 離散事件模擬8.5.1 模擬類的結(jié)構(gòu)8.5.2 冰淇淋店的模擬8.5.3 隨機(jī)數(shù)小結(jié)習(xí)題第九章 集合與字典9.1 集合及其運(yùn)算9.1.1 集合運(yùn)算9.1.2 集合類9.2 位向量集合9.2.1 位向量9.2.2 位向量集合9.2.3 字符集合9.2.4 字符集類的應(yīng)用——將字符串分解為單詞9.3 集合的表實現(xiàn)9.4 關(guān)聯(lián)與字典9.5 字典的關(guān)聯(lián)表實現(xiàn)9.6 字典的應(yīng)用9.6.1 稀疏矩陣9.6.2 排序字典9.6.3 索引的實現(xiàn)小結(jié)習(xí)題第十章 散列結(jié)構(gòu)10.1 散列結(jié)構(gòu)10.2 散列函數(shù)10.3 開地址散列向量10.4 桶散列——用桶解決碰撞10.4.1 桶散列的抽象模板類10.4.2 用樹作為桶的實現(xiàn)10.4.3 桶散列結(jié)構(gòu)操作時間的分析10.5 桶散列結(jié)構(gòu)的遍歷器10.6 用散列表實現(xiàn)集合10.6.1 應(yīng)用——拼寫檢查器10.7 用桶散列表實現(xiàn)字典小結(jié)習(xí)題第十一章 圖11.1 基本概念11.2 圖的鄰接矩陣表示和Warshall算法11.2.1 圖的鄰接矩陣表示11.2.2 圖結(jié)點(diǎn)的可達(dá)性問題11.3 鄰接表方式的圖表示和深度優(yōu)先搜索11.3.1 鄰接表表示中的結(jié)點(diǎn)類11.3.2 用深度優(yōu)先方式求解可達(dá)性問題11.4 帶權(quán)圖的矩陣表示和Floyd算法11.4.1 帶權(quán)圖的鄰接矩陣11.4.2 帶權(quán)圖最短路徑問題Floyd算法11.5 帶權(quán)圖的鄰接表表示與Dijkstra算法11.5.1 帶權(quán)圖的鄰接表表示11.5 ，2從一個結(jié)點(diǎn)出發(fā)的最短路徑和Dijkstra算法11.6 連通性、帶權(quán)連通無向圖與最小生成樹11.7 有限自動機(jī)11.8 拓?fù)渑判蛐〗Y(jié)習(xí)題第十二章 文件12.1 外存、文件及其問題12.1.1 外存儲器的特點(diǎn)與信息組織12.1.2 文件基本結(jié)構(gòu)和操作12.1.3 文件與字典12.1.4 文件組織12.2 C++的字符流文件及其操作12.3 歸并排序12.4 文件的隨機(jī)訪問12.5 文件索引結(jié)構(gòu)12.5.1 索引向量12.5.2 樹形索引結(jié)構(gòu)12.5.3 B樹12.5.4 B+樹12.6 樹索引文件的實現(xiàn)小結(jié)習(xí)題附錄附錄A 主要抽象數(shù)據(jù)類及其相互關(guān)系附錄B BorlandC++集成開發(fā)環(huán)境使用入門附錄C “多叉路口的交通管理系統(tǒng)上機(jī)報告

章節(jié)摘錄

　　另一種常用的算法設(shè)計方法稱為“分治法”，其基本思想是：把一個規(guī)模較大的問題分成兩個或多個較小的與原問題相似的子問題。首先對子問題進(jìn)行求解，然后設(shè)法把子問題的解合并起來，得出整個問題的解，即對問題分而治之。如果一個子問題的規(guī)模仍然比較大，不能很容易地求得解，就可以對這個子問題重復(fù)地應(yīng)用分治策略?！　　岸址z索”就是用分治策略的典型例子。如果要在一個整數(shù)的有序數(shù)組（可以假設(shè)元素按增序排列）中找一個數(shù)，要求查出這個數(shù)在這個數(shù)組里的位置，二分法檢索采用的方法是先找到數(shù)組中居于中間位置的元素，將該元素與所找數(shù)字進(jìn)行比較，如果所查數(shù)字比較小，那么它一定不會出現(xiàn)在中間元素的右邊，下面只需在左半個數(shù)組中檢索。反過來，若所查數(shù)字較大，則不必在左半個數(shù)組中繼續(xù)尋找，只需在右半個數(shù)組中檢索。這樣，通過一次比較就能夠排除掉一半元素。再做下去，只要對剩下的半個數(shù)組重復(fù)使用同樣方式，又可以再排除掉四分之一的元素，如此重復(fù)若干次就能很快確定整數(shù)的存在與否，并確定如果存在時它在什么位置?！　∵€有一類常用算法被稱為“回溯法”。有一些問題，只能通過徹底搜索所有可能情況尋找一個滿足某些預(yù)定條件的最優(yōu)解。由于徹底搜索的運(yùn)算量通常非常大，往往大到使用計算機(jī)也不能在合理時間內(nèi)得到解。回溯算法是處理這類問題的一個方法，基本思想是一步一步向前試探，當(dāng)有多種選擇時可以任意選擇一種，只要可行（或暫時沒有失敗）就繼續(xù)向前，一旦發(fā)現(xiàn)問題或失敗就后退，回到上一步重新選擇，借助于回溯技巧和中間判斷，常?？梢源蟠蟮販p少搜索時間。常見的迷宮問題以及八皇后問題都可以用回溯方法來解決。　　除上面提到的幾種典型方法外，常用的算法設(shè)計方法還有“動態(tài)規(guī)劃”、“局部搜索”和“分支限界”等?！　”緯谟懻摂?shù)據(jù)結(jié)構(gòu)的同時，自然涉及與數(shù)據(jù)結(jié)構(gòu)相關(guān)的許多算法，掌握這些算法的設(shè)計方法和共性，對于提高程序設(shè)計的水平是十分重要的。

圖書封面

評論、評分、閱讀與下載

---

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

---