新一輪科技革命和產(chǎn)業(yè)變革帶動了傳統(tǒng)產(chǎn)業(yè)的升級改造。黨的二十大報告強調(diào)必須堅持科技是第一生產(chǎn)力、人才是第一資源、創(chuàng)新是第一動力,深入實施科教興國戰(zhàn)略、人才強國戰(zhàn)略、創(chuàng)新驅動發(fā)展戰(zhàn)略,開辟發(fā)展新領域新賽道,不斷塑造發(fā)展新動能新優(yōu)勢。建設高質(zhì)量高等教育體系是擺在高等教育面前的重大歷史使命和政治責任。高等教育要堅持國家戰(zhàn)略引領,聚焦重大需求布局,推進新工科、新醫(yī)科、新農(nóng)科、新文科建設,加快培養(yǎng)緊缺型人才。
數(shù)據(jù)結構與算法作為計算機類核心專業(yè)基礎課程之一,是程序設計的重要理論技術基礎,也是操作系統(tǒng)、軟件工程等課程的先修課程。此外,它還是學科競賽、專業(yè)筆試和面試以及研究生錄取考試的重要內(nèi)容。該書具有受眾群體廣、受重視程度高和專業(yè)性強的特點。
通過本教材的學習,應能熟練掌握線性結構、棧和隊列、數(shù)組、樹形結構和圖形結構等數(shù)據(jù)邏輯結構的特點和性質(zhì),掌握順序存儲、鏈式存儲等數(shù)據(jù)存儲結構的特點及其應用。此外,還應該能夠熟練運用查找、排序等數(shù)據(jù)處理技術,深入理解各種數(shù)據(jù)對象的特點,學會數(shù)據(jù)的組織方式和實現(xiàn)方法,掌握數(shù)據(jù)加工處理的基本理論和技能,提升分析問題和解決問題的能力,并初步具備科學研究的能力。
本書將思政元素有機融入數(shù)據(jù)結構與算法的內(nèi)容中,旨在培養(yǎng)學生的專業(yè)認同感、探索未知、終身學習的能力,以及精益求精的工匠精神。
本書共分為10章,第1章介紹數(shù)據(jù)結構與算法這門課程的總體情況,重點介紹基本概念和術語、數(shù)據(jù)的邏輯結構和存儲結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型以及算法和算法分析方法。第2章主要介紹線性表的定義和基本操作、典型案例、線性表的順序存儲、線性表的鏈式存儲、案例分析與實現(xiàn)。第3章主要介紹棧的定義及特點、典型案例、棧的抽象數(shù)據(jù)類型定義、棧的順序存儲、棧的鏈式存儲、棧的案例分析與實現(xiàn)、隊列的定義及特點、典型案例、隊列的抽象數(shù)據(jù)類型定義、隊列的順序存儲、隊列的鏈式存儲、隊列的案例分析與實現(xiàn)。第4章主要介紹串及其基本運算、典型案例、串的存儲結構、匹配模式、案例分析與實現(xiàn)。第5章主要介紹遞歸定義、遞歸調(diào)用的實現(xiàn)原理、遞歸算法的設計。第6章主要介紹數(shù)組的邏輯結構、數(shù)組的物理結構、典型案例、特殊矩陣、廣義表、案例分析與實現(xiàn)。第7章主要介紹樹的基本概念、典型案例、二叉樹、遍歷二叉樹和線索二叉樹、樹的存儲結構、樹和森林、二叉樹的應用、案例分析與實現(xiàn)。第8章主要介紹圖的定義和基本術語、典型案例、圖的類型定義、圖的存儲結構、圖的遍歷、圖的連通性、圖的應用、案例分析與實現(xiàn)。第9章主要介紹查找的基本概念、典型案例、線性表查找、樹表的查找、哈希表查找、案例分析與實現(xiàn)。第10章主要介紹排序的基本概念、典型案例、插入排序、交換排序、選擇排序、歸并排序、各種內(nèi)排序方法的比較和選擇、案例分析與實現(xiàn)。
本書由劉朝霞、趙靜、李紹華擔任主編,刁建華、李敏、樸在吉、邵峰擔任副主編。全書由劉朝霞、趙靜負責統(tǒng)稿。
本書的編寫得到了大連外國語大學軟件學院領導以及任課教師的大力支持,在此表示衷心的感謝。
本書出版得到了遼寧省一流本科課程建設項目、遼寧省本科教學改革研究項目、大連外國語大學本科教學改革研究重點項目、大連外國語大學課程思政示范課建設項目的資助。
本教材示例的源程序、微視頻及電子教案可在清華大學出版社網(wǎng)站上免費下載。
雖然編者力求完美,但水平有限,書中難免會出現(xiàn)疏漏,懇請廣大讀者批評指正。
編者
2023年7月
隨書資源
第1章緒論
1.1數(shù)據(jù)結構與算法總覽
1.2基本概念和術語
1.3數(shù)據(jù)的邏輯結構
1.4數(shù)據(jù)的存儲結構
1.5數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.5.1數(shù)據(jù)類型
1.5.2抽象數(shù)據(jù)類型
1.6算法和算法分析方法
1.6.1算法及算法的特性
1.6.2算法的時間復雜度
1.6.3算法的空間復雜度
1.7本章小結
習題1
第2章線性表
2.1線性表的定義
2.2典型案例
2.3線性表的抽象數(shù)據(jù)類型定義
2.4順序表的定義和基本操作
2.4.1順序表的定義
2.4.2順序表的基本操作
2.5鏈表的定義和基本操作
2.5.1單鏈表的定義
2.5.2單鏈表的基本操作
2.5.3循環(huán)鏈表
2.5.4雙向鏈表
2.6順序表和鏈表的比較
2.7案例分析與實踐
2.8小結
習題2
數(shù)據(jù)結構與算法(C語言)微課視頻·在線題庫版
目錄
第3章棧和隊列
3.1棧的定義及特點
3.2棧的典型案例
3.3棧的抽象數(shù)據(jù)類型定義
3.4棧的順序存儲
3.4.1順序棧的定義
3.4.2順序棧的存儲形態(tài)
3.4.3順序棧的入棧和出棧
3.4.4順序棧的基本操作
3.5棧的鏈式存儲
3.5.1鏈棧的定義
3.5.2鏈棧的基本操作
3.6棧的案例分析與實現(xiàn)
3.7隊列的定義及特點
3.8隊列的典型案例
3.9隊列的抽象數(shù)據(jù)類型定義
3.10隊列的順序存儲
3.10.1順序隊列的定義
3.10.2順序隊列的基本操作
3.10.3循環(huán)隊列
3.10.4循環(huán)隊列的基本操作
3.11隊列的鏈式存儲
3.11.1鏈隊列的定義
3.11.2鏈隊列的基本操作
3.12隊列的案例分析與實現(xiàn)
3.13小結
習題3
第4章串
4.1串的定義及其基本運算
4.1.1串的基本概念
4.1.2串的基本運算
4.2典型案例
4.3串的存儲結構
4.3.1串的順序存儲結構
4.3.2串的鏈式存儲結構
4.4模式匹配
4.5案例分析與實現(xiàn)
4.6小結
習題4
第5章遞歸
5.1遞歸的定義
5.1.1遞歸的基本概念
5.1.2何時使用遞歸
5.1.3遞歸模型
5.2遞歸調(diào)用的實現(xiàn)原理
5.3遞歸算法的設計
5.3.1遞歸算法設計的步驟
5.3.2遞歸數(shù)據(jù)結構的遞歸算法設計
5.3.3遞歸求解方法的遞歸算法設計
5.4本章小結
習題5
第6章數(shù)組和廣義表
6.1多維數(shù)組的定義
6.1.1數(shù)組的邏輯結構
6.1.2數(shù)組的物理結構
6.2典型案例
6.3特殊矩陣
6.3.1對稱矩陣
6.3.2三角矩陣
6.3.3對角矩陣
6.4稀疏矩陣
6.4.1稀疏矩陣的定義
6.4.2稀疏矩陣的三元組表存儲
6.4.3稀疏矩陣的十字鏈表存儲
6.5廣義表
6.5.1廣義表的定義和基本運算
6.5.2廣義表的存儲
6.5.3廣義表的基本操作
6.6案例分析與實現(xiàn)
6.7小結
習題6
第7章樹與二叉樹
7.1樹的基本概念
7.1.1樹的定義
7.1.2基本術語
7.2典型案例
7.3二叉樹
7.3.1二叉樹的定義
7.3.2二叉樹的性質(zhì)
7.3.3二叉樹的存儲結構
7.3.4二叉樹的基本操作
7.4遍歷二叉樹和線索二叉樹
7.4.1遍歷二叉樹
7.4.2線索二叉樹
7.5樹、森林與二叉樹
7.5.1樹的存儲結構
7.5.2樹和二叉樹的轉換
7.5.3森林和二叉樹的轉換
7.5.4樹的遍歷
7.5.5森林的遍歷
7.6二叉樹的應用
7.6.1二叉排序樹
7.6.2哈夫曼樹
7.6.3哈夫曼編碼
7.7案例分析與實現(xiàn)
7.8小結
習題7
第8章圖
8.1圖的定義和基本術語
8.1.1圖的定義
8.1.2圖的基本術語
8.2典型案例
8.3圖的類型定義
8.4圖的存儲結構
8.4.1鄰接矩陣
8.4.2鄰接表
8.4.3十字鏈表
8.5圖的遍歷
8.5.1深度優(yōu)先搜索
8.5.2廣度優(yōu)先搜索
8.6圖的連通性
8.7圖的應用
8.7.1最小生成樹
8.7.2最短路徑
8.7.3拓撲排序
8.7.4關鍵路徑
8.8案例分析與實現(xiàn)
8.9小結
習題8
第9章查找
9.1查找的基本概念
9.2典型案例
9.3線性表查找
9.3.1順序查找
9.3.2折半查找
9.3.3分塊查找
9.4樹表的查找
9.4.1二叉排序樹
9.4.2平衡二叉樹
9.5哈希表查找
9.5.1哈希表的基本概念
9.5.2哈希表的構造方法
9.5.3哈希沖突的解決方法
9.5.4哈希表查找算法分析
9.6案例分析與實現(xiàn)
9.7小結
習題9
第10章排序
10.1排序的基本概念
10.2典型案例
10.3插入排序
10.3.1直接插入排序
10.3.2希爾排序
10.4交換排序
10.4.1冒泡排序
10.4.2快速排序
10.5選擇排序
10.5.1直接選擇排序
10.5.2堆排序
10.6歸并排序
10.6.1一次歸并
10.6.2一趟歸并排序
10.6.3二路歸并排序
10.7各種內(nèi)排序方法的比較和選擇
10.8案例分析與實現(xiàn)
10.9小結
習題10
參考文獻