数据结构引言.ppt

《数据结构引言.ppt》由会员分享，可在线阅读，更多相关《数据结构引言.ppt（61页珍藏版）》请在优知文库上搜索。

1、数据结构-引言4成绩组成成绩组成 大作业大作业 期末考试期末考试 出勤、课堂表现出勤、课堂表现5第一章第一章 引言引言 什么是数据结构什么是数据结构 算法分析算法分析 面向对象的数据结构面向对象的数据结构6什么是数据结构什么是数据结构 没有标准的定义，但有共识没有标准的定义，但有共识 数据结构：通过抽象的方法研究一组有数据结构：通过抽象的方法研究一组有特定特定关系关系的数据的存储与处理的数据的存储与处理 数据结构的研究内容：数据结构的研究内容：数据之间的逻辑关系，以及这种关系对应的操作数据之间的逻辑关系，以及这种关系对应的操作如何存储某种逻辑关系（存储实现）如何存储某种逻辑关系（存储实现）在这

2、种存储模式下，关系的操作是如何实现的在这种存储模式下，关系的操作是如何实现的（运算实现）（运算实现）7数据的逻辑结构数据的逻辑结构 集合结构集合结构：元素间的次序是任意的。元素：元素间的次序是任意的。元素之间除了之间除了“属于同一集合属于同一集合”的联系外没有的联系外没有其他的关系。其他的关系。 线性结构线性结构：数据元素的有序序列。除了第：数据元素的有序序列。除了第一个和最后一个元素外，其余元素都有一一个和最后一个元素外，其余元素都有一个前趋和一个后继个前趋和一个后继 树形结构树形结构：除了根元素外，每个节点有且：除了根元素外，每个节点有且仅有一个前趋，后继数目不限仅有一个前趋，后继数目不限

3、 图型结构图型结构：每个元素的前趋和后继数目都：每个元素的前趋和后继数目都不限不限8集合结构集合结构线性结构线性结构树形结构树形结构图形结构图形结构9数据结构的操作数据结构的操作 创建：创建一个数据结构创建：创建一个数据结构 清除：删除数据结构清除：删除数据结构 插入：在数据结构指定的位置上插入一个新元素插入：在数据结构指定的位置上插入一个新元素 删除：将数据结构中的某个元素删去删除：将数据结构中的某个元素删去 搜索：在数据结构中搜索满足特定条件的元素搜索：在数据结构中搜索满足特定条件的元素 更新：修改数据结构中的某个元素的值更新：修改数据结构中的某个元素的值 访问：访问数据结构中的某个元素访

4、问：访问数据结构中的某个元素 遍历：按照某种次序访问数据结构中的每一元素，使每个遍历：按照某种次序访问数据结构中的每一元素，使每个元素恰好被访问一次元素恰好被访问一次每一种数据结构的特定操作每一种数据结构的特定操作10数据结构的存储实现数据结构的存储实现 包括两个部分：包括两个部分：数据元素的存储数据元素的存储数据元素之间的关系的存储数据元素之间的关系的存储 物理结构由三个部分组成：物理结构由三个部分组成：存储结点，每个存储结点存放一个数据元素；存储结点，每个存储结点存放一个数据元素；数据元素之间的关系的存储，也就是逻辑结构数据元素之间的关系的存储，也就是逻辑结构的机内表示；的机内表示；附加信

5、息，便于运算实现而设置的一些附加信息，便于运算实现而设置的一些“哑结哑结点点”，如链表中的头结点。，如链表中的头结点。 11基本的存储方式基本的存储方式 数据元素的类型可以是各种各样的，通常数据元素的类型可以是各种各样的，通常不会是简单的内置类型，因此存储结点可不会是简单的内置类型，因此存储结点可以是一个结构体类型的变量或对象以是一个结构体类型的变量或对象 数据结构主要讨论关系的存储。因此，数数据结构主要讨论关系的存储。因此，数据结构主要采用据结构主要采用的思想的思想12关系的存储关系的存储顺序存储：用存储的位置表示元素之间的关系。顺序存储：用存储的位置表示元素之间的关系。主要用数组实现。主要

6、用数组实现。链接存储：用指针显式地指出元素之间的关系，链接存储：用指针显式地指出元素之间的关系，如单链表就是表示线性关系的。如单链表就是表示线性关系的。哈希存储方式：是专用于集合结构的数据存放方哈希存储方式：是专用于集合结构的数据存放方式。在哈希存储中，各个结点均匀地分布在一块式。在哈希存储中，各个结点均匀地分布在一块连续的存储区域中，用一个哈希函数将数据元素连续的存储区域中，用一个哈希函数将数据元素和存储位置关联起来。和存储位置关联起来。索引存储方式：所有的存储结点按照生成的次序索引存储方式：所有的存储结点按照生成的次序连续存放。另外设置一个索引区域表示结点之间连续存放。另外设置一个索引区域

7、表示结点之间的关系。的关系。 13第一章第一章 引言引言 什么是数据结构什么是数据结构 算法分析算法分析 面向对象的数据结构面向对象的数据结构14算法分析算法分析 数据结构是讨论一组数据的处理问题数据结构是讨论一组数据的处理问题 每一种存储方式下对应的每一种操作的每一种存储方式下对应的每一种操作的实现都是一个算法实现都是一个算法 每种操作有多种实现方式每种操作有多种实现方式 如何评价这些算法的好坏如何评价这些算法的好坏15算法的质量评价算法的质量评价正确性：算法应能正确地实现预定的功能；正确性：算法应能正确地实现预定的功能；易读性：算法应易于阅读和理解，以便于调试、易读性：算法应易于阅读和理解

8、，以便于调试、修改和扩充；修改和扩充；健壮性：当环境发生变化（如遇到非法输入）时，健壮性：当环境发生变化（如遇到非法输入）时，算法能适当地做出反应或进行处理，不会产生不算法能适当地做出反应或进行处理，不会产生不正确的运算结果；正确的运算结果；高效率：具有较高的时间和空间性能。高效率：具有较高的时间和空间性能。这四个指标往往是互相冲突的，数据结构主要考这四个指标往往是互相冲突的，数据结构主要考虑的是时空性能。虑的是时空性能。16算法效率分析算法效率分析 如何确定一个算法是高效的算法就是分析如何确定一个算法是高效的算法就是分析该算法所需要的资源。算法的资源包括：该算法所需要的资源。算法的资源包括：

9、时间：程序运行所需要的时间。要运行一年时间：程序运行所需要的时间。要运行一年的算法是很难让人接受的的算法是很难让人接受的空间：程序运行所需要的空间。需要几个空间：程序运行所需要的空间。需要几个G G的的内存的算法同样也令人难以接受。内存的算法同样也令人难以接受。17算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 18程序的运行时间程序的运行时间 影响运行时间的因素影响运行时间的因素问题规模和输入数据的分布问题规模和输入数据的分布编译器生成的目标代码的质量编

10、译器生成的目标代码的质量计算机系统的性能计算机系统的性能程序采用的算法的优劣程序采用的算法的优劣 关键是算法的优劣关键是算法的优劣19有效算法的重要性有效算法的重要性计算机不是万能的，并非所有的算法，计算机都能够计算计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一定有实际意义。如果一台计出有用的结果。差的算法不一定有实际意义。如果一台计算机算机 1 秒能处理秒能处理1000条指令，那么如果处理条指令，那么如果处理n个数据所需个数据所需执行的指令数如表中的函数所示执行的指令数如表中的函数所示时间函数时间函数n=20n=50n=100n=500n.02s.05s.1s.

11、5snlogn.09s.3s.6s4.5sn2.4s2.5s10s250sn38s2分分17分分35小时小时2n34分分20有效时间中能够处理的数据量有效时间中能够处理的数据量时间函数时间函数在在 1 秒内秒内 在在 1 分钟内分钟内 在在 1 小时小时n10006 * 1043.6 * 106nlogn14048932 * 105n2312441897n310391532n10152121有效算法的重要性有效算法的重要性关键：提高算法的效率而不是提高机器的速度！关键：提高算法的效率而不是提高机器的速度！时间函数时间函数提速提速10倍前的求倍前的求解规模解规模提速提速10倍后的倍后的求解规模求

12、解规模ns110s1nlogns210s2n2s33.16s3n3s42.15s42ns5s5 + 3.322时间复杂度时间复杂度 算法的时间复杂度是一种抽象的度量，即运算算法的时间复杂度是一种抽象的度量，即运算量与问题规模之间的关系。量与问题规模之间的关系。 算法的时间复杂度也与被处理的数据分布有关算法的时间复杂度也与被处理的数据分布有关 算法的时间复杂度算法的时间复杂度最好情况的时间复杂度最好情况的时间复杂度最坏情况的时间复杂度最坏情况的时间复杂度平均情况的时间复杂度平均情况的时间复杂度 23算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表

13、示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 24算法运算量的计算算法运算量的计算根据问题的特点合理地选择一种或几种根据问题的特点合理地选择一种或几种操作作为操作作为“标准操作标准操作”，将标准操作作，将标准操作作为一个抽象的运算单位；为一个抽象的运算单位；确定每个算法在给定的输入下共执行了确定每个算法在给定的输入下共执行了多少次标准操作；并将它作为算法的计多少次标准操作；并将它作为算法的计算量。算量。25实例实例 如果有一组正整数，存放在数组如果有一组正整数，存放在数组arrayarray中，中，要求设计一个算法求数组中的最大值与要求设计一个算法求

14、数组中的最大值与d d的乘积。的乘积。 26算法一算法一int max1(int array, int size, int d)int max=0, i; for (i=0; i size ; +i) arrayi *= d; for (i=0; i max) max = arrayi; return max;算法二算法二int max2(int array, int size, int d)int max=0, i; for (i=0; i max) max = arrayi; return max * d;27运算量的计算运算量的计算 用用乘法乘法、赋值赋值和和条件判断条件判断作为标准操作

15、作为标准操作 设输入的数组值为设输入的数组值为1,2,3,d=41,2,3,d=4 Max1Max1：3 3次乘法，次乘法，1414次赋值，次赋值，1111次比较，次比较，共共2828次标准操作次标准操作 max2max2执行了执行了1 1次乘法，次乘法，7 7次赋值，次赋值，7 7次比较，次比较，共共1515次标准操作。次标准操作。 28找出运算量的函数找出运算量的函数 如找出如找出max1max1的最坏情况下的运行时间函数的最坏情况下的运行时间函数 第一个第一个forfor循环：循环：循环控制行中，表达式循环控制行中，表达式1 1执行一次，表达式执行一次，表达式2 2执行执行n+1n+1次

16、，次，表达式表达式3 3执行了执行了n n次。次。每个循环周期执行一次乘法、一次赋值。每个循环周期执行一次乘法、一次赋值。总的运算量为总的运算量为1+(n+1)+n+n1+(n+1)+n+n* *2 = 4n+22 = 4n+2。 第二个循环：第二个循环：循环控制行中，表达式循环控制行中，表达式1 1执行了一次，表达式执行了一次，表达式2 2执行了执行了n+1n+1次，表达式次，表达式3 3执行了执行了n n次，次，每个循环周期执行一次比较，一次赋值。每个循环周期执行一次比较，一次赋值。总运算量为总运算量为1+(n+1)+n+n1+(n+1)+n+n* *2 = 4n+22 = 4n+2。 max1max1在最坏情况下的总运算量是在最坏情况下的总运算量是8n+48n+4。 29算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化时间复杂度的概念时间复杂度的概念 30渐进表示法渐进表示法 算法的运行时间函数可能是一个很复杂算法的运行时间函数可能是一个很复杂的函数，如何比较这些函数并从中选