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

內(nèi)容概要

　　本書是國(guó)家精品課程教材，以教育部計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)發(fā)布的“高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)本科專業(yè)規(guī)范”為依據(jù)，以基本數(shù)據(jù)結(jié)構(gòu)為知識(shí)單元而編寫。全書共分12章，包括引論、表、棧、隊(duì)列、排序與選擇、樹、圖、集合、符號(hào)表、字典、優(yōu)先隊(duì)列、并查集等。
　　全書采用C語(yǔ)言作為描述語(yǔ)言，內(nèi)容豐富，敘述簡(jiǎn)明，理論與實(shí)踐并重，每章設(shè)有應(yīng)用舉例和算法實(shí)驗(yàn)題，并為任課教師免費(fèi)提供電子課件和課程實(shí)驗(yàn)用數(shù)據(jù)。

書籍目錄

第1章 引論
　1.1 算法及其復(fù)雜性的概念
　1.1.1 算法與程序
　1.1.2 算法復(fù)雜性的概念
　1.1.3 算法復(fù)雜性的漸近性態(tài)
　1.2 算法的表達(dá)與數(shù)據(jù)表示
　1.2.1 問(wèn)題求解
　1.2.2 表達(dá)算法的抽象機(jī)制
　1.3 抽象數(shù)據(jù)類型
　1.3.1 抽象數(shù)據(jù)類型的基本概念
　1.3.2 使用抽象數(shù)據(jù)類型的好處
　1.4 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型
　1.5 用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)與算法
　1.5.1 變量和指針
　1.5.2 函數(shù)與參數(shù)傳遞
　1.5.3 結(jié)構(gòu)
　1.5.4 動(dòng)態(tài)存儲(chǔ)分配
　1.6 遞歸
　1.6.1 遞歸的基本概念
　1.6.2 間接遞歸
　本章小結(jié)
　習(xí)題1
　算法實(shí)驗(yàn)1
　算法實(shí)驗(yàn)題1.1 哥德巴赫猜想問(wèn)題
　算法實(shí)驗(yàn)題1.2 連續(xù)整數(shù)和問(wèn)題
第2章 表
　2.1 表的基本概念
　2.2 用數(shù)組實(shí)現(xiàn)表
　2.3 用指針實(shí)現(xiàn)表
　2.4 用間接尋址方法實(shí)現(xiàn)表
　2.5 用游標(biāo)實(shí)現(xiàn)表
　2.6 循環(huán)鏈表
　2.7 雙鏈表
　2.8 表的搜索游標(biāo)
　2.8.1 用數(shù)組實(shí)現(xiàn)表的搜索游標(biāo)
　2.8.2 單循環(huán)鏈表的搜索游標(biāo)
　2.9 應(yīng)用舉例——Josephus排列問(wèn)題
　本章小結(jié)
　習(xí)題2
　算法實(shí)驗(yàn)2
　算法實(shí)驗(yàn)題2.1 向量分類問(wèn)題
　算法實(shí)驗(yàn)題2.2 條形圖輪廓問(wèn)題
第3章 棧
　3.1 棧的基本概念
　3.2 用數(shù)組實(shí)現(xiàn)棧
　3.3 用指針實(shí)現(xiàn)棧
　3.4 應(yīng)用舉例——等價(jià)類劃分問(wèn)題
　本章小結(jié)
　習(xí)題3
　算法實(shí)驗(yàn)3
　算法實(shí)驗(yàn)題3.1 車皮編序問(wèn)題
　算法實(shí)驗(yàn)題3.2 單柱Hanoi塔問(wèn)題
　算法實(shí)驗(yàn)題3.3 多棧模擬問(wèn)題
　算法實(shí)驗(yàn)題3.4 親兄弟問(wèn)題
第4章 隊(duì)列
　4.1 隊(duì)列的基本概念
　4.2 用指針實(shí)現(xiàn)隊(duì)列
　4.3 用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列
　4.4 應(yīng)用舉例——電路布線問(wèn)題
　本章小結(jié)
　習(xí)題4
　算法實(shí)驗(yàn)4
　算法實(shí)驗(yàn)題4.1 組隊(duì)列問(wèn)題
　算法實(shí)驗(yàn)題4.2 雙棧隊(duì)列問(wèn)題
　算法實(shí)驗(yàn)題4.3 猴子分桃問(wèn)題
　算法實(shí)驗(yàn)題4.4 逆序表問(wèn)題
第5章 排序與選擇
　5.1 簡(jiǎn)單排序算法
　5.1.1 冒泡排序
　5.1.2 插入排序
　5.1.3 選擇排序
　5.1.4 簡(jiǎn)單排序算法的計(jì)算復(fù)雜性
　5.2 快速排序算法
　5.2.1 算法基本思想及實(shí)現(xiàn)
　5.2.2 算法的性能
　5.2.3 隨機(jī)快速排序算法
　5.2.4 非遞歸快速排序算法
　5.2.5 三數(shù)取中劃分算法
　5.2.6 三劃分快速排序算法
　5.3 合并排序算法
　5.3.1 算法基本思想及實(shí)現(xiàn)
　5.3.2 對(duì)基本算法的改進(jìn)
　5.3.3 自底向上的合并排序算法
　5.3.4 自然合并排序
　5.3.5 鏈表結(jié)構(gòu)的合并排序算法
　5.4 線性時(shí)間排序算法
　5.4.1 計(jì)數(shù)排序
　5.4.2 桶排序
　5.5 中位數(shù)與第k小元素
　5.5.1 平均情況下的線性時(shí)間選擇算法
　5.5.2 最壞情況下的線性時(shí)間選擇算法
　5.6 應(yīng)用舉例——帶權(quán)中位數(shù)問(wèn)題
　本章小結(jié)
　習(xí)題5
　算法實(shí)驗(yàn)5
　算法實(shí)驗(yàn)題5.1 交換排序問(wèn)題
　算法實(shí)驗(yàn)題5.2 DNA排序問(wèn)題
　算法實(shí)驗(yàn)題5.3 輸油管道問(wèn)題
　算法實(shí)驗(yàn)題5.4 最優(yōu)服務(wù)次序問(wèn)題
第6章 樹
　6.1 樹的定義
　6.2 樹的遍歷
　6.3 樹的表示法
　6.3.1 父結(jié)點(diǎn)數(shù)組表示法
　6.3.2 兒子鏈表表示法
　6.3.3 左兒子右兄弟表示法
　6.4 二叉樹的基本概念
　6.5 二叉樹的運(yùn)算
　6.6 二叉樹的實(shí)現(xiàn)
　6.6.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu)
　6.6.2 二叉樹的結(jié)點(diǎn)度表示法
　6.6.3 用指針實(shí)現(xiàn)二叉樹
　6.7 線索二叉樹
　6.8 應(yīng)用舉例——信號(hào)增強(qiáng)裝置布局問(wèn)題
　本章小結(jié)
　習(xí)題6
　算法實(shí)驗(yàn)6
　算法實(shí)驗(yàn)題6.1 層序列表問(wèn)題
　算法實(shí)驗(yàn)題6.2 最近公共祖先問(wèn)題
　算法實(shí)驗(yàn)題6.3 子樹問(wèn)題
　算法實(shí)驗(yàn)題6.4 同構(gòu)二叉樹問(wèn)題
　算法實(shí)驗(yàn)題6.5 后序中序遍歷問(wèn)題
第7章 圖
　7.1 圖的基本概念
　7.2 抽象數(shù)據(jù)類型ADT圖
　7.3 圖的表示法
　7.3.1 鄰接矩陣表示法
　7.3.2 鄰接表表示法
　7.3.3 緊縮鄰接表
　7.4 用鄰接矩陣實(shí)現(xiàn)圖
　7.4.1 用鄰接矩陣實(shí)現(xiàn)賦權(quán)有向圖
　7.4.2 用鄰接矩陣實(shí)現(xiàn)賦權(quán)無(wú)向圖
　7.4.3 用鄰接矩陣實(shí)現(xiàn)有向圖
　7.4.4 用鄰接矩陣實(shí)現(xiàn)無(wú)向圖
　7.5 用鄰接表實(shí)現(xiàn)圖
　7.5.1 用鄰接表實(shí)現(xiàn)有向圖
　7.5.2 用鄰接表實(shí)現(xiàn)無(wú)向圖
　7.5.3 用鄰接表實(shí)現(xiàn)賦權(quán)有向圖
　7.5.4 用鄰接表實(shí)現(xiàn)賦權(quán)無(wú)向圖
　7.6 圖的遍歷
　7.6.1 廣度優(yōu)先搜索
　7.6.2 深度優(yōu)先搜索
　7.7 最短路徑
　7.7.1 單源最短路徑
　7.7.2 Bellman-Ford最短路徑算法
　7.7.3 所有頂點(diǎn)對(duì)之間的最短路徑
　7.8 無(wú)圈有向圖DAG
　7.8.1 拓?fù)渑判?br />　7.8.2 DAG的最短路徑
　7.8.3 DAG的最長(zhǎng)路徑
　7.8.4 DAG所有頂點(diǎn)對(duì)之間的最短路徑
　7.9 最小支撐樹
　7.9.1 最小支撐樹性質(zhì)
　7.9.2 Prim算法
　7.9.3 Kruskal算法
　7.10 圖匹配
　7.11 應(yīng)用舉例——差分約束系統(tǒng)
　本章小結(jié)
　習(xí)題7
　算法實(shí)驗(yàn)7
　算法實(shí)驗(yàn)題7.1 圖的二著色問(wèn)題
　算法實(shí)驗(yàn)題7.2 賦權(quán)有向圖中心問(wèn)題
　算法實(shí)驗(yàn)題7.3 最長(zhǎng)簡(jiǎn)單路徑問(wèn)題
　算法實(shí)驗(yàn)題7.4 計(jì)算機(jī)網(wǎng)絡(luò)問(wèn)題
　算法實(shí)驗(yàn)題7.5 差分約束問(wèn)題
　算法實(shí)驗(yàn)題7.6 有截止時(shí)間的工作排序問(wèn)題
第8章 集合
　8.1 以集合為基礎(chǔ)的抽象數(shù)據(jù)類型
　8.1.1 集合的定義和記號(hào)
　8.1.2 定義在集合上的基本運(yùn)算
　8.2 用位向量實(shí)現(xiàn)集合
　8.3 用鏈表實(shí)現(xiàn)集合
　8.4 應(yīng)用舉例——Eratosthenes篩法
　本章小結(jié)
　習(xí)題8
　算法實(shí)驗(yàn)8
　算法實(shí)驗(yàn)題8.1 半數(shù)集問(wèn)題
第9章 符號(hào)表
　9.1 實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法
　9.2 用散列表實(shí)現(xiàn)符號(hào)表
　9.2.1 開散列
　9.2.2 閉散列
　9.2.3 散列函數(shù)及其效率
　9.2.4 閉散列的重新散列技術(shù)
　9.3 應(yīng)用舉例——字符串頻率統(tǒng)計(jì)問(wèn)題
　本章小結(jié)
　習(xí)題9
　算法實(shí)驗(yàn)9
　算法實(shí)驗(yàn)題9.1 偽隨機(jī)排列問(wèn)題
　算法實(shí)驗(yàn)題9.2 字符串散列問(wèn)題
　算法實(shí)驗(yàn)題9.3 英文文本分析問(wèn)題
　算法實(shí)驗(yàn)題9.4 最長(zhǎng)模式串問(wèn)題
第10章 字典
　10.1 字典的定義
　10.2 用數(shù)組實(shí)現(xiàn)字典
　10.3 用二叉搜索樹實(shí)現(xiàn)字典
　10.4 AVL樹
　10.4.1 AVL樹的定義和性質(zhì)
　10.4.2 旋轉(zhuǎn)變換
　10.4.3 AVL樹的插入運(yùn)算
　10.4.4 AVL樹的刪除運(yùn)算
　10.5 應(yīng)用舉例——條形圖統(tǒng)計(jì)問(wèn)題
　本章小結(jié)
　習(xí)題10
　算法實(shí)驗(yàn)10
　算法實(shí)驗(yàn)題10.1 裝箱問(wèn)題
　算法實(shí)驗(yàn)題10.2 電路板連線問(wèn)題
　算法實(shí)驗(yàn)題10.3 辭典問(wèn)題
第11章 優(yōu)先隊(duì)列
　11.1 優(yōu)先隊(duì)列的定義
　11.2 用字典實(shí)現(xiàn)優(yōu)先隊(duì)列
　11.3 優(yōu)先級(jí)樹和堆
　11.4 用數(shù)組實(shí)現(xiàn)堆
　11.5 可并優(yōu)先隊(duì)列
　11.5.1 左偏樹的定義
　11.5.2 用左偏樹實(shí)現(xiàn)可并優(yōu)先隊(duì)列
　11.6 應(yīng)用舉例——哈夫曼編碼
　本章小結(jié)
　習(xí)題11
　算法實(shí)驗(yàn)11
　算法實(shí)驗(yàn)題11.1 多機(jī)調(diào)度問(wèn)題
　算法實(shí)驗(yàn)題11.2 整數(shù)字典問(wèn)題
　算法實(shí)驗(yàn)題11.3 最小權(quán)語(yǔ)言問(wèn)題
　算法實(shí)驗(yàn)題11.4 二叉搜索堆問(wèn)題
第12章 并查集
　12.1 并查集的定義及其簡(jiǎn)單實(shí)現(xiàn)
　12.2 用父結(jié)點(diǎn)數(shù)組實(shí)現(xiàn)并查集
　12.3 應(yīng)用舉例——離線最小值問(wèn)題
　本章小結(jié)
　習(xí)題12
　算法實(shí)驗(yàn)12
　算法實(shí)驗(yàn)題12.1 二進(jìn)制方程問(wèn)題
　算法實(shí)驗(yàn)題12.2 網(wǎng)絡(luò)連通問(wèn)題
　算法實(shí)驗(yàn)題12.3 朋友問(wèn)題
　算法實(shí)驗(yàn)題12.4 無(wú)向圖的連通分支問(wèn)題
參考文獻(xiàn)

圖書封面

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

---

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

---