數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹了數據結構、算法以及抽象數據類型的概念；介紹了線性表、棧和隊列、字符串和多維數組、樹和二叉樹、圖等常用數據結構；討論了基本的查找和排序技術。
本書合理規劃教學內容，梳理知識單元及其拓撲結構，兼顧概念層和實現層，既強調了數據結構的基本概念和原理方法，又注重了數據結構的程序實現和實際運用，在提煉基礎知識的同時，進行了適當的擴展和提高。
本書內容豐富，層次清晰，深入淺出，結合實例，可作為計算機及相關專業數據結構課程的教材，也可供從事計算機軟件開發和應用的工程技術人員參考和閱讀。
本書在概念的描述、實例的選擇、知識的前后銜接、內容的組織結構，以及教學內容的理解、教學目標的實現、教學意圖的融入、教學方法的運用等方面進行了系統思考和統籌設計，力圖通過本書為讀者構建多層次的知識體系。在問題求解層面，給出問題?想法?算法?程序的思維模式；在算法設計層面，采用闡述基本思想偽代碼描述算法C語言實現算法的過程模式；在算法分析層面，理解什么是好算法，給出算法分析的基本方法；在存儲結構層面，通過存儲示意圖理解數據表示，再給出存儲結構定義；在程序實現層面，給出所有數據結構的C程序實現以及使用舉例；在數據結構和算法的運用層面，通過應用實例理解如何為求解問題設計適當的數據結構，如何基于數據結構設計算法，從而將數據結構、算法設計和程序實現有機地融合在一起。本書是一本難得的易學易教的好教材。
前言
結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。作為程序設計的重要補充和延伸，數據結構所討論的知識內容、蘊含的技術方法、體現的思維方式，無論進一步學習計算機專業的其他課程，還是從事計算機領域的各項工作，都有著不可替代的作用。數據結構課程的知識豐富，內容抽象，隱藏在各知識單元的概念和方法較多，貫穿于各知識單元的鏈表和遞歸更是加重了學習難度。本書的編寫者長期從事數據結構的研究和教學，深切理解學生在學習數據結構過程中遇到的問題和困惑，深入探究掌握數據結構的有效途徑和方法，深刻思考數據結構對培養程序設計和計算思維的地位和作用，深度把握課程的教學目標和重點難點，本書在教學內容和教學設計等方面進行了如下處理。1. 合理規劃教學內容。緊扣《高等學校計算機專業核心課程教學實施方案》和《計算機學科碩士研究生入學考試大綱》，涵蓋教學方案及考研大綱要求的全部知識點。2. 遵循認知規律，理清教學主線。根據學生的認知規律和課程的知識結構，按照從已知到未知的思維進程逐步推進教學內容，梳理和規劃了各知識單元及其拓撲結構，設計了清晰的教學主線。知識單元及其拓撲結構如圖1所示。圖1數據結構課程的知識單元及拓撲結構3. 提煉基礎知識，適當擴展提高。考慮到不同學校教學要求的差異以及不同學生學習需求的差別，一方面本著夠用、實用的原則，抓牢核心概念，提煉基礎性知識，貫徹數據結構課程的基本教學要求；另一方面對某些知識點進行了適當的擴充和提高（圖1中打星號部分），這部分內容可用于選講，也可用于學生自學或課外閱讀（教學建議: 目錄中打一個星號可用于選講，打兩個星號可用于課外閱讀，其他是必講的基礎知識）。數據結構從概念到C實現前言4. 兼顧概念層和實現層。從抽象數據類型的角度將數據結構的實現過程分為抽象層、設計層和實現層，其中抽象層定義數據結構和基本操作集合，設計層是數據結構的存儲表示和算法設計，實現層用C語言實現數據結構，既強調了數據結構的基本概念和原理方法，又注重了數據結構的程序實現和實際運用。5. 展現求解過程，培養計算思維。通過講思路講過程講方法，按照問題想法算法程序的模式進行問題求解，采用闡述基本思想偽代碼描述算法C語言實現算法的模式進行算法設計，這個過程正是計算思維的運用過程。每章通過兩個應用實例展示問題求解過程以及算法設計過程。6. 明確重點，化解難點。每一章開篇即給出該章的重點難點，以及各知識點的教學要求，在具體闡述時還有針對性的處理方法。針對數據結構內容抽象的特點，全書設計了大量插圖，將抽象內容進行了具體化處理，降低了理解問題的復雜性。總之，本書在概念的描述、實例的選擇、知識的前后銜接、內容的組織結構，以及教學內容的理解、教學目標的實現、教學意圖的融入、教學方法的運用等方面進行了系統思考和統籌設計，力圖通過本書為讀者構建多層次的知識體系。在問題求解層面，以數據表示和數據處理為主線，給出問題想法算法程序的思維模式；在算法設計層面，通過偽代碼描述算法，強調計算思維的培養；在算法分析層面，理解什么是好算法，給出算法分析的基本方法；在存儲結構層面，通過存儲示意圖理解數據表示，再給出存儲結構定義；在程序實現層面，給出所有數據結構的C程序實現以及使用范例；在數據結構和算法的運用層面，通過應用實例理解如何為求解問題設計適當的數據結構，如何基于數據結構設計算法，從而將數據結構、算法和程序設計有機地融合在一起。參加本書編寫的還有董亞則、王濤、黨源源、肖巍、劉冰、王有敬等老師，2015級碩士研究生唐東凱和李芬田同學參與了本書的代碼調試工作，本書所有代碼均在DevC 5.11、Visual Studio 2013、Microsoft Visual C 6.0編程環境下調試通過，讀者可向出版社或作者索要程序源碼。由于作者的知識和寫作水平有限，書稿雖再三斟酌幾經修改，仍難免有缺點和錯誤，歡迎專家和讀者批評指正。作者的電子郵箱是: wanghm@ccut.edu.cn。
作者2016年2月
目錄
第1章緒論1
1.1問題求解與程序設計2
1.1.1程序設計的一般過程2
1.1.2數據結構在程序設計中的作用4
1.1.3算法在程序設計中的作用6
1.1.4本書討論的主要內容7
1.2數據結構的基本概念8
1.2.1數據結構8
1.2.2抽象數據類型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法14
1.4算法分析15
1.4.1算法的時間復雜度16
1.4.2算法的空間復雜度17
1.4.3算法分析舉例18
1.5擴展與提高20
1.5.1從數據到大數據20
1.5.2算法分析的其他漸進符號22
習題123
第2章線性表25
2.1引言26
2.2線性表的邏輯結構27
2.2.1線性表的定義27
2.2.2線性表的抽象數據類型定義27數據結構從概念到C實現目錄2.3線性表的順序存儲結構及實現29
2.3.1順序表的存儲結構定義29
2.3.2順序表的實現30
2.3.3順序表的使用34
2.4線性表的鏈接存儲結構及實現35
2.4.1單鏈表的存儲結構定義35
2.4.2單鏈表的實現37
2.4.3單鏈表的使用44
2.4.4雙鏈表45
2.4.5循環鏈表47
2.5順序表和鏈表的比較48
2.6擴展與提高48
2.6.1線性表的靜態鏈表存儲48
2.6.2順序表的動態分配方式51
2.7應用實例52
2.7.1約瑟夫環問題52
2.7.2一元多項式求和55
習題259
第3章棧和隊列63
3.1引言64
3.2棧65
3.2.1棧的邏輯結構65
3.2.2棧的順序存儲結構及實現66
3.2.3棧的鏈接存儲結構及實現68
3.2.4順序棧和鏈棧的比較71
3.3隊列72
3.3.1隊列的邏輯結構72
3.3.2隊列的順序存儲結構及實現73
3.3.3隊列的鏈接存儲結構及實現77
3.3.4循環隊列和鏈隊列的比較80
3.4擴展與提高81
3.4.1兩棧共享空間81
3.4.2雙端隊列82
3.5應用舉例83
3.5.1括號匹配問題83
3.5.2表達式求值85
習題388第4章字符串和多維數組91
4.1引言92
4.2字符串92
4.2.1字符串的邏輯結構92
4.2.2字符串的存儲結構94
4.2.3模式匹配94
4.3多維數組98
4.3.1數組的邏輯結構98
4.3.2數組的存儲結構與尋址99
4.4矩陣的壓縮存儲100
4.4.1特殊矩陣的壓縮存儲100
4.4.2稀疏矩陣的壓縮存儲102
4.5擴展與提高105
4.5.1稀疏矩陣的轉置運算105
4.5.2廣義表107
4.6應用實例111
4.6.1發紙牌111
4.6.2八皇后問題112
習題4115
第5章樹和二叉樹119
5.1引言120
5.2樹的邏輯結構121
5.2.1樹的定義和基本術語121
5.2.2樹的抽象數據類型定義123
5.2.3樹的遍歷操作123
5.3樹的存儲結構124
5.3.1雙親表示法124
5.3.2孩子表示法125
5.3.3孩子兄弟表示法126
5.4二叉樹的邏輯結構127
5.4.1二叉樹的定義127
5.4.2二叉樹的基本性質129
5.4.3二叉樹的抽象數據類型定義130
5.4.4二叉樹的遍歷操作131
5.5二叉樹的存儲結構133
5.5.1順序存儲結構133
5.5.2二叉鏈表134
5.5.3三叉鏈表138
5.6森林138
5.6.1森林的邏輯結構138
5.6.2樹、森林與二叉樹的轉換139
5.7最優二叉樹141
5.7.1哈夫曼算法141
5.7.2哈夫曼編碼143
5.8擴展與提高145
5.8.1二叉樹遍歷的非遞歸算法145
5.8.2線索二叉樹148
5.9應用實例151
5.9.1堆與優先隊列151
5.9.2并查集154
習題5155
第6章圖159
6.1引言160
6.2圖的邏輯結構161
6.2.1圖的定義和基本術語161
6.2.2圖的抽象數據類型定義163
6.2.3圖的遍歷操作164
6.3圖的存儲結構及實現167
6.3.1鄰接矩陣167
6.3.2鄰接表170
6.3.3鄰接矩陣和鄰接表的比較174
6.4最小生成樹175
6.4.1Prim算法176
6.4.2Kruskal算法178
6.5最短路徑182
6.5.1Dijkstra算法183
6.5.2Floyd算法185
6.6有向無環圖及其應用187
6.6.1AOV網與拓撲排序187
6.6.2AOE網與關鍵路徑190
6.7擴展與提高193
6.7.1圖的其他存儲方法193
6.7.2圖的連通性194
6.8應用實例196
6.8.1七巧板涂色問題196
6.8.2醫院選址問題198
習題6200
第7章查找技術205
7.1概述206
7.1.1查找的基本概念206
7.1.2查找算法的性能207
7.2線性表的查找技術207
7.2.1順序查找207
7.2.2折半查找208
7.3樹表的查找技術211
7.3.1二叉排序樹211
7.3.2平衡二叉樹217
7.3.3B樹220
7.4散列表的查找技術225
7.4.1散列查找的基本思想225
7.4.2散列函數的設計226
7.4.3處理沖突的方法227
7.4.4散列查找的性能分析231
7.4.5開散列表與閉散列表的比較232
7.5各種查找方法的比較232
7.6擴展與提高233
7.6.1順序查找的改進分塊查找233
7.6.2折半查找的改進插值查找234
7.6.3B樹的改進B 樹235
習題7236
第8章排序技術239
8.1概述240
8.1.1排序的基本概念240
8.1.2排序算法的性能241
8.2插入排序241
8.2.1直接插入排序241
8.2.2希爾排序243
8.3交換排序245
8.3.1起泡排序245
8.3.2快速排序247
8.4選擇排序250
8.4.1簡單選擇排序250
8.4.2堆排序252
8.5歸并排序256
8.5.1二路歸并排序的遞歸實現256
8.5.2二路歸并排序的非遞歸實現257
8.6各種排序方法的比較259
8.7擴展與提高261
8.7.1排序問題的時間下界261
8.7.2基數排序262
習題8264
附錄A預備知識269
A.1數學術語269
A.2級數求和269
A.3集合270
A.4關系271
附錄BC語言基本語法273
B.1程序結構273
B.2數據的基本表現形式常量和變量274
B.3數據類型275
B.4控制語句277
B.5函數278
B.6動態存儲分配281
附錄C詞匯索引283
參考文獻287
新書資訊