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

前言

　　“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)等電氣信息類相關(guān)專業(yè)的一門重要的基礎(chǔ)課程，也是一門必修的核心課程。在計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域都要用到不同的數(shù)據(jù)結(jié)構(gòu)，例如在操作系統(tǒng)中要用到隊(duì)列；編譯系統(tǒng)中要用到棧、散列表、語法樹；人工智能中要用到有向圖。另外，面向?qū)ο蟪绦蛟O(shè)計(jì)、計(jì)算機(jī)圖形學(xué)、軟件工程、多媒體技術(shù)等領(lǐng)域，都會(huì)用到很多數(shù)據(jù)結(jié)構(gòu)。　　“數(shù)據(jù)結(jié)構(gòu)”課程涉及各種離散結(jié)構(gòu)在計(jì)算機(jī)上如何存儲(chǔ)和處理，其內(nèi)容豐富、涉及面廣，而且還在隨各種基于計(jì)算機(jī)的應(yīng)用技術(shù)的發(fā)展而不斷增加新的內(nèi)容。通過學(xué)習(xí)，學(xué)生可以較全面理解算法和數(shù)據(jù)結(jié)構(gòu)的概念，掌握各種數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。“數(shù)據(jù)結(jié)構(gòu)”是一門理論與實(shí)際緊密聯(lián)系的課程，它旨在分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，從而使建立在其上的解決問題的算法達(dá)到最優(yōu)，并在此基礎(chǔ)上，編寫出結(jié)構(gòu)清晰、正確易讀、符合軟件工程規(guī)范的程序，從而為進(jìn)一步學(xué)習(xí)后續(xù)專業(yè)課程和軟件的開發(fā)打下堅(jiān)實(shí)的基礎(chǔ)?！　”緯鴮哟畏置?、結(jié)構(gòu)清晰、理論深度適當(dāng)，側(cè)重應(yīng)用。在教材組織方式上，注重從問題求解的角度出發(fā)，討論相關(guān)的基礎(chǔ)理論、數(shù)據(jù)和算法抽象、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)以及在C++程序設(shè)計(jì)語言中的實(shí)現(xiàn)。作為普通高等教育“十一五”國家級(jí)規(guī)劃教材《數(shù)據(jù)結(jié)構(gòu)（第二版）》的再版，本書保持了前兩版的基本框架，概念清晰、論述透徹、面向應(yīng)用。進(jìn)一步完善了算法與數(shù)據(jù)結(jié)構(gòu)的內(nèi)容體系，強(qiáng)調(diào)與考研大綱的一致性；對(duì)所有算法進(jìn)行了詳盡的注釋，進(jìn)一步細(xì)化了算法的描述，強(qiáng)調(diào)C++中面向?qū)ο蟮乃枷耄桓膶懥说诙嬷胁焕谧x者理解的描述，細(xì)化其中由讀者自行補(bǔ)充的部分，以利于讀者理解算法的基本思想。各章均安排有知識(shí)要點(diǎn)和習(xí)題。與本書配套的《數(shù)據(jù)結(jié)構(gòu)習(xí)題解答與實(shí)驗(yàn)指導(dǎo)（第三版）》詳細(xì)給出了書中習(xí)題的解答思路和參考答案，并且結(jié)合數(shù)據(jù)結(jié)構(gòu)課堂和實(shí)踐教學(xué)，設(shè)計(jì)了7項(xiàng)實(shí)驗(yàn)內(nèi)容，與本書一起構(gòu)成了一個(gè)完整的教學(xué)系列。　　本書的第1章～第3章由石強(qiáng)編寫修訂，第8章～第10章由羅文劫編寫修訂，第4章由金作濤編寫修訂，第5章、第7章由谷海紅編寫修訂，第6章由胡子義編寫修訂，最后由劉振鵬統(tǒng)一定稿?！　”緯趯懽骱托抻嗊^程中，得到了許多專家和眾多院?！皵?shù)據(jù)結(jié)構(gòu)”任課教師的大力支持和幫助，提出了許多中肯的意見和很好的建議，對(duì)本書的編寫修訂起到了很大的指導(dǎo)作用。對(duì)此，作者表示衷心的感謝?！　「兄x作者的多位同事和學(xué)生，他們在本書的資料收集、書稿編寫、算法驗(yàn)證和代碼調(diào)試、插圖繪制與內(nèi)容審核等各個(gè)環(huán)節(jié)提出了很多寶貴的意見，做了很多實(shí)質(zhì)性的工作?！　「兄x中國鐵道出版社的各位編輯和圖書推廣人員，他們?yōu)楸緯軌蛞暂^高的質(zhì)量完成和在更多院校使用做出了巨大貢獻(xiàn)。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)（第3版）》根據(jù)教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)關(guān)于“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)基本要求進(jìn)行編寫，介紹了各種最常用的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊(duì)列、矩陣的壓縮存儲(chǔ)、樹與二又樹、圖、查找、排序等?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計(jì)算機(jī)中的存儲(chǔ)表示，以及在這些數(shù)據(jù)結(jié)構(gòu)下的運(yùn)算和實(shí)現(xiàn)的算法，并對(duì)算法的效率進(jìn)行了簡要的分析?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》既注重原理又重視算法的實(shí)現(xiàn)，每個(gè)算法均給出Visual C++語言的描述，并加以詳細(xì)的注釋，每章都附有大量的習(xí)題?！　　稊?shù)據(jù)結(jié)構(gòu)（第3版）》內(nèi)容豐富、結(jié)構(gòu)清晰、深入淺出、突出算法，注重實(shí)踐和應(yīng)用，強(qiáng)調(diào)理論與實(shí)踐的結(jié)合，便于教學(xué)?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》適合作為高等院校計(jì)算機(jī)科學(xué)與應(yīng)用、通信工程、電子工程等電子信息類專業(yè)的教材，也可供相關(guān)證書考試、考研或從事計(jì)算機(jī)應(yīng)用與工程技術(shù)的工作者及計(jì)算機(jī)愛好者自學(xué)或參考使用。

書籍目錄

第1章緒論1.1 數(shù)據(jù)結(jié)構(gòu)的概念1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.1.2 相關(guān)概念和術(shù)語1.1.3 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1.2 數(shù)據(jù)類型和抽象數(shù)據(jù)類型1.2.1 數(shù)據(jù)類型1.2.2 抽象數(shù)據(jù)類型1.3 算法和算法分析1.3.1 算法特性1.3.2 算法描述1.3.3 算法性能分析與度量小結(jié)習(xí)題第2章 線性表2.1 線性表的邏輯結(jié)構(gòu)2.1.1 線性表的定義2.1.2 線性表的基本操作2.2 線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn)2.2.1 順序表2.2.2 順序表上基本運(yùn)算的實(shí)現(xiàn)2.2.3 順序表應(yīng)用舉例2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和運(yùn)算實(shí)現(xiàn)2.3.1 單鏈表2.3.2 單鏈表上基本運(yùn)算的實(shí)現(xiàn)2.3.3 循環(huán)鏈表2.3.4 雙向鏈表2.3.5 靜態(tài)鏈表2.3.6 間接尋址2.3.7 單鏈表應(yīng)用舉例2.4 順序表和鏈表的比較小結(jié)習(xí)題第3章 棧和隊(duì)列3.1 棧3.1.1 棧的定義及基本運(yùn)算3.1.2 棧的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)3.1.3 棧的應(yīng)用舉例3.2 隊(duì)列3.2.1 隊(duì)列的定義及基本運(yùn)算3.2.2 隊(duì)列的存儲(chǔ)實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)3.2.3 隊(duì)列應(yīng)用舉例小結(jié)習(xí)題第4章 串4.1 串及其基本運(yùn)算4.1.1 串的基本概念4.1.2 串的基本運(yùn)算4.2 串的定長順序存儲(chǔ)及基本運(yùn)算4.2.1 串的定長順序存儲(chǔ)4.2.2 定長順序串的基本運(yùn)算4.2.3 模式匹配4.3 串的堆存儲(chǔ)結(jié)構(gòu)4.3.1 串名的存儲(chǔ)映像4.3.2 堆存儲(chǔ)結(jié)構(gòu)4.3.3 基于堆結(jié)構(gòu)的串的基本運(yùn)算實(shí)現(xiàn)小結(jié)習(xí)題第5章 數(shù)組和廣義表5.1 數(shù)組5.1.1 一維數(shù)組5.1.2 多維數(shù)組5.1.3 數(shù)組的內(nèi)存映像5.2 特殊矩陣的壓縮存儲(chǔ)5.2.1 對(duì)稱矩陣5.2.2 三角矩陣5.2.3 帶狀矩陣5.3 稀疏矩陣5.3.1 稀疏矩陣的三元組表存儲(chǔ)5.3.2 稀疏矩陣的十字鏈表存儲(chǔ)5.4 廣義表5.4.1 廣義表的定義和基本運(yùn)算5.4.2 廣義表的存儲(chǔ)5.4.3 廣義表基本操作的實(shí)現(xiàn)小結(jié)習(xí)題第6章 二叉樹6.1 二叉樹的定義與性質(zhì)6.1.1 二叉樹的基本概念6.1.2 二叉樹的主要性質(zhì)6.2 二叉樹的基本操作與存儲(chǔ)實(shí)現(xiàn)6.2.1 二叉樹的存儲(chǔ)6.2.2 二叉樹的基本操作及實(shí)現(xiàn)6.3 二叉樹的遍歷6.3.1 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)6.3.2 二叉樹遍歷的非遞歸實(shí)現(xiàn)6.3.3 由遍歷序列恢復(fù)二叉樹6.3.4 不用棧的二叉樹遍歷的非遞歸方法6.4 線索二叉樹6.4.1 線索二叉樹的定義及結(jié)構(gòu)6.4.2 線索二叉樹的基本操作實(shí)現(xiàn)6.5 二叉樹的應(yīng)用舉例6.5.1 查找數(shù)據(jù)元素6.5.2 統(tǒng)計(jì)給定二叉樹中葉結(jié)點(diǎn)的數(shù)目6.5.3 創(chuàng)建二叉樹的二叉鏈表存儲(chǔ)6.5.4 表達(dá)式運(yùn)算6.6 哈夫曼樹6.6.1 問題引入6.6.2 哈夫曼樹的基本概念及其構(gòu)造方法6.6.3 哈夫曼樹的構(gòu)造算法6.6.4 哈夫曼編碼小結(jié)習(xí)題第7章 樹與森林7.1 樹的概念與表示7.1.1 樹的定義及相關(guān)術(shù)語7.1.2 樹的表示7.2 樹的基本操作與存儲(chǔ)7.2.1 樹的基本操作7.2.2 樹的存儲(chǔ)結(jié)構(gòu)7.3 樹、森林與二叉樹的轉(zhuǎn)換7.3.1 樹轉(zhuǎn)換為二叉樹7.3.2 森林轉(zhuǎn)換為二叉樹7.3.3 二叉樹轉(zhuǎn)換為樹和森林7.4 樹和森林的遍歷7.4.1 樹的遍歷7.4.2 森林的遍歷7.5 樹的應(yīng)用舉例7.5.1 判定樹7.5.2 集合的表示7.5.3 等價(jià)問題小結(jié)習(xí)題第8章 圖8.1 圖的基本概念8.1.1 圖的定義和術(shù)語8.1.2 圖的基本操作8.2 圖的存儲(chǔ)結(jié)構(gòu)8.2.1 鄰接矩陣8.2.2 鄰接表8.2.3 十字鏈表8.2.4 鄰接多重表8.3 圖的遍歷8.3.1 深度優(yōu)先搜索8.3.2 廣度優(yōu)先搜索8.3.3 應(yīng)用圖的遍歷判定圖的連通性8.3.4 生成樹和生成森林8.4 最小生成樹8.4.1 最小生成樹的概念8.4.2 普里姆(Prim)算法8.4.3 克魯斯卡爾(Kruskal)算法8.5 最短路徑8.5.1 迪杰斯特拉(Dijkstra)算法8.5.2 弗洛伊德(Floyd)算法8.6 拓?fù)渑判蚺c關(guān)鍵路徑8.6.1 有向無環(huán)圖的概念8.6.2 拓?fù)渑判?.6.3 關(guān)鍵路徑小結(jié)習(xí)題第9章 查找9.1 基本概念9.1.1 相關(guān)術(shù)語9.1.2 查找表結(jié)構(gòu)9.2 靜態(tài)查找表9.2.1 順序查找9.2.2 折半查找9.2.3 插值查找和斐波那契查找9.2.4 分塊查找9.3 二叉排序樹9.3.1 二叉排序樹的定義9.3.2 二叉排序樹的查找過程9.3.3 二叉排序樹的插入操作9.3.4 二叉排序樹的刪除操作9.4 平衡二叉樹9.4.1 平衡二叉樹的定義9.4.2 平衡二叉樹的平衡化旋轉(zhuǎn)9.4.3 平衡二叉樹的插入9.4.4 平衡二叉樹的查找性能分析9.5 B樹和B+樹9.5.1 B樹的定義9.5.2 B樹的查找9.5.3 B樹的插入9.5.4 B樹的刪除9.5.5 B+樹9.6 哈希表查找9.6.1 哈希表與哈希方法9.6.2 常用的哈希函數(shù)9.6.3 處理沖突的方法9.6.4 哈希表的查找性能分析小結(jié)習(xí)題第10章 排序10.1 排序的基本概念10.1.1 相關(guān)術(shù)語10.1.2 排序的時(shí)間開銷10.2 插入排序10.2.1 直接插入排序10.2.2 折半插入排序10.2.3 表插入排序10.2.4 希爾排序10.3 交換排序10.3.1 冒泡排序10.3.2 快速排序10.4 選擇排序10.4.1 簡單選擇排序10.4.2 樹形選擇排序10.4.3 堆排序10.5 歸并排序10.6 基數(shù)排序10.6.1 多關(guān)鍵碼排序10.6.2 鏈?zhǔn)交鶖?shù)排序10.7 外排序10.7.1 外部排序的方法10.7.2 多路平衡歸并的實(shí)現(xiàn)小結(jié)習(xí)題參考文獻(xiàn)

章節(jié)摘錄

　　1.1數(shù)據(jù)結(jié)構(gòu)的概念　　計(jì)算機(jī)在發(fā)展的初期，其應(yīng)用范圍是數(shù)值計(jì)算，所處理的數(shù)據(jù)都是整型、實(shí)型、布爾型等簡單數(shù)據(jù)，以此為加工、處理對(duì)象的程序設(shè)計(jì)稱為數(shù)值型程序設(shè)計(jì)。隨著計(jì)算技術(shù)的發(fā)展，計(jì)算機(jī)逐漸進(jìn)入到商業(yè)、制造業(yè)等其他領(lǐng)域，廣泛地應(yīng)用于數(shù)據(jù)處理和過程控制中。與此相對(duì)應(yīng)，計(jì)算機(jī)所處理的數(shù)據(jù)也不再是簡單的數(shù)值，而是字符串、圖形、圖像、語音、視頻等復(fù)雜的數(shù)據(jù)。這些復(fù)雜的數(shù)據(jù)不僅量大，而且具有一定的結(jié)構(gòu)。例如，一幅圖像是一個(gè)由簡單數(shù)值組成的矩陣，一個(gè)圖形中的幾何坐標(biāo)可以組成表。此外，語言編譯過程中所使用的棧、符號(hào)表和語法樹，操作系統(tǒng)中用到的隊(duì)列、磁盤目錄樹等，都是有結(jié)構(gòu)的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)所研究的就是這些有結(jié)構(gòu)的數(shù)據(jù)，因此，數(shù)據(jù)結(jié)構(gòu)的知識(shí)不論對(duì)研制系統(tǒng)軟件還是開發(fā)應(yīng)用軟件都非常重要，它是學(xué)習(xí)軟件知識(shí)和提高軟件設(shè)計(jì)水平的重要基礎(chǔ)。　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的基礎(chǔ)課，也是核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計(jì)算機(jī)來解決實(shí)際問題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語言是難以應(yīng)付眾多復(fù)雜課題的。要想有效地使用計(jì)算機(jī)并充分發(fā)揮計(jì)算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。打好數(shù)據(jù)結(jié)構(gòu)這門課程的扎實(shí)基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程、人工智能等都是十分有益的。

圖書封面

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

---

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

---