数据结构0163260.pptVIP

——林焕祥 D a t a S t r u c t u r e —第一章 绪论— 算法与数据结构 课内课时：34+17 学时 授课教师: 林焕祥 * 课程要求 作业提交方式： 课后第二天晚上10点前发邮件邮件地址：lhxzust@ 163.com邮件附件为.cpp文件邮件标题：班级_学号_姓名_作业题号邮件一定要署名。 书面作业：下一次上课前交 考试方式 ： 闭卷，难度同平时练习； 平时成绩20%,考试卷面成绩80% * 教材：数据结构 （C语言版） 严蔚敏 吴伟民 清华大学出版社 参考书： 1、数据结构（用面向对象方法与C++语言)（第2版）殷人昆著清华大学出版社 2、C++ Primer Plus(第五版) 中文版 Stephen prata 著人民邮电出版社 * 1.1 什么是数据结构 数据结构: 简单来说就是问题的数学模型。 数据结构: 研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算;第一章绪论 * 1.2 基本概念和术语 数据: 所有能被输入到计算机中，且被计算机处理的符号的集合 ； 是计算机操作的对象的总称。 数据元素(Data Element): 数据中的一个“个体”，数据结构中讨论的基本单位 。 数据项：数据结构中讨论的最小单位 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 姓名 俱乐部名称 出生日期 入队日期 职位 业绩 * 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据类型(Data Type ):是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合；包括逻辑结构、存储结构、算法。 * 逻辑结构：数据元素间的关系种类：线性结构、非线性结构 存储结构：逻辑结构在计算机中的表示种类：顺序、链式、索引和散列存储结构 算法： 算法的特性：有穷性、确定性、可行性、输入、输出 * 1.4 算法与算法分析 算法: 是为了解决某类问题而规定的一个有限长的操作序列。 算法的5个特性: 1. 有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，算法中的每个步骤都能在有限时间内完成； 2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径； * 3．可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之； 4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。 5．有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。 * 算法分析 通常有两种衡量算法效率的方法 : 1.事后统计法缺点：必须执行程序; 其它因素掩盖算法本质 。 2.事前分析估算法 时间复杂度：一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。 通常的做法是从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。 一般情况下，算法中原操作重复执行的次数是规模 n的某个函数T(n)。* 许多时候要精确地计算T(n)是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。 定义（大Ο记号）：如果存在两个正常数c和n0，使得对所有的n，n≥n0，有： T(n) ≤ c g(n) 则有： T(n) ＝ Ο(g(n)) 使用大Ο记号表示的算法的时间复杂度，称为算法的渐近时间复杂度（Asymptotic Complexity）。 * 通常用Ο(1)表示常数计算 时间。 常见的渐进时间复杂度有： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n) * for (i=0; in; ++i)n+1 for (j=0; jn; ++j)n(n+1){c[i][j] = 0;n*nfor (k=0; kn; ++k)n*n(n+1)c[i][j] += a[i][k]*b[k][j];n*n*n } ? T(n) = 2*n*n*n + 3n*n + 2n+1 T(n)= O(n*n*n) 实例分析： * 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： void bubble_sort(int a[ ]，int n)//改进的冒泡排序 {for( i=n-1 ,change=TURE; i1 change ; - -