数据结构第1章绪论.ppt

第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班为一个学生数据,而其中的“张三”是一个数据元素)。,数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,可以把数据结构看成是带结构的数据元素的集合。,数据结构包括如下几个方面：(1)数据元素之间的逻辑关系,即数据的逻辑结构。(2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。(3)施加在该数据上的操作,即数据的运算。,例1.1 有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。,表1.1 学生表,该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为：,其中尖括号“”表示元素ai和ai+1之间是相邻的,即ai在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;,结构体数组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,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,学生表构成的链表,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,为了更确切地描述一种数据结构,通常采用二元组表示：B=(D,R)其中,B是一种数据结构,它由数据元素的集合D和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表示,则对应的二元组表示为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,11R=r1,r2 其中,r1表示行关系,r2表示列关系r1=,r2=,一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,(1)线性结构 所谓线性结构,该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。,1.1.2 逻辑结构类型,返回,(2)非线性结构 所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。,所谓树形结构,该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点。非线性结构树形结构简称为树。所谓图形结构,该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此,可能没有开始结点和终端结点,也可能有多个开始结点、多个终端结点。图形结构简称为图。,例 人机对奕问题,将每个棋局都抽象成一个结点：,棋局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.用顶点代表比赛项目:不能同时进行比赛的项目之间连上一条边。,安排四个单位时间进行比赛,A,E,B,F,D,C,(1)顺序存储方法,(2)链式存储方法,(3)索引存储方法,(4)散列存储方法,1.1.3 存储结构类型,返回,（具体细节略),(1)数据类型 在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是值的集合和定义在此集合上的一组操作的总称。,1.1.4 数据结构和数据类型,返回,如C/C+中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为32768到32767的全体整数)和相关的整数运算(如、等)。,C+的各种数据类型介绍略如：float,long,char,指针类型，数组类型，结构体类型，共用体类型。,自定义数据类型名称：用typedeftypedef 旧数据类型 新数据类型名如：typedef char ElemType则：ElemType 就是char 如：typedef struct stud int no;char name10;int score;student;,定义变量时：可用 student x,y;,(2)抽象数据类型 抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型=带关系的数据元素集合抽象运算,例如,抽象数据类型“复数”的定义：ADT Complex 数据对象：D=e1,e2|e1,e2均为实数数据关系：R1=|e1是复数的实数部分,e2 是复 数的虚数部分,基本操作：AssignComplex(&Z,v1,v2)：构造复数Z,其实部和虚部分别赋以参数v1和v2的值。DestroyComplex(&Z):复数Z被销毁。GetReal(Z,&real):用real返回复数Z的实部值。GetImag(Z,&Imag):用Imag返回复数Z的虚部值。Add(z1,z2,&sum):用sum返回两个复数z1,z2的和值。ADT Complex,1.2 算法及其描述,1.2.1 什么是算法,1.2.2 算法描述,1.2.1 什么是算法 数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。通常把具体存储结构上的操作实现步骤或过程称为算法。广义地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每个指令表示计算机的一个或多个操作。,算法的五个重要的特性,(1)有穷性:在有穷步之后结束。,(2)确定性:无二义性。,(3)可行性:每个操作都足够基本，可通过已经实现基本运算有限次执行来实现。,(4)有输入：有0个或多个外部输入,(5)有输出：有1个或多个输出,例 考虑下列两段描述：(1)void exam1()n2;while(n%20)nn+2;coutn;,(1)算法是一个死循环,违反了算法的有穷性特征。,(2)void exam2()y=0;x=5/y;coutx“”y;算法包含除零错误,违反了算法的可行性特征。,缺少：return sum;或者：coutsum=“sum;,1.2.2 算法描述,本书中采用C/C+语言描述算法。说明：C+语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。注意：Turbo C不支持引用类型。,返回,引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数(其中的形参均为引用型形参)：void swap(int y=tmp；当用执行语句swap(a,b)时,a和b的值发生了交换。,反之，有以下函数swap1()void swap1(int x,int y)int temp;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(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。,例 编写一个算法,读入三个整数x,y和z的值,要求从大到小输出这三个数。解：依次输入x,y和z这三个整数,通过比较交换后,使得xyz,然后输出x,y,z。在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行3次比较和7次移动。,void Descending()printf(输入x,y,z);/coutxyz;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.3.3 算法存储空间分析,设计的目标：正确性。要求算法能正确地执行预先规定的功能和性能要求。可使用性。要求算法能方便地使用。也叫用户友好性。可读性。算法应该易于理解。健壮性。能对异常数据作出特殊处理，不会造成异常中断或死机。高效率和低存储量需求。,1.3.1 算法设计的目标,衡量算法效率的方法：事后统计法：-执行程序，计算时间。事前分析估算法。一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。,1.3.2 算法效率分析,例1.8 求两个n阶方阵的加法#define MAX 20void matrixadd(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)=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阶方阵的乘积#define n 100MATRIXMLT(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),例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;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,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亿次运算）。,空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出,记作：S(n)=O(g(n)若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。若所需存储量依赖于特定的输入,则通常按最坏情况考虑。,1.3.3 算法存储空间分析,返回,例 分析下例的空间复杂度。#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;解：由于这个算法中临时变量的个数与问题规模n无关,所以空间复杂度均为O(1)。,1.4 数据结构+算法=程序,N.Wirth提出：数据结构+算法=程序 程序设计的本质是：对要处理的问题选择好的数据结构，在此结构上施加好的算法。,例 电话公司的电话号码查询服务。方案1：数据结构是线性表。,通过姓名查询号码的算法采用顺序查询算法，时间=n/2,方案2：采用树结构查询算法的时间=log2 n当n=1000000时，方案1的关键字比较次数=n/2=500000 方案2的关键字比较次数=log2 100000020,本章小结 本章介绍了数据结构的基本概念,主要学习要点如下：(1)数据结构的定义,数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。(2)各种逻辑结构即线性结构、树形结构和图形结构之间的差别。,返回,(3)数据结构和数据类型的差别和联系。(4)算法的定义及其特性。(5)算法的时间复杂度和空间复杂度分析。,