《数据结构教程（第3版）一ppt》由会员分享，可在线阅读，更多相关《数据结构教程（第3版）一ppt（286页珍藏版）》请在金锄头文库上搜索。
1、数据结构教程（第3版）一,第1章 绪论,1.2 算法及其描述,1.1 什么是数据结构,1.3 算法分析,本章小结,1.4 数据结构算法程序,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 学生表,该表中的记录顺序反映了数据元素之间的逻辑关系, 用
3、学号标识每个学生记录,这种逻辑关系可以表示为： , 其中尖括号“”表示元素ai和ai+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各元素在内存中顺序存放
4、,即第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；,链表首结点地址head,1,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华
5、,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。,学生表构成的链表,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。,例如,查找学号为20的学生的姓名： 对于Stud数组,可以从Stud0开始比较,Stud0.no不等于20,再与Stud1.no比较,直到Stud3.no等于20,返回Stud3
6、.name。 对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于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
7、表示集合R中的第j个二元关系(后面均简称关系)。 m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。,序偶(x,yK) x为第一结点,y为第二结点。 x为y的直接前驱结点(通常简称前驱结点) y为x的直接后继结点(通常简称后继结点)。 若某个结点没有前驱结点,则称该结点为开始结点；若某个结点没有后继结点,则称该结点为终端结点。,说明：表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。,例如,采用二元组表示例1.1的学生表。 学生表中共有7个结点,依次用k1k7表示,则对应的二元组表示为B=(K,R),其中： K=k1,k2,k
8、3,k4,k5,k6,k7 R=r /只有一种关系 r=,又例如,有如下数据即一个矩阵：,对应的二元组表示为B=(K,R),其中： K=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中,r1表示行关系,r2表示列关系 r1=, , r2=, , ,一个二维数组,可以利用图形形象地表示逻辑结构。 例如，上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,(1) 线性结构 结点之间关系：一对一。 特点：开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。,1.1.2 逻辑结构类
9、型,(2) 树形结构 结点之间关系：一对多。 特点：开始结点惟一,终端结点不惟一。除终端结点以外,每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前驱结点。,(3) 图形结构 结点之间关系：多对多。 特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。,(2) 链式存储方法,(3) 索引存储方法,(4) 散列存储方法,1.1.3 存储结构类型,(1) 顺序存储方法,(1) 数据类型 高级程序语言中,一般须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。 数据类型是一个值的集合和定
10、义在此集合上的一组操作的总称。,1.1.4 数据结构和数据类型,如C/C+中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为3276832767的全体整数)和相关的整数运算(如、等)。,(2) 抽象数据类型 抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=数据元素集合抽象运算,例如,抽象数据类型复数的定义： ADT Complex 数据对象： D=e1,e2|e1,e2均为实数 数据关系： R1=| e1是
11、复数的实数部分,e2 是复数的 虚数部分 ,e1e2i,基本操作： AssignComplex(&Z,v1,v2)：构造复数Z。 DestroyComplex(&Z):复数Z被销毁。 GetReal(Z,&real):返回复数Z的实部值。 GetImag(Z,&Imag):返回复数Z的虚部值。 Add(z1,z2,&sum):返回两个复数z1,z2的和。 ADT Complex,1.2 算法及其描述,1.2.1 什么是算法,1.2.2 算法描述,1.2.1 什么是算法 数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。 通常把具体存储结构上的操
12、作实现步骤或过程称为算法。,算法的五个重要的特性,(1) 有穷性:在有穷步之后结束。,(2) 确定性:无二义性。,(3) 可行性:可通过基本运算有限次执行来实现。,(4) 有输入,(5) 有输出,例1.2 考虑下列两段描述： (1) 描述一 void exam1() n2; while (n%20) nn+2; printf(“%dn“,n); ,华中科大考研题,(2) 描述二 void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,解：(1)算法是一个死循环,违反了算法的有穷性特征。 (2)算法包
13、含除零错误,违反了算法的可行性特征。,1.2.2 算法描述,本书中采用C/C+语言描述算法。 说明：C+语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。 注意：Turbo C不支持引用类型。,编写一个函数swap1(x,y)，当执行语句swap1(a,b)时,交换a和b的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：a和b的值不会发生了交换。,为此，采用指针的方式来回传形参的值，需将上述函数改
14、为： void swap2(int *x,int *y) int tmp; tmp=*x; /*将x的值放在tmp中*/ *x=*y; /*将x所指的值改为*y*/ *y=tmp； /*将y所指的值改为tmp*/ 上述函数的调用改为swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。,引入“引用”的概念 例如： int a=4; /*a为普通的整型变量*/ int /*b是a的引用变量*/ 这里说明b变量是变量a的引用,b也等于4,之后这两个变量同步改变。当a改变时b也同步改变，同样，当b改变时a也同步改变。,难点,main() int a=2; int
15、/*输出：a=4,b=4*/ ,引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数(其中的形参均为引用型形参)： void swap(int y=tmp 当用执行语句swap(a,b)时,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 算法时间复杂度分析,控制语句1 原操作,控制语句n 原操作,一个算法,同一问题可以采用多种算法实现。如何比较算法执行效率？ 算法描述的语言不同 算法执行的环境不同 其他因素 所以不能用绝对执行时间进行比较,为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的
