【全套精品课件】数据结构课件.ppt

数 据 结 构 书山有路勤为径 学海无涯苦作舟 会当凌绝顶 一览众山小 第一章 绪论 本章概要（4学时） 本章的主要内容,是介绍和数据结构相关的一些初始概念、术语 以及算法的描述和对其性能的评价。 通过学习应当掌握： * 数据、数据元素、数据对象、数据类型; * 数据结构与存储结构； * 四种基本的数据结构与两种存储结构； * 用C语言描述算法的基本格式； * 对算法性能的评价标准； * 算法的时间复杂度与空间复杂度的估算； 3 一. 有关数据的概念 1、数据(data)的形式定义 数据是对客观实体的一种描述（表现）形式。 实体可以分为可 见的与抽象的两类。在计算机领域多为抽象实体。 *常用的几种数据形式： 1）数值数据：是用0到9十个数字的组合描述一个实体。 2）符号数据：是用公认的一些符号的组合描述一个实体。这种数 据具有广泛性、模糊性。 3）图像（图形）数据：是用图像、图形描述一个实体。 这种数据 能直观的表现实体各部分之间的关系，便于我们了解分析实体的本 质。正因为如此，虽然处理复杂。但是，在许多领域我们仍然要使 用这种数据形式。 4）语音数据：是用自然语言描述一个实体。 总之，在计算机科学领域，凡是计算机能识别与处理的数字、符 号、图像、图形、语音以及它们的汇集通称数据。 2 、 信息(information) 及信息与数据的关系 信息是客观世界向人们或向计算机提供的新知识。所谓新知识 是指人们不知道、 不了解的客观事物。 我们任何一个人都是从无知到有知识的，从不认识客观世界到 识客观世界的。那么，人们是通过什么方式认识客观世界的呢？无 非是通过上述四种数据形式。所以说：数据是载荷信息的一种物理 号。而 数据的形式随着设备、环境的不同而异。但是 ， 信息不受 数据形式变化的影响。 在某种意义上讲信息更能反映客观世界的本 质。 由上可知，信息与数据是不可分割的。 所以，在许多场合信 息与数据可以互相代替。另外，信息的度量单位是熵。其含义是不 肯定性的大小，不知道的程度。 抽象、描述 去旧取新、抽取 学习、积累 客观实体 数据 信息 知识 3、数据元素(data element) 是系统中数据的基本单位（即在内存 中,具有可访问地址号的最小数据单位）。在实际应用中,一个数据 元素往往是有几部分组成，其中每一部分称为一个数据项（数据项 是数据处理时不可再分割的最小数据单元）。每一个数据项都有一 个值，习惯上称这个值为关键字。应用时，关键字又分主关键字与 次关键字。 主关键字是指它能唯一的标识一个数据元素。如表1中 学号2026为主关键字。下表1为一张学生的登记卡,在学籍管理系统 中。用C语言中的结构类型描述如下： ：Structxs{Int:xh;Char:xm[10];Char:xb[];Int:nl;Char:jg[10];};其中保留字Struct定义一个结构，五个数据项xh、xm、xb、nl、jg分别表示学号、姓名、性别、年龄、藉贯  。 5 4、数据对象（data object）是性质相同的数据元素的集合，是数据 的一个子集。例如，整数数据对象是集合：N={0，1，2，。。。} 5、数据类型 (data type) 是把主要特性相同的一些独立的数据个体 用一个标识符来代表它们。那么,就构成一个数据的群体，习惯上称 这个群体为数据类型。在高级程序语言中的整型数就是整数类型， 实型数就是实数类型。（1）取值范围。（2）操作运算。 6、 抽象数据类型(data type) 是指一个数学模型以及定义在该模 型上的一组操作。其定义仅取决于它的一组逻辑特性，而与其在计 算机内部如何表示和实现无关。即不论起内部结构如何变化，只要 它的数学特性不变，都不影响其外部的使用。 抽象数据类型可用三元组表示： （D，S，P） D是数据对象，S是D上的数据关系集，P 是对D的基本操作集。 7、数据结构(data structure) 数据结构的形式定义: 数据结构是数据本身固有的,以及数据与数据之间的关系。 所谓 本身固有是指他人或先人已经设计好的，