數據結構

內容概要

　　《數據結構：c語言描述》是根據2007年教育部頒發(fā)的《高等學校計算機科學與技術專業(yè)公共核心知識體系與課程》規(guī)范和2010年修訂的《全國碩士研究生入學統(tǒng)一考試計算機專業(yè)基礎綜合考試大綱》編寫的數據結構課程教材。全書共分7章：第1章介紹數據結構的地位和主要知識點，數據結構和算法的基本概念，算法分析的簡單方法，以及用c語言編程的要點；第2～7章對應考試大綱的6個知識單元，包括線性表，棧、隊列和數組，樹與二叉樹，圖，查找，排序。本書融入了作者三十多年的教學經驗和考試輔導體會，合理安排相關知識點，對學生容易忽略的地方和隱含在所討論問題之后的內容給出適當的提示。　　《數據結構：c語言描述》既可作為普通高校計算機科學與技術及相關專業(yè)本科生學習數據結構課程的教材，也可作為計算機專業(yè)考研的輔導教材或其他專業(yè)計算機考試的復習教材，還可作為計算機系統(tǒng)開發(fā)人員的學習資料。

作者簡介

殷人昆，清華大學計算機系教授，中國科學院研究生院工程教育部兼職教授。1985年赴日本東京理科大學做訪問學者，研究方向為軟件工程過程的質量管理和軟件產品的質量評價。主要負責清華大學計算機系“數據結構”、“軟件工程”的本科課程教學工作和“軟件工程技術與設計”、“軟件項目管理”的研究生課程教學工作。主講的“數據結構”課程被評為清華大學精品課程。曾與人合作或單獨編寫教材十余本。曾在核心刊物和專業(yè)會議發(fā)表論文多篇。

書籍目錄

出版者的話 編委會 叢書序言 前言 教學安排建議 第1章 緒論1 1.1 數據結構的概念及分類1 1.1.1 為什么要學習數據結構1 1.1.2 與數據結構相關的基本術語2 1.1.3 數據結構的分類4 1.1.4 數據結構的存儲結構6 1.1.5 定義在數據結構上的操作6 1.2 使用c語言描述數據結構6 1.2.1 數據類型7 1.2.2 算法的控制結構7 1.2.3 算法的函數結構8 1.2.4 動態(tài)存儲分配10 1.2.5 邏輯和關系運算的約定11 1.2.6 輸入與輸出11 1.3 算法和算法設計12 1.3.1 算法的定義和特性12 1.3.2 算法的設計步驟12 1.3.3 算法設計的基本方法13 1.4 算法分析與度量16 1.4.1 算法的評價標準16 1.4.2 算法的時間和空間復雜度度量16 1.4.3 算法的漸近分析19 小結21 習題21 第2章 線性表23 2.1 線性表的定義及操作23 2.1.1 線性表的定義和特點23 2.1.2 線性表的主要操作24 2.2 順序表25 2.2.1 順序表的定義和特點25 2.2.2 順序表的結構定義25 2.2.3 順序表主要操作的實現(xiàn)26 2.2.4 順序表主要操作的性能分析28 2.2.5 順序表的應用舉例29 2.3 單鏈表30 2.3.1 單鏈表的定義和特點30 2.3.2 單鏈表的結構定義31 2.3.3 單鏈表中的插入與刪除31 2.3.4 帶頭結點的單鏈表33 2.3.5 單鏈表主要操作的性能分析35 2.3.6 單鏈表的順序訪問與尾遞歸36 2.3.7 單鏈表的應用舉例38 2.4 順序表與線性鏈表的比較40 2.5 線性鏈表的其他變形41 2.5.1 循環(huán)鏈表41 2.5.2 雙向鏈表44 2.5.3 靜態(tài)鏈表46 2.6 線性表的應用：字符串47 2.6.1 字符串的概念47 2.6.2 字符串的初始化和賦值48 2.6.3 c語言中有關字符串的庫函數48 2.6.4 自定義字符串的存儲表示50 2.7 單鏈表的應用：一元多項式及其運算53 2.7.1 一元多項式的表示53 2.7.2 多項式的結構定義54 2.7.3 多項式的加法55 2.7.4 多項式的乘法56 小結58 習題58 第3章 棧、隊列和數組61 3.1 棧61 3.1.1 棧的概念61 3.1.2 順序棧62 3.1.3 鏈式棧66 3.1.4 棧的混洗68 3.2 隊列69 3.2.1 隊列的概念69 3.2.2 循環(huán)隊列70 3.2.3 鏈式隊列73 3.3 棧的應用75 3.3.1 數制轉換75 3.3.2 括號匹配75 3.3.3 表達式的計算與優(yōu)先級處理76 3.3.4 棧與遞歸的實現(xiàn)80 3.4 隊列的應用83 3.4.1 打印楊輝三角形與逐行處理83 3.4.2 電路布線與兩點間的最短路徑84 3.5 數組86 3.5.1 一維數組86 3.5.2 多維數組87 3.5.3 數組的應用舉例89 3.6 在算法設計中使用遞歸89 3.6.1 漢諾塔問題與分治法90 3.6.2 迷宮問題與回溯法92 3.6.3 計算組合數與動態(tài)規(guī)劃95 3.7 特殊矩陣96 3.7.1 對稱矩陣的壓縮存儲96 3.7.2 三對角線矩陣的壓縮存儲97 3.7.3 稀疏矩陣的壓縮存儲98 3.8 雙端隊列100 3.8.1 雙端隊列的概念100 3.8.2 雙端隊列的主要操作101 3.8.3 雙端隊列的順序存儲表示101 3.8.4 雙端隊列的鏈接存儲表示103 小結103 習題104 第4章 樹與二叉樹108 4.1 樹的基本概念108 4.1.1 樹的定義和術語108 4.1.2 樹的基本操作110 4.2 二叉樹111 4.2.1 二叉樹的概念111 4.2.2 二叉樹的性質112 4.2.3 二叉樹的主要操作113 4.3 二叉樹的存儲表示114 4.3.1 二叉樹的順序存儲表示114 4.3.2 二叉樹的鏈表存儲表示115 4.4 二叉樹的遍歷116 4.4.1 二叉樹遍歷的遞歸算法116 4.4.2 遞歸遍歷算法的應用舉例117 4.4.3 二叉樹遍歷的非遞歸算法120 4.4.4 非遞歸遍歷算法的應用舉例123 4.4.5 二叉樹的計數125 4.5 線索二叉樹127 4.5.1 線索二叉樹的概念127 4.5.2 線索二叉樹的種類128 4.5.3 中序線索二叉樹的建立和遍歷129 4.5.4 前序與后序線索二叉樹131 4.6 樹與森林132 4.6.1 樹的存儲表示132 4.6.2 森林與二叉樹的轉換134 4.6.3 樹與森林的深度優(yōu)先遍歷135 4.6.4 樹與森林的廣度優(yōu)先遍歷137 4.6.5 樹遍歷算法的應用舉例138 4.7 二叉樹的應用：二叉排序樹138 4.7.1 二叉排序樹的概念138 4.7.2 二叉排序樹的查找139 4.7.3 二叉排序樹的插入140 4.7.4 二叉排序樹的刪除141 4.7.5 二叉排序樹的性能分析142 4.8 二叉樹的應用：平衡二叉樹144 4.8.1 平衡二叉樹的概念144 4.8.2 平衡化旋轉144 4.8.3 平衡二叉樹的插入146 4.8.4 平衡二叉樹的刪除147 4.8.5 平衡二叉樹的性能分析149 4.9 二叉樹的應用：huffman樹150 4.9.1 帶權路徑長度的概念150 4.9.2 huffman樹與huffman算法151 4.9.3 huffman樹的應用：最優(yōu)判定樹153 4.9.4 huffman樹的應用：huffman編碼154 4.10 二叉樹的應用：堆155 4.10.1 小根堆和大根堆155 4.10.2 堆的建立156 4.10.3 堆的插入158 4.10.4 堆的刪除158 4.11 樹的應用：八皇后問題與樹的剪枝159 4.11.1 八皇后問題的提出159 4.11.2 八皇后問題的狀態(tài)樹160 4.11.3 八皇后問題算法161 小結162 習題162 第5章 圖168 5.1 圖的基本概念168 5.1.1 與圖有關的概念168 5.1.2 圖的基本操作170 5.2 圖的存儲結構171 5.2.1 圖的鄰接矩陣表示171 5.2.2 圖的鄰接表表示175 5.2.3 鄰接矩陣表示與鄰接表表示 的比較178 5.2.4 圖的鄰接多重表表示179 5.3 圖的遍歷180 5.3.1 深度優(yōu)先搜索181 5.3.2 廣度優(yōu)先搜索182 5.3.3 連通分量183 5.3.4 重連通圖184 5.3.5 歐拉回路與一筆畫問題186 5.3.6 有向圖的強連通分量187 5.4 最小生成樹188 5.4.1 最小生成樹求解和貪婪法188 5.4.2 kruskal算法190 5.4.3 prim算法193 5.5 最短路徑194 5.5.1 非負權重的單源最短路徑194 5.5.2 所有頂點之間的最短路徑197 5.5.3 無權重的最短路徑199 5.6 用頂點表示活動的網絡（aov網絡）200 5.7 用邊表示活動的網絡（aoe網絡）204 小結207 習題208 第6章 查找212 6.1 查找的基本概念與性能分析212 6.1.1 查找的概念212 6.1.2 查找算法的性能分析213 6.2 順序查找法213 6.2.1 順序表上的順序查找算法213 6.2.2 線性鏈表上的順序查找算法216 6.3 折半查找法216 6.3.1 一般的折半查找法216 6.3.2 擬最優(yōu)查找樹：折半查找的 改進方法219 6.3.3 斐波那契查找：折半查找的 變形222 6.3.4 插值查找：折半查找的變形223 6.4 b樹224 6.4.1 索引順序表與分塊查找224 6.4.2 多級索引結構與m叉查找樹225 6.4.3 b樹的概念226 6.4.4 b樹上的查找227 6.4.5 b樹上的插入228 6.4.6 b樹上的刪除229 6.4.7 b+樹231 6.5 散列表及其查找233 6.5.1 散列的概念233 6.5.2 常見的散列函數234 6.5.3 解決沖突的開地址法236 6.5.4 解決沖突的鏈地址法242 6.5.5 散列法分析244 小結245 習題245 第7章 排序250 7.1 排序的概念與算法性能250 7.1.1 排序的概念250 7.1.2 排序算法的性能251 7.1.3 數據表和靜態(tài)鏈表的結構定義251 7.2 幾種簡單的排序方法253 7.2.1 直接插入排序253 7.2.2 基于鏈表的直接插入排序254 7.2.3 折半插入排序255 7.2.4 起泡排序256 7.2.5 簡單選擇排序258 7.3 希爾排序259 7.3.1 希爾排序的設計思路259 7.3.2 希爾排序的算法實現(xiàn)260 7.4 快速排序261 7.4.1 快速排序的設計思路261 7.4.2 快速排序的算法描述262 7.4.3 快速排序的算法分析262 7.4.4 快速排序的改進算法263 7.5 堆排序264 7.5.1 大根堆264 7.5.2 堆排序的算法265 7.5.3 堆排序的算法分析267 7.6 歸并排序267 7.6.1 兩路歸并267 7.6.2 遞歸的歸并排序算法268 7.6.3 迭代的歸并排序算法269 7.6.4 基于鏈表的歸并排序算法271 7.7 基數排序272 7.7.1 基數排序的概念272 7.7.2 msd基數排序273 7.7.3 lsd基數排序274 7.8 內排序算法的分析與比較276 7.8.1 排序方法的下界276 7.8.2 各種內排序方法的比較279 7.8.3 鏈表排序結果的重排280 小結282 習題283 附錄一 2009～2011年全國考研計算機學科聯(lián)考專業(yè)基礎綜合考試數據結構部分試題解析288 附錄二 大作業(yè)要求及樣例303 參考文獻308

章節(jié)摘錄

版權頁：插圖：

編輯推薦

《數據結構:C語言描述》特點：采用“工科”思維，啟發(fā)學生掌握“化復雜為簡單”的方式，從問題入手，通過“問題／子問題”分解，尋找解決方案。對基本知識點講深講透，通過多種應用舉例，讓學生了解不同問題需要采取什么方法來應對。通過大量習題，從不同視點、不同層面訓練學生，培養(yǎng)其聯(lián)想能力，提高其分析問題、解決問題的能力?？膳浜陷o助教材《數據結構習題精析與考研輔導》進行學習該書提供了600多題的參考答案和解析，并就關鍵點進行點撥，另外，提供了多套模擬題。涵蓋2009-2011年計算機學科研究生聯(lián)考數據結構部分的真題及解析。

圖書封面

評論、評分、閱讀與下載

---

    數據結構 PDF格式下載

---