《数据结构教学课件：第一次课 绪论》由会员分享，可在线阅读，更多相关《数据结构教学课件：第一次课 绪论（16页珍藏版）》请在金锄头文库上搜索。
1、n n什么是数据结构？什么是数据结构？n n数据结构这门课讲些什么？数据结构这门课讲些什么？n n算法定义算法定义n n性能分析与度量性能分析与度量什么是数据结构什么是数据结构定义定义:由由某一数据对象某一数据对象及及该对象中所有数该对象中所有数据成员据成员之间的关系组成。记为：之间的关系组成。记为： Data_Structure = D, R 其中，其中，D是某一数据对象，是某一数据对象，R是该对象是该对象中所有数据成员之间的关系的有限集合。中所有数据成员之间的关系的有限集合。 n个网站之间的连通关系个网站之间的连通关系树形关系树形关系树形关系树形关系网状关系网状关系网状关系网状关系&数据结
2、构的三个方面的含义：数据结构的三个方面的含义：&逻辑结构逻辑结构- 数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。&存储结构（物理结构）存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。&运算（算法）运算（算法）&数据结构的三个方面的含义之：数据结构的三个方面的含义之：&逻辑结构逻辑结构-划分方法一划分方法一 （1）线性结构- 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串 （2）非线性结构- 一个结点
3、可能有多个直接前趋和直接后继。 例如：树、图、广义表等。&数据结构的三个方面的含义之：数据结构的三个方面的含义之：&逻辑结构逻辑结构-划分方法二（细分）划分方法二（细分）一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。&数据结构的三个方面的含义之：数据结构的三个方面的含义之：&存储结构存储结构n存储结构两方面的内容：存储结构两方面的内容： （1）数据元素自身值的表示（数据域） （2）该结点与其它结点关系的域（链域）n
4、四种基本的存储方法：四种基本的存储方法： （1）顺序存储方法（连续存储结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。&数据结构的三个方面的含义数据结构的三个方面的含义之：之：&逻辑结构存储结构小结：逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法定义算法定义n n定义：定义：一
5、个有穷的指令集，这些指令为解一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列决某一特定任务规定了一个运算序列n n特性：特性：uu输入输入 有有0 0个或多个输入个或多个输入uu输出输出 有一个或多个输出有一个或多个输出( (处理结果处理结果) )uu确定性确定性 每步定义都是确切、无歧义每步定义都是确切、无歧义的的uu有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束uu有效性有效性 每一条运算应足够基本每一条运算应足够基本算法的性能标准算法的性能标准n n正确性正确性n n可使用性可使用性n n可读性可读性n n效率效率n n健壮性健壮性算法效率的度量：采用算法效
6、率的度量：采用时间复杂度时间复杂度1）时间频度度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。2）时间复复杂度度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行
7、的次数是问题规模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 (j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度
8、是：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 另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1 它们的频度不同，但时间复杂度相同，都为O(n2)。容易混淆的地方：T(n)=nT(n)=n+10000000T(n)=1000000n谁更复杂？
