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

內(nèi)容概要

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)教學(xué)計(jì)劃中的核心課程，也是計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)考研和水平等級(jí)考試的必考科目。要從事和計(jì)算機(jī)科學(xué)與技術(shù)相關(guān)的工作，尤其是計(jì)算機(jī)應(yīng)用領(lǐng)域的開(kāi)發(fā)和研制工作，必須具備堅(jiān)實(shí)的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。在本書(shū)第1版成功的基礎(chǔ)上，作者進(jìn)行了修訂，作為第2版，本書(shū)內(nèi)容更貼合《計(jì)算機(jī)學(xué)科專(zhuān)業(yè)碩士研究生入學(xué)考試基礎(chǔ)綜合考試大綱》，可讀性和實(shí)用性更強(qiáng)。
王紅梅、胡明、王濤編著的《數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》介紹了數(shù)據(jù)結(jié)構(gòu)、算法以及抽象數(shù)據(jù)類(lèi)型的概念，介紹了線性表、棧、隊(duì)列和串、數(shù)組、樹(shù)和二叉樹(shù)、圖等常用數(shù)據(jù)結(jié)構(gòu)，討論了常用的查找、排序和索引技術(shù)，給出了較多的數(shù)據(jù)結(jié)構(gòu)的應(yīng)用實(shí)例。限于篇幅，把貫穿所有數(shù)據(jù)結(jié)構(gòu)的綜合案例放在了網(wǎng)站上，供讀者下載。
《數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》內(nèi)容豐富，層次清晰，講解深入淺出，可作為計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)本、專(zhuān)科數(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計(jì)算機(jī)軟件開(kāi)發(fā)和應(yīng)用的工程技術(shù)人員閱讀、參考。

書(shū)籍目錄

第1章 緒論
 1.1 數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用
 1.2 本書(shū)討論的主要內(nèi)容
 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念
 1.3.1 數(shù)據(jù)結(jié)構(gòu)
 1.3.2 抽象數(shù)據(jù)類(lèi)型
 1.4 算法及算法分析
 1.4.1 算法及其描述方法
 1.4.2 算法分析
 思想火花——好算法是反復(fù)努力和重新修正的結(jié)果
 習(xí)題
 思考題
第2章 線性表
 2.1 線性表的邏輯結(jié)構(gòu)
 2.1.1 線性表的定義
 2.1.2 線性表的抽象數(shù)據(jù)類(lèi)型定義
 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表
 2.2.2 順序表的實(shí)現(xiàn)
 2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 2.3.1 單鏈表
 2.3.2 循環(huán)鏈表
 2.3.3 雙鏈表
 2.4 順序表和鏈表的比較
 2.4.1 時(shí)間性能比較
 2.4.2 空間性能比較
 2.5 線性表的其他存儲(chǔ)方法
 2.5.1 靜態(tài)鏈表
 2.5.2 間接尋址
 2.6 應(yīng)用舉例
 2.6.1 順序表的應(yīng)用舉例——大整數(shù)求和
 2.6.2 單鏈表的應(yīng)用舉例——一元多項(xiàng)式求和
 思想火花——好程序要能識(shí)別和處理各種輸入
 習(xí)題
 思考題
第3章 棧和隊(duì)列
 3.1 棧
 3.1.1 棧的邏輯結(jié)構(gòu)
 3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 3.1.3 棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 3.1.4 順序棧和鏈棧的比較
 3.2 隊(duì)列
 3.2.1 隊(duì)列的邏輯結(jié)構(gòu)
 3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 3.2.3 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 3.2.4 循環(huán)隊(duì)列和鏈隊(duì)列的比較
 3.3 應(yīng)用舉例
 3.3.1 棧的應(yīng)用舉例——表達(dá)式求值
 3.3.2 隊(duì)列的應(yīng)用舉例——火車(chē)車(chē)廂重排
 思想火花——直覺(jué)可能是錯(cuò)誤的
 習(xí)題
 思考題
第4章 字符串和多維數(shù)組
 4.1 字符串
 4.1.1 字符串的定義
 4.1.2 字符串的存儲(chǔ)結(jié)構(gòu)
 4.1.3 模式匹配
 4.2 多維數(shù)組
 4.2.1 數(shù)組的定義
 4.2.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址
 4.3 矩陣的壓縮存儲(chǔ)
 4.3.1 對(duì)稱矩陣的壓縮存儲(chǔ)
 4.3.2 三角矩陣的壓縮存儲(chǔ)
 4.3.3 對(duì)角矩陣的壓縮存儲(chǔ)
 4.3.4 稀疏矩陣的壓縮存儲(chǔ)
 4.4 應(yīng)用舉例
 4.4.1 字符串的應(yīng)用舉例——?jiǎng)P撒密碼
 4.4.2 數(shù)組的應(yīng)用舉例——幻方
 思想火花——用常識(shí)性的思維去思考問(wèn)題
 習(xí)題
 思考題
第5章 樹(shù)和二叉樹(shù)
 5.1 樹(shù)的邏輯結(jié)構(gòu)
 5.1.1 樹(shù)的定義和基本術(shù)語(yǔ)
 5.1.2 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義
 5.1.3 樹(shù)的遍歷操作
 5.2 樹(shù)的存儲(chǔ)結(jié)構(gòu)
 5.2.1 雙親表示法
 5.2.2 孩子表示法
 5.2.3 雙親孩子表示法
 5.2.4 孩子兄弟表示法
 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)
 5.3.1 二叉樹(shù)的定義
 5.3.2 二叉樹(shù)的基本性質(zhì)
 5.3.3 二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義
 5.3.4 二叉樹(shù)的遍歷操作
 5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 5.4.1 順序存儲(chǔ)結(jié)構(gòu)
 5.4.2 二叉鏈表
 5.4.3 三叉鏈表
 5.4.4 線索鏈表
 5.5 二叉樹(shù)遍歷的非遞歸算法
 5.5.1 前序遍歷非遞歸算法
 5.5.2 中序遍歷非遞歸算法
 5.5.3 后序遍歷非遞歸算法
 5.6 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換
 5.7 應(yīng)用舉例
 5.7.1 二叉樹(shù)的應(yīng)用舉例——哈夫曼樹(shù)及哈夫曼編碼
 5.7.2 樹(shù)的應(yīng)用舉例——八枚硬幣問(wèn)題
 思想火花——調(diào)試程序與魔術(shù)表演
 習(xí)題5
 思考題5
第6章 圖
 6.1 圖的邏輯結(jié)構(gòu)
 6.1.1 圖的定義和基本術(shù)語(yǔ)
 6.1.2 圖的抽象數(shù)據(jù)類(lèi)型定義
 6.1.3 圖的遍歷操作
 6.2 圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
 6.2.1 鄰接矩陣
 6.2.2 鄰接表
 6.2.3 十字鏈表
 6.2.4 鄰接多重表
 6.2.5 鄰接矩陣和鄰接表的比較
 6.3 最小生成樹(shù)
 6.3.1 MST性質(zhì)
 6.3.2 Prim算法
 6.3.3 Kruskal算法
 6.4 最短路徑
 6.4.1 Dijkstra算法
 6.4.2 Floyd算法
 6.5 有向無(wú)環(huán)圖及其應(yīng)用
 6.5.1 AOV網(wǎng)與拓?fù)渑判?br /> 6.5.2 AOE網(wǎng)與關(guān)鍵路徑
 6.6 應(yīng)用舉例
 6.6.1 圖的應(yīng)用舉例1——七橋問(wèn)題
 6.6.2 圖的應(yīng)用舉例2——七巧板涂色
 思想火花——數(shù)據(jù)模型在問(wèn)題求解中的作用
 習(xí)題6
 思考題6
第7章 查找技術(shù)
 7.1 概述
 7.1.1 查找的基本概念
 7.1.2 查找算法的性能
 7.2 線性表的查找技術(shù)
 7.2.1 順序查找
 7.2.2 折半查找
 7.3 樹(shù)表的查找技術(shù)
 7.3.1 二叉排序樹(shù)
 7.3.2 平衡二叉樹(shù)
 7.4 散列表的查找技術(shù)
 7.4.1 概述
 7.4.2 散列函數(shù)的設(shè)計(jì)
 7.4.3 處理沖突的方法
 7.4.4 散列查找的性能分析
 7.4.5 開(kāi)散列表與閉散列表的比較
 思想火花——把注意力集中于主要因素，不要糾纏于噪聲
 習(xí)題7
 思考題7
第8章 排序技術(shù)
 8.1 概述
 8.1.1 排序的基本概念
 8.1.2 排序算法的性能
 8.2 插入排序
 8.2.1 直接插入排序
 8.2.2 希爾排序
 8.3 交換排序
 8.3.1 起泡排序
 8.3.2 快速排序
 8.4 選擇排序
 8.4.1 簡(jiǎn)單選擇排序
 8.4.2 堆排序
 8.5 歸并排序
 8.5.1 二路歸并排序的非遞歸實(shí)現(xiàn)
 8.5.2 二路歸并排序的遞歸實(shí)現(xiàn)
 8.6 分配排序
 8.6.1 桶式排序
 8.6.2 基數(shù)排序
 8.7 各種排序方法的比較
 思想火花——學(xué)會(huì)“盒子以外的思考”
 習(xí)題8
 思考題8
第9章 索引技術(shù)
 9.1 索引的基本概念
 9.2 線性索引技術(shù)
 9.2.1 稠密索引
 9.2.2 分塊索引
 9.2.3 多重表
 9.2.4 倒排表
 9.3 樹(shù)形索引
 9.3.1 2-3樹(shù)
 9.3.2 B_樹(shù)
 9.3.3 B+樹(shù)
 思想火花——隨處可見(jiàn)的索引
 習(xí)題9
附錄A 預(yù)備知識(shí)
 A.1 數(shù)學(xué)術(shù)語(yǔ)
 A.2 級(jí)數(shù)求和
 A.3 集合
 A.4 關(guān)系
附錄B C++語(yǔ)言基本語(yǔ)法
 B.1 程序結(jié)構(gòu)
 B.2 數(shù)據(jù)類(lèi)型
 B.3 控制語(yǔ)句
 B.4 輸入與輸出
 B.5 動(dòng)態(tài)存儲(chǔ)分配
 B.6 函數(shù)
 B.7 類(lèi)與對(duì)象
 B.8 模板
 B.9 異常處理
附錄C 詞匯索引
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：插圖：1.4.2 算法分析可能有人認(rèn)為，隨著計(jì)算機(jī)功能的日益強(qiáng)大，程序的運(yùn)行效率變得越來(lái)越不那么重要了。然而，計(jì)算機(jī)功能越強(qiáng)大，人們就越想去嘗試更復(fù)雜的問(wèn)題，而更復(fù)雜的問(wèn)題需要更大的計(jì)算量。實(shí)際上，我們不僅需要算法，而且需要“好”算法。以破解密碼的算法為例，理論上，通過(guò)窮舉法列出所有可能的輸入字符的組合情況可以破解任何密碼。但是，如果密碼較長(zhǎng)或組合情況太多，這個(gè)破解算法就需要很長(zhǎng)時(shí)間，可能幾年、十幾年甚至更多，這樣的算法顯然沒(méi)有實(shí)際意義。所以，在選擇和設(shè)計(jì)算法時(shí)要有效率的觀念，這一點(diǎn)比提高計(jì)算機(jī)本身的速度更為重要。1.度量算法效率的方法如何度量一個(gè)算法的效率呢？一種方法是事后統(tǒng)計(jì)的方法，先將算法實(shí)現(xiàn)，然后輸入適當(dāng)?shù)臄?shù)據(jù)運(yùn)行，測(cè)算其時(shí)間和空間開(kāi)銷(xiāo)。事后統(tǒng)計(jì)的方法至少有以下缺點(diǎn)：編寫(xiě)程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；②所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。通常我們采用事前分析估算的方法——漸進(jìn)復(fù)雜度，它是對(duì)算法所消耗資源的一種估算方法。

編輯推薦

《普通高校本科計(jì)算機(jī)專(zhuān)業(yè)特色教材精選·算法與程序設(shè)計(jì):數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》定位準(zhǔn)確，合理規(guī)劃教學(xué)內(nèi)容。能夠抓牢核心概念，提煉基礎(chǔ)性內(nèi)容，側(cè)重工程實(shí)踐，減少形式化描述，注重算法設(shè)計(jì)與程序?qū)崿F(xiàn)。本教材能夠結(jié)合教學(xué)對(duì)象分析課程特點(diǎn)，根據(jù)學(xué)生的認(rèn)知規(guī)律，按照從已知到未知的思維進(jìn)程逐步推進(jìn)教學(xué)內(nèi)容，知識(shí)單元的拓?fù)浣Y(jié)構(gòu)安排合理，主線清晰。針對(duì)數(shù)據(jù)結(jié)構(gòu)內(nèi)容抽象的特點(diǎn)，全書(shū)共設(shè)計(jì)了250多個(gè)插圖，大量的插圖將抽象的內(nèi)容進(jìn)行了具體化處理，降低了理解問(wèn)題的復(fù)雜性。數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)需要較強(qiáng)的C++語(yǔ)言的應(yīng)用能力，《普通高校本科計(jì)算機(jī)專(zhuān)業(yè)特色教材精選·算法與程序設(shè)計(jì):數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》的抽象數(shù)據(jù)類(lèi)型用“類(lèi)＋結(jié)構(gòu)體”的形式實(shí)現(xiàn)，既解釋了數(shù)據(jù)結(jié)構(gòu)的本質(zhì)內(nèi)容，又簡(jiǎn)化了程序設(shè)計(jì)。《普通高校本科計(jì)算機(jī)專(zhuān)業(yè)特色教材精選·算法與程序設(shè)計(jì):數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》第1版自出版以來(lái)，國(guó)內(nèi)有近100所院校將《普通高校本科計(jì)算機(jī)專(zhuān)業(yè)特色教材精選·算法與程序設(shè)計(jì):數(shù)據(jù)結(jié)構(gòu)(C++版)(第2版)》作為主講教材。在第1版成功的基礎(chǔ)上，作者不斷銳化思想、總結(jié)經(jīng)驗(yàn)，在教學(xué)思想、課程結(jié)構(gòu)、教材內(nèi)容、教材體例、表述方式等方面進(jìn)一步探索和實(shí)踐，形成了第2版。定位準(zhǔn)確，合理規(guī)劃教學(xué)內(nèi)容。能夠抓牢核心概念，提煉基礎(chǔ)性內(nèi)容，側(cè)重工程實(shí)踐，減少形式化描述，注重算法設(shè)計(jì)與程序?qū)崿F(xiàn)。遵循認(rèn)知規(guī)律，理清教學(xué)主線。能夠結(jié)合教學(xué)對(duì)象分析課程特點(diǎn)，根據(jù)學(xué)生的認(rèn)知規(guī)律，按照從已知到未知的思維進(jìn)程逐步推進(jìn)教學(xué)內(nèi)容，知識(shí)單元的拓?fù)浣Y(jié)構(gòu)安排合理，主線清晰。以知識(shí)為載體，注重能力培養(yǎng)。能夠注意引導(dǎo)思維，通過(guò)講思路講過(guò)程講方法，展現(xiàn)問(wèn)題的求解過(guò)程。分析難點(diǎn)，針對(duì)處理。針對(duì)數(shù)據(jù)結(jié)構(gòu)內(nèi)容抽象的特點(diǎn)，全書(shū)共設(shè)計(jì)了250多個(gè)插圖，大量的插圖將抽象的內(nèi)容進(jìn)行了具體化處理，降低了理解問(wèn)題的復(fù)雜性，使本教材做到“教師易教，學(xué)生易學(xué)”。立體化教材保證教學(xué)的有效實(shí)施。中國(guó)大學(xué)出版社圖書(shū)獎(jiǎng)優(yōu)秀教材一等獎(jiǎng)。

圖書(shū)封面

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

---

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

---