清華大學電子工程系核心課系列教材:數據與算法 清华大学电子工程系核心课系列教材:数据与算法

吳及，清華大學電子工程系副系主任，長聘副教授，博士生導師。1996年和2001年在清華大學電子工程系獲得學士和工學博士學位。2013—2015年在美國佐治亞理工學院擔任訪問學者。主要從事數據與算法方面的教學工作，以及人工智能和大數據領域的研究工作。2006起擔任清華-訊飛語音技術聯合實驗室主任。目前是中國語音產業聯盟技術工作組組長。先後獲得2011年度國家科技進步二等獎和2014年度北京市科學技術獎一等獎。已在國內外刊物和學術會議上發表論文一百餘篇，現在為IEEE高級會員。

陳健生，博士，出生於安徽省蕪湖市，畢業於清華大學計算機科學與技術系（學士、碩士）和香港中文大學計算機科學與工程系（博士）。目前在清華大學電子工程系任副教授，博士生導師。教學方面，擔任電子系本科生核心課“數據與算法”及限選課“視聽信息系統導論”的主講教師；曾獲清華大學第六屆青年教師教學大賽理工科一等獎。主要研究領域為計算機視覺與機器學習。在國際期刊及會議上發表有多篇論文，曾獲2013年度北京市科學技術獎一等獎。

白鉑，男，1982年生於陝西西安，2004年畢業於西安電子科技大學，獲學士學位，陝西省優秀畢業生。2010畢業於清華大學，獲博士學位，電子系學術新秀。2010—2012年在香港科技大學做博士後研究。隨後，進入清華大學電子系任講師，碩士生導師。曾獲2016年清華大學青年教師教學基本功大賽一等獎（理工組）。2017年加入華為技術有限公司2012實驗室，任未來網絡理論實驗室高級研究員。研究方向包括無線協作資源分配、Cloud/Fog-無線計算網絡、網絡信息論、網絡大數據分析等。發表學術論文近80篇，其中SCI檢索論文近30篇，曾獲IEEE ICC 2016最佳論文獎。

第1章數據、數學模型和算法1 
1.1數據時代1 
1.1.1什麼是數據1 
1.1.2大數據時代2 
1.1.3數據的重要性4 
1.2數據的表示5 
1.2.1二元關係及其性質5 
1.2.2數據的邏輯結構9 
1.2.3數據的存儲結構12 
1.2.4抽像數據類型12 
1.3數學模型13 
1.3.1什麼是數學模型13 
1.3.2數學模型的種類14 
1.3.3數學模型與計算機15 
1.3.4數據結構16 
1.4算法及復雜度分析16 
1.4.1什麼是算法16 
1.4.2問題與解17 
1.4.3算法的分析與評價18 
1.5本章小結22 

第2章線性結構24 
2.1線性表24 
2.1.1線性表的概念及其抽像數據類型24 
2.1.2線性表的順序存儲——順序表27 
2.1.3線性表的鍊式存儲——鍊錶30 
2.1.4線性表小結35 
2.2棧35 
2.2.1棧的概念與實現35 
2.2.2棧的應用38 
2.2.3遞歸41 
2.3隊列48 
2.3.1隊列的概念與實現48
2.3.2優先級隊列51 
2.4字符串55 
2.4.1字符串的概念和ADT55 
2.4.2字符串的存儲表示56 
2.4.3字符串的模式匹配和簡單匹配算法57 
2.4.4KMP算法58 
2.5本章小結61 

第3章樹與二叉樹62 
3.1樹的基本概念62 
3.1.1普遍存在的樹結構62 
3.1.2樹的定義和性質65 
3.2二叉樹67 
3.2.1二叉樹的定義和性質68 
3.2.2二叉樹的表示和實現70 
3.2.3二叉樹的遍歷76 
3.2.4二叉樹運算81 
3.2.5二叉樹的建立83 
3.3二叉樹的應用84 
3.3.1表達式求值84 
3.3.2二叉搜索樹85 
3.3.3Hu.man樹與編碼89 
3.3.4堆95 
3.4並查集102 
3.5本章小結103
 
第4章圖105 
4.1圖的基本概念105 
4.1.1圖的定義和概念105 
4.1.2圖的抽像數據類型110 
4.1.3歐拉路徑110 
4.2圖的存儲結構112 
4.2.1圖的鄰接矩陣表示112 
4.2.2圖的鄰接表表示115 
4.2.3圖的其他表示方法119
4.3圖的遍歷122 
4.3.1圖的深度優先遍歷123 
4.3.2圖的廣度優先遍歷124 
4.3.3圖遍歷的應用125 
4.3.4圖的連通性128 
4.4有向圖與有向無環圖129 
4.4.1有向圖的連通性和傳遞閉包129 
4.4.2有向無環圖和拓撲排序132 
4.4.3關鍵路徑135 
4.5最小生成樹137 
4.5.1圖的生成樹與最小生成樹137 
4.5 .2普里姆（Prim）算法139 
4.5.3克魯斯卡爾（Kruskal）算法142 
4.6最短路徑問題144 
4.6.1單源最短路徑145 
4.6.2全源最短路徑147 
4.7最大流149 
4.7.1網絡流的基本概念150 
4.7.2Ford—Fulkerson方法151 
4.8匹配154 
4.8.1二分圖和匹配的基本概念154 
4.8.2匈牙利算法155 
4.8.3最大匹配與最大流157 
4.9本章小結157