数据结构-绪论课件_第1页
数据结构-绪论课件_第2页
数据结构-绪论课件_第3页
数据结构-绪论课件_第4页
数据结构-绪论课件_第5页
已阅读5页,还剩21页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、Name: 李娟Mobile:mail: lijuanlijuanDepartment: 计通学院-计算机应用技术系Who am I?1第1章 绪论1.1 什么是数据结构1.2 基本概念和术语1.3 算法和算法分析2Hanoi塔问题设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;规则3:在满足移动规则1和2的前

2、提下,可将圆盘移至a,b,c中任一塔座上。1.1 什么是数据结构3学号姓名年龄专业1001张红19英语1002王卫18化工1003安然17数学1800李梅21储运一行为一个数据元素 也称为记录数据元素之间存在一种简单的线性关系为线性数据结构。操作举例:插入学生、删除学生、查找学生等。除首行外每条记录有一个前驱,除末尾外每条记录有一个后继。线性结构例1 学生名单4例2 族谱一个数据元素也称为节点。数据元素之间存在一种非线性关系,除首节点外每个节点只有一个前驱,除叶节点外每个节点有若干个后继 树型结构。操作举例:查找爷爷有几个孙子树型结构爷爷父亲伯伯叔叔哥哥弟弟你 5数据(data):是对客观事物

3、的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(data element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 如N=1,2,3,4,5中整数1至5均为数据元素。数据元素不一定是单个的数字或字符,也可能是若干个数据项的组合,如学生信息。 学生(学号,姓名,性别,成绩)数据元素有时也称结点或记录。注意:数据元素是基本单位,数据项是最小单位。1.2 基本概念和术语7数据对象(data object):是具有相同性质的数据元素的集合。如大写字母字符的数据对象是集合:C= A,B,.,Z 。数据结构(data structure

4、):是相互之间存在一种或多种特定关系的数据元素的集合。 用集合论方法定义数据结构为:S =(D,R) D是数据元素的有限集,R是数据元素之间关系的有限集。 逻辑结构(数据结构)与物理结构(存储结构):数据的逻辑结构是数据间关系的描述,它只抽象地反映数据之间的逻辑关系。数据的物理结构指的是其逻辑结构在计算机存储器里的实现,它反映数据在计算机内部的存储方式。 1.2 基本概念和术语8物理结构顺序存储结构:所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内存仍然相邻。链式存储结构:所有元素存放在可以不连续的存贮单元中,但元素之间的关系可以通过地址(指针)确定。1.2 基本概念和术语1

5、06.数据类型(data type) 是一个值的集合和定义在这个集合上的一组操作的总称。 基本数据类型 比如C的 int a; 其上的操作有+ - * /, 若有a/3,则其值为整数。结构类型 比如数组。1.2 基本概念和术语117.抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。如C语言中的结构体。typedef struct int num; char name20; char sex; float score; student1.2 基本概念和术语12在我们这门课中,所采用的描述语言基本类似于C语言的形式,有时也用自然语言。注释部分用/或/*.*/表示。有些地方为方便起见,可

6、能省略变量定义等有关内容。算法描述语言1.3 算法和算法分析14一个可执行的算法不一定是一个好算法,算法的分析是一个复杂的问题,通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。这两个标准分别称为时间复杂度和空间复杂度。一般时间复杂度考虑的较多。度量一个程序的执行时间通常有两种方法: 事后统计和事前分析估算这里我们介绍第二种方法。算法分析1.3 算法和算法分析15 在频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,引入时间复杂度概念。 T(n) O(g(n),其中大写字母为英文Order(即数量级)一词的

7、第一个字母,称g(n)是T(n)的同数量级函数。 例如,若T(n)=n(n+1)/2,则它的时间复杂度为(n2), 即(n)与n2 数量级相同。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,算法的时间量度记作: T(n)=O(g(n)称作算法的渐近时间复杂度,简称时间复杂度。1.3 算法和算法分析17例2:s=0 for (i=0; in; i +) for (j=0; jn; j +) s+=B ij; sum=s算法的频度:T(n)=O(2n2+2n+3)时间复杂度:O(n2)定理:若T(n)=am nm +am-1 nm-1 +a1n+a0是一个m次多项式,则T(n)=

8、O(nm)/* 1次 */* n+1次 */* n(n+1)次 */* n2次 */* 1次 */1.3 算法和算法分析18例3:1 for (i=0; in; i+)2 for (j=0; jn; j+) 3 bij=0;4 for (k=0; kn; k+)5 bij=bij+aik*akj;6 语句频度(第5行)为:F(n)=n3 时间复杂度:T(n)=O(F(n)=O(n3)1.3 算法和算法分析19例4:交换i和j的内容。 Temp=i; i=j; j=temp;时间复杂度:T(n)=O(1)该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(

9、1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。1.3 算法和算法分析20例5: x=0;y=0;(2) for(k=1;k=n;k+)(3) x+;(4) for(i=1;i=n;i+)(5) for(j=1;j=n;j+)(6) y+; 一般情况下,对循环语句只需考虑循环体中语句的执行次数,忽略该语句中步长加1、终值判别、控制转移等成分。因此,以上程序段中频度最大的语句是(6),其频度为f(n)=n2,所以该程序段的时间复杂度为T(n)=O(n2)。 当有若干个循环语句时,算法的时间复杂度是由嵌

10、套层数最多的循环语句中最内层语句的频度f(n)决定的。T(n)=O(n)T(n)=O(n2)21例6: for (j=2; j=n; j+) for (k=2; k=j-1; k+) x=x+1;计算方法:对于外层循环中的j,从2到n循环,计算出j每取一个值时,内层循环执行的次数0、1、2、.、(n-1)-1,然后累加起来,得到一个n的多项式(n-1)(n-2)/2,取出次数最高的项即可。(n-1)(n-2)/2T(n)=O(n2)1.3 算法和算法分析22例8:时间复杂度不仅依赖于问题的规模,还与输入的值有关。 int An; for (i=0;i=0&(Ai!=k) i-; /*( 求频度) */ return i; 语句的频度不仅与n有关,还与A的各元素及K的取值有关:最坏时间复杂度:若A中没有与K相等的元素,则语句的频度f(n)=n;最好时间复杂度:若A的最后一个元素等于K,则语句的频度f(n)是常数0。平均时间复杂度:是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间(1+2+3+n)/n。不特别说明,时间复杂度均是最坏

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论