數(shù)據(jù)結(jié)構(gòu)及應(yīng)用

前言

在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一種在計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)，以便高效利用這些數(shù)據(jù)的有效方式。幾乎所有的程序或軟件系統(tǒng)都用到了數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是許多高效算法的基本要素，同時(shí)它也使得管理大規(guī)模數(shù)據(jù)成為可能。數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)的一門非常重要的專業(yè)基礎(chǔ)課，也是IT類各專業(yè)的核心基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)和結(jié)構(gòu)是兩個(gè)緊密聯(lián)系而又相互關(guān)聯(lián)的概念，數(shù)據(jù)是數(shù)據(jù)結(jié)構(gòu)的主要組成部分，它不涉及數(shù)據(jù)之間的關(guān)系；結(jié)構(gòu)才涉及而且只涉及數(shù)據(jù)之間的關(guān)系。從中文構(gòu)詞上來(lái)看，數(shù)據(jù)結(jié)構(gòu)更強(qiáng)調(diào)的是結(jié)構(gòu)，即數(shù)據(jù)之間的關(guān)聯(lián)方式。我們需要將適用于計(jì)算機(jī)的問題求解策略用計(jì)算機(jī)能理解的形式輸入到計(jì)算機(jī)中，告訴計(jì)算機(jī)如何一步一步地處理數(shù)據(jù)并最終得到問題的解，這就是算法。因此，從抽象層面上講，數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的。不同的應(yīng)用需求需要不同的算法，不同的算法需要不同的數(shù)據(jù)結(jié)構(gòu)來(lái)支持。從實(shí)現(xiàn)層面上講，數(shù)據(jù)結(jié)構(gòu)是為算法實(shí)現(xiàn)服務(wù)的。本書作者具有多年的教學(xué)和科研經(jīng)驗(yàn)，對(duì)各種數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法有深入的了解。本書對(duì)什么是數(shù)據(jù)結(jié)構(gòu)，什么是算法，算法和數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系進(jìn)行了生動(dòng)的闡述，并對(duì)各種線性數(shù)據(jù)結(jié)構(gòu)、非線性數(shù)據(jù)結(jié)構(gòu)、查找算法和排序算法等作了詳盡的描述和分析。本書基本概念清晰，重點(diǎn)和難點(diǎn)問題討論深入，而且循序漸進(jìn)，為讀者深入理解和應(yīng)用數(shù)據(jù)結(jié)構(gòu)給出了啟示。本書既注重對(duì)數(shù)據(jù)結(jié)構(gòu)經(jīng)典內(nèi)容的論述，又強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，對(duì)相關(guān)內(nèi)容進(jìn)行了啟發(fā)式討論，是一本值得閱讀和選用的教科書。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語(yǔ)言描述》系統(tǒng)地介紹各種常用的數(shù)據(jù)結(jié)構(gòu)以及排序、查找的各種算法，闡述各種數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系、存儲(chǔ)表示及運(yùn)算，涵蓋研究生入學(xué)考試大綱的所有內(nèi)容。全書采用c語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言，并對(duì)C語(yǔ)言描述的算法作了詳細(xì)的注解和簡(jiǎn)要的性能分析。全書共分為六個(gè)部分：第一部分主要介紹什么是數(shù)據(jù)結(jié)構(gòu)，什么是算法，它們之間有著怎樣的聯(lián)系，如何進(jìn)行算法分析；第二部分針對(duì)后續(xù)學(xué)習(xí)的需要幫助讀者溫習(xí)一些相關(guān)知識(shí)；第三部分和第四部分分別重點(diǎn)介紹幾種常見的線性結(jié)構(gòu)和非線性結(jié)構(gòu)；第五部分介紹在實(shí)際應(yīng)用中最常遇到的兩個(gè)運(yùn)算——查找（即搜索）和排序，以及實(shí)現(xiàn)這兩種運(yùn)算的各種算法；第六部分則簡(jiǎn)要介紹文件和外排序的相關(guān)內(nèi)容。 為了幫助讀者直觀、正確地理解各種數(shù)據(jù)結(jié)構(gòu)和算法的要旨，《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語(yǔ)言描述》利用大量的圖表進(jìn)行詮釋，并通過典型的思考題、例題和習(xí)題來(lái)加深讀者對(duì)相關(guān)知識(shí)的理解。 《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語(yǔ)言描述》內(nèi)容豐富、概念清楚、邏輯推理嚴(yán)謹(jǐn)、通俗易懂，可以作為計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)本科生的教材，也可以作為高等院校計(jì)算機(jī)專業(yè)碩士研究生入學(xué)考試的復(fù)習(xí)用書，同時(shí)還可以作為廣大工程技術(shù)人員的參考資料。

書籍目錄

序前言教學(xué)建議第一部分 概論第1章 數(shù)據(jù)結(jié)構(gòu)1.1 什么是數(shù)據(jù)1.2 什么是數(shù)據(jù)結(jié)構(gòu)1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)1.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1.2.3 數(shù)據(jù)的運(yùn)算1.3 什么是數(shù)據(jù)類型1.4 知識(shí)點(diǎn)小結(jié)習(xí)題第2章 算法2.1 什么是算法2.2 算法的描述2.3 算法分析2.3.1 時(shí)間復(fù)雜度2.3.2 漸近符號(hào)2.3.3 空間復(fù)雜度2.3.4 復(fù)雜度分析舉例2.4 知識(shí)點(diǎn)小結(jié)習(xí)題第二部分 預(yù)備知識(shí)第3章 C語(yǔ)言、遞歸及存儲(chǔ)分配方式3.1 C語(yǔ)言的相關(guān)內(nèi)容3.1.1 函數(shù)的參數(shù)傳遞與結(jié)果返回3.1.2 結(jié)構(gòu)體類型3.1.3 指針3.2 遞歸3.3 存儲(chǔ)分配方式3.4 知識(shí)點(diǎn)小結(jié)習(xí)題第三部分 線性結(jié)構(gòu)第4章 線性表4.1 線性表的類型定義4.1.1 線性表的邏輯結(jié)構(gòu)4.1.2 線性表的基本運(yùn)算4.2 線性表的順序存儲(chǔ)表示4.2.1 順序表4.2.2 順序表中基本運(yùn)算的實(shí)現(xiàn)4.3 線性表的鏈?zhǔn)酱鎯?chǔ)表示4.3.1 單鏈表4.3.2 單鏈表中基本運(yùn)算的實(shí)現(xiàn)4.4 線性表的其他鏈?zhǔn)酱鎯?chǔ)表示4.4.1 靜態(tài)單鏈表4.4.2 雙(向)鏈表4.4.3 循環(huán)單(向)鏈表4.4.4 循環(huán)雙(向)鏈表4.5 線性表的應(yīng)用舉例4.6 順序表和鏈表的比較4.7 知識(shí)點(diǎn)小結(jié)習(xí)題第5章 棧5.1 棧的類型定義5.1.1 棧的邏輯結(jié)構(gòu)5.1.2 棧的基本運(yùn)算5.2 棧的順序存儲(chǔ)表示5.2.1 順序棧5.2.2 順序棧中基本運(yùn)算的實(shí)現(xiàn)5.3 棧的鏈?zhǔn)酱鎯?chǔ)表示5.3.1 鏈棧5.3.2 鏈棧中基本運(yùn)算的實(shí)現(xiàn)5.4 兩個(gè)方向生長(zhǎng)的棧5.5 棧的應(yīng)用舉例5.6 知識(shí)點(diǎn)小結(jié)習(xí)題第6章 隊(duì)列6.1 隊(duì)列的類型定義6.1.1 隊(duì)列的邏輯結(jié)構(gòu)6.1.2 隊(duì)列的基本運(yùn)算6.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示6.2.1 鏈隊(duì)列6.2.2 鏈隊(duì)列中基本運(yùn)算的實(shí)現(xiàn)6.3 隊(duì)列的順序存儲(chǔ)表示6.3.1 順序隊(duì)列6.3.2 循環(huán)隊(duì)列6.3.3 循環(huán)隊(duì)列中基本運(yùn)算的實(shí)現(xiàn)6.4 雙端隊(duì)列6.5 隊(duì)列的應(yīng)用舉例6.6 知識(shí)點(diǎn)小結(jié)習(xí)題第7章 串7.1 串的類型定義7.1.1 串的邏輯結(jié)構(gòu)7.1.2 串的基本運(yùn)算7.2 串的順序存儲(chǔ)表示7.3 串的堆分配存儲(chǔ)表示7.4 串的塊鏈存儲(chǔ)表示7.5 串的模式匹配7.6 知識(shí)點(diǎn)小結(jié)習(xí)題第8章 數(shù)組及廣義表8.1 數(shù)組的類型定義8.1.1 數(shù)組的定義8.1.2 數(shù)組的性質(zhì)8.1.3 數(shù)組的基本運(yùn)算8.2 數(shù)組的順序存儲(chǔ)表示8.3 特殊矩陣的壓縮存儲(chǔ)8.3.1 特殊形狀矩陣的壓縮存儲(chǔ)8.3.2 隨機(jī)稀疏矩陣的壓縮存儲(chǔ)及其運(yùn)算8.4 廣義表8.4.1 廣義表的基本概念8.4.2 廣義表的基本運(yùn)算8.4.3 廣義表的存儲(chǔ)結(jié)構(gòu)8.5 知識(shí)點(diǎn)小結(jié)習(xí)題第四部分 非線性結(jié)構(gòu)第9章 樹9.1 概述9.1.1 樹的定義及基本術(shù)語(yǔ)9.1.2 樹的存儲(chǔ)結(jié)構(gòu)9.2 二叉樹9.2.1 二叉樹的定義9.2.2 二叉樹的性質(zhì)9.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)9.3 二叉樹的遍歷9.3.1 遍歷操作9.3.2 先序遍歷9.3.3 中序遍歷9.3.4 后序遍歷9.3.5 層次遍歷9.3.6 二叉樹遍歷的應(yīng)用舉例9.4 線索二叉樹9.4.1 二叉樹的線索化9.4.2 線索二叉樹上的運(yùn)算9.5 二叉樹的應(yīng)用9.5.1 哈夫曼樹及其應(yīng)用9.5.2 二叉排序樹9.5.3 平衡二叉樹9.6 樹、森林與二叉樹的相互轉(zhuǎn)換9.6.1 樹與二叉樹的相互轉(zhuǎn)換9.6.2 森林與二叉樹的相互轉(zhuǎn)換9.7 樹、森林的遍歷9.7.1 樹的遍歷9.7.2 森林的遍歷9.8 樹的應(yīng)用舉例9.9 知識(shí)點(diǎn)小結(jié)習(xí)題第10章 圖10.1 概述10.1.1 圖的定義及基本術(shù)語(yǔ)10.1.2 圖的存儲(chǔ)結(jié)構(gòu)10.1.3 圖的創(chuàng)建10.2 圖的遍歷10.2.1 深度優(yōu)先搜索遍歷10.2.2 廣度優(yōu)先搜索遍歷10.2.3 圖遍歷的應(yīng)用舉例10.3 生成樹10.3.1 連通圖的生成樹10.3.2 連通網(wǎng)的最小生成樹10.4 最短路徑10.4.1 單源最短路徑10.4.2 每對(duì)頂點(diǎn)間的最短路徑10.5 有向無(wú)環(huán)圖及其應(yīng)用10.5.1 AOV網(wǎng)與拓?fù)渑判?0.5.2 AOE網(wǎng)與關(guān)鍵路徑10.6 知識(shí)點(diǎn)小結(jié)習(xí)題第五部分 兩種重要運(yùn)算第11章 查找11.1 查找的基本概念11.2 主要查找方法簡(jiǎn)介11.3 靜態(tài)查找11.3.1 順序查找11.3.2 二分查找11.3.3 分塊查找11.4 動(dòng)態(tài)查找11.5 散列查找11.5.1 散列表的概念11.5.2 散列函數(shù)的構(gòu)造方法11.5.3 處理沖突的方法11.5.4 散列表的查找11.6 知識(shí)點(diǎn)小結(jié)習(xí)題第12章 內(nèi)排序12.1 排序的基本概念12.2 插入排序12.2.1 直接插入排序12.2.2 希爾排序12.3 交換排序12.3.1 冒泡排序12.3.2 快速排序12.4 選擇排序12.4.1 直接選擇排序12.4.2 樹形選擇排序12.4.3 堆排序12.5 歸并排序12.6 分配排序12.6.1 箱排序12.6.2 基數(shù)排序12.7 各種內(nèi)排序法的比較12.8 知識(shí)點(diǎn)小結(jié)習(xí)題第六部分 文件的組織結(jié)構(gòu)及排序第13章 文件13.1 文件的基本概念13.2 順序文件13.3 索引文件13.4 索引順序文件13.5 散列文件13.6 多關(guān)鍵字文件13.7 知識(shí)點(diǎn)小結(jié)習(xí)題第14章 外排序14.1 多路平衡歸并14.2 置換選擇排序14.3 歸并樹及最佳歸并樹14.4 知識(shí)點(diǎn)小結(jié)習(xí)題參考文獻(xiàn)

章節(jié)摘錄

插圖：有用就會(huì)有需求，有了需求就會(huì)有動(dòng)力，因此在開始本課程學(xué)習(xí)之前，我們必須弄清楚一個(gè)問題：我們?yōu)槭裁葱枰獙W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？計(jì)算機(jī)領(lǐng)域分兩個(gè)大的方向：一個(gè)是硬件方向，另一個(gè)是軟件方向。硬件方向又包括兩個(gè)大的方面：一個(gè)是硬件技術(shù)的發(fā)展，另一個(gè)是如何在現(xiàn)有硬件條件下設(shè)計(jì)出高性能的計(jì)算機(jī)系統(tǒng)。軟件是程序、數(shù)據(jù)以及文件的集合，它大致可分為系統(tǒng)軟件和應(yīng)用軟件兩大類。系統(tǒng)軟件追求的是如何在方便用戶使用的前提下將計(jì)算機(jī)系統(tǒng)的性能發(fā)揮到極致；應(yīng)用軟件則是直接面對(duì)終端用戶，它尋求的是更高的服務(wù)質(zhì)量和更好的用戶服務(wù)體驗(yàn)。我們將從應(yīng)用軟件開發(fā)者的視角來(lái)探尋數(shù)據(jù)結(jié)構(gòu)的重要性。實(shí)際問題往往很復(fù)雜，當(dāng)我們求解實(shí)際問題的時(shí)候，往往是對(duì)實(shí)際問題的模型進(jìn)行求解。所謂模型就是對(duì)實(shí)際問題的簡(jiǎn)化，是反映問題本質(zhì)的數(shù)據(jù)集合以及數(shù)據(jù)之間關(guān)系的集合。對(duì)模型的求解則是找到對(duì)給定的輸入數(shù)據(jù)的一系列處理步驟，使得能夠得到預(yù)期的輸出。為了讓計(jì)算機(jī)實(shí)現(xiàn)我們對(duì)模型的求解思路，則必須將模型映射到存儲(chǔ)器中，這樣計(jì)算機(jī)才能根據(jù)人的意圖對(duì)操作對(duì)象（即數(shù)據(jù)）進(jìn)行處理。通過上面的分析可知，計(jì)算機(jī)的各種應(yīng)用實(shí)際上都是對(duì)數(shù)據(jù)的處理，因此對(duì)數(shù)據(jù)以及它們之間的關(guān)系進(jìn)行分析、表示是必不可少的。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用:C語(yǔ)言描述》系統(tǒng)地介紹了各種常用的數(shù)據(jù)結(jié)構(gòu)以及排序、查找的各種算法，闡述了各種數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系、存儲(chǔ)表示及運(yùn)算操作，基本涵蓋了研究生入學(xué)考試大綱的所有內(nèi)容。基礎(chǔ)與應(yīng)用并重?！稊?shù)據(jù)結(jié)構(gòu)及應(yīng)用:C語(yǔ)言描述》不僅對(duì)什么是數(shù)據(jù)結(jié)構(gòu)，什么是算法，它們之間有著怎樣的聯(lián)系，如何鑒定一個(gè)算法的好壞，數(shù)據(jù)結(jié)構(gòu)有哪些常用的線性結(jié)構(gòu)和非線性結(jié)構(gòu)，它們各有什么特點(diǎn)和應(yīng)用，有哪些經(jīng)典的查找和排序算法等問題進(jìn)行清晰、全面的闡述，而且關(guān)注應(yīng)用，利用眾多實(shí)例幫助讀者加深對(duì)基本知識(shí)的理解并靈活運(yùn)用。圖文并茂，生動(dòng)有趣。《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用:C語(yǔ)言描述》為了幫助讀者直觀、正確地理解各種數(shù)據(jù)結(jié)構(gòu)和算法的要旨，利用大量的圖表進(jìn)行詮釋，以通俗易懂的方式介紹復(fù)雜的概念。積極引導(dǎo)，活躍思維?！稊?shù)據(jù)結(jié)構(gòu)及應(yīng)用:C語(yǔ)言描述》在介紹完重要知識(shí)點(diǎn)后會(huì)設(shè)置一些思考題，引導(dǎo)讀者對(duì)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用進(jìn)行深入思考和理解，訓(xùn)練讀者的發(fā)散性思維。讀者對(duì)象廣泛?！稊?shù)據(jù)結(jié)構(gòu)及應(yīng)用:C語(yǔ)言描述》內(nèi)容豐富、概念清楚、邏輯推理嚴(yán)謹(jǐn)、通俗易懂，既便于教學(xué)，又適合自學(xué)，可作為計(jì)算機(jī)及相關(guān)專業(yè)本科生的教材，也可作為計(jì)算機(jī)專業(yè)碩士研究生入學(xué)考試的復(fù)習(xí)用書，還可作為廣大工程技術(shù)人員的參考資料。

圖書封面

圖書標(biāo)簽Tags

無(wú)

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

---

    數(shù)據(jù)結(jié)構(gòu)及應(yīng)用 PDF格式下載

---