動手學數據結構與算法

俞勇 翁惠玉 傅凌玥 周聰

  • 出版商: 人民郵電
  • 出版日期: 2024-08-01
  • 定價: $539
  • 售價: 8.5$458
  • 語言: 簡體中文
  • 頁數: 261
  • ISBN: 7115647801
  • ISBN-13: 9787115647801
  • 下單後立即進貨 (約2週~3週)

  • 動手學數據結構與算法-preview-1
  • 動手學數據結構與算法-preview-2
動手學數據結構與算法-preview-1

相關主題

商品描述

本書系統介紹了數據結構與算法的基本概念和相關知識,既註重理論,又註重算法設計,更突出代碼實現,是一本著眼於數據結構與基本算法的教學實踐的教材。 本書介紹了線性表、隊列與棧、樹與優先級隊列、集合與靜態查找表、動態查找表、排序、外部查找與排序、圖、最小生成樹與最短路徑、算法設計思想等內容,將數據結構的理論與真實應用的實踐緊密結合,從各種數據結構的代碼實現到火車票管理系統的代碼實現,手把手地指導讀者學習數據結構與算法,幫助讀者輕松掌握數據結構與算法的基本知識及基本技能,為後續進行更多專業課程的學習打下扎實基礎。

作者簡介

俞勇,享受国务院特殊津贴专家,首批“国家高层次人才特殊支持计划”教学名师,上海交通大学特聘教授,上海交通大学ACM班创始人,APEX数据与知识管理实验室主任。曾获得“全国模范教师”“全国师德标兵”“CCF杰出教育奖”“上海市五一劳动奖章”和“上海交通大学校长奖”等荣誉。2018年创办了伯禹人工智能学院,在上海交通大学ACM班人工智能专业课程体系的基础上,对人工课程体系进行创新,致力于培养卓越的人工智能算法工程师和研究员。翁惠玉,上海交通大学教授,长期担任ACM班程

序设计和数据结构课程的主讲教师,著有“十二五”普通高等教育本科国家级规划教

材《数据结构:思想与实现》(第2版)、工业和信息化部“十四五”规划教材《C++

程序——设计思想与方法》(慕课版)(第4版)等。 傅凌玥,上海交通大学博士生,本科毕业于上海交通大学ACM班;担任2019学年ACM班“数据结构”“编程综合实践”课程助教,2022学年工科平台“程序设计思想与方法(C++)”课程助教。周聪,上海交通大学博士生,本科毕业于上海交通大学ACM班;担任2020学年ACM班“程序设计”“数据结构”“编程综合实践”课程助教组组长,2021学年ACM班“程序设计”课程助教组组长。

目錄大綱

第 1章 緒論 1

11 問題引入 1

12 什麽是數據結構 3

121 數據的邏輯結構 3

122 數據的存儲結構 4

123 數據的操作 5

13 算法分析 5

131 算法的基本概念 5

132 時間復雜度 6

133 空間復雜度 11

14 算法優化 11

141 時間復雜度為O(n3)的算法11

142 時間復雜度為O(n2)的算法 12

143 時間復雜度為O(nlogn)的算法 13

144 時間復雜度為O(n)的算法 15

15 大型應用實現:火車票管理系統總覽 16

16 小結 17

17 習題 18

第 2章 線性表 19

21 問題引入 19

22 線性表的定義 20

23 線性表的實現 20

231 線性表的順序實現 20

232 線性表的鏈接實現 23

24 線性表的簡單應用 27

241 大整數處理 27

242 多項式求和 32

25 大型應用實現:列車運行計劃管理類 34

26 小結 36

27 習題 37

第3章 隊列與棧 38

31 問題引入 38

32 隊列 38

321 隊列的定義 39

322 隊列的順序實現 39

323 隊列的鏈接實現 44

324 隊列的簡單應用:排隊洗衣 45

33 棧 47

331 棧的定義 47

332 棧的順序實現 48

333 棧的鏈接實現 50

334 棧的簡單應用:括號匹配 52

34 大型應用實現:排隊交易類 53

35 小結 55

36 習題 55

第4章 樹與優先級隊列 57

41 問題引入 57

42 樹的定義 57

43 二叉樹 59

431 二叉樹的定義 59

432 二叉樹的順序實現 63

433 二叉樹的鏈接實現 63

434  二叉樹的簡單應用:哈夫曼編碼

和哈夫曼樹 69

44 優先級隊列 74

441 優先級隊列的定義 74

442 優先級隊列的實現 74

443  優先級隊列的簡單應用:

任務調度 81

45 大型應用實現:帶優先級的排隊

交易類 82

46 小結 83

47 習題 83

第5章 集合與靜態查找表 85

51 問題引入 85

52 集合的定義 85

53 靜態查找表 86

531 無序查找的實現 86

532 有序查找的實現 87

54 集合的簡單應用:並查集 89

55 大型應用實現:列車運行圖類(1) 92

56 小結 94

57 習題 94

第6章 動態查找表 96

61 問題引入 96

62 動態查找表的定義 96

63 二叉查找樹 97

631 二叉查找樹的定義 97

632 二叉查找樹的實現 97

64 AVL樹102

641 AVL樹的定義 102

642 AVL樹的實現 104

65 紅黑樹 112

651 紅黑樹的定義 112

652 紅黑樹的實現 114

66 哈希表 123

661 哈希表的定義 124

662 哈希表的實現 124

67 大型應用實現:旅客管理類129

68 小結 131

69 習題 132

第7章 排序 134

71 問題引入 134

72 排序的定義 134

73 插入排序 135

731 直接插入排序 135

732 二分插入排序 136

733 希爾排序 136

74 選擇排序 138

741 直接選擇排序 138

742 堆排序 139

75 交換排序 141

751 冒泡排序 141

752 快速排序 142

76 歸並排序 144

77 基數排序 145

78 小結 147

79 習題 148

第8章 外部查找與排序 150

81 問題引入 150

82 外部查找表的定義 150

83 B樹 151

831 B樹的定義 151

832 B樹的實現 152

84 B+樹 155

841 B+樹的定義 155

842 B+樹的實現 158

85 外排序 174

851 外排序的定義 174

852 外排序的實現 174

86 大型應用實現:餘票管理類與行程

管理類 177

87 小結 183

88 習題 183

第9章 圖 185

91 問題引入 185

92 圖的定義 185

93 圖的實現 188

931 鄰接矩陣 188

932 鄰接表 191

94 圖的遍歷 194

941 深度優先搜索(DFS) 194

942 廣度優先搜索(BFS) 196

95 圖的遍歷的簡單應用 197

951 圖的連通性 197

952 歐拉迴路 198

953 拓撲排序 202

954 關鍵路徑 204

96 大型應用實現:列車運行圖類(2) 206

97 小結 209

98 習題 209

第 10章 最小生成樹與最短路徑 211

101 問題引入 211

102 最小生成樹 211

1021 最小生成樹的定義 211

1022 克魯斯卡爾算法 212

1023 普里姆算法 214

103 單源最短路徑 217

1031 非加權圖的單源最短路徑 217

1032 加權圖的單源最短路徑 219

1033  帶有負權值圖的單源最短

路徑 221

1034 無環圖的單源最短路徑 222

104 所有頂點對的最短路徑 223

105 大型應用實現:列車運行圖類(3) 224

106 小結 226

107 習題 226

第 11章 算法設計思想 228

111 枚舉法 228

112 貪婪算法 229

113 分治法 230

114 回溯法 233

115 動態規劃 235

116 隨機算法 237

117 算法綜合分析:外賣配送任務 238

118 小結 240

119 習題 240

附錄A 書中部分命題的證明 242

A1 證明二叉樹的性質 242

A2  證明兩種遍歷方法是否能夠唯一確定

一棵二叉樹 244

A3 證明AVL樹的高度是對數級別的 245

A4  證明AVL樹插入後至多只需要調整一個

結點即可恢復平衡 246

A5  證明快速排序的平均時間復雜度為

O(nlogn) 246

A6  證明歸並排序的時間復雜度為

O(nlogn) 247

附錄B 電子資源與運行環境配置 248

B1 動手練平臺 248

B2 電子資料倉庫 248

B3 本地環境搭建和倉庫代碼運行 249

B31 Linux環境 249

B32 Windows環境 255

B33 macOS環境 260