《《数据结构(C／C++描述)》-第1章 绪论》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-第1章 绪论（71页珍藏版）》请在金锄头文库上搜索。
1、中国水利水电出版社,1,21世纪高等院校计算机系列教材数据结构（C/C+ 描述） 中国水利水电出版社,中国水利水电出版社,2,内 容 安 排,中国水利水电出版社,3,第1章 绪 论,中国水利水电出版社,4,1.1 数据结构的概念,1.2 抽象数据类型,1.3 算法和算法分析,中国水利水电出版社,5,1.1 数据结构的概念,（数据结构在软件开发中的地位）,系统分析,系统设计,系统实现,系统维护,系统设计,中国水利水电出版社,6,程序设计:算法: 数据结构:,为计算机处理问题编制一组指令集,处理问题的策略,问题的数学模型,系统设计,中国水利水电出版社,7,非数值计算的程序设计问题:,例1.1 学生
2、信息检索系统,算法: ?模型：？,基本操作是：查询,线性表,中国水利水电出版社,8,例1.2 计算机和人对弈问题,算法：?模型：?,求从树根到树叶的一条路径,树,中国水利水电出版社,9,例1.3 教学计划编排问题,算法：?模型：?,拓扑排序,图,中国水利水电出版社,10,概括地说，,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,中国水利水电出版社,11,基本概念 和 术语,中国水利水电出版社,12,所有能被输入到计算机中，且能被计算机处理的符号(包括 数字、字符、声音、图像等信息)的集合。,1.数据（data）,是计算机操作的对象的
3、总称。,是计算机处理信息的某种特定符号的表示形式。,中国水利水电出版社,13,是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位（又称元素、结点，顶点、记录）.,2.数据元素（data element）,如:整数“5”,字符“N”等。 -是不可分割的数据元素.,中国水利水电出版社,14,其中每一项，称为一个 “数据项”。(又称为：字段、域、属性 等。),它是数据结构中讨论的最小单位。,数据元素也可以由若干项构成。,例如：,描述一个学生的数据元素。,称之为组合项,原子项,中国水利水电出版社,15,3.数据项（Data item） 构成数据元素的项
4、目，是具有独立含 义的最小标识单位。（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄 、,中国水利水电出版社,16,4.数据结构（data structure）,带结构的数据元素的集合,有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。,指的是数据元素之间存在的关系。,中国水利水电出版社,17,例如，在 2 行 3 列的二维数组中 6 个元素a1, a2, a3, a4, a5, a6之间存在两个关系：,行的次序关系:,row = ,col = ,列的次序关系:,中国水利水电出版社,18,若
5、在 6 个数据元素a1, a2, a3, a4, a5, a6 之间存在如下的次序关系：, | i=1, 2, 3, 4, 5,数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,则构成一维数组的定义。,中国水利水电出版社,19,从关系或结构分，数据结构可归结为以下 4 类:,线性结构,树形结构,图状结构,集合结构,一对一（1:1) 一对多（1:n)多对多 (m:n)仅同属一个集合,中国水利水电出版社,20,数据结构涵盖的内容,中国水利水电出版社,21,5.逻辑结构(logic structure) 是对数据元素之间逻辑关系的描述，它可以用一个数据元
6、素的集合和定义在此集合上的若干关系来表示。,中国水利水电出版社,22,数据的逻辑结构，简称为数据结构其形式定义描述为:,数据结构是一个二元组,Data_Structures =（D, S）,其中: D 是数据元素的有限集， S 是 D上关系的有限集。,中国水利水电出版社,23,例如:定义 “班集体”为一个数据结构。,Class =（D, S）,D = a, b1,bn, c1,cn, d1,dn ,S = R1, R2 R1 = , R2 = , , | j = 2, 3, , n ,树结构,中国水利水电出版社,24,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,（1）
7、 S=（D, R） D= a, b, c, d, e, f R=, , , , ,解： 上述数据结构表达式可用图形表示为：,b c a e f d,所以，此结构为线性的。,中国水利水电出版社,25,（2） S=（D, R） D= di | 1i5 R= | ij ,d1 d5 d2 d4 d3,该结构是图结构。,解：上述数据结构表达式可用图形表示为：,中国水利水电出版社,26,6.存储结构(storage structure) 是数据的逻辑结构在计算机中的表示和实现，故又称“物理结构”。,中国水利水电出版社,27,数据的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象 ？,“关系”的映
8、象 ？,中国水利水电出版社,28,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,中国水利水电出版社,29,关系的映象方法,（表示x, y的方法）,（1）顺序映象,-以相对的存储位置表示后继关系。,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C。,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息。,中国水利水电出版社,30,（2）链式映象,- 以附加信息(指针)表示后继关系。,对前例，需要用一个和 x 在一起的附加信息（指针）指示 y 的存储
9、位置。,中国水利水电出版社,31,在不同的编程环境中，,存储结构可有不同的描述方法。,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述存储结构。,中国水利水电出版社,32,例如:,以3个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型，,typedef int Long_int 3;,定义长整数为:,中国水利水电出版社,33,typedef struct int y; / 年号 Year int m; / 月号 Month int d; / 日号 Day DateType; / 日期类型,定义“日期”为:,定义“学生”为:,typedef str
10、uct char id8; / 学号 char name16; / 姓名 char sex; / 性别M/F:男/女 DateType bdate; / 出生日期 Student; / 学生类型,中国水利水电出版社,34,7. 数据运算,是在数据的逻辑结构上定义的操作算法,它在数据的存储结构上实现。,最常用的数据运算有5种：,插入、删除、修改、查找、排序,中国水利水电出版社,35,数据类型,在用高级程序语言编写的程序中：必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。,中国水利水电出版社,36,例如，C 语言中提供的基本数据类型有:,整型 int,浮点型 float,字符
11、型 char,逻辑型 bool （ C+语言）,双精度型 double,中国水利水电出版社,37,数据类型 是一个值的集合和定义在此集合上的一组操作的总称。,不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,例如：整型 值的范围是：-32768-32767 操作是：+，-，*，/，%,中国水利水电出版社,38,1.2 抽象数据类型 (Abstract Data Type 简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作。,中国水利水电出版社,39,例如:“整数”是一个抽象数据类型。,其数学特性和具体的计算机或语言无关。 “抽象”的意义在于强调数据类型的数学特性。,中国
12、水利水电出版社,40,例如，定义抽象数据类型“复数”, 数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1 是复数的实数部分, e2 是复数的虚数部分 ,ADT Complex,中国水利水电出版社,41,基本操作：,AssignComplex( &Z, v1, v2 )操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。,DestroyComplex( &Z)操作结果：复数 Z 被销毁。,GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。,中国水利水电出版社,42,GetImag
13、( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。,Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的 和值。, ADT Complex,中国水利水电出版社,43,ADT 有两个重要特征:,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,中国水利水电出版社,44,抽象数据类型的描述方法：,抽象数据类型可用三元组（D，S，P）表示。其中：D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。,中国水利水电出版社,45,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,其中基本操作的定义格式为:,基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,中国水利水电出版社,46,赋值参数 只为操作提供输入值；引用参数 以&打头，除可提供输入值外，还将返回操作结果。,
