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

前言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)等電子信息類相關(guān)專業(yè)的一門重要的基礎(chǔ)課程。許多高等院校將它作為理科各系主干基礎(chǔ)課列入學(xué)校的教學(xué)計(jì)劃之中。通過講授本課，學(xué)生可以較全面地理解算法和數(shù)據(jù)結(jié)構(gòu)的概念，掌握各種數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)方式，比較不同的數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。這是一門理論與實(shí)際緊密結(jié)合的課程。通過本課程的學(xué)習(xí)，學(xué)生可以學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)特性，以便在以后的工作實(shí)踐中，能夠針對具體問題選擇和設(shè)計(jì)出適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并在此基礎(chǔ)上，能編寫出結(jié)構(gòu)清晰、正確易讀、符合軟件工程規(guī)范的程序，從而為進(jìn)一步學(xué)習(xí)后續(xù)專業(yè)課程和軟件的開發(fā)打下堅(jiān)實(shí)的基礎(chǔ)。本書在內(nèi)容組織和編排上，力求理論與實(shí)際應(yīng)用緊密結(jié)合，而且更加突出運(yùn)用。本書的主要特點(diǎn)有以下3點(diǎn)。（1）內(nèi)容組織上層次分明、結(jié)構(gòu)清晰。在內(nèi)容的選取上堅(jiān)持學(xué)以致用、學(xué)用結(jié)合的原則，集先進(jìn)性、科學(xué)性和實(shí)用性于一體，盡可能地將最基礎(chǔ)、最適用的軟件技術(shù)寫入教材，省略一些純理論的推導(dǎo)和煩瑣的數(shù)學(xué)證明。（2）在內(nèi)容的深淺程度上，把握理論深度、側(cè)重實(shí)用、由淺入深的原則，通過大量翔實(shí)的例題、算法和每一章的最后給出的練習(xí)題，進(jìn)一步提高學(xué)生對數(shù)據(jù)的抽象能力和程序設(shè)計(jì)的能力。（3）內(nèi)容敘述深入淺出，文體規(guī)范，文字淺顯易懂，相互銜接自然，表述嚴(yán)謹(jǐn)，邏輯性強(qiáng)，以利于學(xué)生自學(xué)和理解。本書作為2003年版《數(shù)據(jù)結(jié)構(gòu)》的第二版，保持了前一版的基本框架，概念清楚、論述充實(shí)、面向應(yīng)用，進(jìn)一步完善了算法與數(shù)據(jù)結(jié)構(gòu)的體系內(nèi)容，對所有算法進(jìn)行了詳盡的注釋和完善，以利于讀者理解算法的基本思想。各章均安排有章節(jié)提要和課后習(xí)題。本書的第l章和10章由劉振鵬編寫修訂，第2章～第5章由張小莉編寫修訂，第6章～第9章由鄭艷娟編寫修訂，最后由劉振鵬、張小莉統(tǒng)一定稿。本書在寫作和修訂過程中，得到了許多專家和眾多院校數(shù)據(jù)結(jié)構(gòu)任課教師的大力支持和幫助，他們提出了許多中肯的意見和很好的建議，對本書的編寫修訂起到了很大的指導(dǎo)作用。對此，作者表示衷心的感謝。也正是他們的認(rèn)可和支持，使得本書入選普通高等教育“十一五”國家級規(guī)劃教材。感謝作者的多位同事和學(xué)生，許百成、羅文劫參與了編寫大綱的討論并編寫了初稿的部分內(nèi)容，王苗編寫書中習(xí)題部分并提供了全部答案，石強(qiáng)、史青宣制作了電子講義，趙紅、苗秀芬等在使用本書的過程中指出了書中的一些不足之外，使得本書更加完善。盡管我們做了很大的努力，但由于編者水平有限，書中難免有不妥之處，懇請讀者予以指正。

內(nèi)容概要

　　本書介紹了：各種最常用的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊(duì)列、矩陣的壓縮存儲、樹與二叉樹、圖、查找、排序等。闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計(jì)算機(jī)中的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)下的運(yùn)算和實(shí)現(xiàn)的算法，并對算法的效率進(jìn)行了簡要的分析。本書既注重原理又重視算法的實(shí)現(xiàn)，均給出用Visual
C++語言描述的算法，并加以詳細(xì)的注釋，分析算法的基本思路，每章都附有大量的習(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é)系列。
　　本書內(nèi)容豐富、結(jié)構(gòu)清晰、突出算法、注重應(yīng)用，強(qiáng)調(diào)理論與實(shí)踐的結(jié)合。既適合作為高等院校計(jì)算機(jī)科學(xué)與應(yīng)用、通信工程、電子工程等電子信息類專業(yè)的教材，又適合于計(jì)算機(jī)愛好者自學(xué)，對于從事計(jì)算機(jī)應(yīng)用和開發(fā)的技術(shù)人員也具有一定的參考價(jià)值。

書籍目錄

第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 算法性能分析與度量
習(xí)題
第2章 線性表
2-1 線性表的邏輯結(jié)構(gòu)
2-1-1 線性表的定義
2-1-2 線性表的基本操作
2-2 線性表的順序存儲及運(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)酱鎯瓦\(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 單鏈表應(yīng)用舉例
2-4 順序表和鏈表的比較
習(xí)題
第3章 棧和隊(duì)列
3-1 棧
3-1-1 棧的定義及基本運(yùn)算
3-1-2 棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)
3-2 棧的應(yīng)用舉例
3-3 隊(duì)列
3-3-1 隊(duì)列的定義及基本運(yùn)算
3-3-2 隊(duì)列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)
3-4 隊(duì)列應(yīng)用舉例
習(xí)題
第4章 串
4-1 串及其基本運(yùn)算
4-1-1 串的基本概念
4-1-2 串的基本運(yùn)算
4-2 串的定長順序存儲及基本運(yùn)算
4-2-1 串的定長順序存儲
4-2-2 定長順序串的基本運(yùn)算
4-2-3 模式匹配
4-3 串的堆存儲結(jié)構(gòu)
4-3-1 串名的存儲映像
4-3-2 堆存儲結(jié)構(gòu)
4-3-3 基于堆結(jié)構(gòu)的串的基本運(yùn)算實(shí)現(xiàn)
習(xí)題
第5章 數(shù)組和廣義表
5-1 多維數(shù)組
5-1-1 數(shù)組的邏輯結(jié)構(gòu)
5-1-2 數(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 廣義表的定義和基本運(yùn)算
5-4-2 廣義表的存儲
5-4-3 廣義表基本操作的實(shí)現(xiàn)
習(xí)題
第6章 二叉樹
6-1 二叉樹的定義與性質(zhì)
6-1-1 二叉樹的基本概念
6-1-2 二叉樹的主要性質(zhì)
6-2 二叉樹的基本操作與存儲實(shí)現(xiàn)
6-2-1 二叉樹的存儲
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 二叉樹遍歷的應(yīng)用
6-5-2 最優(yōu)二叉樹——哈夫曼樹
習(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-4 生成樹與最小生成樹
8-4-1 生成樹和生成森林
8-4-2 最小生成樹的概念
8-4-3 構(gòu)造最小生成樹的Prim算法
8-4-4 構(gòu)造最小生成樹的Kruska1算法
8-5 最短路徑
8-5-1 從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑
8-5-2 每-對頂點(diǎn)之間的最短路徑
8-6 有向無環(huán)圖及其應(yīng)用
8-6-1 有向無環(huán)圖的概念
8-6-2 AOV網(wǎng)與拓?fù)渑判?br />8-6-3 AOE圖與關(guān)鍵路徑
習(xí)題
第9章 查找
9-1 基本概念
9-2 靜態(tài)查找表
9-2-1 靜態(tài)查找表結(jié)構(gòu)
9-2-2 順序查找
9-2-3 有序表的查找
9-2-4 分塊查找
9-3 動態(tài)查找表
9-3-1 二叉排序樹：
9-3-2 平衡二叉樹
9-3-3 B樹和B樹
9-4 哈希表查找（雜湊法）
9-4-1 哈希表與哈希方法
9-4-2 常用的哈希函數(shù)
9-4-3 處理沖突的方法
9-4-4 哈希表的查找分析
習(xí)題
第10章 排序
10-1 排序的基本概念
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)
習(xí)題
參考文獻(xiàn)

章節(jié)摘錄

插圖：數(shù)據(jù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過對問題的抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)；類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個(gè)方面的結(jié)合使人們將問題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個(gè)從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)，這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。熟練地掌握這兩個(gè)過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國外是從1968年才開始的，但在此之前其有關(guān)內(nèi)容已放在編譯原理及操作系統(tǒng)課程之中。20世紀(jì)60年代中期，美國的一些大學(xué)開始設(shè)立有關(guān)課程，但當(dāng)時(shí)的課程名稱并不叫數(shù)據(jù)結(jié)構(gòu)。1968年美國唐·歐·克努特（Donald E.knuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》（Art of Computer Vrogramming，現(xiàn)翻譯為《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》）第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們越來越重視數(shù)據(jù)結(jié)構(gòu)。從20世紀(jì)70年代中期到80年代，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼問世。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，例如，多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢，越來越受到人們的重視。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)》：所有算法均給出C＋＋語言的描述，并加以詳細(xì)的注釋，利于讀者理解算法的基本思想。

圖書封面

評論、評分、閱讀與下載

---

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

---