数据结构(第一章).pptVIP

数据结构　　　 参考书目 第一章　绪 论 本章主要介绍下列内容 1.1 问题的引入——什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型及其表示实现 1.4 算法和算法分析 一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边vi，vj，则表示课程i必须先于课程j进行。 数据： 计算机程序所处理的符号的总称。 数据元素： 数据的基本单位，它可由若干数据项组成。 数据对象： 是性质相同的数据元素的集合，是数据的子集。 数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构 一个数据结构有两个要素：一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。 Data_Structure=(D,S) 其中：D是数据元素的有限集，S是D上关系的有限集。 数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。 抽象数据类型（Abstract Data Type） 抽象数据类型(ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。 与机内表示和实现无关，指的是数学抽象性。 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。 原子类型：变量的值是不可分解的 固定聚合类型：由确定数目的成分按某种结构组成。 可变聚合类型；构成可变聚合类型“值”的成分的数目不确定。 抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。 抽象数据类型用三元组表示： （D，S，P） 其中：D是数据对象，S是D上的关系，P是对D的基本操作集。 例：抽象数据类型——复数 ADT Complex{ 数据对象：D={c1,c2∈FloatSet} 数据关系：R1={c1,c2} 基本操作： Creatc(a); /*输入c1,c2，使得a=c1+c2i*/ Add(d,a,b); /*d=a+b*/ … Outputc(a); /*已知a，输出a=c1+c2i的形式*/ }ADT Complex 例：抽象数据类型——三元组 ADT Triplet{ 数据对象：D={e1,e2,e3|e1,e2,e3∈ElemSet} 数据关系：R1={e1,e2,e2,e3} 基本操作： InitTriplet(T,v1,v2,v3) 操作结果：构造三元组T,元素ei分别赋值vi … Min(T,e) 初始条件：三元组T已经存在 操作结果:用e返回T的3个元素中最小值。 }ADT Triplet 面向过程的方法 面向对象的方法 算法的时间效率主要由两个因素决定： l所需处理问题的数据量大小，数据量大，所花费的时间就多； l在解决问题的过程中，基本操作的执行次数 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数， T(n)=O(f(n)) 好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。 问题的规模：是数据元素的个数，通常用n来表示 例如：对一个学院，n可为数百人；对整个学校，n可为上千至上万人。 算法分析要脱离开具体机型、语言因素来分析，主要是时间因素，还有内存空间的占用。 空间复杂度：S(n)=O(f(n)) ，辅助空间的度量。 辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。 1. 预定义常量及类型 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 Status 是函数的类型，其值是函数结果状态代码 typedef int Status; 2. 数据结构的表示（存储结构）用类型定义(typedef)描述。数据元素被约定为ElemType 类型，用户需要根据具体情况，自行定义该数据类型。