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

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

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

---

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

---