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

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無(wú)

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

---

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

---