数据结构ppt1绪论

1、数据结构胡 少 军联系方式Email: 办公室：信息工程学院办公楼213室电 话：(o)助教赵耀博(硕士生) Email：1. 课程要求先修课程C语言程序设计成绩平时成绩30%：考勤+OJ系统成绩考试成绩70%：闭卷笔试!编辑编译环境推荐使用Code:Blocks下的GCC2. 为何学习数据结构？前人智慧的结晶，有助于提高分析解决复杂问题的能力后续课程的准备考研、找工作3. 国内外数据结构课程教学美国计算机科学排名前十位大学CMUJavaMITPythonStanford UniversityC+University of California at BerkeleyJavaCornell U

2、niversityJavaUniversity of Illinois: Urbana ChampaignC+University of WashingtonJavaPrinceton UniversityJavaUniversity of Texas-AustinJavaGeorgia Institute of TechnologyJava国外课程名：数据结构与算法（分析）、 算法设计与分析、 算法导论等。3. 国内外数据结构课程教学美国计算机科学排名前十位大学选用教材3. 国内外数据结构课程教学美国计算机科学排名前十位大学选用教材Data Structures and Algorithm

3、Analysis in C+, Mark A. Weiss, 2006.Data Structures and Algorithm Analysis in Java, Mark A. Weiss, 2007.3. 国内外数据结构课程教学美国计算机科学排名前十位大学选用教材Algorithms in Java. Robert Sedgewick, 2003.Algorithms in C+. Robert Sedgewick, 1998.3. 国内外数据结构课程教学美国计算机科学排名前十位大学选用教材Data Structures and Algorithms. Alfred V. Aho et

4、.al, 1983.Introduction to Algorithms. Thomas H. Cormen et.al, 2001.3. 国内外数据结构课程教学国内大学数据结构教学清华大学C+（殷人昆）精品课程链接：北大： 西工大： 哈工大： 福州大学： 北京大学C+(张铭 )浙江大学C4. 本课程选用教材数据结构，严蔚敏，清华大学出版社.考研权威参考书5. 本课程主要参考书籍Data structures is the goal!Language is the tool!6. 编程语言: C优势简洁宜用(small & clean)先修课程缺点无面向对象机制，不能实现抽象数据类型(ADT)

5、无自动垃圾回收机制（Automatic garbage collection）语言是工具，数据结构与算法设计的思想最重要！7. 怎样学好数据结构？主动学习，多读多练参考国内外经典教材、精品课程及网络资源，理解经典数据结构和算法的设计思想在经典算法基础上修改调试，加强上机实习后期自学数据结构的Java或C+描述（本课程将适当介绍数据结构的C+描述）8. 本课程的学习目标掌握数据结构与算法涵盖的基本内容以最新考研大纲为参考了解算法的基本思想简单的数据结构与经典算法要求记忆 - 考试？复杂的数据结构与算法 - 了解算法思想！后面研究或工作中若用到，根据实际情况自学。第一章绪论第二章线形表第三章栈和队

6、列第四章并查集第五章串、数组第六章树和二叉树第七章图第八章查找第九章排序目录不包含：广义表与内存管理字符树与后缀树组伸展树倒排索引搜索引擎技术摊还分析等计算机理论研究三大期刊（一）Communication of the ACM计算机理论研究的Nature/Science，高水平、前瞻性及通俗化的学术论文与综述计算机理论研究三大期刊（二）Journal of the ACM算法、图论、复杂度、组合数学等计算机理论研究三大期刊（三）SIAM Journal on ComputingCoverage of the most significant work going on in the math

7、ematical and formal aspects of computer science and non-numerical computing.计算机理论研究的最好期刊与“数据结构”相关图灵奖获得者与“数据结构”相关其他著名人物About me?擅长树的数据结构及算法（计算机图形学）第一章绪论数据结构讨论范畴基本概念和术语数据类型和抽象数据类型算法和算法分析算法设计的要求算法效率的度量算法存储空间的度量1.1 数据结构讨论范畴算法+数据结构=程序设计Niklaus Wirth,designer of PascalWirth, Niklaus (1976) (in English). A

8、lgorithms + Data Structures = Program. Prentice Hall. 0130224189. ISBN 87程序设计：为计算机解题编制的一组指令集算法：处理问题的策略数据结构：处理信息的表示Turing Award, 19841.1 数据结构讨论范畴应用举例数据库中表的设计与管理：线性表登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件1.1 数据结构讨论范畴应用举例数据库中表的设计与管理：线性表按书名按作者名按分类号书目文件1.1 数据结构讨论范畴应用举例根据输入关键字Google搜索引擎快速搜索到相关记录：搜索地图中寻找两个城市之

9、间的最短路径：图北京济南石家庄太原西安郑州武汉1.1 数据结构讨论范畴应用举例计算机图形学快速光线跟踪技术：八叉树AABB树1.1 数据结构讨论范畴应用举例操作系统中的资源管理器：树型结构操作系统如何快速寻找内存或磁盘中的空余空间？1.1 数据结构讨论范畴应用举例编译器中对标识符的快速查找：哈希表数据库中快速存取和查找记录或键值：B树VLSI的配线法：图1.1 数据结构讨论范畴应用举例编译器中表达式计算：堆栈、树人机对弈：堆栈、树First computer program to defeat world champion in 1997.卡斯巴罗夫(Kasparov) vs. 深蓝 1.1

10、数据结构讨论范畴数学模型数值计算非线性方程和线性方程组的求解偏微分方程的求解数值微积分，插值与逼近等非数值计算线性表哈希表树图等1.1 数据结构讨论范畴结论数据结构是一门“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。非数值计算线性表哈希表树图等1.2 基本概念和术语数据（data）所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。 1.2 基本概念和术语数据元素(data element)元素、结点(node)数据结构中讨论的“基本单位”，在计算机中通常作为一个整体进行考虑和处理。（图的结点、表中的记录等）数据项(data item

11、)构成数据元素的最小单位。（城市名、位置、人口等）北京济南石家庄太原西安郑州武汉（序号、书名、作者名、分类号等）关键字(key)能识别一个或多个数据元素的数据项。若能唯一识别作用，则称之为“主” 关键字，否则称之为“次”关键字。数据对象(data object)具有相同特性的数据元素的集合，如：整数、实数、书目信息等。1.2 基本概念和术语（序号、书名、作者名、分类号等）数据结构相互之间存在一种或多种特定关系的数据元素的集合。集合、线性结构、树形结构、图（网）状结构其它定义The way of organizing information so that we can find, update

12、, add, and delete portions of it efficiently 数据的效率化组织方式1.2 基本概念和术语形式定义数据结构是一个二元组：Data_Structures = ( D, S ) D是数据元素的有限集，S是D上关系的有限集。例如：复数的数据结构：Complex = (C, R)C = c1, c2 实数集合；R = 表示关系：c1是实部，c2是虚部1.2 基本概念和术语数据结构的两个方面： 数据逻辑结构：数据之间的相互关系称为逻辑结构，可以用一个数据元素的集合和定义在此集合上的若干关系表示。（线性与非线性）数据物理结构：数据逻辑结构在计算机中的表示（映象），

13、又称“存储结构”。 顺序存储链式存储1.2 基本概念和术语存储地址存储内容Si = L0 +(i-1)*mL0L0+mL0+(i-1)*mL0+(n-1)*m001,高等数学,樊映川002,理论力学,罗远详003,高等数学,华罗庚004,线性代数,栾汝书顺序存储： 存储地址存储内容L0L0+mL0+(i-1)*mL0+(n-1)*m001,高等数学,樊映川002,理论力学,罗远详003,高等数学,华罗庚004,线性代数,栾汝书链式存储： L0+(n-2)*mL0+(i-1)*m0 L0+m+1L0+m+1L0+(n-2)*m1.3 数据类型和抽象数据类型 数据类型(data type)是一个值

14、的集合和定义在此集合上的一组操作的总称。 原子类型: int, float结构类型(固定聚合和可变聚合): struct抽象数据类型（Abstract Data Type, 简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型的形式描述：ADT = ( D，S，P )其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集。定义：ADT 抽象数据类型名 数据对象： 数据对象的定义 数据关系： 数据关系的定义 基本操作： 基本操作的定义 ADT 抽象数据类型名1.3 数据类型和抽象数据类型 例1：“复数”的ADT定义ADT Complex 数据对象：D =

15、c1,c2 | c1,c2 实数集 数据关系：R1 = | c1是实部，c2是虚部 基本操作：Init(&Z, v1, v2 )/构造复数Z Destroy(&Z) /销毁复数Z GetReal(Z, &realPart) /返回复数Z的实部值GetImag(Z, &ImagPart) /返回复数Z的虚部值Add(Z1, Z2, &sum) /返回两个复数的和值 ADT Complex例2：“简单城市地图” 的ADT定义ADT CityMap 数据对象：D=ai | aiCityInfo, i = 1,2, , n 数据关系： R= | v,wD, 表示从v到w的弧基本操作： Init(&m,

16、 D, VR) /构造一个图, D是顶点, VR是弧LocateCity(&m, u) /城市查找, u是待查找的城市名RenameCity(&m, u1, u2) /修改城市名RemoveCity(&m, u) /删除城市名InsertCity(&m, u) /插入城市名FindShortestPath(&m, u1, u2) /寻求最短路径ADT CityMap北京济南石家庄太原西安郑州武汉多形数据类型： 如结点CityInfo(城市信息)C+中的templateADT的特征：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它

17、的方法）。数据封装：将实体的外部特性和其内部实现细节分离，对外部用户隐藏其内部实现细节。1.3 数据类型和抽象数据类型 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构：线性表、栈、队列非线性结构顺序存储链式存储 树形结构图形结构小结按某种逻辑关系组织起来的一批数据，按一定的映象方式存放于存贮器中，并在这些数据上定义了一个运算（操作）的集合。1.4 算法和算法分析算法(Algorithm)算法是对特定问题求解步骤的一种描述，是指令的有限序列，每一条指令表示一个或多个操作。为何进行算法分析？1.4.1 算法设计要求算法的五个特点：输入 (Input)：零个或多

18、个输入。输出 (Output)：一个或多个输出。有穷性 (Finiteness)：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。可行性 (Effectiveness)：所有操作都可通过已经实现的基本操作运算有限次来实现。确定性 (Definiteness)：算法中每一步的描述都无二义性，只要输入相同，初始状态相同，无论执行多少遍，结果都应该相同。Turing Award, 1974“好” 算法的特点：正确性 (Correctness)：满足问题的需求。无语法错误对几组测试数据能正确输出结果对苛刻的数据依然能得到正确结果对一切合法输入都能输出正确结果可读性(Readability)：便

19、于理解、测试和修改。健壮性(Robustness)：输入非法数据时，算法能做出适当处理，不会产生难以预料的结果。时空效率 (Efficiency)：执行时间短，低存储。1.4.1 算法设计要求算法执行时间：依据算法编制的程序在计算机上执行所消耗的时间。事后统计：计时函数必须先运行程序依赖于软硬件等因素，掩盖算法本质事前分析估算：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度1.4.2 算法效率的度量依赖于语言、编译器和机器一个特定算法的“运行工作量”只依赖于问题的规模，是问题规模的函数。以算法中选取的原操作重复执行的次数（语句频度）作为算法的时间度量。原操作：

20、固有数据类型的操作控制结构：顺序、分支和循环1.4.2 算法效率的度量for(i=1;i=n;i+) for(j=1;j=i;j+) +x; 1.4.2 算法效率的度量原操作 ：自加运算原操作执行次数：T(n) = n(n+1)/2渐进时间复杂度(asymptotic time complexity) 描述算法的执行时间随问题规模的增长而增长的趋势。随着问题规模n的增长，若算法执行时间T(n)的增长率和f(n)的增长率相同，则记作T(n)=O(f(n)。1.4.2 算法效率的度量渐进时间复杂度(asymptotic time complexity) 定义：如果存在两个正常数c和n0，对于所有的

21、nn0，有T(n) cf(n) 则记作 T(n) = O(f(n)。for(i=1;i=n;i+) for(j=1;j=i;j+) +x;T(n) = O(n2)如何证明？1.4.2 算法效率的度量1.4.2 算法效率的度量时间复杂度分析例子H(n) = 2n-1M(n) = nlog2n n + 1000nH(n)M(n)2310008255101632429496729511281.4.2 算法效率的度量时间复杂度分析例子斐波拉契数列(Fibonacci)求解的时间复杂度0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 非递归求解时间复杂度: O(

22、n)int F(int n) int f0 = 0, f1 = 1, f2; if (n=0 | n=1) return n; else for (int i=2; i=n; i+) f2 = f0+f1; f0=f1; f1=f2; return f1; 1.4.2 算法效率的度量时间复杂度分析例子斐波拉契数列(Fibonacci)求解的时间复杂度0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 递归求解int F(int n) if(n=0 | n=1) return n; else return F(n-1)+F(n-2); 时间复杂度:1.4.2 算法效率的度量常用时间复杂度表示:O(1) 常数型O(n)线性型O(n2)平方型 O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)线性对数阶O(1) O(logan) O(n) O(nlogan) O(n2) O(2n) O(n!)1.4.2 算法效率的度量时间频度随输入数据集变化而变化最好情况下的复杂度最坏情况下的复杂度平均时间复杂度for(i=1;i O(n)nlog2n 100n (n2100)其它度量方法：空间复杂度：s(n) = O(f(n)表示随问题规模n的增大，算法