適讀人群 ：本書可以作為全日制高等學校計算機應用專業、微電子和信息工程專業、計算機信息管理和經濟信息管理類等專業普通本科學生的專業基礎課教材，也可以作為上述專業高職高專學生的參考教材，還可以作為計算機等級考試的參考書，供廣大從事計算機應用工作的管理人員和技術人員學習參考。
本書是普通高等教育“十一五”國家級規劃教材。書中全部程序均上機驗證並調試通過。在每章中都收集了難度各異的習題和例題，有習題答案。各章中的“簡單應用舉例”有很強的實用性和可操作性。

本書是普通高等教育“十一五”國家級規劃教材。全書共10章，內容包括：數據結構的概念，幾種基本的線性結構（如線性表），棧和隊列，串，幾種非線性結構（如多維數組和廣義表），樹，圖，常用的數據處理技術（如排序），查找，文件的存儲結構和組織方法等。在每章中都收集了難度各異的習題和例題，全書采用C語言作為算法描述語言，並有詳細的注釋，書中全部程序均上機驗證並調試通過，同時給出部分程序的運行結果。各章中的“簡單應用舉例”，既是本章算法的綜合應用，也可作為本章實訓內容和課程設計的綜合練習，全書有很強的實用性和可操作性。
本書可以作為全日制高等學校計算機應用專業、微電子和信息工程專業、計算機信息管理和經濟信息管理類等專業普通本科學生的專業基礎課教材，也可以作為上述專業高職高專學生的參考教材，還可以作為計算機等級考試的參考書，供廣大從事計算機應用工作的管理人員和技術人員學習參考。

田魯懷，女，碩士學位，副教授職稱。於1982年獲中國石油大學（原華東石油學院）采油工程專業學士學位和1996年獲上海大學（原上海工業大學）計算機應用專業碩士學位；先後在大學、高專學校和高職技術學院任教，分別於1989年和1996年獲講師和副教授職稱。從1984年起，一直從事計算機專業的教學和科研工作。先後主講了《數據結構》、《PASCAL語言程序設計》、《C語言程序設計》、《數據庫原理及其應用》、《管理信息繫統》等課程。現已退休。

第1章 概論 1
1．1 概述 1
1．2 數據結構的基本概念 4
1．2．1 數據結構的基本術語 4
1．2．2 數據的邏輯結構 6
1．2．3 數據的存儲結構 8
1．3 算法性能分析與度量 12
1．3．1 算法和算法的描述方法 12
1．3．2 算法的特性 14
1．3．3 算法設計的要求 14
1．3．4 算法時間復雜度的分析與度量 15
1．3．5 算法存儲空間的分析與度量 19
本章小結 19
習題1 20
第2章 線性表 23
2．1 線性表的定義及基本運算 23
2．1．1 線性表的定義 23
2．1．2 線性表的基本運算 24
2．2 線性表的順序存儲結構及其運算 25
2．2．1 線性表的順序存儲結構 25
2．2．2 順序表上的基本運算 26
2．2．3 順序表上插入和刪除運算的時間分析 30
2．2．4 順序表的優點和缺點 31
2．3 線性表的鏈接存儲結構及其運算 31
2．3．1 單鏈表 31
2．3．2 單鏈表上的基本運算 32
2．3．3 單鏈表上查找、插入和刪除運算的時間分析 40
2．3．4 循環鏈表 40
2．3．5 雙向鏈表 43
2．4 順序表和鏈表的比較 46
2．5 線性表的簡單應用舉例 47
本章小結 62
習題2 63
第3章 棧和隊列 66
3．1 棧的基本概念 66
3．2 棧的存儲結構 67
3．2．1 棧的順序存儲結構 67
3．2．2 棧的鏈接存儲結構 68
3．2．3 棧的兩種存儲結構的比較 69
3．2．4 多個順序棧共享一個數組的存儲空間 69
3．3 棧的基本運算 70
3．3．1 順序存儲結構上順序棧的運算實現 71
3．3．2 鏈接存儲結構上鏈棧的運算實現 72
3．4 棧的簡單應用舉例 73
3．4．1 棧在遞歸過程中的作用 73
3．4．2 棧的幾個簡單應用實例 76
3．5 隊列的基本概念 81
3．6 隊列的存儲結構 82
3．6．1 隊列的順序存儲結構 82
3．6．2 順序存儲的循環隊列 84
3．6．3 隊列的鏈接存儲結構 85
3．7 隊列的基本運算 86
3．7．1 順序存儲結構上順序隊列的運算實現 86
3．7．2 順序存儲結構上循環隊列的運算實現 87
3．7．3 鏈接存儲結構上鏈隊列的運算實現 89
3．8 隊列的簡單應用舉例 91
本章小結 97
習題3 98
第4章 串 100
4．1 串的基本概念 100
4．2 串的存儲結構 101
4．2．1 串的順序存儲結構 101
4．2．2 串的鏈接存儲結構 103
4．3 串的基本運算及實現 105
4．3．1 串的基本運算 105
4．3．2 順序串上基本運算的實現 106
4．3．3 鏈串上基本運算的實現 108
4．4 串的模式匹配運算 112
4．4．1 BF模式匹配算法 112
4．4．2 BM模式匹配算法 115
4．4．3 KMP模式匹配算法 117
4．5 串的簡單應用舉例 124
本章小結 131
習題4 131
第5章 數組和廣義表 133
5．1 數組的概念和存儲 133
5．1．1 數組的概念 133
5．1．2 數組的存儲結構 134
5．2 特殊矩陣的壓縮存儲 137
5．2．1 對稱矩陣的壓縮存儲 137
5．2．2 三角矩陣的壓縮存儲 138
5．2．3 對角矩陣的壓縮存儲 139
5．3 稀疏矩陣的壓縮存儲 141
5．3．1 稀疏矩組表示 141
5．3．2 稀疏矩陣的十字鏈表表示 148
5．3．3 稀疏矩陣的簡單應用舉例 152
5．4 廣義表 157
5．4．1 廣義表的基本概念 157
5．4．2 廣義表的鏈接存儲結構 158
5．4．3 廣義表的基本運算 161
5．4．4 廣義表的簡單應用舉例 166
本章小結 167
習題5 168
第6章 樹 170
6．1 樹的基本概念 170
6．1．1 樹的定義 170
6．1．2 樹的基本術語 172
6．2 二叉樹 174
6．2．1 二叉樹的概念 174
6．2．2 二叉樹的基本性質 176
6．2．3 二叉樹的存儲結構 177
6．3 二叉樹的運算 180
6．3．1 二叉樹的遍歷 180
6．3．2 二叉樹的建立 185
6．3．3 二叉樹的其他運算舉例 187
6．4 線索二叉樹 192
6．4．1 線索二叉樹的概念 192
6．4．2 二叉樹的中序線索化 193
6．4．3 線索二叉樹的遍歷和插入運算 195
6．5 樹和森林 198
6．5．1 樹的存儲結構 198
6．5．2 樹和森林與二叉樹的轉換 201
6．5．3 樹的遍歷 205
6．5．4 森林的遍歷 206
6．6 哈夫曼樹及其應用 207
6．6．1 哈夫曼樹的基本概念 207
6．6．2 哈夫曼樹的構造及實現 208
6．6．3 哈夫曼編碼 211
6．6．4 哈夫曼譯碼 215
6．6．5 哈夫曼樹在編碼問題中的完整程序 216
本章小結 218
習題6 219
第7章 圖 222
7．1 圖的基本概念 222
7．1．1 圖的實際背景 222
7．1．2 圖的定義 223
7．1．3 圖的基本術語 224
7．2 圖的存儲結構 227
7．2．1 鄰接矩陣表示法 227
7．2．2 鄰接表表示法 231
7．3 圖的遍歷 234
7．3．1 連通圖的深度優先搜索遍歷 235
7．3．2 連通圖的廣度優先搜索遍歷 237
7．3．3 非連通圖的遍歷 240
7．3．4 連通圖和非連通圖的建立與遍歷運算實例 241
7．4 生成樹和最小生成樹 243
7．4．1 生成樹和最小生成樹的概念 244
7．4．2 Kruskal算法 245
7．4．3 Prim算法 248
7．5 最短路徑 250
7．5．1 最短路徑的概念 250
7．5．2 單源最短路徑 252
7．5．3 所有頂點對之間的最短路徑 255
7．6 AOV網和拓撲排序 260
7．6．1 AOV網和拓撲排序的概念 260
7．6．2 拓撲排序算法 261
7．7 AOE網和關鍵路徑 265
7．7．1 AOE網和關鍵路徑的概念 265
7．7．2 關鍵路徑的確定 267
7．8 圖的簡單應用舉例 269
本章小結 277
習題7 278
第8章 排序 281
8．1 排序的基本概念 281
8．2 插入排序 284
8．2．1 直接插入排序 284
8．2．2 希爾排序 286
8．3 交換排序 288
8．3．1 冒泡排序 288
8．3．2 快速排序 291
8．4 選擇排序 294
8．4．1 直接選擇排序 294
8．4．2 堆排序 295
8．5 歸並排序 302
8．5．1 兩個相鄰有序表的一次歸並過程 303
8．5．2 一趟歸並排序過程 303
8．5．3 二路歸並排序 304
8．6 各種內排序方法的比較和選擇 305
8．6．1 各種內排序方法的總結 305
8．6．2 各種內排序方法的比較 305
8．6．3 排序方法的選擇 306
8．7 排序的簡單應用舉例 307
本章小結 311
習題8 312
第9章 查找 315
9．1 查找的基本概念 315
9．2 線性表的查找 316
9．2．1 順序查找 316
9．2．2 二分查找 317
9．2．3 分塊查找 320
9．3 樹表的查找 323
9．3．1 二叉排序樹 323
9．3．2 平衡的二叉排序樹 330
9．3．3 B-樹 335
9．4 散列表的查找 342
9．4．1 散列表的概念 342
9．4．2 散列函數的構造方法 344
9．4．3 處理衝突的方法 347
9．4．4 散列表的運算 351
9．4．5 散列表的查找及分析 355
9．5 查找的簡單應用舉例 357
本章小結 362
習題9 363
第10章 文件 365
10．1 文件的基本概念 365
10．2 順序文件 367
10．3 索引文件 368
10．4 索引順序文件 370
10．4．1 ISAM文件 370
10．4．2 VSAM文件 373
10．5 散列文件 375
10．6 多關鍵字文件 376
10．6．1 多重表文件 376
10．6．2 倒排文件 377
本章小結 378
習題10 379
參考文獻 380

再版前言
本書是普通高等教育“十一五”國家級規劃教材。本書較繫統地介紹了程序設計中最常用的一些數據結構，如線性表、棧和隊列、數組、串、樹、圖等；闡述各種數據結構的邏輯關繫，討論它們在計算機中的存儲表示，以及在這些數據結構上的運算，並對其算法的復雜度進行簡要的分析；另外，還介紹了程序設計中常用的各種排序和查找算法；每章中的“簡單應用舉例”，既是本章算法的綜合應用，也可作為本章實訓內容和課程設計的綜合練習，具有很強的實用性和可操作性。
本書共分10章，內容包括：數據結構的概念，幾種基本的線性結構（如線性表），棧和隊列，串，幾種非線性結構（如多維數組和廣義表），樹，圖，常用的數據處理技術（如排序），查找，文件的存儲結構和組織方法等。
本書既重視理論又重視實踐，配有大量的習題和例題，解釋頗為詳細。全書采用C語言作為描述語言，並有詳細的注釋，書中全部程序均上機在TURBOC2。0環境下進行驗證並調試通過，同時給出部分程序的運行結果。
本書是作者在講授“數據結構”和“高級程序設計語言”等課程20餘年教學經驗的基礎上，集歷年各種版本教材及作者多年來的備課筆記之精華，結合本科教學特點編寫而成的。因此，學生通過相關內容的學習之後，可以直接使用書中算法或程序，有助於提高學生對所學知識的融會貫通和靈活應用，培養學生理論聯繫實際的良好學風。
本書第1版於2006年出版，經過近10年在上海交通大學、上海大學、海南大學、山東理工大學等多所高校的計算機及應用、微電子和信息工程、信息安全、計算機信息管理和自動控制等相關專業的多屆學生中的使用，取得了較好的教學效果並獲得了較高的評價。另外，本書還於2009年9月獲得上海交通大學第12屆優秀教材二等獎。
本書在再版過程中，山東理工大學電氣與電子工程學院姜吉順副教授對全書進行了全面修訂並對書中的例題和習題以及書中的全部程序進行了驗證和調試。
本書的再版不僅更正了原書中的疏漏和錯誤，也增補了一些細節；另外，在文字的敘述方面也進行了一些潤色和刪繁就簡的工作。
此書的再版，首先要感謝電子工業出版社和冉哲編輯。因為目前的出版業與10年前已發生很大的變化，市場的競爭更加激烈、更為市場化。所以，對於出版社來說，決定一本書是否再版，是需要一定的眼光和需要承擔一定風險的。但是，對於一個作者來說，能夠在這種情況下，再版一本舊作，比完成一本新書更有成就感。因為，書作為科學的載體，其價值是需要用時間來檢驗的，隻有經得起時間考驗的作品，纔是真正具有價值的。
原上海大學計算機學院院長張吉鋒教授、原上海交通大學軟件學院副院長侯文永教授對本書的內容以及實驗和課程設計教學環節提出了很多寶貴的意見與建議；上海大學計算機工程與科學學院的曹旻、劉華兩位老師，海南大學信息學院信息安全繫的周曉誼老師在本書的使用和推介過程中做了大量的工作，並對此書的部分內容提出了一些建設性的修改意見，謹在此一並表示衷心的感謝。
本書主要作為全日制高等學校計算機應用專業、微電子和信息工程專業、計算機信息管理和經濟信息管理類等專業普通本科學生的專業基礎課教材；也可以作為上述專業高職高專學生的參考教材；還可以作為計算機等級考試的參考書，供廣大從事計算機應用工作的管理人員和技術人員學習參考。
由於作者水平有限，書中缺點和錯誤在所難免，希望廣大讀者批評指正。
作者
於上海交通大學