123,123

內(nèi)容簡(jiǎn)介

　　《數(shù)據(jù)結(jié)構(gòu)（第2版）》是國(guó)家精品課程“數(shù)據(jù)結(jié)構(gòu)”的研究成果之一，是面向21世紀(jì)課程教材和普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材?！稊?shù)據(jù)結(jié)構(gòu)（第2版）》系統(tǒng)介紹了數(shù)據(jù)結(jié)構(gòu)的概念、原理與技術(shù)，主要內(nèi)容包括緒論，基本數(shù)據(jù)結(jié)構(gòu)，排序、查找與內(nèi)存管理，相關(guān)工具和文件等。其中，第一章緒論主要對(duì)算法描述語(yǔ)言（ADL）、算法書寫規(guī)范、數(shù)據(jù)結(jié)構(gòu)與算法基本概念、算法分析基礎(chǔ)和算法正確性證明等進(jìn)行了介紹；第二至五章是基本數(shù)據(jù)結(jié)構(gòu)部分，主要涉及線性表、堆棧和隊(duì)列，數(shù)組和字符串，樹(shù)與二叉樹(shù)，圖結(jié)構(gòu)等內(nèi)容；第七至九章從算法的視角討論了排序、查找和內(nèi)存管理等方面的內(nèi)容，給出了若干典型算法的描述、時(shí)間復(fù)雜性分析和相關(guān)算法的比較等；第六章和十一章分別對(duì)遞歸和隨機(jī)數(shù)兩種主要工具進(jìn)行了講解，其中隨機(jī)數(shù)是數(shù)據(jù)結(jié)構(gòu)的新內(nèi)容；文件這種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)則在第十章中闡明。《數(shù)據(jù)結(jié)構(gòu)（第2版）》的附錄主要包括書中ADL算法的C++程序、一些基本數(shù)據(jù)結(jié)構(gòu)的C++類實(shí)現(xiàn)以及習(xí)題答案或解題思路?！稊?shù)據(jù)結(jié)構(gòu)（第2版）》配套教學(xué)資源中包括電子教案、ADL算法的C++程序、較難習(xí)題答案的C++代碼以及相關(guān)的測(cè)試和運(yùn)行支持程序，可供讀者自學(xué)和上機(jī)使用。《數(shù)據(jù)結(jié)構(gòu)（第2版）》可作為高等學(xué)校計(jì)算機(jī)相關(guān)專業(yè)的教材和教學(xué)參考書，也可供相關(guān)專業(yè)的工程技術(shù)人員參考使用。

作者簡(jiǎn)介

　　劉大有，吉林大學(xué)教授、博士生導(dǎo)師。國(guó)家基金委專家評(píng)審組成員，吉林省計(jì)算機(jī)學(xué)會(huì)理事長(zhǎng)，中國(guó)人工智能學(xué)會(huì)常務(wù)理事，知識(shí)工程與分布智能專委會(huì)副主任，中國(guó)計(jì)算機(jī)學(xué)會(huì)人工智能與模式識(shí)別專委會(huì)副主任。1997-2008年曾任國(guó)務(wù)院學(xué)位委員會(huì)學(xué)科評(píng)議組成員。在知識(shí)工程.專家系統(tǒng)、分布智能.智能體，時(shí)空推理和數(shù)據(jù)挖掘等方面取得了系統(tǒng)的創(chuàng)造性成果.為提高我國(guó)智能推理與智能系統(tǒng)等方面的研究與應(yīng)用水平做出了突出貢獻(xiàn)承擔(dān)國(guó)家和省部級(jí)項(xiàng)目50余項(xiàng)，出版著作9部，發(fā)表論文390余篇，三大檢索270余篇；獲國(guó)家科技進(jìn)步獎(jiǎng)2項(xiàng)、省部級(jí)科技進(jìn)步獎(jiǎng)9項(xiàng)；獲國(guó)家教學(xué)成果二等獎(jiǎng)1項(xiàng)、省教學(xué)成果一等獎(jiǎng)2項(xiàng)、國(guó)家精品課程和國(guó)家級(jí)教學(xué)團(tuán)隊(duì)稱號(hào)；并獲國(guó)務(wù)院特殊津貼，省突出貢獻(xiàn)專家，首批和二批省管優(yōu)秀專家.一、二批省高級(jí)專家等榮譽(yù)。

圖書目錄

第一章緒論
1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
1.2 數(shù)據(jù)結(jié)構(gòu)概念
1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)
1.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
1.2.3 對(duì)數(shù)據(jù)結(jié)構(gòu)的操作
1.2.4 數(shù)據(jù)結(jié)構(gòu)示例
1.3 算法
1.3.1 算法及其特性
1.3.2 算法的描述
1.3.3 算法的評(píng)價(jià)準(zhǔn)則
1.4 算法的正確性證明
1.5 算法分析基礎(chǔ)
1.5.1 算法時(shí)間復(fù)雜性的分析方法
1.5.2 復(fù)雜性函數(shù)的漸近表示
1.5.3 算法時(shí)間與空間分析
1.5.4 計(jì)算復(fù)雜性和算法的效率
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第二章線性表、堆棧和隊(duì)列
2.1 線性表的定義和基本操作
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)
2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)
2.3.1 單鏈表
2.3.2 循環(huán)鏈表
2.3.3 雙向鏈表
2.4 復(fù)雜性分析
2.5 堆棧
2.5.1 堆棧的定義和基本操作
2.5.2 順序棧
2.5.3 鏈?zhǔn)綏?br />2.5.4 順序棧與鏈?zhǔn)綏５谋容^
2.5.5 堆棧應(yīng)用——括號(hào)匹配
2.6 隊(duì)列
2.6.1 隊(duì)列的定義和基本操作
2.6.2 順序隊(duì)列
2.6.3 鏈?zhǔn)疥?duì)列
2.6.4 順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較
2.6.5 隊(duì)列與堆棧的擴(kuò)展
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第三章數(shù)組和字符串
3.1 數(shù)組
3.1.1 數(shù)組的存儲(chǔ)和尋址
3.1.2 一維數(shù)組類
3.2 矩陣
3.2.1 矩陣類
3.2.2 特殊矩陣
3.2.3 三元組表
3.2.4 十字鏈表
3.3 字符串
3.3.1 字符串的定義與字符串類
3.3.2 模式匹配算法
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第四章樹(shù)
4.1 樹(shù)的基本概念
4.1.1 樹(shù)的定義
4.1.2 樹(shù)的相關(guān)術(shù)語(yǔ)
4.2 二叉樹(shù)
4.2.1 二叉樹(shù)定義和主要性質(zhì)
4.2.2 二叉樹(shù)順序存儲(chǔ)
4.2.3 二叉樹(shù)鏈接存儲(chǔ)
4.2.4 二叉樹(shù)遍歷
4.2.5 創(chuàng)建二叉樹(shù)
4.2.6 復(fù)制二叉樹(shù)
4.3 線索二叉樹(shù)
4.3.1 線索二叉樹(shù)定義
4.3.2 線索二叉樹(shù)存儲(chǔ)
4.3.3 線索二叉樹(shù)基本算法
4.4 樹(shù)和森林
4.4.1 樹(shù)與二叉樹(shù)的轉(zhuǎn)換
4.4.2 樹(shù)的順序存儲(chǔ)
4.4.3 樹(shù)的鏈接存儲(chǔ)
4.4.4 樹(shù)和森林的遍歷
4.5 壓縮與哈夫曼樹(shù)
4.5.1 文件編碼
4.5.2 擴(kuò)充二叉樹(shù)
4.5.3 哈夫曼樹(shù)和哈夫曼編碼
4.6 應(yīng)用
4.6.1 表達(dá)式求值
4.6.2 分類與決策樹(shù)
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第五章圖
5.1 圖的基本概念
5.2 圖的存儲(chǔ)結(jié)構(gòu)與類定義
5.2.1 存儲(chǔ)結(jié)構(gòu)
5.2.2 Graph類
5.3 圖的遍歷算法
5.3.1 深度優(yōu)先遍歷
5.3.2 廣度優(yōu)先遍歷
5.4 拓?fù)渑判?br />5.5 關(guān)鍵路徑
5.6 最短路徑問(wèn)題
5.6.1 無(wú)權(quán)最短路徑問(wèn)題
5.6.2 正權(quán)最短路徑問(wèn)題
5.6.3 每對(duì)頂點(diǎn)之間的最短路徑
5.7 最小支撐樹(shù)
5.7.1 普里姆算法
5.7.2 克魯斯卡爾算法
5.8 圖的應(yīng)用
5.8.1 可及性與Warshall算法
5.8.2 連通分量
5.8.3 圖在網(wǎng)絡(luò)分析和信息檢索
中的應(yīng)用
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第六章遞歸
6.1 遞歸的定義
6.2 基本遞歸過(guò)程
6.3 遞歸過(guò)程實(shí)現(xiàn)與堆棧
6.4 遞歸法求解問(wèn)題
6.4.1 委員會(huì)問(wèn)題
6.4.2 回溯
6.5 遞歸的效率
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第七章排序
7.1 排序問(wèn)題的基本概念
7.2 插入排序
7.2.1 直接插入排序
7.2.2 Shell排序
7.3 交換排序
7.3.1 冒泡排序
7.3.2 快速排序
7.4 選擇排序
7.4.1 直接選擇排序
7.4.2 堆排序
7.5 合并排序
7.6 基于關(guān)鍵詞比較的排序算法分析
7.6.1 平方階排序算法及改進(jìn)算法
7.6.2 線性對(duì)數(shù)階排序算法
7.6.3 分治排序的一般方法
7.6.4 基于關(guān)鍵詞比較的排序算法下界
7.7 分布排序
7.7.1 基數(shù)分布
7.7.2 值分布
7.8 外排序
7.8.1 外存儲(chǔ)器
7.8.2 磁帶排序
7.8.3 磁盤排序
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第八章查找
8.1 順序查找
8.1.1 無(wú)序表的順序查找
8.1.2 有序表的順序查找
8.2 基于關(guān)鍵詞比較的查找
8.2.1 對(duì)半查找
8.2.2 一致對(duì)半查找
8.2.3 斐波那契查找
8.2.4 插值查找
8.3 二叉查找樹(shù)
8.3.1 基本概念和性質(zhì)
8.3.2 查找、插入和刪除
8.3.3 平均情況時(shí)間分析
8.4 最優(yōu)二叉查找樹(shù)
8.4.1 訪問(wèn)頻率
8.4.2 最優(yōu)二叉查找樹(shù)
8.4.3 近似最優(yōu)樹(shù)的構(gòu)造
8.5 平衡樹(shù)
8.5.1 高度平衡樹(shù)
8.5.2 重量平衡樹(shù)
8.6 紅黑樹(shù)
8.6.1 紅黑樹(shù)的性質(zhì)
8.6.2 旋轉(zhuǎn)
8.6.3 插入
8.6.4 刪除
8.7 B樹(shù)及其變形樹(shù)
8.7.1 多又樹(shù)
8.7.2 B樹(shù)
8.7.3 B樹(shù)變形樹(shù)
8.8 數(shù)字查找
8.8.1 檢索結(jié)構(gòu)查找
8.8.2 數(shù)字樹(shù)查找
8.9 散列
8.9.1 散列函數(shù)
8.9.2 沖突調(diào)節(jié)
8.9.3 刪除
8.9.4 重量平衡樹(shù)的應(yīng)用——按位置查找
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第九章內(nèi)存管理
9.1 概述
9.2 均勻大小記錄的分配和回收算法
9.2.1 記錄分配算法
9.2.2 訪問(wèn)計(jì)數(shù)器法
9.2.3 廢料收集方法
9.3 不同大小記錄的分配和回收算法
9.3.1 查找分配策略
9.3.2 邊界標(biāo)識(shí)法
9.3.3 壓縮分配
9.4 伙伴系統(tǒng)
9.4.1 伙伴系統(tǒng)概述
9.4.2 分配記錄和釋放記錄算法
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第10章文件
10.1 文件的基本概念
10.1.1 文件及其分類
10.1.2 文件的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)
10.2 順序文件
10.2.1 順序無(wú)序文件
10.2.2 順序有序文件
10.2.3 增補(bǔ)文件
10.3 散列文件
10.3.1 散列文件
10.3.2 可擴(kuò)充的散列文件
10.4 索引文件
10.4.1 動(dòng)態(tài)索引結(jié)構(gòu)和靜態(tài)索引結(jié)構(gòu)
10.4.2 ISAM文件
10.4.3 VSAM文件
10.5 多關(guān)鍵字文件
10.5.1 多重鏈表文件
10.5.2 倒排文件
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
第11章隨機(jī)數(shù)
11.1 生成隨機(jī)數(shù)
11.1.1 均勻分布隨機(jī)數(shù)
11.1.2 其他分布隨機(jī)數(shù)
11.2 隨機(jī)數(shù)檢驗(yàn)
11.2.1 一般檢驗(yàn)方法
11.2.2 經(jīng)驗(yàn)檢驗(yàn)方法
11.3 隨機(jī)排列與隨機(jī)組合
11.3.1 隨機(jī)排列
11.3.2 隨機(jī)組合
11.4 應(yīng)用
11.4.1 隨機(jī)算法
11.4.2 使用隨機(jī)數(shù)的快速排序算法
小結(jié)
參考文獻(xiàn)與推薦讀物
習(xí)題
附錄
附錄1 各章算法的C++實(shí)現(xiàn)
附錄2 習(xí)題參考答案或解題思路