数据结构第1章 绪论.ppt_第1页
数据结构第1章 绪论.ppt_第2页
数据结构第1章 绪论.ppt_第3页
数据结构第1章 绪论.ppt_第4页
数据结构第1章 绪论.ppt_第5页
已阅读5页,还剩70页未读 继续免费阅读

下载本文档

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

文档简介

1、第1章 绪论,1.2 算法及其描述,1.1 什么是数据结构,1.3 算法分析,本章小结,1.1.1 数据结构的定义,1.1.2 逻辑结构类型,1.1.3 存储结构类型,1.1.4 数据结构和数据类型,1.1 什么是数据结构,数据:是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。,数据元素:是数据(集合)中的一个“个体”,是数据的基本单位。,1.1.1 数据结构的定义,例如,200402班为一个学生数据,而其中的“张三”是一个数据元素)。,数据结构:是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特

2、定关系的数据元素的集合。 因此,可以把数据结构看成是带结构的数据元素的集合。,数据结构包括如下几个方面: (1)数据元素之间的逻辑关系,即数据的逻辑结构。 (2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。 (3)施加在该数据上的操作,即数据的运算。,例1.1 有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。,表1.1 学生表,该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为: , , 其中尖括号“”表示元素ai和ai+1之间是相邻的,即a

3、i在ai+1之前,ai+1在ai之后。,将每行(一个学生)抽象为一个结点:,模型:n个元素的集合及其内在关系构成了一个数据结构(叫线性表),一个数据结构,这些数据在计算机存储器中的存储方式就是存储结构。通常可以采用C/C+语言中的结构体数组和链表两种方式实现其存储结构。,存放学生表的结构体数组Stud定义为: struct Student int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ ; Student Stud7= 1,“张斌”,“男”,“9901”, , 5,王萍,女,9901

4、 ;,结构体数组Stud各元素在内存中顺序存放,即第i(1i6)个学生对应的元素Studi存放在第i+1个学生对应的元素Studi+1之前,Studi+1正好在Studi之后。,存放学生表的链表的结点类型StudType定义为: typedef struct studnode int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ struct studnode *next; /*存储指向下一个学生的指针*/ StudType; StudType * head;,head,1,张斌,男,99

5、01,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,学生表构成的链表,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,为了更确切地描述一种数据结构,通常采用二元组表示: B=(D,R) 其中,B是一种数据结构,它由数据元素的集合D

6、和D上二元关系的集合R所组成。其中: D=di| 1in, n0 R=rj| 1jm, m0,其中di表示集合D中的第i个结点或数据元素,n为D中结点的个数,特别地,若n=0,则D是一个空集,因而B也就无结构可言。 如:D=d1, d2, d3, d4, d5, d6, d7 rj表示集合R中的第j个二元关系(后面均简称关系),m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合D中的元结点间不存在任何关系,彼此是独立的。 如: R=r1, r2 有2种不同的关系 r1= , , r2= , ,例如,采用二元组表示例1.1的学生表。 学生表中共有7个结点,依次用d1d7表示,则对应的

7、二元组表示为B=(D,R),其中: D=d1, d2, d3, d4, d5, d6, d7 R=r r = , , , , , ,又例如,有如下数据即一个矩阵:,对应的二元组表示为B=(D,R),其中: D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中,r1表示行关系,r2表示列关系 r1=, , r2=, ,一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。 上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,(1)线性结构 所谓线性结构,该结构中的结点之间存在一对一的关系。其特点是

8、开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。,1.1.2 逻辑结构类型,返回,(2)非线性结构 所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。,所谓树形结构,该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点。非线性结构树形结构简称为树。 所谓图形结构,该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此,可能没有开始结点和终端结点,也可能有多个开始结点、多

9、个终端结点。图形结构简称为图。,例 人机对奕问题,将每个棋局都抽象成一个结点:,棋局1,棋局2,棋局3,棋局4,棋局5,棋局6,棋局7,棋局8,棋局9,棋局10,整体:是一个数据结构,叫“树结构” 运算:遍历整棵树,找出“赢”的路线;等,例:田径赛的时间安排问题: 设有六个比赛项目,规定每个选手至多可参加三个项目,有五人报名参加比赛(如下表所示)设计比赛日程表,使得在尽可能短的时间内完成比赛。,A,E,B,F,D,C,1.设代号代表不同的项目 跳高 跳远 标枪 A B C 铅球 100米 200米 D E F,2.用顶点代表比赛项目: 不能同时进行比赛的项目之间连上一条边。,安排四个单位时间进

10、行比赛,A,E,B,F,D,C,(1)顺序存储方法,(2)链式存储方法,(3)索引存储方法,(4)散列存储方法,1.1.3 存储结构类型,返回,(具体细节略),(1)数据类型 在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是值的集合和定义在此集合上的一组操作的总称。,1.1.4 数据结构和数据类型,返回,如C/C+中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为32768到32767的全体整数)和相关的整数运算(如、等)。,C+的各种数据类型介绍略 如:f

11、loat, long, char, 指针类型,数组类型, 结构体类型,共用体类型。,自定义数据类型名称:用typedef typedef 旧数据类型 新数据类型名 如:typedef char ElemType 则:ElemType 就是char 如: typedef struct stud int no; char name10; int score; student ;,定义变量时: 可用 student x , y ;,(2)抽象数据类型 抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的

12、运算,而不考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=带关系的数据元素集合抽象运算,例如,抽象数据类型“复数”的定义: ADT Complex 数据对象: D=e1, e2 | e1,e2均为实数 数据关系: R1= | e1是复数的实数部分,e2 是复 数的虚数部分 ,基本操作: AssignComplex( while (n%20) nn+2; coutn; ,(1)算法是一个死循环,违反了算法的有穷性特征。,(2) void exam2( ) y=0; x=5/y; coutx“ ” y; 算法包含除零错误,违反了算法的可行性特征。,缺少:return sum; 或者:

13、coutsum=“sum;,1.2.2 算法描述,本书中采用C/C+语言描述算法。 说明:C+语言中提供了一种引用运算符“ temp=x; x=y; y=temp; 当用执行语句swap1(a,b)时, a和b的值不会发生了交换。,在C语言中,由于不支持引用类型,所以采用指针的方式来回传形参的值,需将上述函数改为: int swap2(int *x,int *y) int temp; temp=*x;/* 将*x的值放在temp中 */ *x=*y; /* 将*x所指的值改为*y */ *y=temp;/* 将*y所指的值改为temp */ 上述函数的调用改为swap2( / coutxyz;

14、 if (x=y */ if (yz*/ if (x=temp) y=temp; else y=x;x=temp; printf(%d,%d,%dn,x,y,z); / coutxyz“n”; ,另一写法: void Descending( int x, int y, int z ) / 参数作为输入 if (x=y*/ if (yz*/ if (x=temp) y=temp; else y=x;x=temp; printf(%d,%d,%dn,x,y,z); ,再一种写法: void Descending( int ,1.3 算法分析,1.3.1 算法设计的目标,1.3.2 算法效率分析,1

15、.3.3 算法存储空间分析,设计的目标: 正确性。要求算法能正确地执行预先规定的功能和性能要求。 可使用性。要求算法能方便地使用。也叫用户友好性。 可读性。算法应该易于理解。 健壮性。能对异常数据作出特殊处理,不会造成异常中断或死机。 高效率和低存储量需求。,1.3.1 算法设计的目标,衡量算法效率的方法: 事后统计法:-执行程序,计算时间。 事前分析估算法。 一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。,1.3.2 算法效率分析,例1.8 求两个n阶方阵的加法 #define MAX 20 void matrixadd(

16、int n, int A MAX , B MAX , C MAX ) int i, j; for(i=0; in; i+) 循环结构1 for(j=0; jn; j+) 循环结构2 Cij=Aij+Bij; 基本运算(原操作) 算法的执行时间=循环结构1的总时间+循环结构2总时间 +基本运算的总时间,算法执行时间大致为基本运算所需的时间与其执行次数(也称为频度)的乘积。 为简便,取每个基本运算的时间=1 执行时间 = 基本运算的执行次数,算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作: T(n)=O( f(n) ) 将O( f(n) ) 称为算法的时间复杂度 例如, T(n)=

17、3n2-5n+10000=O(n2) T(n)的数量级是n2, 时间复杂度是O(n2) 主要反映n值很大时算法的时间性能,记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间T(n)的增长率和f(n)的增长率相同。“O”的形式定义为: 若f(n)是正整数n的一个函数,则T(n)=O(f(n)表示存在一个正的常数M,使得当nn0时都满足: |T(n)|M|f(n)| 也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。 例如,T(n)=3n2-5n+10000=O(n2),例. 求两个n阶方阵的乘积 #defin

18、e n 100 MATRIXMLT(float A n, B n, C n ); int i, j, k; 语句频度 for(i=0; in; i+) n+1 for(j=0; jn; j+) n(n+1) Cij=0; n2 for(k=0; kn; k+) n2 (n+1) Cij=Cij+Aik*Bkj; n3 ,语句频度之和:T(n)=2n3+3n2+2n+1,该算法的时间复杂度T(n)=2n3+3n2+2n+1 =O(n3 ) 一般地,估算算法中频度最大的语句 该算法中的基本运算是三重循环中最深层的语句Cij=Cij+Aij*Bij, 分析它的频度, 即: T(n)= =O(n3),

19、例1.8 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #define MAX 20 /*定义最大的方阶*/ void matrixadd( int n, int AMAXMAX, int BMAXMAX, int CMAXMAX ) int i, j; for (i=0;in;i+) for (j=0;jn;j+) Cij=Aij+Bij; ,该算法中的基本运算是两重循环中最深层的语句Cij=Aij+Bij,分析它的频度,即: T(n)= =O(n2),例 分析以下算法的时间复杂度。 int fun(int n) int i, j, k, s; s=0; for (i=0;

20、i=n; i+) for (j=0; j=i; j+) for (k=0; k=j; k+) s+; return(s); ,解:该算法的基本操作是语句s+,其频度: T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。,例1.10 算法: void fun( int a , int n, int k) int i; if (k=n-1) for (i=0; in; i+) coutaiendl; else for ( i=k; in; i+) ai=ai+i*i; fun(a, n, k+1); / 递归调用 调用函数:fun(a, n, 0 ), 求其时间复杂度。 设 fun(a,

21、 n, k) 的执行时间为 T1(n , k),fun(a,n,0) 的时间复杂度T(n)=T1(n,0)=O(n2),一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1), 也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。 其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。,各种不同数量级对应的值存在着如下关系: O(1)O(log2n)O(n)O(n*log2n)O(n2) O(n3)O(2n)O(n!)O(nn),当n取得很大时,指数阶算法和多项式时间算法在所需时间上非常悬殊。 多项式时间算法解决的问题叫P问题; 指数阶算法解决的问题叫NP问题。 世界难题: NP问题 = P问题 若有人能将现有NP问题中的任何一个算法化简为多项式时间算法,那就取得了一个伟大的成就。,?,例:多项式时间算法与指数时间算法的执行时间比较。 假设算法P1的时间复杂度为T1(n) = n2,算法P2的时间复杂度为T2(n) = 2 n , 计算机的运算速度是1微秒(即每秒1000000次运算)。,例:多项式时间算法与指数时间算法的执行时间比较。 假设算法P1的时间复杂度为T1(n) = n2,算法P2的时间复杂度为T2(n) = n! , 计算机的运算速度是每秒1亿次运算)。,

温馨提示

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

评论

0/150

提交评论