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

前言

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

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)（第3版）》根據(jù)教育部高等學(xué)校計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會關(guān)于“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)基本要求進行編寫，介紹了各種最常用的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊列、矩陣的壓縮存儲、樹與二又樹、圖、查找、排序等?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計算機中的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)下的運算和實現(xiàn)的算法，并對算法的效率進行了簡要的分析?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》既注重原理又重視算法的實現(xiàn)，每個算法均給出Visual C++語言的描述，并加以詳細的注釋，每章都附有大量的習(xí)題?！　　稊?shù)據(jù)結(jié)構(gòu)（第3版）》內(nèi)容豐富、結(jié)構(gòu)清晰、深入淺出、突出算法，注重實踐和應(yīng)用，強調(diào)理論與實踐的結(jié)合，便于教學(xué)?！稊?shù)據(jù)結(jié)構(gòu)（第3版）》適合作為高等院校計算機科學(xué)與應(yīng)用、通信工程、電子工程等電子信息類專業(yè)的教材，也可供相關(guān)證書考試、考研或從事計算機應(yīng)用與工程技術(shù)的工作者及計算機愛好者自學(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 線性表的順序存儲及運算實現(xiàn)2.2.1 順序表2.2.2 順序表上基本運算的實現(xiàn)2.2.3 順序表應(yīng)用舉例2.3 線性表的鏈式存儲和運算實現(xiàn)2.3.1 單鏈表2.3.2 單鏈表上基本運算的實現(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章 棧和隊列3.1 棧3.1.1 棧的定義及基本運算3.1.2 棧的存儲實現(xiàn)和運算實現(xiàn)3.1.3 棧的應(yīng)用舉例3.2 隊列3.2.1 隊列的定義及基本運算3.2.2 隊列的存儲實現(xiàn)及運算實現(xiàn)3.2.3 隊列應(yīng)用舉例小結(jié)習(xí)題第4章 串4.1 串及其基本運算4.1.1 串的基本概念4.1.2 串的基本運算4.2 串的定長順序存儲及基本運算4.2.1 串的定長順序存儲4.2.2 定長順序串的基本運算4.2.3 模式匹配4.3 串的堆存儲結(jié)構(gòu)4.3.1 串名的存儲映像4.3.2 堆存儲結(jié)構(gòu)4.3.3 基于堆結(jié)構(gòu)的串的基本運算實現(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 特殊矩陣的壓縮存儲5.2.1 對稱矩陣5.2.2 三角矩陣5.2.3 帶狀矩陣5.3 稀疏矩陣5.3.1 稀疏矩陣的三元組表存儲5.3.2 稀疏矩陣的十字鏈表存儲5.4 廣義表5.4.1 廣義表的定義和基本運算5.4.2 廣義表的存儲5.4.3 廣義表基本操作的實現(xiàn)小結(jié)習(xí)題第6章 二叉樹6.1 二叉樹的定義與性質(zhì)6.1.1 二叉樹的基本概念6.1.2 二叉樹的主要性質(zhì)6.2 二叉樹的基本操作與存儲實現(xiàn)6.2.1 二叉樹的存儲6.2.2 二叉樹的基本操作及實現(xiàn)6.3 二叉樹的遍歷6.3.1 二叉樹的遍歷方法及遞歸實現(xiàn)6.3.2 二叉樹遍歷的非遞歸實現(xiàn)6.3.3 由遍歷序列恢復(fù)二叉樹6.3.4 不用棧的二叉樹遍歷的非遞歸方法6.4 線索二叉樹6.4.1 線索二叉樹的定義及結(jié)構(gòu)6.4.2 線索二叉樹的基本操作實現(xiàn)6.5 二叉樹的應(yīng)用舉例6.5.1 查找數(shù)據(jù)元素6.5.2 統(tǒng)計給定二叉樹中葉結(jié)點的數(shù)目6.5.3 創(chuàng)建二叉樹的二叉鏈表存儲6.5.4 表達式運算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 樹的基本操作與存儲7.2.1 樹的基本操作7.2.2 樹的存儲結(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é)習(xí)題第8章 圖8.1 圖的基本概念8.1.1 圖的定義和術(shù)語8.1.2 圖的基本操作8.2 圖的存儲結(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 拓撲排序與關(guān)鍵路徑8.6.1 有向無環(huán)圖的概念8.6.2 拓撲排序8.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 排序的時間開銷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 鏈式基數(shù)排序10.7 外排序10.7.1 外部排序的方法10.7.2 多路平衡歸并的實現(xiàn)小結(jié)習(xí)題參考文獻

章節(jié)摘錄

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

圖書封面

評論、評分、閱讀與下載

---

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

---