在編寫計算機程序解決實際問題之前,應該首先建立針對該問題的邏輯模型,包括相關數(shù)據(jù)的組織結(jié)構和處理算法,本書就是針對如何有效地組織數(shù)據(jù)以及如何設計處理算法而編寫的。本書采用通俗易懂的語言,結(jié)合大量圖示和實例,幫助讀者理解和掌握數(shù)據(jù)結(jié)構相關的基本概念、基礎知識和主要算法。第2章、第5章和第6章還針對最典型的線性結(jié)構、樹結(jié)構和圖結(jié)構給出了綜合性較強的應用案例,以幫助讀者綜合運用所學知識解決實際問題。本書用C和Java兩種程序設計語言來描述相關的存儲結(jié)構和處理算法,使學生能夠掌握數(shù)據(jù)結(jié)構的面向過程和面向?qū)ο蟪绦蛟O計方法。本書適合作為高等院校計算機類專業(yè)“數(shù)據(jù)結(jié)構”課程的教材,也適合作為相關領域工作人員的參考圖書。
數(shù)據(jù)結(jié)構在計算機科學中具有基礎性地位,是高等院校計算機類專業(yè)及其他相關專業(yè)必修的專業(yè)核心基礎課程,在進行程序設計之前,首先要利用數(shù)據(jù)結(jié)構知識進行數(shù)據(jù)的邏輯結(jié)構、存儲結(jié)構及處理算法的設計。本書主要介紹集合、線性結(jié)構、樹形結(jié)構、圖形結(jié)構、查找和排序等相關理論,幫助讀者理解和掌握數(shù)據(jù)結(jié)構與算法的分析設計方法。本書用C和Java兩種語言來描述相關的存儲結(jié)構與算法,幫助讀者掌握數(shù)據(jù)結(jié)構的面向過程和面向?qū)ο蟪绦蛟O計方法。本書包含以下理論、技術與應用:?線性表;?棧和隊列;?串、數(shù)組和廣義表;?樹;?圖;?查找;?排序。教學資源?微課視頻?教學課件?教學大綱?思政元素?習題解答?算法代碼?綜合案例?示例插圖說明:微課視頻在書中掃碼即可觀看,其他資源可掃描上方二維碼獲取,也可以到清華大學出版社網(wǎng)站本書頁面(或“電子信息教材事業(yè)部”微信公眾號)下載。
前言
“數(shù)據(jù)結(jié)構”是高等院校計算機類專業(yè)及其他相關專業(yè)的一門必修的專業(yè)核心基礎課程,主要講解數(shù)據(jù)的各種邏輯結(jié)構和存儲結(jié)構,以及對每種結(jié)構的處理算法,使學生能夠使用數(shù)據(jù)結(jié)構和算法的基本分析和設計方法,提高學生分析和解決實際問題的能力,也為學生學習后續(xù)專業(yè)課程奠定基礎。
本書內(nèi)容涉及集合、線性結(jié)構、樹結(jié)構和圖結(jié)構4種邏輯結(jié)構,以及查找和排序方法,學習內(nèi)容較多,對初學者也有較高的難度。在學習“數(shù)據(jù)結(jié)構”這門課程時,應牢固掌握有關的基本概念、基礎知識和主要算法,深刻理解數(shù)據(jù)組織和處理的思想方法,學會針對具體問題建立有效的邏輯模型,培養(yǎng)分析和解決實際問題的能力。在學習過程中,對于每個具體內(nèi)容,都要深入思考“3W”,即What(是什么)、How(怎么做)和Why(為什么),切記不要死記硬背,要學會將狹義問題廣義化,復雜問題簡單化,不同問題統(tǒng)一化,形象問題抽象化,靈活運用,舉一反三。
全書共8章,第1章講解數(shù)據(jù)結(jié)構、算法和算法分析的基本概念,第2章講解線性表的邏輯結(jié)構、存儲結(jié)構和處理算法,第3章講解棧和隊列這兩種特殊的線性結(jié)構,第4章講解串、數(shù)組和廣義表的基本概念和基礎知識,第5章講解二叉樹、樹和森林的邏輯結(jié)構、存儲結(jié)構和處理算法,第6章講解圖的邏輯結(jié)構、存儲結(jié)構和處理算法,第7章講解查找表的組織方式以及查找算法,第8章講解常用的排序算法。每章之后都有習題,其中,第2章和第5章還借應用案例講解了集合的線性結(jié)構和樹結(jié)構的實現(xiàn)方法。
本書用通俗易懂的語言,結(jié)合大量圖示和實例來講解數(shù)據(jù)結(jié)構的基本概念、基礎知識和處理算法,幫助讀者理解和掌握相關內(nèi)容,其中,在第2章、第5章和第6章還給出了應用案例; 注重講解數(shù)據(jù)結(jié)構和算法的分析設計方法,使讀者能夠理解數(shù)據(jù)結(jié)構和算法為什么如此設計。本書算法比較全面,并且用C和Java兩種程序設計語言來描述相關的存儲結(jié)構和處理算法,這兩種語言正是面向過程程序設計語言和面向?qū)ο蟪绦蛟O計語言的典型代表,使讀者能夠掌握數(shù)據(jù)結(jié)構的面向過程和面向?qū)ο蟪绦蛟O計方法。
本書由費如純、劉麗華和胡楠主編,趙楊川、王彥明和吳吉紅副主編。本書第6章由費如純編寫,第5章由劉麗華編寫,第2章由胡楠編寫,第7章由王彥明編寫,第1章和第3章由趙楊川編寫,第4章和第8章由吳吉紅編寫。
本書在編寫過程中,參閱了大量圖書和網(wǎng)絡資料,在此向有關作者表示最誠摯的謝意!由于編者水平有限,本書中難免存在疏漏或不足之處,懇請廣大讀者批評指正。
編者
2025年4月
費如純遼寧科技學院教授,武漢大學博士。曾任遼寧科技學院電子與信息工程學院副院長(2010—2016年),遼寧科技學院曙光大數(shù)據(jù)學院副院長(2016—2018年),遼寧科技學院信息化管理辦公室主任(2018—2022年)。目前主要研究方向為密碼學、網(wǎng)絡安全及大數(shù)據(jù)技術。出版教材5部、學術專著1部。在國內(nèi)外學術期刊發(fā)表EI檢索論文10余篇。
目錄
第1章緒論
1.1數(shù)據(jù)結(jié)構有什么用
1.2基本概念
1.2.1數(shù)據(jù)
1.2.2數(shù)據(jù)結(jié)構
1.2.3數(shù)據(jù)類型
1.3算法及性能分析
1.3.1算法
1.3.2算法描述
1.3.3性能分析
小結(jié)
習題1
第2章線性表
2.1基本概念
2.1.1線性表的概念
2.1.2抽象數(shù)據(jù)類型
2.2順序表
2.2.1基本概念
2.2.2插入與刪除操作
2.2.3數(shù)據(jù)類型及算法描述
2.3動態(tài)鏈表
2.3.1基本概念
2.3.2單鏈表
2.3.3雙向鏈表
2.4靜態(tài)鏈表
2.4.1基本概念
2.4.2存儲結(jié)構
2.4.3基本操作
2.5集合的線性表實現(xiàn)
2.5.1用線性表存儲集合元素
2.5.2位圖
2.5.3并查集
2.6應用案例
小結(jié)
習題2
第3章棧和隊列
3.1棧
3.1.1基本概念
3.1.2順序棧
3.1.3鏈式棧
3.2隊列
3.2.1基本概念
3.2.2順序隊列
3.2.3鏈式隊列
3.2.4優(yōu)先隊列
3.3棧和隊列的應用
3.3.1棧的應用
3.3.2棧與遞歸
3.3.3隊列的應用
小結(jié)
習題3
第4章串、數(shù)組和廣義表
4.1串
4.1.1基本概念
4.1.2存儲結(jié)構
4.1.3模式匹配
4.2數(shù)組
4.2.1基本概念和存儲結(jié)構
4.2.2特殊矩陣的壓縮存儲
4.3廣義表
4.3.1基本概念
4.3.2存儲結(jié)構
小結(jié)
習題4
第5章樹
5.1基本概念
5.1.1樹的定義
5.1.2樹的基本術語
5.2二叉樹
5.2.1二叉樹的定義
5.2.2二叉樹的基本形態(tài)
5.2.3滿二叉樹和完全二叉樹
5.2.4二叉樹的性質(zhì)
5.2.5二叉樹的順序存儲結(jié)構
5.2.6二叉樹的鏈式存儲結(jié)構
5.3二叉樹的遍歷
5.3.1按層次遍歷
5.3.2先序遍歷、中序遍歷和后序遍歷
5.3.3由遍歷序列重構二叉樹
5.3.4二元運算表達式與二叉樹的遍歷
5.3.5非遞歸遍歷
5.3.6通過遍歷對二叉樹進行處理
5.4線索二叉樹
5.4.1線索二叉樹的基本概念
5.4.2線索二叉樹的構建
5.4.3線索二叉樹的遍歷
5.5樹和森林
5.5.1樹和森林的存儲結(jié)構
5.5.2樹和森林與二叉樹之間的相互轉(zhuǎn)換
5.5.3樹和森林的遍歷
5.5.4通過遍歷對樹和森林進行處理
5.5.5基于森林的并查集
5.6哈夫曼樹
5.6.1基本概念
5.6.2哈夫曼樹的構建
5.6.3哈夫曼編碼與解碼
5.7應用案例
小結(jié)
習題5
第6章圖
6.1基本概念
6.2圖的存儲結(jié)構
6.2.1鄰接矩陣
6.2.2鄰接表
6.2.3十字鏈表
6.3圖的遍歷
6.3.1深度優(yōu)先搜索
6.3.2廣度優(yōu)先搜索
6.4圖的連通性
6.4.1路徑
6.4.2生成樹
6.4.3可達分量與連通分量
6.4.4最小生成樹
6.5最短路徑
6.5.1迪杰斯特拉算法
6.5.2弗洛伊德算法
6.6有向無環(huán)圖
6.6.1拓撲排序
6.6.2關鍵路徑
6.7應用案例
6.7.1迷宮問題
6.7.2華容道游戲
小結(jié)
習題6
第7章查找
7.1基本概念
7.2順序查找
7.3折半查找
7.4索引順序查找
7.5二叉排序樹與平衡二叉樹
7.5.1二叉排序樹
7.5.2平衡二叉樹
7.6B樹
7.6.1B樹的定義
7.6.2B樹的操作
7.7哈希查找
7.7.1基本概念
7.7.2哈希函數(shù)
7.7.3解決沖突的方法
7.7.4插入、刪除與擴容
小結(jié)
習題7
第8章排序
8.1基本概念
8.2插入排序
8.2.1直接插入排序
8.2.2折半插入排序
8.2.3希爾排序
8.3交換排序
8.3.1冒泡排序
8.3.2快速排序
8.4選擇排序
8.4.1簡單選擇排序
8.4.2樹狀選擇排序
8.4.3堆排序
8.5歸并排序
8.6基于比較的排序方法的對比
8.7計數(shù)排序和基數(shù)排序
8.7.1計數(shù)排序
8.7.2基數(shù)排序
8.8外排序
小結(jié)
習題8
參考文獻