第1章緒論

1.1解決問題的一般過程

1.2數據結構的基本概念

1.3算法及算法分析

1.3.1算法及其特點

1.3.2高級程序設計語言

1.3.3算法和程序的關繫

1.3.4算法分析

1.4小結

習題

第2章線性表

2.1線性表的邏輯結構

2.1.1線性表的定義

2.1.2線性表的基本操作

2.2線性表的順序存儲結構

2.2.1順序表

2.2.2順序表的實現

2.3順序表的應用

2.3.1有序素的刪除

2.3.2有序表的合並

2.4線性表的鏈式存儲結構及實現

2.4.1單鏈表

2.4.2單鏈表的實現

2.4.3其他鏈表形式

2.5順序表和鏈表的比較

2.5.1空間性能

2.5.2時間性能

2.6單鏈表的應用

2.6.1單鏈表的原地逆置

2.6.2判斷單鏈表是否有序及對單鏈表排序

2.6.3利用單鏈表實現有序表的合並

2.6.4利用單鏈表判斷兩個集合是否相等

2.6.5利用單鏈表求兩個集合的並集

2.6.6利用單鏈表求兩個集合的交集

〖1〗

〖2〗
2.6.7利用單鏈表刪除有序表中素

2.6.8刪除普通單鏈表中素

2.6.9利用單鏈表多項式相加

2.7小結

習題

第3章棧和隊列

3.1棧

3.1.1棧的邏輯結構

3.1.2棧的順序存儲結構

3.1.3棧的鏈式存儲結構

3.1.4順序棧和鏈棧的比較

3.2棧的應用

3.2.1Hanoi塔問題

3.2.2利用順序棧實現進制轉換

3.2.3迷宮問題

3.2.4八皇後問題

3.2.5火車調度問題

3.2.6表達式括號匹配問題

3.2.7後綴表達式求值

3.2.8中綴表達式求值

3.2.9中綴表達式轉換為後綴表達式

3.3隊列

3.3.1隊列的邏輯結構

3.3.2順序隊列

3.3.3循環隊列

3.3.4雙端隊列

3.3.5鏈隊列

3.4小結

習題

第4章字符串和多維數組

4.1字符串

4.1.1字符串的邏輯結構

4.1.2字符串的存儲結構

4.2字符串的模式匹配

4.2.1樸素的模式匹配算法

4.2.2KMP算法

4.3字符串的應用

4.3.1凱撒密碼

4.3.2統計文本中單詞的個數

4.3.3找詞遊戲

4.3.4變位詞判斷

4.3.5字符串的長公共子序列

4.4多維數組

4.4.1多維數組的邏輯結構

4.4.2多維數組的尋址

4.5矩陣的壓縮存儲

4.5.1特殊矩陣的壓縮存儲

4.5.2稀疏矩陣的壓縮存儲

4.6多維數組的應用

4.6.1約瑟夫環問題

4.6.2求解矩陣的馬鞍點

4.6.3螺旋方陣

4.6.4幻方

4.7小結

習題

第5章樹和二叉樹

5.1樹的邏輯結構

5.1.1樹的基本術語

5.1.2樹的抽像數據類型定義

5.1.3樹的遍歷

5.2樹的存儲結構

5.2.1雙親表示法

5.2.2孩子鏈表表示法

5.2.3孩子兄弟表示法

5.3二叉樹的邏輯結構

5.3.1二叉樹的定義

5.3.2二叉樹的性質

5.3.3二叉樹的抽像數據類型定義

5.3.4二叉樹的遍歷

5.4二叉樹的存儲結構及實現

5.4.1順序存儲結構

5.4.2二叉鏈表

5.4.3三叉鏈表

5.5二叉樹的應用

5.5.1非遞歸遍歷二叉樹

5.5.2二叉樹遍歷的應用

5.5.3線索二叉樹的構造和應用

5.5.4赫夫曼樹和赫夫曼編碼

5.5.5求二叉樹的小深度

5.5.6判斷二叉樹是否是完全二叉樹

5.5.7判斷二叉樹的結構是否對稱

5.5.8判斷二叉樹是否對稱

5.5.9求二叉樹第k層的結點個數和葉子結點個數

5.5.10打印二叉樹第k層的結點和葉子結點

5.5.11求二叉樹的結點距離

5.5.12由前序序列和中序序列構造二叉樹

5.5.13由後序序列和中序序列構造二叉樹

5.5.14求二叉樹的鏡像

5.5.15判斷兩棵二叉樹是否等價

5.6樹、森林與二叉樹的轉換

5.7小結

習題

第6章圖

6.1圖的邏輯結構

6.1.1基本術語

6.1.2圖的抽像數據類型定義

6.1.3圖的遍歷

6.2圖的存儲結構

6.2.1鄰接矩陣

6.2.2鄰接表

6.2.3十字鏈表

6.2.4鄰接多重表

6.3小生成樹

6.3.1MST性質

6.3.2Prim算法

6.3.3Kruscal算法

6.4短路徑問題

6.4.1Dijkstra算法

6.4.2Floyd算法

6.5拓撲排序

6.6關鍵路徑

6.7圖的其他應用

6.7.1七巧板塗色問題

6.7.2五岔路口交通燈問題

6.7.3選址問題

6.7.4農夫過河問題

6.7.5旅行商問題

6.8小結

習題

第7章查找

7.1概述

7.1.1基本概念

7.1.2查找算法的性能分析

7.2線性表的查找

7.2.1順序查找

7.2.2折半查找

7.2.3斐波那契查找

7.3樹表的查找

7.3.1二叉排序樹

7.3.2平衡二叉樹

7.3.3樹表的應用

7.4散列表的查找

7.4.1概述

7.4.2散列函數的設計

7.4.3處理衝突的方法

7.4.4散列表的查找性能分析

7.4.5閉散列表和開散列表的比較

7.5小結

習題

第8章排序

8.1概述

8.1.1基本概念

8.1.2排序的分類

8.1.3排序算法的性能

8.2插入排序

8.2.1直接插入排序

8.2.2希爾排序

8.3交換排序

8.3.1起泡排序

8.3.2雙向起泡排序

8.3.3快速排序

8.4選擇排序

8.4.1簡單選擇排序

8.4.2堆排序

8.5歸並排序

8.5.1二路歸並的非遞歸實現

8.5.2二路歸並的遞歸實現

8.6分配排序

8.6.1桶式排序

8.6.2基數排序

8.7各種排序算法的比較

8.8排序算法的應用

8.8.1荷蘭國旗問題

8.8.2螺釘和螺母問題

8.9小結

習題

第9章索引

9.1基本概念

9.2線性索引

9.2.1稠密索引

9.2.2分塊索引

9.2.3多重表

9.2.4倒排表

9.3樹形索引

9.3.123樹

9.3.2B樹

9.3.3B 樹

9.4小結

習題

參考文獻

“數據結構”是計算機及相關專業的一門綜合性的專業基礎課，同時也是計算機相關專業考研的必考科目。數據結構的研究不僅涉及計算機硬件，例如編碼理論、數據存儲、存取方法等，而且和計算機軟件也有密切的關繫，編譯程序和操作繫統都涉素在存儲器中的分配問題。信息檢索領域也涉及數據的組織和查找方式。在計算機學科中，數據結構不僅是程序設計的基礎，也是編譯原理、操作繫統、數據庫繫統等課程的基礎。
算法的設計依賴於邏輯結構，算法的實現則依賴於物理結構。要成為專業的程序開發人員必須能夠熟練地選擇和設計各種數據結構和算法。要設計出結構合理、效率高的算法，必須研素的特點素之間的關繫。要在算法的基礎上利用高級程序設計語言實現算法，則必須考慮邏輯結構在內存中的實現，即物理結構。
數據結構中涉及許素的組織方式及算法，例如線性表、棧和隊列、樹和二叉樹、圖等重要的數據結構，以及查找、排序、插入、刪除等常見操作。對於特定的數據結構和操作，已有許多成熟的經典算法。掌握這些算法有助於培養學生的抽像思維能力，提高他們分析和解決復雜問題的能力。“數據結構”課程的知識點邏輯性和抽像性較強，一些算法設計得較為復雜，如果不付諸實踐，很難真正理解算法的精髓。因此要把“數據結構”這門課程學好，必須在熟練掌握理論知識的基礎上，加強實踐環節。
編者結合多年來從事“數據結構”課程教學的經驗，編寫了此教材。本書理論和實踐並重，采用邊學邊做的方式，首先對理論知識進行闡述，然後實現各種數據結構常見的算法，並附有程序運行結果和說明。本書采用類C 語言描述算法，基本上涵蓋了各種常見的數據結構及算法，也包括了一些擴展應用，例如農夫過河問題和多岔路口交通燈問題等。對於一些較復雜的問題，分別給出了問題描述、模型說明、算法描述、源代碼以及實驗結果。本書同時提供課件、視頻、源代碼、課後習題答案等相關教輔材料。請讀者用手機微信掃一掃封底刮刮卡內二維碼，獲得權限，再掃一掃書中二維碼，即可觀看教學視頻。其他配套資源可從清華大學出版社網站下載。本書可作為計算機各相關專業的數據結構教材，也可以作為感興趣的自學者的參考教材。

感謝山東省教育服務新舊動能轉換專業對接產業項目（曲阜師範大學精品旅遊）對本書的資助。感謝山東省高等教育本科教改項目(Z2018S022)、曲阜師範大學實驗技術研究項目（SJ201726)對本書的資助。
由於編者水平有限，書稿雖幾經修改，但仍難免有疏漏和不足之處，敬請讀者朋友們批評指正。
編者
2020年4月