《數(shù)據(jù)結(jié)構(gòu)(第2版)》的主要任務(wù)是介紹并探討有關(guān)數(shù)據(jù)組織、算法設(shè)計(jì)、時(shí)間和空間效率的概念和通用分析方法,幫助讀者學(xué)會(huì)數(shù)據(jù)的組織方法和現(xiàn)實(shí)世界問(wèn)題在計(jì)算機(jī)內(nèi)部的表示方法,針對(duì)問(wèn)題的應(yīng)用背景分析,選擇合適的數(shù)據(jù)結(jié)構(gòu),從而培養(yǎng)高級(jí)程序設(shè)計(jì)技能。 《數(shù)據(jù)結(jié)構(gòu)(第2版)》第1章介紹了數(shù)據(jù)結(jié)構(gòu)與算法的基本概念;第2章是對(duì)C語(yǔ)言關(guān)鍵內(nèi)容的復(fù)習(xí),為后續(xù)章節(jié)理解數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)做準(zhǔn)備;第3章至第7章分別介紹了線性表、樹、散列表、圖、排序算法等經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法;最后在第8章通過(guò)對(duì)兩個(gè)實(shí)際生活中提煉出的問(wèn)題的解答,幫助讀者更深刻地體會(huì)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。 《數(shù)據(jù)結(jié)構(gòu)(第2版)》可作為高等學(xué)校計(jì)算機(jī)類專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程的教材。
《數(shù)據(jù)結(jié)構(gòu)(第2版)》特色:
《數(shù)據(jù)結(jié)構(gòu)(第2版)》的主要任務(wù)是介紹并探討有關(guān)數(shù)據(jù)組織、算法設(shè)計(jì)、時(shí)間和空間效率的概念和通用分析方法,幫助讀者學(xué)會(huì)數(shù)據(jù)的組織方法和現(xiàn)實(shí)世界問(wèn)題在計(jì)算機(jī)內(nèi)部的表示方法,針對(duì)問(wèn)題的應(yīng)用背景分析,選擇合適的數(shù)據(jù)結(jié)構(gòu),從而培養(yǎng)高級(jí)程序設(shè)計(jì)技能。
從實(shí)際應(yīng)用問(wèn)題出發(fā),導(dǎo)出各種經(jīng)典數(shù)據(jù)結(jié)構(gòu)的定義、實(shí)現(xiàn)(存儲(chǔ))方法以及操作實(shí)現(xiàn),并以更豐富的綜合應(yīng)用案例幫助讀者增強(qiáng)對(duì)理論的感性認(rèn)識(shí),從而明白這些數(shù)據(jù)結(jié)構(gòu)為什么存在、以及在什么情況下可以解決什么樣的問(wèn)題。
提供了豐富的學(xué)習(xí)資源,包括源代碼及配套電子課件、浙江大學(xué)提供的在線系統(tǒng)PTA、《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)與實(shí)驗(yàn)指導(dǎo)(第2版)》等。讀者可以通過(guò)使用這些學(xué)習(xí)資源隨時(shí)檢測(cè)自己的學(xué)習(xí)效果與編程能力。
“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)類專業(yè)的重要專業(yè)基礎(chǔ)課。它所討論的知識(shí)內(nèi)容和提倡的技術(shù)方法,無(wú)論對(duì)進(jìn)一步學(xué)習(xí)計(jì)算機(jī)相關(guān)領(lǐng)域的其他課程,還是對(duì)從事大型信息工程的開(kāi)發(fā),都有著樞紐的作用。
解決問(wèn)題往往有多種方法,且不同方法之間的效率可能相差甚遠(yuǎn)。解決問(wèn)題方法的效率,與數(shù)據(jù)的組織方式有關(guān),與空間的利用效率有關(guān),也與方法的巧妙程度有關(guān)。本書的主要任務(wù)是介紹并探討有關(guān)數(shù)據(jù)組織、算法設(shè)計(jì)、時(shí)間和空間效率的概念和通用分析方法,幫助讀者學(xué)會(huì)數(shù)據(jù)的組織方法和現(xiàn)實(shí)世界問(wèn)題在計(jì)算機(jī)內(nèi)部的表示方法,針對(duì)問(wèn)題的應(yīng)用背景分析,選擇合適的數(shù)據(jù)結(jié)構(gòu),從而培養(yǎng)高級(jí)程序設(shè)計(jì)技能。
本書的特點(diǎn)是從實(shí)際應(yīng)用問(wèn)題出發(fā),導(dǎo)出各種經(jīng)典數(shù)據(jù)結(jié)構(gòu)的定義、實(shí)現(xiàn)(存儲(chǔ))方法以及操作實(shí)現(xiàn),并以更豐富的綜合應(yīng)用案例幫助讀者增強(qiáng)對(duì)理論的感性認(rèn)識(shí),從而明白這些數(shù)據(jù)結(jié)構(gòu)為什么存在,以及在什么情況下可以最好地解決什么樣的問(wèn)題。
數(shù)據(jù)結(jié)構(gòu)的思想和原理是不依賴于編程語(yǔ)言的,但對(duì)于每一個(gè)抽象概念的具體實(shí)現(xiàn)和應(yīng)用則需要一種編程語(yǔ)言作為載體。本書根據(jù)國(guó)內(nèi)多數(shù)學(xué)校計(jì)算機(jī)專業(yè)教學(xué)的實(shí)際情況,選擇了C語(yǔ)言作為具體實(shí)現(xiàn)的語(yǔ)言,并提供了大量可以直接編譯運(yùn)行的源代碼。不僅使得學(xué)生在學(xué)習(xí)時(shí)容易起步,可以在現(xiàn)有源代碼的基礎(chǔ)上不斷修改擴(kuò)充,從而解決更為復(fù)雜的問(wèn)題,而且也為IT專業(yè)人士提供了方便的經(jīng)典代碼庫(kù)。
本書第1章介紹了數(shù)據(jù)結(jié)構(gòu)與算法的基本概念和兩者的關(guān)聯(lián),重點(diǎn)介紹了抽象數(shù)據(jù)類型和算法復(fù)雜度的概念;第2章基本上是對(duì)C語(yǔ)言關(guān)鍵內(nèi)容的復(fù)習(xí),為后續(xù)章節(jié)理解數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)做準(zhǔn)備;第3章介紹了線性表以及最基本的兩種應(yīng)用——堆棧和隊(duì)列;第4章討論一種重要的非線性結(jié)構(gòu)——樹,重點(diǎn)介紹了二叉樹和搜索樹,并將查找、哈夫曼樹和集合表示等作為樹形結(jié)構(gòu)的應(yīng)用進(jìn)行了討論;第5章通過(guò)對(duì)從海量信息中高效查找關(guān)鍵字問(wèn)題的再思考,引出對(duì)散列表和經(jīng)典哈希映射技術(shù)的討論;第6章介紹圖的各種表示方法和相關(guān)算法;第7章討論了各種經(jīng)典的排序算法;最后在第8章通過(guò)對(duì)兩個(gè)實(shí)際生活中提煉出的問(wèn)題的求解,幫助讀者更深刻體會(huì)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。
讀者可以根據(jù)自身的基礎(chǔ)選擇相應(yīng)章節(jié)進(jìn)行閱讀,熟悉C語(yǔ)言的讀者完全可以跳過(guò)第2章有關(guān)C語(yǔ)言基礎(chǔ)的部分。目錄中帶*號(hào)的章節(jié)及習(xí)題中帶*號(hào)的題目,是本書的擴(kuò)展內(nèi)容,讀者可以在學(xué)習(xí)基礎(chǔ)內(nèi)容之后再閱讀擴(kuò)展內(nèi)容。
本書作為第2版,除了修訂第1版的錯(cuò)誤外,還重新整理了全部源代碼,提供了部分微視頻,并提供了新的在線練習(xí)資源。希望讀者能通過(guò)本書的學(xué)習(xí)提高實(shí)踐能力,使數(shù)據(jù)結(jié)構(gòu)與算法成為用計(jì)算機(jī)解決實(shí)際問(wèn)題的有效工具。
陳越,浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授,教育部高等學(xué)校軟件工程專業(yè)教學(xué)指導(dǎo)委員會(huì)委員。為程序設(shè)計(jì)能力標(biāo)準(zhǔn)化測(cè)試(PAT)系統(tǒng)的創(chuàng)始人。與何欽銘教授共同在“中國(guó)大學(xué)MOOC”和網(wǎng)易“云課程”平臺(tái)開(kāi)設(shè)在線開(kāi)放課程“數(shù)據(jù)結(jié)構(gòu)”,注冊(cè)人數(shù)累計(jì)超過(guò)8萬(wàn)人。為國(guó)家精品課程“軟件工程”、國(guó)家雙語(yǔ)示范課程“數(shù)據(jù)結(jié)構(gòu)與算法”、國(guó)家教學(xué)團(tuán)隊(duì)“程序設(shè)計(jì)系列課程教學(xué)團(tuán)隊(duì)”的負(fù)責(zé)人。曾獲教學(xué)成果二等獎(jiǎng)、浙江省教學(xué)成果一等獎(jiǎng)、寶鋼優(yōu)秀教師獎(jiǎng)等。
第1章 概論
1.1 引子
1.2 數(shù)據(jù)結(jié)構(gòu)
1.2.1 定義
1.2.2 抽象數(shù)據(jù)類型
1.3 算法
1.3.1 定義
1.3.2 算法復(fù)雜度
1.3.3 漸進(jìn)表示法
1.4 應(yīng)用實(shí)例:最大子列和問(wèn)題
本章小結(jié)
習(xí)題
第2章 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基礎(chǔ)
2.1 引子
2.2 數(shù)據(jù)存儲(chǔ)基礎(chǔ)
2.2.1 數(shù)組
2.2.2 類型定義typedef
2.2.3 指針
2.2.4 結(jié)構(gòu)
2.2.5 鏈表
2.3 流程控制基礎(chǔ)
2.3.1 分支控制
2.3.2 循環(huán)控制
2.3.3 函數(shù)與遞歸
本章小結(jié)
習(xí)題
第3章 線性結(jié)構(gòu)
3.1 引子
3.2 線性表的定義與實(shí)現(xiàn)
3.2.1 線性表的定義
3.2.2 線性表的順序存儲(chǔ)實(shí)現(xiàn)
3.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
3.2.4 廣義表與多重鏈表
3.3 堆棧
3.3.1 堆棧的定義
3.3.2 堆棧的實(shí)現(xiàn)
3.3.3 堆棧應(yīng)用:表達(dá)式求值
3.4 隊(duì)列
3.4.1 隊(duì)列的定義
3.4.2 隊(duì)列的實(shí)現(xiàn)
3.5 應(yīng)用實(shí)例
3.5.1 多項(xiàng)式加法運(yùn)算
3.5.2 迷宮問(wèn)題
本章小結(jié)
習(xí)題
第4章 樹
4.1 引子
4.1.1 問(wèn)題的提出
4.1.2 查找
4.2 樹的定義、表示和術(shù)語(yǔ)
4.3 二叉樹
4.3.1 二叉樹的定義及其邏輯表示
4.3.2 二叉樹的性質(zhì)
4.3.3 二叉樹的存儲(chǔ)結(jié)構(gòu)
4.3.4 二叉樹的操作
4.4 二叉搜索樹
4.4.1 二叉搜索樹的定義
4.4.2 二叉搜索樹的動(dòng)態(tài)查找
4.4.3 二叉搜索樹的插入
4.4.4 二叉搜索樹的刪除
4.5 平衡二叉樹
4.5.1 平衡二叉樹的定義
4.5.2 平衡二叉樹的調(diào)整
4.6 樹的應(yīng)用
4.6.1 堆及其操作
4.6.2 哈夫曼樹
4.6.3 集合及其運(yùn)算
本章小結(jié)
習(xí)題
第5章 散列查找
5.1 引子
5.2 基本概念
5.3 散列函數(shù)的構(gòu)造方法
5.3.1 數(shù)字關(guān)鍵詞的散列函數(shù)構(gòu)造
5.3.2 字符串關(guān)鍵詞的散列函數(shù)構(gòu)造
5.4 處理沖突的方法
5.4.1 開(kāi)放定址法
5.4.2 分離鏈接法
5.5 散列表的性能分析
5.6 應(yīng)用實(shí)例
本章小結(jié)
習(xí)題
第6章 圖
6.1 引子
6.2 圖的基本概念
6.2.1 圖的定義和術(shù)語(yǔ)
6.2.2 圖的抽象數(shù)據(jù)類型
6.3 圖的存儲(chǔ)結(jié)構(gòu)
6.3.1 鄰接矩陣
6.3.2 鄰接表
6.4 圖的遍歷
6.4.1 迷宮探索
6.4.2 深度優(yōu)先搜索
6.4.3 廣度優(yōu)先搜索
6.5 最小生成樹
6.5.1 生成樹的構(gòu)建與最小生成樹的概念
6.5.2 構(gòu)造最小生成樹的Prim算法
6.5.3 構(gòu)造最小生成樹的Kruskal算法
6.6 最短路徑
6.6.1 單源最短路徑
6.6.2 每一對(duì)頂點(diǎn)之間的最短路徑
6.7 拓?fù)渑判?/span>
6.8 關(guān)鍵路徑計(jì)算
6.9 應(yīng)用實(shí)例
6.9.1 六度空間理論
6.9.2 六度分隔理論的驗(yàn)證
本章小結(jié)
習(xí)題
第7章 排序
7.1 引子
7.2 選擇排序
7.2.1 簡(jiǎn)單選擇排序
7.2.2 堆排序
7.3 插入排序
7.3.1 簡(jiǎn)單插入排序
7.3.2 希爾排序
7.4 交換排序
7.4.1 冒泡排序
7.4.2 快速排序
7.5 歸并排序
7.6 基數(shù)排序
7.6.1 桶排序
7.6.2 基數(shù)排序
7.6.3 單關(guān)鍵字的基數(shù)分解
7.7 外部排序
7.8 排序的比較和應(yīng)用
7.8.1 排序算法的比較
7.8.2 排序算法應(yīng)用案例
本章小結(jié)
習(xí)題
第8章 綜合應(yīng)用案例分析
8.1 銀行排隊(duì)問(wèn)題
8.1.1 單隊(duì)列多窗口服務(wù)
8.1.2 單隊(duì)列多窗口+VIP服務(wù)
8.2 暢通工程問(wèn)題
8.2.1 建設(shè)道路數(shù)量問(wèn)題
8.2.2 最低成本建設(shè)問(wèn)題
本章小結(jié)
習(xí)題
附錄PTA使用說(shuō)明
參考文獻(xiàn)