《数据结构讲稿（上）ppt》由会员分享，可在线阅读，更多相关《数据结构讲稿（上）ppt（263页珍藏版）》请在金锄头文库上搜索。
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+
3、1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。,这些数据在计算机存储器中的存储方式就是存储结构。通常可以采用C/C+语言中的结构体数组和链表两种方式实现其存储结构。,存放学生表的结构体数组Stud定义为： struct int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ Stud7=1,“张斌”,“男”,“9901”, 5,“王萍“,“女“,“9901“;,结构体数组Stud各元素在内存中顺序存放,即第i(1i6)个学生对应的元素Studi存放在第i+1个学生对应的元素Stu
4、di+1之前,Studi+1正好在Studi之后。,存放学生表的链表的结点类型StudType定义为： typedef struct studnode int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ struct studnode *next; /*存储指向下一个学生的指针*/ StudType；,head,1,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学
5、生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,学生表构成的链表,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,例如,查找学号为20的学生的姓名： 对于Stud数组,可以从Stud0开始比较,Stud0.no不等于20,再与Stud1.no比较,直到Stud3.no等于20,返回Stud3.name。 对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于
6、20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,直到某结点的no域等于20,返回其name域。,为了更确切地描述一种数据结构,通常采用二元组表示： B=(K,R) 其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中： K=ki| 1in,n0 R=rj| 1jm,m0,其中ki表示集合K中的第i个结点或数据元素,n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。 rj表示集合R中的第j个二元关系(后面均简称关系),m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间
7、不存在任何关系,彼此是独立的。,K上的一个关系r是序偶的集合,对于r中的任一序偶(x,yK),我们把x叫做序偶的第一结点,把y叫做序偶的第二结点,又称序偶的第一结点为第二结点的直接前驱结点(通常简称前驱结点),称第二结点为第一结点的直接后继结点(通常简称后继结点)。如在的序偶中,x为y的前驱结点,而y为x的后继结点。 若某个结点没有前驱,则称该结点为开始结点；若某个结点没有后继,则称该结点为终端结点。,例如,采用二元组表示例1.1的学生表。 学生表中共有7个结点,依次用k1k7表示,则对应的二元组表示为B=(K,R),其中： K=k1,k2,k3,k4,k5,k6,k7 R=r r=, ,又例
8、如,有如下数据即一个矩阵：,对应的二元组表示为B=(K,R),其中： K=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中,r1表示行关系,r2表示列关系 r1=, , r2=, ,一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。 上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,(1)线性结构 所谓线性结构,该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构
9、。,1.1.2 逻辑结构类型,返回,(2)非线性结构 所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。,所谓树形结构,该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点。非线性结构树形结构简称为树。 所谓图形结构,该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此,可能没有开始结点和终端结点,也可能有多个开始结点、多个终端结点。图形结构简称为图。,(1)顺序存储方法,(2)链式存储方法,(3)索引存储方法,(4)散列存储方法,1.1.3 存储结构类型
10、,返回,(1)数据类型 在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是一个值的集合和定义在此集合上的一组操作的总称。,1.1.4 数据结构和数据类型,返回,如C/C+中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为32768到32767的全体整数)和相关的整数运算(如、等)。,(2)抽象数据类型 抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不
11、考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=数据元素集合抽象运算,例如,抽象数据类型复数的定义： 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
12、返回两个复数z1,z2的和值。 ADT Complex,1.2 算法及其描述,1.2.1 什么是算法,1.2.2 算法描述,1.2.1 什么是算法 数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。 通常把具体存储结构上的操作实现步骤或过程称为算法。,返回,算法的五个重要的特性,(1)有穷性:在有穷步之后结束。,(2)确定性:无二义性。,(3)可行性:可通过基本运算有限次执行来实现。,(4)有输入,(5)有输出,例1.2 考虑下列两段描述： (1) void exam1() n2; while (n%20) nn+2; printf(“%dn“
13、,n); ,(2) void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,解：(1)算法是一个死循环,违反了算法的有穷性特征。 (2)算法包含除零错误,违反了算法的可行性特征。,1.2.2 算法描述,本书中采用C/C+语言描述算法。 说明：C+语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。 注意：Turbo C不支持引用类型。,返回,例如： int a=4;
14、/*a为普通的整型变量*/ int /*b是a的引用变量*/ 这里说明b变量是变量a的引用,b也等于4,之后这两个变量同步改变。当a改变时b也同步改变，同样，当b改变时a也同步改变。,引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数(其中的形参均为引用型形参)： void swap(int y=tmp 当用执行语句swap(a,b)时,a和b的值发生了交换。,反之，有以下函数swap1()，当用执行语句swap1(a,b)时,a和b的值不会发生了交换。 void swap1(int x,int y) int temp; temp=a;a=b;b=te
15、mp; ,在C语言中，由于不支持引用类型，所以采用指针的方式来回传形参的值，需将上述函数改为： int swap2(int *x,int *y) int temp; temp=*a; /*将a的值放在temp中*/ *a=*b; /*将a所指的值改为*b*/ *b=temp；/*将b所指的值改为temp*/ 上述函数的调用改为swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。,例1.3 编写一个算法, 读入三个整数x,y和z的值,要求从大到小输出这三个数。 解：依次输入x,y和z这三个整数,通过比较交换后,使得xyz,然后输出x,y,z。 在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行3次比较和7次移动。,void Descending() printf(“输入x,y,z“); scanf(“%d,%d,%d“, ,1.3 算法分析,1.3.1 算法时间复杂度分析,1.3.2 算法空间复杂度分析,返回,一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。,1.3.1 算法时间复杂度分析,返回,为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的问题来说是基本运算的原操作(以下将基本运算的原操作简称为基本运算)。 算法执行
