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

前言

　　數(shù)據(jù)結(jié)構(gòu)是計算機學科各專業(yè)一門重要的專業(yè)基礎(chǔ)課，也是其他計算機相關(guān)專業(yè)的一門必修課或選修課。數(shù)據(jù)結(jié)構(gòu)課程主要討論現(xiàn)實世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計算機中的存儲結(jié)構(gòu)以及各種算法的設計問題。數(shù)據(jù)結(jié)構(gòu)課程的目的，是使學生掌握組織數(shù)據(jù)、存儲數(shù)據(jù)以及處理數(shù)據(jù)的基本概念和軟件設計的基本方法，從而為進一步學習后續(xù)專業(yè)課程打下堅實的基礎(chǔ)。　　本書包含了2009年研究生入學統(tǒng)考大綱的全部內(nèi)容。本書討論的典型數(shù)據(jù)結(jié)構(gòu)問題包括線性表、堆棧、隊列、串、數(shù)組、遞歸、廣義表、樹、二叉樹、圖、排序、查找、文件等。對于線性表、堆棧、隊列、串、數(shù)組、廣義表、樹、二叉樹和圖等基本數(shù)據(jù)結(jié)構(gòu)問題，都詳細討論了各自的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及各種算法的設計方法。排序和查找是兩個應用廣泛的算法設計問題，本書討論了幾種典型的排序算法，討論了靜態(tài)查找、動態(tài)查找和哈希查找的存儲結(jié)構(gòu)和查找方法。廣義表、樹、二叉樹和圖這些非線性結(jié)構(gòu)的算法經(jīng)常要設計成遞歸算法，本書專設一章討論遞歸算法的設計方法等問題?！　?shù)據(jù)結(jié)構(gòu)課程是一門理論和實踐結(jié)合密切的課程。本書采用理論敘述簡潔準確、實踐應用舉例豐富完整的方法編寫。理論采用豐富、完整的設計實例予以說明，設計實例從側(cè)面解釋了概念和應用方法，從而達到理論和實踐密切結(jié)合的教學目的。本書采用c語言描述算法。　　本書具有如下特點。　?。?）內(nèi)容豐富，難度適中，文字簡潔準確，圖文并茂?！　。?）本書的所有算法都經(jīng)上機調(diào)試通過，包括各章的操作實現(xiàn)函數(shù)、各章的程序設計實例以及習題解答中給出的算法設計。　?。?）習題全面，覆蓋面廣，擇要解答。每章最后設計了大量的習題，覆蓋了各章的全部教學內(nèi)容，并在附錄B中給出了部分習題解答?！　。?）課內(nèi)上機參考資料豐富。數(shù)據(jù)結(jié)構(gòu)課程是一門理論結(jié)合實踐的課程，通常要求包含10多課時的課內(nèi)上機實習（或稱項目設計）。本書各章的習題部分都專門設計了一定數(shù)量的上機實習題。另外，附錄A還給出了上機實習報告書寫規(guī)范和一個上機實習報告書寫實例，可供學生參考?！　”緯髡?0多年來一直從事數(shù)據(jù)結(jié)構(gòu)課程的教學工作，曾編著過若干本采用不同算法描述語言的數(shù)據(jù)結(jié)構(gòu)教材。本書是在經(jīng)過長期使用的以前出版的教材基礎(chǔ)上，參照新的研究生入學統(tǒng)考大綱，通過作者進一步修改、補充和完善而成的?！　「鶕?jù)作者的經(jīng)驗，使用本教材授課約需54～80課時，其中包括約10課時的課內(nèi)上機實習?！　∈褂帽緯淖x者可登錄華信教育資源網(wǎng)免費下載教學課件。

內(nèi)容概要

數(shù)據(jù)結(jié)構(gòu)是計算機學科各專業(yè)的一門重要的專業(yè)基礎(chǔ)課。本書系統(tǒng)地介紹了各種典型的數(shù)據(jù)結(jié)構(gòu)，以及遞歸、查找和排序的方法。本書采用理論敘述簡潔準確、實踐應用舉例豐富完整的方法編寫，從而達到理論和實踐密切結(jié)合的教學目的。本書采用C語言描述算法。
本書內(nèi)容豐富，難度適中，文字簡潔準確，圖文并茂，應用實例多，教學參考資料豐富。
本書既可作為計算機本科、專科學生的教材，也可供從事計算機工程和應用工作的科技工作者參考。

書籍目錄

第1章  緒論
  1.1  數(shù)據(jù)結(jié)構(gòu)的基本概念
    1.1.1  數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)元素的數(shù)據(jù)類型
    1.1.2  數(shù)據(jù)的邏輯結(jié)構(gòu)
    1.1.3  數(shù)據(jù)的存儲結(jié)構(gòu)
    1.1.4  數(shù)據(jù)的操作
    1.1.5  數(shù)據(jù)結(jié)構(gòu)課程討論的主要內(nèi)容
  1.2  抽象數(shù)據(jù)類型
  1.3  算法和算法的時間復雜度
    1.3.1  算法
    1.3.2  算法的性質(zhì)和設計目標
    1.3.3  算法的時間效率分析
    1.3.4  算法耗時的實際測試
    1.3.5  數(shù)據(jù)元素個數(shù)和時間復雜度
  1.4  算法書寫規(guī)范
  習題1
第2章  線性表
  2.1  線性表概述
    2.1.1  線性表的定義
    2.1.2  線性表的抽象數(shù)據(jù)類型
  2.2  線性表的順序表示和實現(xiàn)
    2.2.1  順序表的存儲結(jié)構(gòu)
    2.2.2  順序表操作的實現(xiàn)
    2.2.3  順序表操作的效率分析
    2.2.4  順序表應用舉例
  2.3  線性表的鏈式表示和實現(xiàn)
    2.3.1  單鏈表的存儲結(jié)構(gòu)
    2.3.2  單鏈表的操作實現(xiàn)
    2.3.3  單鏈表操作的效率分析
    2.3.4  單鏈表應用舉例
    2.3.5  循環(huán)單鏈表
    2.3.6  雙向鏈表
  2.4  靜態(tài)鏈表
    2.5  算法設計舉例
    2.5.1  順序表算法設計舉例
    2.5.2  單鏈表算法設計舉例
  習題2
第3章  堆棧和隊列
  3.1  堆棧
    3.1.1  堆棧的基本概念
    3.1.2  堆棧的抽象數(shù)據(jù)類型
    3.1.3  堆棧的順序表示和實現(xiàn)
    3.1.4  堆棧的鏈式表示和實現(xiàn)
  3.2  堆棧應用
    3.2.1  括號匹配問題
    3.2.2  算術(shù)表達式計算問題
  3.3  隊列
    3.3.1  隊列的基本概念
    3.3.2  隊列的抽象數(shù)據(jù)類型
    3.3.3  順序隊列以及存在的問題
    3.3.4  順序循環(huán)隊列的表示和實現(xiàn)
    3.3.5  鏈式隊列
    3.3.6  隊列的應用
  3.4  優(yōu)先級隊列
    3.4.1  順序優(yōu)先級隊列的設計和實現(xiàn)
    3.4.2  優(yōu)先級隊列的應用
  習題3
第4章  串
  4.1  串概述
    4.1.1  串及其基本概念
    4.1.2  串的抽象數(shù)據(jù)類型
    4.1.3  C語言的串函數(shù)
  4.2  串的存儲結(jié)構(gòu)
  4.3  串基本操作的實現(xiàn)算法
  4.4  串的模式匹配算法
    4.4.1  Brute-Force算法
    4.4.2  KMP算法
    4.4.3  Brute-Force算法和KMP算法的比較
  習題4
第5章  數(shù)組
  5.1  數(shù)組概述
    5.1.1  數(shù)組的定義
    5.1.2  數(shù)組的實現(xiàn)機制
    5.1.3  數(shù)組的抽象數(shù)據(jù)類型
  5.2  動態(tài)數(shù)組
    5.2.1  動態(tài)數(shù)組的設計方法
    5.2.2  動態(tài)數(shù)組和靜態(tài)數(shù)組對比
  5.3  特殊矩陣的壓縮存儲
    5.4  稀疏矩陣的壓縮存儲
    5.4.1  稀疏矩陣的三元組順序表
    5.4.2  稀疏矩陣的三元組鏈表
  習題5
第6章  遞歸算法
  6.1  遞歸的概念
  6.2  遞歸算法的執(zhí)行過程
  6.3  遞歸算法的設計方法
  6.4  遞歸過程和運行時棧
  6.5  遞歸算法的時間效率分析
  6.6  遞歸算法到非遞歸算法的轉(zhuǎn)換
  6.7  設計舉例
    6.7.1  一般遞歸算法設計舉例
    6.7.2  回溯算法及設計舉例
  習題6
第7章  廣義表
  7.1  廣義表概述
    7.1.1  廣義表的概念
    7.1.2  廣義表的抽象數(shù)據(jù)類型
  7.2  廣義表的存儲結(jié)構(gòu)
    7.2.1  頭鏈和尾鏈存儲結(jié)構(gòu)
    7.2.2  原子和子表存儲結(jié)構(gòu)
  7.3  廣義表的操作實現(xiàn)
    7.3.1  頭鏈和尾鏈存儲結(jié)構(gòu)下的操作實現(xiàn)
    7.3.2  頭鏈和尾鏈存儲結(jié)構(gòu)應用舉例
    7.3.3  原子和子表存儲結(jié)構(gòu)下的操作實現(xiàn)
    7.3.4  原子和子表存儲結(jié)構(gòu)應用舉例
  習題7
第8章  樹和二叉樹
  8.1  樹
    8.1.1  樹的定義
    8.1.2  樹的表示方法
    8.1.3  樹的抽象數(shù)據(jù)類型
    8.1.4  樹的存儲結(jié)構(gòu)
  8.2  二叉樹
    8.2.1  二叉樹的定義
    8.2.2  二叉樹的抽象數(shù)據(jù)類型
    8.2.3  二叉樹的性質(zhì)
  8.3  二叉樹的設計和實現(xiàn)
    8.3.1  二叉樹的存儲結(jié)構(gòu)
    8.3.2  二叉樹的操作實現(xiàn)
  8.4  二叉樹遍歷
    8.4.1  二叉樹遍歷的方法和結(jié)構(gòu)
    8.4.2  二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn)
    8.4.3  二叉樹遍歷的應用
    8.4.4  非遞歸的二叉樹遍歷算法
  8.5  線索二叉樹
    8.5.1  線索二叉樹及其用途
    8.5.2  中序線索二叉樹的設計
    8.5.3  中序線索二叉樹循環(huán)操作的設計
    8.5.4  設計舉例
  8.6  哈夫曼樹
    8.6.1  哈夫曼樹的基本概念
    8.6.2  哈夫曼編碼問題
    8.6.3  哈夫曼編碼問題設計和實現(xiàn)
  8.7  等價問題
  8.8  樹與二叉樹的轉(zhuǎn)換
  8.9  樹的遍歷
  習題8
第9章  圖
  9.1  圖概述
    9.1.1  圖的基本概念
    9.1.2  圖的抽象數(shù)據(jù)類型
  9.2  圖的存儲結(jié)構(gòu)
    9.2.1  圖的鄰接矩陣存儲結(jié)構(gòu)
    9.2.2  圖的鄰接表存儲結(jié)構(gòu)
  9.3  圖的實現(xiàn)
    9.3.1  鄰接矩陣存儲結(jié)構(gòu)下圖操作的實現(xiàn)
    9.3.2  鄰接表存儲結(jié)構(gòu)下圖操作的實現(xiàn)
  9.4  圖的遍歷
    9.4.1  圖的深度和廣度優(yōu)先遍歷算法
    9.4.2  圖的深度和廣度優(yōu)先遍歷算法實現(xiàn)
  9.5  最小生成樹
    9.5.1  最小生成樹的基本概念
    9.5.2  普里姆算法
    9.5.3  克魯斯卡爾算法
  9.6  最短路徑
    9.6.1  最短路徑的基本概念
    9.6.3  每對頂點之間的最短路徑
  9.7  拓撲排序
  9.8  關(guān)鍵路徑
  習題9
第10章  排序
  10.1  排序的基本概念
  10.2  插入排序
    10.2.1  直接插入排序
    10.2.2  希爾排序
  10.3  選擇排序
    10.3.1  直接選擇排序
    10.3.2  堆排序
  10.4  交換排序
    10.4.1  冒泡排序
    10.4.2  快速排序
  10.5  歸并排序
  10.6  基數(shù)排序
  10.7  排序算法性能比較
  習題10
第11章  查找
  11.1  查找的基本概念
  11.2  靜態(tài)查找
    11.2.1  順序表
    11.2.2  有序順序表
    11.2.3  索引順序表
  11.3  動態(tài)查找
    11.3.1  二叉排序樹和平衡二叉樹
    11.3.2  B-樹和B樹
  11.4  哈希查找
    11.4.1  哈希表的基本概念
    11.4.2  哈希函數(shù)構(gòu)造方法
    11.4.3  哈希沖突解決方法
    11.4.4  哈希表設計
  習題11
第12章  文件
  12.1  文件概述
    12.1.1  文件的演變過程及基本概念
    12.1.2  文件的存儲介質(zhì)
    12.1.3  文件的基本操作
  12.2  順序文件
  12.3  索引文件
  12.4  ISAM文件
  12.5  VSAM文件
  12.6  散列文件
  習題12
附錄A  上機實習內(nèi)容規(guī)范和上機實習報告范例
  附錄A.1  上機實習內(nèi)容規(guī)范
  附錄A.2  上機實習報告范例
附錄B  部分習題解答
參考文獻

章節(jié)摘錄

　　【問題分析】 迷宮問題中包括有很多路口，每個路口最多有三個搜索分支，把算法設計為如下的搜索過程：把整個搜索分解為向左、向前和向右三個方向上子問題的搜索。當搜索到某個路口（設該路口為c）、發(fā)現(xiàn)該路口沒有可搜索方向時，就讓搜索過程回溯退到該路口的前一路口（設該路口為B），然后搜索這個路口（即路口B）的其他尚未搜索過的搜索方向；如果發(fā)現(xiàn)這個路口（即路口B）也沒有可搜索方向時，就讓搜索過程繼續(xù)回溯退到這個路口的前一路口（設該路口為A）繼續(xù)這樣的搜索過程。這樣的搜索過程一直進行到找到出口或搜索完了全部可連通的路口的可能搜索方向沒有找到出口為止?！　　緮?shù)據(jù)結(jié)構(gòu)設計】 要用計算機模仿迷宮問題，首先要把迷宮問題數(shù)值化。把每個路口定義成一個包括lefc、forward和right三個域的結(jié)構(gòu)體，分別表示向左、向前和向右的搜索方向。如果某個域的值x為非0，則表示該方向上可到路口x；如果某個域的值x為0，則表示該方向上是死路。

編輯推薦

　　《數(shù)據(jù)結(jié)構(gòu)：使用C語言（第4版）》包含了2009年研究生入學統(tǒng)考大綱的全部內(nèi)容?！稊?shù)據(jù)結(jié)構(gòu)：使用C語言（第4版）》討論的典型數(shù)據(jù)結(jié)構(gòu)問題。對于線性表、堆棧、隊列、串、數(shù)組、廣義表、樹、二叉樹和圖等基本數(shù)據(jù)結(jié)構(gòu)問題，都詳細討論了各自的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及各種算法的設計方法。排序和查找是兩個應用廣泛的算法設計問題，《數(shù)據(jù)結(jié)構(gòu)：使用C語言（第4版）》討論了幾種典型的排序算法，討論了靜態(tài)查找、動態(tài)查找和哈希查找的存儲結(jié)構(gòu)和查找方法。廣義表、樹、二又樹和圖這些非線性結(jié)構(gòu)的算法經(jīng)常要設計成遞歸算法，《數(shù)據(jù)結(jié)構(gòu)：使用C語言（第4版）》專設一章討論遞歸算法的設計方法等問題。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---