数据结构－第01章 节 －绪论.pptVIP

数 据 结 构 孟 刚 二○一二年二月 课程介绍 计算机及相关学科的重要专业基础课 研究数据的逻辑结构、表示形式以及基本操作的算法 设计和实现编译程序、操作系统、数据库系统等系统程序和大型应用程序的基础 计算机科学的“方法论” 学习本课程的基本方法 ① 上课认真听讲； ② 仔细阅读教材中的大量算法，从而体会并最终掌握数据结构中的基本概念； ③ 独立完成每个章节后面的练习题； ④认真完成上机实习作业，培养应用算法和编写调试程序的能力。 教师联系方式 办公室：第二实验楼108 GIS教研室 电子邮箱： mgbooker@163.com QQ电话第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 由以上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。 通过以上几例可以这么认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。 1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。 上述数据结构的定义仅是对操作对象的一种数学描述——是从操作对象抽象出来的数学模型。 定义： 1. 结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。 2.数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 数据结构的研究目的和研究内容 研究目的：寻求有效的组织和处理非数值数据的理论技术和方法。 研究内容： 数据的逻辑结构（线性、树、图） 数据的存储结构（顺序、链表） 相应的基本操作运算（编辑、修改、查找、排序） 数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示 由此得出两种不同的存储结构：顺序存储结构和链式存储结构 顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针（pointer），用此指针来表示数据元素之间的逻辑关系。 数据类型：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义 数据对象：某种数据类型元素的集合。 例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…} 英文字符类型的数据对象是{A，B，C，D，E，F，…} 数据对象可以是有限的，也可以是无限的。 　数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。 　　抽象数据类型实际上就是对该数据结构的定义。因为它定义了一