数据结构教学课件：第一次课 绪论

1、什么是数据结构？数据结构这门课讲些什么？算法定义性能分析与度量第一章 绪论什么是数据结构定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为： Data_Structure = D, R 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 n个网站之间的连通关系树形关系网状关系数据结构的三个方面的含义：逻辑结构-数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）-数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算（算法）数据结构的三个方

2、面的含义之：逻辑结构-划分方法一（1）线性结构-有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串（2）非线性结构-一个结点可能有多个直接前趋和直接后继。例如：树、图、广义表等。数据结构的三个方面的含义之：逻辑结构-划分方法二（细分）一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。数据结构的三个方面的含义之：存储结构存储结构两方面的内容：（1）数据元素自身值的表示

3、（数据域）（2）该结点与其它结点关系的域（链域）四种基本的存储方法：（1）顺序存储方法（连续存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。数据结构的三个方面的含义之：逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法定义定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算

4、序列特性：输入 有0个或多个输入输出 有一个或多个输出(处理结果)确定性 每步定义都是确切、无歧义的有穷性 算法应在执行有穷步后结束有效性 每一条运算应足够基本算法的性能标准正确性可使用性可读性效率健壮性算法效率的度量：采用时间复杂度1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。2）时间复杂度

5、 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T( n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。常见的f(n)一般为：常数级；线性级；指数级；对数级。例1: 分析以下程序段的时间复杂度for (i=1;in;i+) y=y+1; for

6、(j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：则该程序段的时间复杂度： 可以定义f(n)=n2lim(T(n)/f(n)=2(常数) T(n)=例2: 分析以下程序段的时间复杂度i=1;while (i=n) i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即 ，取最大值则该程序段的时间复杂度为：/* 2 * /例3：计算时间复杂度Sum1( int n ) int p=1, sum=0, m ;for (m=1; m=n; m+) p*=m ; sum+=p ; return (sum) ; Sum1( int n ) int p=1, sum=0, m ; /1次for (m=1; m=n; m+) /n+1次 p*=m ; /n次sum+=p ; /n次return (sum) ; /1次 最后总的次数为1+（n+1）+n+n+1+1=3n+3 时间复杂度：O(n) 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。例如：算法与n无关：T(n)=3000+200+23+50000 另外，在时间频度不相同时，时间复