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

前言

數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)以及其他一些和計算機技術(shù)關(guān)系密切的專業(yè)的一門核心必修課程。數(shù)據(jù)結(jié)構(gòu)課程的任務是討論現(xiàn)實世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計算機中的存儲結(jié)構(gòu)以及實現(xiàn)各種操作的算法設計問題。數(shù)據(jù)結(jié)構(gòu)課程的目的是使學生掌握組織數(shù)據(jù)、存儲數(shù)據(jù)和處理數(shù)據(jù)的基本方法，從而為以后進行軟件開發(fā)和應用、進一步學習后續(xù)專業(yè)課程打下堅實的基礎(chǔ)。計算機軟件開發(fā)方法是不斷發(fā)展的，數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容也應隨著軟件開發(fā)方法的不斷發(fā)展而發(fā)展。目前面向?qū)ο蟮能浖治龊驮O計技術(shù)已發(fā)展成為軟件開發(fā)的主流方法，因此，用面向?qū)ο蟮姆椒枋鰯?shù)據(jù)結(jié)構(gòu)就成為數(shù)據(jù)結(jié)構(gòu)課程改革的必然。用面向?qū)ο蟮挠^點描述具體的數(shù)據(jù)結(jié)構(gòu)問題時，首先涉及選用什么樣的面向?qū)ο蟮母呒壵Z言問題。c++語言是目前最普遍使用的面向?qū)ο蟪绦蛟O計的最底層語言，因此本書采用c++語言作為數(shù)據(jù)結(jié)構(gòu)的描述語言。數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實踐結(jié)合密切的課程。數(shù)據(jù)結(jié)構(gòu)教材的編寫方法有兩種：一種是注重理論基礎(chǔ)，另一種是注重實踐應用?？紤]到高職高專和成人教育等的特點，本書采用理論敘述簡明、應用實例豐富的方法編寫。數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)，本書討論的內(nèi)容主要包括：線性表、堆棧、隊列、串、數(shù)組、樹、二叉樹、圖、排序、查找以及遞歸。其中，線性表、堆棧、隊列、串和數(shù)組屬于線性結(jié)構(gòu)，樹和二叉樹屬于樹結(jié)構(gòu)，圖屬于圖結(jié)構(gòu)，排序和查找是線性結(jié)構(gòu)問題中兩個應用最廣泛的算法設計問題。樹結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。很多非線性結(jié)構(gòu)的算法設計問題需要使用遞歸方法，因此，本書專設一章討論遞歸的概念和遞歸算法的設計方法。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)（C++語言描述）》為普通高等教育“十五”國家級規(guī)劃教材。全書系統(tǒng)地介紹了各種類型的數(shù)據(jù)結(jié)構(gòu)和查找、排序的各種方法。對于每一種類型的數(shù)據(jù)結(jié)構(gòu)，都詳細闡述了基本概念、各種不同的存儲結(jié)構(gòu)和不同存儲結(jié)構(gòu)上一些主要操作的實現(xiàn)算法，并給出了許多設計實例，以幫助讀者理解。另外，書中還介紹了遞歸算法的設計方法。全書采用C++語言作為算法描述語言。為方便學習，附錄中還給出了部分典型習題解答。　　《數(shù)據(jù)結(jié)構(gòu)（C++語言描述）》既可作為高等學校應用型本科計算機相關(guān)專業(yè)、成人及高職高專計算機相關(guān)專業(yè)的教材，也可作為從事計算機應用的工程技術(shù)人員的自學參考書。

書籍目錄

第0章 C++程序設計基礎(chǔ)0．1 程序的結(jié)構(gòu)0．2 函數(shù)0．2．1 函數(shù)參數(shù)0．2．2 函數(shù)的返回值0．2．3 重載0．3 類0．3．1 訪問權(quán)限0．3．2 構(gòu)造函數(shù)和析構(gòu)函數(shù)0．3．3 運算符重載0．3．4 友元0．3．5 分辨符0．3．6 內(nèi)聯(lián)函數(shù)0．3．7 默認值0．3．8 派生類和繼承性0．3．9 多態(tài)性和虛函數(shù)0．3．10 純虛函數(shù)和抽象類0．3．11 結(jié)構(gòu)體0．3．12 對象0．4 通用化的軟件設計0．4．1 抽象數(shù)據(jù)類型0．4．2 模板0．5 動態(tài)申請和動態(tài)釋放內(nèi)存習題第1章 緒論1．1 數(shù)據(jù)結(jié)構(gòu)的基本概念1．2 抽象數(shù)據(jù)類型和軟件構(gòu)造方法1．3 算法及其時間復雜度1．3．1 算法1．3．2 算法設計目標1、3．3 算法時間效率的度量1．4 算法書寫規(guī)范習題第2章 線性表2．1 線性表抽象數(shù)據(jù)類型2．1．1 線性表的定義2．1．2 線性表抽象數(shù)據(jù)類型2．2 順序表類2．2．1 順序表的存儲結(jié)構(gòu)2．2．2 順序表類定義2．2．3 順序表類實現(xiàn)2．2．4 順序表類方法的效率分析2．2．5 順序表類應用舉例2．3 單鏈表類2．3．1 單鏈表的結(jié)構(gòu)2．3．2 單鏈表的動態(tài)內(nèi)存分配方法2．3．3 結(jié)點類的定義和實現(xiàn)2．3．4 單鏈表類的定義和實現(xiàn)2．3．5 單鏈表操作的效率分析2．3．6 單鏈表應用舉例2．4 循環(huán)單鏈表2．5 雙向鏈表2．6 靜態(tài)鏈表2．7 設計舉例2．7．1 順序表設計舉例2．7．2 單鏈表設計舉例習題第3章 堆棧和隊列3．1 堆棧3．1．1 堆棧的基本概念3．1．2 堆棧抽象數(shù)據(jù)類型3．1．3 順序堆棧類3．1．4 鏈式堆棧類3．2 堆棧應用3．2．1 括號匹配問題3．2．2 表達式計算問題3．3 隊列3．3．1 隊列的基本概念3．3．2 隊列抽象數(shù)據(jù)類型3．3．3 順序隊列3．3．4 順序循環(huán)隊列類3．3．5 鏈式隊列類3．3．6 隊列的應用3．4 優(yōu)先級隊列3．4．1 順序優(yōu)先級隊列類3．4．2 優(yōu)先級隊列的應用習題第4章 串4．1 串的基本概念、抽象數(shù)據(jù)類型和c++語言的串函數(shù)4．1．1 串的基本概念4．1．2 串的抽象數(shù)據(jù)類型4．1．3 C++語言的串函數(shù)4．2 串的存儲結(jié)構(gòu)4．2．1 串的順序存儲結(jié)構(gòu)4．2．2 串的鏈式存儲結(jié)構(gòu)4．3 順序串類4．3．1 順序串類的定義4．3．2 構(gòu)造函數(shù)和析構(gòu)函數(shù)4．3．3 插入、刪除和取子串成員函數(shù)4．3．4 常用操作符重載4．3．5 邏輯操作符重載4．3．6 順序串類的測試4．4 串的模式匹配算法4．4．1 Brute—Force算法4．4．2 KMP算法4．4．3 Brute—Force算法和KMP算法的運行效率比較習題第5章 數(shù)組5．1 數(shù)組的基本概念5．1．1 數(shù)組的定義5．1．2 數(shù)組的實現(xiàn)機制5．1．3 數(shù)組抽象數(shù)據(jù)類型5．2 動態(tài)數(shù)組類5．3 特殊矩陣5．3．1 特殊矩陣的壓縮存儲5．3．2 n階對稱矩陣順序表類5．4 稀疏矩陣5．4．1 稀疏矩陣的壓縮存儲5．4．2 三元組順序表類5．4 三元組鏈表習題第6章 遞歸算法6．1 遞歸的概念6．2 遞歸算法的執(zhí)行過程6．3 遞歸算法的設計方法6．4 遞歸過程和運行時棧6．5 遞歸算法的效率分析6．6 遞歸算法到非遞歸算法的轉(zhuǎn)換6．7 設計舉例6．7．1 一般遞歸函數(shù)設計舉例6．7．2 回溯法及其設計舉例習題第7章 樹和二叉樹7．1 樹7．1．1 樹的定義7．1．2 樹的表示方法7．1．3 樹的抽象數(shù)據(jù)類型7．1．4 樹的存儲結(jié)構(gòu)7．2 二叉樹7．2．1 二叉樹的定義7．2．2 二叉樹抽象數(shù)據(jù)類型7．2．3 二叉樹的性質(zhì)7．2．4 二叉樹的存儲結(jié)構(gòu)7．3 以結(jié)點類為基礎(chǔ)的二叉樹設計7．3．1 二叉樹的結(jié)點類7．3．2 二叉樹的遍歷7．3．3 二叉樹遍歷的應用7．3．4 應用舉例_7．3．5 非遞歸的二叉樹遍歷算法7．4 二叉樹類7．5 二叉樹的分步遍歷7．5．1 二叉樹遍歷游標類7．5．2 二叉樹中序遍歷游標類7．5．3 二叉樹層序遍歷游標類7．6 線索二叉樹7．7 哈夫曼樹7．7．1 哈夫曼樹的基本概念7．7．2 哈夫曼編碼問題7．7．3 哈夫曼編碼的軟件設計7．8 樹與二叉樹的轉(zhuǎn)換7．9 樹的遍歷習題第8章 圖8．1 圖的基本概念和抽象數(shù)據(jù)類型8．1．1 圖的基本概念8．1．2 圖的抽象數(shù)據(jù)類型8．2 圖的存儲結(jié)構(gòu)8．2．1 圖的鄰接矩陣存儲結(jié)構(gòu)8．2．2 圖的鄰接表存儲結(jié)構(gòu)8．3 鄰接矩陣圖類8．4 圖的遍歷8．4．1 圖的深度和廣度優(yōu)先遍歷算法8．4．2 圖的深度和廣度優(yōu)先遍歷函數(shù)實現(xiàn)8．5 最小生成樹8．5．1 最小生成樹的基本概念8．5．2 普里姆算法8．5．3 克魯斯卡爾算法8．6 最短路徑8．6．1 最短路徑的基本概念8．6．2 從一個頂點到其余各頂點的最短路徑8．6．3 每對頂點之間的最短路徑習題第9章 排序9．1 排序的基本概念9．2 插入排序9．2．1 直接插入排序9．2．2 希爾排序9．3 選擇排序9．3．1 直接選擇排序9．3．2 堆排序9．4 交換排序9．4．1 冒泡排序9．4．2 快速排序9．5 歸并排序9．6 基數(shù)排序9．7 性能比較習題第10章 查找10．1 查找的基本概念10．2 靜態(tài)查找表10．2．1 順序表10．2．2 有序順序表10．2．3 索引順序表10．3 動態(tài)查找表10．3．1 二叉排序樹10．3．2 B一樹10．4 哈希表10．4．1 哈希表的基本概念10．4．2 哈希函數(shù)構(gòu)造方法10．4．3 哈希沖突解決方法10．4．4 哈希表類習題附錄部分典型習題解答參考文獻

章節(jié)摘錄

插圖：0．3．2構(gòu)造函數(shù)和析構(gòu)函數(shù)構(gòu)造函數(shù)是當定義對象時被自動調(diào)用的特殊成員函數(shù)，構(gòu)造函數(shù)是用來在內(nèi)存中建立類的具體對象（即在內(nèi)存中為該對象分配適當?shù)目臻g）并對其進行初始化賦值的成員函數(shù)。構(gòu)造函數(shù)的名字必須和類的名字相同，構(gòu)造函數(shù)沒有返回值。構(gòu)造函數(shù)允許有默認值，當構(gòu)造函數(shù)有默認值時，若定義該類的對象時沒有給出初始化值，按默認值處理。例0—4中對象h有初始化值（plus，3，30），對象g和hg沒有初始化值，因此對象g和hg的初始化值為默認值（plus，0，0）。一個類允許有多個構(gòu)造函數(shù)，當一個類有多個構(gòu)造函數(shù)時，系統(tǒng)將根據(jù)定義對象時的參數(shù)類型和參數(shù)個數(shù)選擇恰當?shù)臉?gòu)造函數(shù)來建立對象和對該對象進行初始化。析構(gòu)函數(shù)是當對象被撤銷時被自動調(diào)用的特殊成員函數(shù)。當一個對象被撤銷時，析構(gòu)函數(shù)提供了釋放該類對象占用內(nèi)存空間的方法。析構(gòu)函數(shù)的名字是在類的名字前面加上前綴～。析構(gòu)函數(shù)沒有返回值。如果對象的內(nèi)存空間是用非動態(tài)方法建立的，該類對象被撤銷時系統(tǒng)能自動識別出這些對象占用的內(nèi)存空間，此種情況下析構(gòu)函數(shù)的函數(shù)體為空。當析構(gòu)函數(shù)的函數(shù)體為空時，C++允許省略析構(gòu)函數(shù)。如果對象的內(nèi)存空間是用動態(tài)方法建立的，該類對象被撤銷時系統(tǒng)不能識別出這些對象占用的內(nèi)存空間，需要通過系統(tǒng)自動調(diào)用析構(gòu)函數(shù)來釋放此類對象占用的內(nèi)存空間，此種情況下析構(gòu)函數(shù)的函數(shù)體不能為空。每個類只能有一個析構(gòu)函數(shù)。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)(C++語言描述)》為普通高等教育十五國家級規(guī)劃教材之一。

圖書封面

評論、評分、閱讀與下載

---

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

---