![](/c49/99/12796854.jpg)
出版社:電子工業出版社 ISBN:9787121366321 版次:1 商品編碼:12796854 品牌:電子工業出版社 包裝:平裝 叢書名:普通高等教育“十三五”規劃教材,新工科建設之路·計算機類專業規劃教材 開本:16開 出版時間:2020-01-01 用紙:膠版紙 頁數:336 正文語種:中文 作者:陳慧南
" 內容簡介 作者依據ACM/IEEE的《計算機科學課程體繫規範2013》,參考了近年來國內外很多優秀教材,對《數據結構:C++語言描述》一書從教材結構和內容方面都做了很大調整,編寫了《數據結構:C++語言描述》。本次編寫保留了經典數據結構和算法知識,引入更多高級數據結構的內容。《數據結構:C++語言描述》重視問題求解,反映抽像、封裝和信息隱蔽等現代軟件設計理念,重視算法的時間和空間分析,包括查找和排序時間的下界分析。數據結構和算法使用C++語言描述。《數據結構:C++語言描述》重視實踐性和程序設計。書中算法都有完整的C++程序,構思精巧、結構清晰、注釋詳細,並且所有程序都已在VC++環境下編譯通過並能正確運行。它們既是很好的學習數據結構和算法的示例,也是很好的C++程序設計示例。《數據結構:C++語言描述》配有大量的實例和圖示,並有豐富的習題和實習題,易教易學。《數據結構:C++語言描述》涵蓋計算機學科專業考研大綱數據結構部分的考查內容。 作者簡介 陳慧南,教授,南京郵電大學計算機學院,主持了多項信息產業部基金項目的研究工作,並負責了多項企業辦公自動化和信息管理網絡繫統的研制開發。出版多本教材。曾獲江蘇省普通高校教學成果三等獎,其主持的《數據結構》課程獲江蘇省高校一類優秀課程。 目錄 目 錄 第1章 概論\t1 1.1 問題求解方法\t1 1.1.1 問題和問題求解\t1 1.1.2 問題求解過程\t1 1.1.3 計算機求解問題的過程\t2 1.2 什麼是數據結構\t2 1.2.1 算法與數據結構\t2 1.2.2 數據結構基本概念\t3 1.2.3 數據的邏輯結構\t4 1.2.4 數據的存儲表示\t5 1.2.5 數據結構的操作\t6 1.3 數據抽像和抽像數據類型\t7 1.3.1 數據抽像和過程抽像\t7 1.3.2 模塊化、封裝與信息隱蔽\t7 1.3.3 數據類型和抽像數據類型\t8 1.4 面向對像方法\t10 1.4.1 面向對像方法的由來\t10 1.4.2 面向對像方法的基本思想\t10 1.4.3 面向對像方法的基本要素\t11 1.4.4 抽像數據類型和面向對像方法\t12 1.4.5 C++語言對抽像數據類型的支持\t13 1.5 描述數據結構和算法\t13 1.5.1 數據結構的規範\t13 1.5.2 實現數據結構\t14 1.6 算法分析的基本方法\t15 1.6.1 算法及其性能標準\t15 1.6.2 算法的時間復雜度\t16 1.6.3 漸近時間復雜度\t18 1.6.4 最好、最壞和平均情況時間復雜度\t19 1.6.5 算法按時間復雜度分類\t19 1.6.6 算法的空間復雜度\t19 本章小結\t20 習題1\t20 第2章 數組和鏈表\t22 2.1 兩種基本的存儲表示方式\t22 2.2 結構和類\t22 2.2.1 結構\t22 2.2.2 結素\t23 2.3 指針和動態存儲分配\t24 2.3.1 指針\t24 2.3.2 動態存儲分配\t25 2.3.3 靜態變量和動態變量\t26 2.4 數組\t26 2.4.1 一維數組\t26 2.4.2 二維數組\t27 2.4.3 多維數組\t28 2.4.4 數組和指針\t28 2.4.5 固定長度數組和可變長度數組\t28 2.5 鏈表\t29 2.5.1 指向結構的指針\t30 2.5.2 單鏈表\t30 2.5.3 帶表頭結點的單鏈表\t33 2.5.4 單循環鏈表\t33 2.5.5 雙向鏈表\t33 2.6 采用模擬指針的鏈表\t35 2.6.1 結點結構\t35 2.6.2 可用空間表\t35 2.7 異常處理\t37 本章小結\t38 習題2\t38 第3章 棧和隊列\t40 3.1 棧\t40 3.1.1 棧ADT\t40 3.1.2 棧的順序表示\t41 3.1.3 棧的鏈接表示\t44 3.2 隊列\t47 3.2.1 隊列ADT\t47 3.2.2 隊列的順序表示\t48 3.2.3 隊列的鏈接表示\t51 3.3 表達式計算\t51 3.3.1 表達式\t51 3.3.2 中綴表達式轉換為後綴表達式\t52 3.3.3 計算後綴表達式的值\t55 3.4 演示與測試\t58 本章小結\t61 習題3\t61 第4章 遞歸\t63 4.1 遞歸和遞歸算法\t63 4.1.1 遞歸的概念\t63 4.1.2 遞歸算法示例\t64 4.2 歸納證明\t66 4.3 遞推關繫\t67 4.4 實現遞歸\t67 4.4.1 函數調用和繫統棧\t68 4.4.2 遞歸函數的性能\t69 4.4.3 尾遞歸\t69 4.4.4 消去遞歸\t70 本章小結\t70 習題4\t70 第5章 線性表和串\t72 5.1 線性表\t72 5.1.1 線性表ADT\t72 5.1.2 線性表的順序表示\t73 5.1.3 線性表的鏈接表示\t76 5.1.4 兩種存儲表示的比較\t79 5.2多項式算術運算\t80 5.2.1 多項式ADT\t80 5.2.2 多項式的鏈接表示\t80 5.2.3 項結點類\t81 5.2.4 多項式類\t82 5.2.5 多項式的輸入和輸出\t83 5.2.6 多項式相加\t84 5.2.7 多項式相乘\t85 5.2.8 重載運算符\t86 5.3 串\t86 5.3.1 串ADT\t86 5.3.2 串的存儲表示\t87 5.3.3 串運算的實現\t88 5.3.4 簡單模式匹配算法\t89 5.3.5 KMP算法\t91 本章小結\t95 習題5\t95 第6章 數組和廣義表\t97 6.1 數組作為抽像數據類型\t97 6.1.1 數組ADT\t97 6.1.2 一維數組的C++類\t98 6.2 矩陣\t99 6.2.1 矩陣的概念\t99 6.2.2 矩陣ADT\t99 6.2.3 矩陣的二維數組表示\t100 6.3 特殊矩陣\t101 6.3.1 對稱矩陣\t101 6.3.2 帶狀矩陣\t102 6.4 稀疏矩陣\t103 6.4.1 稀疏矩組表\t103 6.4.2 稀疏矩陣轉置\t105 6.4.3 稀疏矩陣相加\t107 6.4.4 稀疏矩陣相乘\t108 6.5 稀疏矩陣的正交鏈表\t109 6.5.1 正交鏈表結構\t109 6.5.2 正交鏈表結點類\t110 6.5.3 正交鏈表類\t111 6.5.4 建立正交鏈表\t111 6.5.5 輸出正交鏈表\t113 6.6 廣義表\t113 6.6.1 廣義表的概念\t113 6.6.2 廣義表ADT\t114 6.6.3 廣義表的存儲表示\t115 6.6.4 廣義表算法\t116 本章小結\t116 習題6\t117 第7章 樹\t118 7.1 樹的基本概念\t118 7.1.1 樹的定義\t118 7.1.2 基本術語\t119 7.2 二叉樹\t120 7.2.1 二叉樹的定義\t120 7.2.2 二叉樹的性質\t121 7.2.3 二叉樹ADT\t122 7.2.4 二叉樹的存儲表示\t123 7.2.5 二叉樹類\t123 7.2.6 實現二叉樹的基本操作\t124 7.3 二叉樹的遍歷\t126 7.3.1 二叉樹遍歷算法\t126 7.3.2 二叉樹遍歷的遞歸算法\t128 7.3.3 二叉樹遍歷的應用實例\t129 7.4 二叉樹遍歷的非遞歸算法\t131 7.4.1 遍歷器類\t131 7.4.2 中序遍歷器類\t132 7.4.3 後序遍歷器類\t134 7.5 二叉線索樹\t136 7.5.1 二叉線索樹的定義\t136 7.5.2 構造中序線索樹\t137 7.5.3 遍歷中序線索樹\t138 7.6 樹和森林\t139 7.6.1 森林與二叉樹的轉換\t139 7.6.2 樹和森林的存儲表示\t141 7.6.3 樹和森林的遍歷\t142 本章小結\t143 習題7\t143 第8章 樹的應用\t145 8.1 堆\t145 8.1.1 堆的定義\t145 8.1.2 堆的順序表示\t145 8.1.3 向下調整和建堆操作\t145 8.2 優先權隊列\t147 8.2.1 優先權隊列ADT\t147 8.2.2 優先權隊列類\t148 8.2.3 實現優先權隊列\t148 8.3 哈夫曼樹和哈夫曼編碼\t150 8.3.1 樹的路徑長度\t151 8.3.2 哈夫曼算法\t152 8.3.3 哈夫曼樹類\t152 8.3.4 構造哈夫曼樹\t153 8.3.5 哈夫曼編碼\t155 8.3.6 哈夫曼編碼算法\t156 8.4 並查集和等價關繫\t156 8.4.1 並查集ADT\t157 8.4.2 並查集的存儲表示\t157 8.4.3 並查集類\t158 8.4.4 Union和Find函數\t159 8.4.5 改進的Union和Find函數\t159 8.4.6 按等價關繫分組\t160 本章小結\t161 習題8\t161 第9章 字典和查找\t162 9.1 字典及其表示\t162 9.1.1 字典\t162 9.1.2 字典查找\t163 9.1.3 字典ADT\t163 9.1.4 字典的存儲表示\t164 9.2 順序查找\t165 9.2.1 無序表的順序查找\t165 9.2.2 有序表的順序查找\t165 9.2.3 平均查找長度\t166 9.2.4 自組織表\t166 9.3 二分查找\t167 9.3.1 二分查找算法\t167 9.3.2 對半查找算法\t168 9.3.3 二叉判定樹\t169 9.3.4 斐波那契查找算法\t170 9.3.5 插值查找\t172 9.4 分塊查找\t172 9.5 查找算法的時間復雜度下界\t173 本章小結\t174 習題9\t174 第10章 二叉查找樹\t175 10.1 二叉查找樹表示字典\t175 10.1.1 二叉查找樹的定義\t175 10.1.2 二叉查找樹的查找操作\t176 10.1.3 二叉查找樹的插入操作\t177 10.1.4 二叉查找樹的刪除操作\t178 10.1.5 二叉查找樹的高度\t179 10.2 二叉平衡樹\t179 10.2.1 二叉平衡樹的定義\t179 10.2.2 二叉平衡樹類\t180 10.2.3 二叉平衡樹的平衡旋轉\t181 10.2.4 二叉平衡樹的插入操作\t185 10.2.5 二叉平衡樹的刪除操作\t187 10.2.6 二叉平衡樹的高度\t189 10.3 伸展樹\t190 10.3.1 自調節樹和伸展樹\t190 10.3.2 伸展樹的伸展操作\t191 10.3.3 伸展樹類\t193 10.3.4 旋轉的實現\t193 10.3.5 伸展樹的插入操作\t194 10.3.6 分攤時間分析\t195 10.4 紅黑樹\t195 10.4.1 紅黑樹的定義\t195 10.4.2 紅黑樹的查找操作\t196 10.4.3 紅黑樹的插入操作\t196 10.4.4 紅黑樹的刪除操作\t198 10.4.5 紅黑樹的高度\t199 本章小結\t199 習題10\t199 第11章 多叉查找樹\t201 11.1 m叉查找樹\t201 11.2 B?樹\t202 11.2.1 B?樹的定義\t203 11.2.2 B?樹的高度\t203 11.2.3 B?樹的查找操作\t203 11.2.4 B?樹的插入操作\t204 11.2.5 B?樹的刪除操作\t206 11.2.6 B?樹類\t207 11.2.7 B?樹的查找操作\t208 11.2.8 B?樹的插入函數\t209 11.2.9 B?樹的刪除函數\t210 11.3 鍵樹\t212 11.3.1 鍵樹的定義\t212 11.3.2 雙鏈樹\t213 11.3.3 Trie樹\t214 11.3.4 Trie樹的查找操作\t216 11.3.5 Trie樹的插入操作\t216 11.3.6 Trie樹的刪除操作\t217 11.3.7 Trie樹性能分析\t217 本章小結\t218 習題11\t218 第12章 跳表和散列表\t219 12.1 跳表\t219 12.1.1 跳表的概念\t219 12.1.2 跳表類\t221 12.1.3 跳表的查找函數\t222 12.1.4 跳表的插入函數\t223 12.1.5 跳表的刪除函數\t224 12.1.6 性能分析\t224 12.2 散列表\t224 12.2.1 散列技術\t225 12.2.2 散列函數\t226 12.2.3 拉鏈法\t227 12.2.4 開地址法\t228 12.2.5 線性探查法\t228 12.2.6 其他開地址法\t231 12.2.7 性能分析\t233 本章小結\t233 習題12\t234 第13章 圖\t235 13.1 圖的基本概念\t235 13.1.1 圖的定義與術語\t235 13.1.2 圖的抽像數據類型\t237 13.2 圖的存儲結構\t238 13.2.1 圖的矩陣表示\t238 13.2.2 圖的鄰接矩陣實現\t239 13.2.3 圖的鄰接表表示\t241 13.2.4 圖的鄰接表實現\t242 13.2.5 有向圖的正交鏈表表示\t245 13.2.6 無向圖的鄰接多重表表示\t245 13.3 圖的遍歷\t246 13.3.1 擴充的圖類\t246 13.3.2 深度優先遍歷\t247 13.3.3 廣度優先遍歷\t248 13.3.4 基本遍歷方法\t249 13.4 拓撲排序\t250 13.4.1 AOV網絡\t250 13.4.2 拓撲排序算法\t252 13.4.3 拓撲排序算法實現\t252 13.5 關鍵路徑\t254 13.5.1 AOE網\t254 13.5.2 關鍵路徑算法\t255 13.5.3 關鍵路徑算法實現\t257 13.6 最小代價生成樹\t258 13.6.1 基本概念\t258 13.6.2 普裡姆算法\t258 13.6.3 克魯斯卡爾算法\t260 13.6.4 算法正確性\t262 13.7 單源最短路徑\t262 13.7.1 最短路徑問題\t262 13.7.2 迪傑斯特拉算法\t263 13.7.3 數據結構選擇\t263 13.7.4 迪傑斯特拉算法實現\t264 13.8 所有頂點之間的最短路徑\t266 13.8.1 弗洛伊德算法\t266 13.8.2 弗洛伊德算法實現\t267 本章小結\t268 習題13\t268 第14章 內排序\t270 14.1 基本概念\t270 14.2 插入排序\t271 14.2.1 直接插入排序\t271 14.2.2 順序表的直接插入排序\t272 14.2.3 單鏈表的直接插入排序\t273 14.2.4 希爾排序\t274 14.2.5 對半插入排序\t276 14.3 選擇排序\t276 14.3.1 簡單選擇排序\t276 14.3.2 堆排序\t277 14.4 交換排序\t278 14.4.1 冒泡排序\t278 14.4.2 快速排序\t280 14.4.3 快速排序性能分析\t281 14.5 兩路合並排序\t283 14.5.1 合並兩個有序序列\t284 14.5.2 兩路合並排序迭代算法\t284 14.5.3 兩路合並排序遞歸算法\t285 14.5.4 單鏈表兩路合並排序\t285 14.6 排序算法的時間復雜度下界\t287 14.7 基數排序\t288 14.7.1 分配排序\t289 14.7.2 基數排序算法\t289 14.7.3 基數排序實現\t290 本章小結\t292 習題14\t292 第15章 文件和外排序\t294 15.1 輔助存儲器簡介\t294 15.1.1 主存儲器和輔助存儲器\t294 15.1.2 磁盤存儲器\t294 15.2 文件\t295 15.2.1 文件的基本概念\t295 15.2.2 文件的組織方式\t296 15.3 文件的索引結構\t298 15.3.1 靜態索引結構\t298 15.3.2 動態索引結構\t299 15.4 外排序\t300 15.4.1 外排序的基本過程\t300 15.4.2 初始遊程的生成\t300 15.4.3 多路合並\t302 15.4.4 最佳合並樹\t304 本章小結\t304 習題15\t305 第16章 實習指導和實習題\t306 16.1 實習目的、要求和步驟\t306 16.2 面向對像表示法\t307 16.3 實習報告和範例\t308 16.3.1 實習報告\t308 16.3.2 實習題範例\t309 16.3.3 實習報告範例\t309 16.4 實習題\t312 實習1 C++語言的類及模板的使用\t312 實習2 數組和鏈表操作\t313 實習3 棧、隊列及表達式計算\t313 實習4 線性表的操作及應用\t314 實習5多項式的相加和相乘\t314 實習6 對稱矩陣和稀疏矩陣的 壓縮存儲\t315 實習7 字符串操作和文本 處理\t315 實習8 二叉樹操作和哈夫曼編碼\t315 實習9 有序表查找\t316 實習10 B?樹檢索\t317 實習11 散列表查找\t317 實習12 圖的操作及應用\t318 實習13 內排序算法及其性能比較\t318 實習14 置換選擇和K路合並的 外排序算法\t318 附錄A 程序測試和調試\t319 A.1 面向對像程序測試\t319 A.2 程序測試步驟\t319 A.3 測試方法\t320 A.4 程序調試\t321 附錄B 2019年計算機考研大綱與教材內容對照\t323 B.1 2019年計算機考研大綱\t323 B.2 教材內容對2019年計算機考研大綱的適應性\t324 參考文獻\t326 查看全部↓
" |