本書是為“數(shù)據(jù)結(jié)構(gòu)”課程編寫的教材，也可以作為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)及其算法的C語言程序設(shè)計(jì)的參考書。
書中系統(tǒng)介紹各種常用的數(shù)據(jù)結(jié)構(gòu)及它們的存儲(chǔ)表示，討論了基于這些數(shù)據(jù)結(jié)構(gòu)的基本操作和實(shí)際的執(zhí)行算法，并闡述了各種常用數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系。全書共分為9章。第1章為概論，引入數(shù)據(jù)結(jié)構(gòu)與算法的一些基本概念，是全書的綜述； 第2~7章分別介紹線性表、棧、隊(duì)列、串、多維數(shù)組、廣義表、樹、二叉樹和圖等幾種基本的數(shù)據(jù)結(jié)構(gòu)； 第8章和第9章分別介紹查找和排序，它們都是數(shù)據(jù)處理時(shí)廣泛使用的技術(shù)。書中既體現(xiàn)了抽象數(shù)據(jù)類型的觀點(diǎn)，又對(duì)每個(gè)算法的具體實(shí)現(xiàn)給出了完整的C語言源代碼描述。
本書的特色是深入淺出，既注重理論又重視實(shí)踐，使用算法設(shè)計(jì)實(shí)例的教學(xué)方式來組織內(nèi)容，重點(diǎn)明確、結(jié)構(gòu)合理。全書配有大量的例題和詳盡的注釋，各章都有小結(jié)和不同類型的習(xí)題。書中自始至終使用C語言來描述算法和數(shù)據(jù)結(jié)構(gòu)，全部程序都在CFree 3.5或Visual C++ 6.0中調(diào)試通過。
本書可作為普通高等學(xué)校計(jì)算機(jī)及相關(guān)專業(yè)本科生的教材，也可作為專科和成人教育的教材，還可供從事計(jì)算機(jī)應(yīng)用的科技人員參考。與本書配套的《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程(C語言版)》也將由清華大學(xué)出版社出版。
本書的特色是深入淺出，注重基本理論、基本知識(shí)和基本技能，每一章的開頭都配有本章要點(diǎn)和本章學(xué)習(xí)目標(biāo)，且思想性、科學(xué)性、啟發(fā)性貫穿于所有章節(jié)。它的教學(xué)要求是：讓學(xué)生學(xué)會(huì)分析和研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，為應(yīng)用的數(shù)據(jù)選擇恰當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析技術(shù)，在學(xué)習(xí)中訓(xùn)練程序設(shè)計(jì)的能力。內(nèi)容中配有大量的例題和詳盡的注釋，末尾處都配有本章小結(jié)，并配置了大量的不同類型的習(xí)題。書中自始至終使用C語言來描述算法和數(shù)據(jù)結(jié)構(gòu)，各章的程序都在C-Free 4.0或Visual C++ 6.0中調(diào)試通過，以方便讀者在計(jì)算機(jī)上進(jìn)行實(shí)踐，有助于理解算法的實(shí)質(zhì)和基本思想。
前言
在社會(huì)信息化的今天，計(jì)算機(jī)及物聯(lián)網(wǎng)+給人類社會(huì)、人們的生活和學(xué)習(xí)等方面帶來了巨大的影響，社會(huì)對(duì)信息技術(shù)型人才的需求量越來越大，而信息技術(shù)型人才的培養(yǎng)又是高等學(xué)校人才培養(yǎng)的重要組成部分，本書就是基于培養(yǎng)信息化人才的需要而編寫的。
“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)的算法理論基礎(chǔ)和軟件設(shè)計(jì)的技術(shù)基礎(chǔ)，主要研究信息的邏輯結(jié)構(gòu)及其基本操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。因此，“數(shù)據(jù)結(jié)構(gòu)”不僅是計(jì)算機(jī)專業(yè)的一門核心課程，也是其他理工科專業(yè)的熱門選修課。學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法并加以實(shí)現(xiàn)，是計(jì)算機(jī)工作者和其他科技工作者不可缺少的知識(shí)和能力。
“數(shù)據(jù)結(jié)構(gòu)”課程內(nèi)容抽象，知識(shí)豐富，隱藏在各章節(jié)內(nèi)容中的方法和技術(shù)多。編者長期從事“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)，對(duì)課程的教學(xué)特點(diǎn)和知識(shí)的難點(diǎn)有比較深切的體會(huì)。在本書中，編者對(duì)多年來形成的“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)內(nèi)容進(jìn)行了合理的剪裁和重組，既強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)的原理和方法，又特別注重其實(shí)踐性與實(shí)用性。
本書介紹了各種常用的數(shù)據(jù)結(jié)構(gòu)和它們在計(jì)算機(jī)中的存儲(chǔ)表示，討論了在這些數(shù)據(jù)結(jié)構(gòu)上的基本運(yùn)算（操作）和實(shí)際的執(zhí)行算法，簡要介紹了算法的時(shí)間分析和空間分析的技巧，并闡述了各種常用數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系。
本書共分9章。第1章為概論； 第2~4章分別介紹線性表、棧、隊(duì)列和串等幾種基本的數(shù)據(jù)結(jié)構(gòu)，它們都屬于線性結(jié)構(gòu)； 第5~7章分別介紹多維數(shù)組、廣義表、樹和圖等非線性結(jié)構(gòu)； 第8章和第9章分別介紹查找和排序，它們都是數(shù)據(jù)處理中需要廣泛使用的技術(shù)。
本書的特色是深入淺出，注重基本理論、基本知識(shí)和基本技能，每一章的開頭都配有本章要點(diǎn)和本章學(xué)習(xí)目標(biāo)，且思想性、科學(xué)性、啟發(fā)性貫穿所有章節(jié)。它的教學(xué)要求是： 讓學(xué)生學(xué)會(huì)分析和研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，為應(yīng)用的數(shù)據(jù)選擇恰當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析技術(shù)，在學(xué)習(xí)中提高程序設(shè)計(jì)的能力。書中配有大量的例題和詳盡的注釋，每一章的末尾處都有本章小結(jié)和不同類型的習(xí)題。書中自始至終使用C語言來描述算法和數(shù)據(jù)結(jié)構(gòu)，各章的程序都在CFree 4.0或Visual C++ 6.0中調(diào)試通過，以方便讀者在計(jì)算機(jī)上進(jìn)行實(shí)踐，有助于理解算法的實(shí)質(zhì)和基本思想。
本書可作為計(jì)算機(jī)專業(yè)本科學(xué)生的教材，其內(nèi)容可以講授一個(gè)學(xué)期。將本書用作其他相關(guān)專業(yè)本科生教材、計(jì)算機(jī)專業(yè)專科生教材或成人教育的教材時(shí)，建議授課教師根據(jù)實(shí)際情況適當(dāng)刪減教材內(nèi)容（帶“*”部分）。在教學(xué)過程中，除了理論教學(xué)以外，上機(jī)實(shí)踐也是一個(gè)不可缺少的環(huán)節(jié)，與本書配套的《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（C語言版）》也將由清華大學(xué)出版社出版。
另外，本書也可供從事計(jì)算機(jī)應(yīng)用等工作的工程技術(shù)人員參考，讀者只需掌握C語言編程的基本技術(shù)就可以學(xué)習(xí)本書。
本書在2013年第2版的基礎(chǔ)上修訂而成。
由于編者水平有限，書中難免存在一些不足之處，殷切希望廣大讀者批評(píng)指正。
編者
2018年5月
目錄
第1章概論
1.1什么是數(shù)據(jù)結(jié)構(gòu)
1.1.1數(shù)據(jù)和數(shù)據(jù)元素
1.1.2數(shù)據(jù)類型與數(shù)據(jù)對(duì)象
1.1.3數(shù)據(jù)結(jié)構(gòu)
1.2為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
1.2.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性
1.2.2數(shù)據(jù)結(jié)構(gòu)的應(yīng)用舉例
1.3算法和算法分析
1.3.1算法的概念
1.3.2算法的描述和設(shè)計(jì)
1.3.3算法分析
本章小結(jié)
習(xí)題1
第2章線性表
2.1線性表的基本概念
2.1.1線性表的定義
2.1.2線性表的基本操作
2.2線性表的順序存儲(chǔ)
2.2.1順序表
2.2.2順序表的基本操作
2.2.3一個(gè)完整的例子（1）
2.3線性表的鏈?zhǔn)酱鎯?chǔ)
2.3.1單鏈表的基本概念
2.3.2單鏈表的基本操作
2.3.3一個(gè)完整的例子（2）
2.3.4循環(huán)鏈表
2.3.5雙向鏈表
2.3.6雙向循環(huán)鏈表
2.3.7靜態(tài)鏈表
2.4線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較
2.5線性表的應(yīng)用
2.5.1約瑟夫問題
2.5.2多項(xiàng)式加法
2.5.3電文加密
本章小結(jié)
習(xí)題2
第3章棧和隊(duì)列
3.1棧
3.1.1棧的定義與基本操作
3.1.2順序棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)
3.1.3鏈棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)
3.2棧的應(yīng)用
3.2.1數(shù)制轉(zhuǎn)換
3.2.2括號(hào)匹配問題
3.2.3子程序的調(diào)用
3.2.4利用一個(gè)順序棧逆置一個(gè)帶頭結(jié)點(diǎn)的單鏈表
3.3隊(duì)列
3.3.1隊(duì)列的定義與基本操作
3.3.2鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)
3.3.3順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)
3.4隊(duì)列的應(yīng)用
3.4.1打印楊輝三角形
3.4.2迷宮問題： 尋找一條從迷宮入口到出口的最短路徑
3.5遞歸
3.5.1遞歸的定義與實(shí)現(xiàn)
3.5.2遞歸消除
本章小結(jié)
習(xí)題3
第4章串
4.1串的定義和基本操作
4.1.1串的定義
4.1.2串的基本操作
4.2串的表示和實(shí)現(xiàn)
4.2.1串的定長順序存儲(chǔ)
4.2.2串的堆存儲(chǔ)結(jié)構(gòu)
4.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)
4.3串的模式匹配算法
4.3.1基本的模式匹配算法
4.3.2模式匹配的改進(jìn)算法——KMP算法
本章小結(jié)
習(xí)題4
第5章多維數(shù)組和廣義表
5.1多維數(shù)組
5.1.1多維數(shù)組的定義
5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)
5.2矩陣的壓縮存儲(chǔ)
5.2.1特殊矩陣
5.2.2稀疏矩陣
5.3廣義表
本章小結(jié)
書單推薦
