数据结构地球信息科学与技术系

1、数据结构梁音地球信息科学与技术系地球物理与空间信息学院绪 论一、教材及相应的参考书二、为什么要学习数据结构？三、什么是数据结构？四、什么是算法？五、算法的设计要求六、算法的分析一、教材及参考书教材：严蔚敏、吴伟民编著，数据结构(C语言版)，清华大学出版社。参考书：Donald E. Knuth，The Arts of Computer Programming (Volume I、II、and III) ，Addison Wesley。Donald E. Knuth是当今计算机业界的大牛，图灵奖得主。他所写的这七卷著作是当今算法分析领域最权威的著作。一、教材及参考书Thomas H. Corme

2、n、 Charles E. Leiserson、 Ronald L. Rivest、Clifford Stein，Introduction to Algorithms，The MIT Press。1996年版只有前面的三位作者。2002年版的增加了一位作者(Clifford Stein)。一、教材及参考书Mark Allen Weiss, Data Structure and Algorithm Analysis in C (Second Edition), Addison Wesley。二、为什么要学习数据结构计算机产业的飞速发展，应用领域的迅速扩展。突破传统的数值计算，处理的对象更多的涉及

3、到字符、表格和图像等非数值元素。数据结构是前人在思考问题时想出的解决方法。学习数据结构可以提高程序设计的水平。三、什么是数据结构数据的组织形式。相互之间存在的一种或多种特定关系的数据元素的集合。集合线性结构树状结构网状结构四、什么是算法对特定问题求解步骤的一种描述。指令的有限序列。算法的五个重要特性：有穷性确定性可行性输入输出五、算法的设计要求正确性：算法应当满足具体问题的需求可读性：算法主要是为了人的阅读与交流健壮性：当输入数据非法时，算法应能适当的作出反应或进行处理效率与低存储量需求：效率指的是算法的执行时间；存储量需求指算法执行过程中所需要的最大存储空间六、算法的分析6.1算法效率的度量

4、1)事后统计的方法：利用计算机的内部计时功能，精确统计算法执行的时间到毫秒级。不足：必须先运行依据算法编制的程序统计的结果依赖于计算机的硬软件环境六、算法的分析6.1算法效率的度量2) 事前分析估计的方法：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。这样就避免了与计算机硬软件有关的诸因素对算法执行时间度量上的不准确六、算法的分析语句的频度：指的是该语句重复执行的次数(a) x+; a = 0;(b) for (i=1;i=n;i+) x+; s+=x;(c) for (j=1;j=n;j+) for(k=1;k=n0时，总有|T(n)|

5、 1时，f(x) g(x)六、算法的分析算法的渐进时间复杂度：对于1，n，n2，n3，2n，3n，nn。1 = O(n)，n = O(n2)， n2 = O(n3)，n3 = O(2n)， 2n = O(3n)， 3n = O(nn)。O(1)O(n)O(n2)O(n3)O(2n)O(3n) 1时，f (x) 0.5g(x)，所以， f (x) = ( g(x)。表示f (x) g(x)为下界。如果当x 1时， g(x) f(x) 2g(x)。则，f(x) = (g(x) 表示f(x)的变化可以始终限制在某个以a*g(x)为上界，以b*g(x)为下界的条带内。六、算法的分析六、算法的分析当n比较小时， (logn)并不一定就比 (2n)变化快，这时的常数系数将起到一定作用。但是当n很大时，对于同一个问题而言，时间复杂度为 (logn)的算法其效率要高于时间复杂度为 (2