數(shù)據(jù)結(jié)構

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

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

---