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

內(nèi)容概要

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

作者簡(jiǎn)介

殷人昆，清華大學(xué)計(jì)算機(jī)系教授，中國科學(xué)院研究生院工程教育部兼職教授。1985年赴日本東京理科大學(xué)做訪問學(xué)者，研究方向?yàn)檐浖こ踢^程的質(zhì)量管理和軟件產(chǎn)品的質(zhì)量評(píng)價(jià)。主要負(fù)責(zé)清華大學(xué)計(jì)算機(jī)系“數(shù)據(jù)結(jié)構(gòu)”、“軟件工程”的本科課程教學(xué)工作和“軟件工程技術(shù)與設(shè)計(jì)”、“軟件項(xiàng)目管理”的研究生課程教學(xué)工作。主講的“數(shù)據(jù)結(jié)構(gòu)”課程被評(píng)為清華大學(xué)精品課程。曾與人合作或單獨(dú)編寫教材十余本。曾在核心刊物和專業(yè)會(huì)議發(fā)表論文多篇。

書籍目錄

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

章節(jié)摘錄

版權(quán)頁：插圖：

編輯推薦

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

圖書封面

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

---

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

---