数据结构一章节绪论.pptVIP

数据结构第一章 绪论 选用教材 课程意义 数据结构是计算机专业的一门专业基础课。 数据结构是关于数据组织和处理的基本技术的一门学科。 程序 = 数据结构 + 算法 + 文档 数据结构是一门实践性很强的课程。 1.1 什么是数据结构？ 问题1：图书检索自动化 图书的基本信息：书名，作者，分类号，出版单位，出版时间 作者简介，内容简介等等。 操作：检索，排序，等等 数据之间的关系：线性关系 数据表示和算法操作的设计：与需求有关 1.1 什么是数据结构？ 1.1 什么是数据结构？ 数据结构课程的主要任务 研究和解决非数值数据的组织和处理 描述非数值计算问题的数学模型，不再是数学方程 例如：前述的三个例子：数据的线性结构，树型结构，图 算法+数据结构=程序 算法和数据结构之间的关系 软件系统的框架应当建立在数据之上，而不是建立在操作之上 数据结构的作用范畴 抽象数据对象的数学模型（逻辑结构）例：图状结构 明确操作（运算的定义） 例：查找、插入、…… 在存储结构上映射数据（存储结构） 例：顺序存储 实现操作 1.2 基本概念和术语 基本术语 数据：被计算机加工处理的对象。 数据元素：是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。 数据项：是数据不可分割的最小单位。 一个数据元素可由若干个数据项组成。 1.2 基本概念和术语 数据对象 是性质相同的数据元素的集合。 什么叫数据结构？ 具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。 逻辑结构 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。 [例] 设有数据结构 B = (D,R) ， 其中 D= {d1, d2, d3, d4, d5, d6}， R={r}， r={d1,d2, d1,d3, d1,d4, d3,d5, d3,d6}， 试画出其逻辑结构图。 （以班级学生关系为例） (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (2)线性结构 数据元素之间存在一对一的关系。 (3)树型结构 数据元素之间存在一对多的关系。 (4)图状结构或网状结构 数据元素之间存在多对多的关系。 数据的逻辑结构 示例１ 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 示例２ 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij} 存储结构 存储结构：数据的逻辑结构在计算机中如何表示。 数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为结点 每个数据项的映象称为数据域 关系的映象 两种基本方法及其组合使用。 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系 在不同的编程环境下，存储结构有不同的描述方式。 用高级程序语言编程时，直接用其提供的数据类型描述。 顺序存储和链式存储 (1) 顺序存储：数据元素依次放在连续的存储单元中。 (2) 链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。 数据运算 运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。 常用的运算有： (1)建立数据结构 (6)检索* (2)清除数据结构 (7)更新 (3)插入数据元素 (8)判空和判满* (4)删除数据元素 (9)求长* (5)排序 操作为引用型操作，即数据值不发生变化； 其它为加工型操作。 这三个方面的关系 数据的逻辑结构独立于计算机，是数据本身所固有的。 存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。 数据结构的三个方面 1.3 数据类型和抽象数据类型 数据类型：是一