为了解决膨胀的知识量与有限的学制之间的矛盾，提高教学效率和质量，培养拔尖型创新人才，清华大学电子工程系进行了全面的教学改革。在梳理出电子信息科学与技术知识构架的基础上，构建起了全新的课程体系。本书是清华大学电子工程系核心课系列教材之一，由清华大学副校长王希勤教授作序推荐。

　　随着大数据和数据科学的兴起和发展，如何看待、处理和利用数据，已经成为理论和应用价值巨大的科学领域。本书从数据与算法的相互作用出发，涵盖数据结构、数学模型、数值分析和算法设计思想等相互关联的重要内容，有利于从整体上学习和把握这个学科的基础知识，培养基础能力。

　　书中，问题和算法两个视角构成了纵横交织的网络，帮助读者更清楚地看到数据和算法的相互关系，更透彻地理解数值和非数值问题的差异和共性，帮助读者更全面地提升利用计算机作为工具解决实际问题的能力。

　　近年来，信息科学技术呈现快速发展的态势，云计算、移动互联网、大数据、人工智能，给我们所处的时代和社会带来了一波又一波的冲击。人们日常生活中的信息获取方式、社会交往方式、生产工作方式都已经发生了很大的变化，而且更为巨大的变化似乎就在并不遥远的未来。我们的教学和人才培养模式如何能够适应这样的变化，对于高等教育的从业者来说是一个严峻的挑战。 

　　为了解决膨胀的知识量与有限的学制之间的矛盾，提高教学效率和质量，培养拔尖型创新人才，清华大学电子工程系进行了全面的教学改革。在梳理出电子信息科学知识构架的基础上，构建起了全新的课程体系，数据与算法就是其中的一门核心课程。数据是客观世界的描述，是信息的载体，也是算法的处理对象；算法是解决问题的方法和步骤，是处理数据的系统。因此数据与算法的关系，本质上是信息载体与系统的相互作用。同时，数据的特性是算法设计中不可忽视的关键性因素，对数据特性利用得越充分，算法的性能和效率就越高，但与此同时，算法的针对性越强，适用面也就越窄。 

　　传统上数据结构和数值分析是两门课程，前者主要研究非数值问题，后者主要研究数值问题。但是，当我们上升到更宏观的视角，也就是数据与算法相互关系的视角，我们就能够更清楚地认识到两者之间的共性和差异。从共性上来讲，它们都把现实世界的问题简化成为数学模型上的问题，并利用计算机作为工具加以求解，因此有很多算法思想不仅能用于处理非数值问题，也能有效地处理数值问题。例如，二分法既可以用于实现有序线性表的高效查找，又可以用于求解非线性方程；寻找图的最小生成树的Prim算法、Kruskal算法和求解多维函数极值的最速下降法都是基于贪心算法的思想。数值和非数值问题的差异也很显著，数值问题中变量取值是连续的，符合一定精度要求的近似解可能有无穷多个，只需要得到符合精度要求的近似解就足够了，因此误差分析在数值分析中处于基础性的地位；而非数值问题的解空间是离散的，不需要考虑误差。在实际应用中，数值问题和非数值问题还经常交织在一起，例如搜索引擎已经成为人们获取信息的主要方式，在其实现过程中就既有非数值问题，也有数值问题。 

　　数据和算法的覆盖范围包括了传统上的数据结构、数值分析两门课程，同时还特别加入了数学模型和算法设计思想的部分，并从总体上对内容上进行了取舍。我们希望这门新设计的课程，能够让同学在学习过程中更清楚地看到数据和算法的相互关系，更透彻地理解数值和非数值问题的差异和共性，更全面地提升利用计算机作为工具解决实际问题的能力，为今后的学习和未来的发展打下扎实的基础。 

　　全书共有9章，分为四个部分。第一部分是第1章，介绍了数据，算法和数学模型的基本概念，是全书的基础。第二部分是第2～5章，包括线性结构、树结构和图结构，以及查找、排序两种最常用的非数值问题及其求解，是传统数据结构的内容。第三部分是第6、7章，包括数值问题和最优化的初步介绍，讨论的是数值问题。第四部分是第8、9章，介绍了随机算法和算法设计思想。 

　　本书第1、2、4、5章由吴及负责撰写；第6、7、8章由陈健生负责撰写；白铂撰写了第3和第9章，并参与了第4和第7章的部分工作。 

　　由于编者水平有限，疏误之处在所难免，敬请同行及各界读者批评指正。作为突破传统教学模式和内容组织方式的一次尝试，我们也希望这样的努力能够成为电子信息学科教学改革的有益探索。 

　　编者 

　　2017年8月 

　　吴及，清华大学电子工程系副系主任，长聘副教授，博士生导师。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字符串的概念和 ADT ......................................................................55 

2.4.2字符串的存储表示 ..........................................................................56 

2.4.3字符串的模式匹配和简单匹配算法 ...................................................57 

2.4.4 KMP算法 .....................................................................................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.3 Hu.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 

目录 IX 

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.2 Ford-Fulkerson方法 ..................................................................... 151 

4.8匹配 ....................................................................................................... 154 

4.8.1二分图和匹配的基本概念 .............................................................. 154 

4.8.2匈牙利算法 .................................................................................. 155 

4.8.3最大匹配与最大流 ........................................................................ 157 

4.9本章小结 ................................................................................................ 157 

　　第 1章数据、数学模型和算法 

　　1.1数据时代 

　　大数据 (big data)是当今学术界和产业界最炙手可热的名词之一，其重要性和价值已经得到广泛的认同。数据科学，也继实验科学、理论科学、计算机仿真之后，被称为科学研究的第四范式。为什么数据处理技术会得到如此普遍的重视？为什么人类会对数据中的价值寄予如此巨大的期望？又为什么人类社会发展到今天，数据的重要性会特别地凸显出来呢？我们从什么是数据谈起。 

　　1.1.1什么是数据 

　　“数”是人们用来表示事物的量的基本数学概念。在人类发展的历史上，这种抽象的“数”的概念是从具体事物中逐步获得和建立起来的。例如“一个苹果”“二个橘子”“三个香蕉”描述的是具体的事物，而“一”“二”“三”则是与具体事物无关的抽象的“数”。另一个相关的概念是“数字”，数字是人们用来计数的符号，如现在人们常用的阿拉伯数字“1”“2”“3”，又如中文的数字“一”“二”“三”和罗马数字“Ⅰ”“Ⅱ”“Ⅲ”。而我们在这里要讨论的“数据”，则是一个范围大得多的概念。 

　　数据是客观事物的符号表示，往往是通过对客观事物的观察得到的未经加工的原始素材，是包含知识和信息的原始材料。在今天的信息社会中，数据可以说无处不在，其表现形式也是多种多样，例如： 

　　文字和符号 :不仅普遍存在于书籍、报纸等传统的纸质媒介上，也广泛存在于计算机、手机、平板电脑等电子设备上；既包括今天人们使用的各种文字符号，也包括从远古时代遗存下来的象形文字和甲骨文等。 

　　多媒体数据：计算机的图形界面、广播电视电影、数码相机 (DC)和数码摄像机 (DV)，使得我们身处于丰富多彩的多媒体时代。多媒体数据的采集、保存和播放已经非常方便；图像、音频、视频等各种媒体数据在我们的日常生活中随处可见。 

　　通信信号：电信号和电磁波已经成为人类社会信息最方便快捷的传输方式，这些用于通信和控制的电话信号、导航信号、手机信号、广播信号，无论是在发送端还是在接收端都是数据。 

　　传感器采集的数据：通过各种各样的温度传感器、压力传感器，以及 CT、B超、声呐等，人们可以采集到各种各样能够描述客观事物的数据。 

　　社会性数据：人类社会生活的方方面面同样需要大量数据来描述，如社会普查数据、人口统计数据和民意调查数据等，著名的如美国总统大选期间盖洛普所做的候选人支持率的民意测验；也包括紧密联系我们日常生活的经济运行数据，如物价、收入等。随着社交网络的发展和普及，人们之间通过互联网和移动互联网的交互行为也成为重要的海量数据来源。 

　　可以很清楚地看到对数据的掌握和处理是当今社会的一个基本问题，在科研活动、经济活动、文化活动和政治活动中，我们随时都会面对各种各样的数据。数据和对数据的处理与我们每个人都息息相关。 

　　我们在这里讨论的数据，进一步被特指为能够输入到计算机并被计算机处理的。 

　　1.1.2大数据时代 

　　数据处理技术包括了数据的获取、数据的存储、数据的传输，以及针对数据的计算等。 

　　数据是客观事物的表示和描述，人具有很强的获取数据的能力，如人对客观事物的观察，社会普查等；数据获取也可以通过多种多样的设备，如温度和压力等各种传感器，万用表和光谱仪等各种测量仪器，照相机和摄像机等图像视频采集设备，麦克风和录音机等声音采集设备，雷达接收机和卫星接收机等信号接收设备等。 

　　传统的数据存储主要依靠纸质媒介，如书籍、报表和纸质文件等，典型的模拟存储介质有胶片和磁带。随着数字技术的发展，数字存储介质已经成为主流。从大型的磁盘存储系统，到容量越来越大的计算机硬盘，再到便携的移动硬盘、 U盘、光盘和闪存卡，存储容量不断增大，而且价格越来越便宜。 

　　语言交流和书信曾是人类历史上数据传输和信息交互的主要手段。电磁波和电信号的发现和利用，造就了电话、电报等快捷的数据传输方式。互联网、移动通信，以及 USB和 IEEE 1394等高速率数据传输技术的发展，使数据传输的快速、高效和方便达到了前所未有的程度。 

　　面向数据的计算涵盖了对数据的分析、管理和利用。其中既包括了以处理器性能为代表的计算能力，又包括了对数据进行处理以实现信息抽取和知识发现的技术方法。 

　　随着信息技术的飞速发展，人类在数据采集、数据存储和数据传输方面的能力得到了长足的发展。我们都知道，二进制是数字计算机的基础，计算机存储容量的基本单位是字节 (Byte)，每个字节包含 8个二进制位。为了描述不同规模的数据，人们定义了一系列的数据计量单位： 

　　Bytes → Kilobyte(210 Bytes) → Megabyte(220 Bytes) → Gigabyte(230 Bytes) → Terabyte(240 Bytes) →Petabyte(250 Bytes)→Exabyte(260 Bytes)→Zettabyte(270 Bytes)→ Yottabyte(280 Bytes) 

　　其中我们比较熟悉的有千字节 (KB)、兆字节 (MB)和吉字节 (GB)。我们甚至难以想象更大的数据量单位意味着什么？美国国会图书馆所有藏书的数据约为 10TB。按照 2001年的数据估算，美国国家航空航天局地球观测系统 (Earth Observing System)三年的数据总和约为 1PB[1]。据称 1个 ZB大概相当于全世界所有海滩上的沙子总和，而 1个 YB大概相当于 7000人体内的原子数总和 [2]。如果以每分钟 1MB的速度不间断播放 MP3格式的歌曲，1ZB存储的歌曲可以让人听上 19亿年。 

　　根据 IDC的统计和预测， 2007年全球数据量约为 161EB；2008年激增到 487EB；金融危机的 2009年，全球数据量达到 0.8ZB，增长 62％； 2010年进一步增长到 1.2ZB，约为 2007年的 8倍；而到 2020年，这一数字将达到 35ZB。人类所拥有的数据量还在以更快的速度增长， 2010年 3月，视频网站 YouTube宣布每分钟就会有 24小时的视频被上传，而到了 2010年 11月，每分钟上传至 YouTube的视频长度已达 35小时。根据 YouTube产品管理负责人的计算：“如果美国三大电视网每天播放 24小时，一周 7天，一年 365天不间断播放 60年，那么这些视频内容才与 YouTube每 30天增加的内容一样多。 ”而到了 2012年 5月，每分钟上传的视频长度已经超过 72小时，YouTube上已经有超过一万亿个视频。 

　　2012年初，Royal Pingdom网站给出 2011年与互联网相关的一些统计数据： 

　　.全世界有 31.46亿个电子邮件账户； 

　　.全世界有 5.55亿个网站，其中有 3亿个是在 2011年创建的； 

　　.全世界有 21亿互联网用户； 

　　. 3.5亿用户使用移动设备登录互联网； 

　　.全世界有超过 24亿个社交媒体账户； 

　　.全球有 26亿个即时通信账户； 

　　.截至 2011年 10月，互联网用户每月在线浏览视频量达到 2014亿个； 

　　.截至 2011年中期，Facebook上有 1000亿张照片； 

　　. Flickr上有 5100万注册用户，这些用户每天上传 450万张照片。 Flickr上一共有 60亿张照片。 

　　很显然，人类获取和生产数据的能力已经十分惊人，当今的时代已经是一个“数据爆炸”的时代。为了应对数据爆炸性的增长，最近二十年以来，人类在数据存储能力上的进步极为迅速。二十年前，我们使用的个人计算机往往只有 40MB的硬盘，数据交换依靠 720KB的 5英寸软盘和 1.44MB的 3.5英寸软盘。对于今天的个人计算机而言， 500GB硬盘几乎成了标准配置，用于数据交换的移动存储设备多为 250GB以上移动硬盘和 2GB以上的 U盘。个人数据存储产品的容量在二十年间增大了成千上万倍。在二十年间，数据中心更是从萌芽走向成熟，当今的数据中心的存储规模往往能达到 PB量级，并且在能效、安全、接入和管理等方面有了越来越完善的考虑和设计。 

　　数据传输技术的发展同样迅猛。一方面是依赖于移动存储介质的数据交换，除了存储量的增大以外，传输速率也飞速增长。传统的 1.44MB软盘的传输速率为 62.5KB/s，计算机串口的传输速率为 14.4KB/s。CD光盘的读取速度为 7.5MB/s，DVD光盘的读取速度为 16.6MB/s。现在得到广泛应用的 USB 2.0理论传输速率为 60MB/s，实际传输速率能达到 20～30MB/s；2008年底发布的 USB 3.0标准理论传输速率已经达到了 600MB/s。因此基于移动存储介质的传输速率在十多年间也得到数百倍乃至数千倍的提升。互联网的发展使得数据传输不再受到地理位置的约束。早期的 Modem拨号上网的速率为 7KB/s；现在 ADSL上网的下行速率可以达到 1MB/s，目前家庭常用的速率为 512KB/s～2MB/s。而局域网的传输速率可以达到 10MB/s甚至 100MB/s。而基于无线传输的移动互联网也可以提供 50～150KB/s的下行速率。随着互联网，特别是移动互联网的发展，人们将继续向随时随地快速传输数据的目标前进。 

　　数据的计算需要强大的处理能力，其中处理器和随机存储器起着至关重要的作用。二十年前的个人计算机，Intel 80386的典型配置是 33MHz主频和 1MB内存；而今天的 Intel Core2的典型配置是主频 3GHz、64KB的一级缓存 (L1 cache)和 6MB的二级缓存 (L2 cache)；而 Intel Core-i系列进一步引入了三级缓存，并实现了 CPU与图形处理单元 GPU的整合封装。因此今天的处理器，其计算能力已经不可同日而语。然而单处理器计算能力的提高仍然远远不能满足数据处理的需要，因此各种并行计算技术风起云涌，从多核处理器、图形加速器 GPU，并行程序设计技术如 OpenMP、MPI，到分布式计算、网格计算和今天声名显赫的云计算，给数据计算提供了前所未有的强大能力。 

　　然而数据的计算除了计算能力之外，同样甚至更为重要的是计算方法，因此近年来以机器学习、数据挖掘为代表的海量数据处理技术都得到了普遍的重视和迅速的发展。 

　　……