[新大纲] 2 数据结构概述.ppt

第二部分数据结构 主讲教师 王永波ybwang 中国矿业大学环境与测绘学院2013年10月26日 提纲 概述线性表栈与队树与二叉树图查找排序 一 概述 1引例 在测量上 控制点的坐标通常用 x y z 进行表示 现在有1000个控制点坐标 要在程序中实现对其的读取 管理 存取等操作 试问 用于存储该控制点坐标的变量该如何定义 1引例 问题求解 方法一 定义3个数组 分别存储每个控制点的x y z坐标 方法二 首先定义一个结构体变量类型 并基于此结构体变量类型定义1个数组 用于存储各控制点的x y z坐标 floatxArray 1000 floatyArray 1000 floatzArray 1000 tpyedefStruct floatx floaty floatz SC SCptArray 1000 2 数据结构讨论的范畴 程序 数据结构 算法数据结构 问题的数据模型数据的逻辑结构与物理结构及其二者之间的关系数据的运算 对每种结构定义与之相应的各种运算分析算法的效率算法 求解问题的策略查找排序 3 数据结构的学科性质 描述现实世界实体的数学模型 非数值计算 及其上的操作在计算机中如何表示和实现的学科为了研究非数值运算的程序设计问题而对数据进行合理组织的方法学 4 学习数据结构的目的 了解计算机处理对象的特性 将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理通过算法训练来提高思维能力 通过程序设计的技能训练来促进综合应用能力和专业素质的提高 学生 表格 课程 表格 学生选课 选课单 包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系 学生 学号 姓名 性别 籍贯 课程 课程号 课程名 学分 选课 学号 课程号 成绩 数据库逻辑设计 5 数据结构的概念及其基本术语 数据 data 信息的载体 是描述客观事物的数 字符 以及所有能输入到计算机中 被计算机程序识别和处理的符号的集合 数值型数据非数值型数据 5 数据结构的概念及其基本术语 数据元素 dataelement 数据结构中讨论的基本单位 也称为结点 node 或记录 record 是数据 集合 中的一个 个体 例如 学生信息检索系统中学生信息表中的一个记录 称为一个数据元素 5 数据结构的概念及其基本术语 数据项 dataitem 有独立含义的数据最小单位 也称域 field 数据元素可以是数据项的集合数据对象性质相同的数据元素的集合数据的一个子集 数据元素是数据对象的一个实例例如整数数据对象是集合N 2 1 0 1 2 学生 表格 5 数据结构的概念及其基本术语 数据结构 datastructure 由某一数据对象及该对象中所有数据成员之间的关系组成的集合例 在一维数组 a1 a2 a3 a4 a5 a6 的数据元素之间存在如下的次序关系 i 1 2 3 4 5 6 数据结构的三个方面 数据的逻辑结构从具体问题抽象出来的数学模型 它与数据的存储无关线性结构 线性表 栈 队列非线性结构 树 图 6 数据结构的三个方面 数据的物理结构数据结构在计算机中的标识 又称映像 称为数据的物理结构 数据的逻辑结构在计算机存储器中的实现顺序存储链式存储数据的运算检索 排序 插入 删除 修改等 6 1数据的逻辑结构 数据的逻辑结构可以用一组数据 表示为结点集合D 以及这些数据之间的一组二元关系 关系集合S 来表示 D S 其中D是数据元素的有限集 是由有限个结点组成的集合 每一个结点都代表一个数据或一组有明确结构的数据S是D上关系的有限集 是定义在集合D上的一组关系 用它描述结点数据之间的逻辑关系 Data Structures D S 6 2数据结构分类 线性结构线性表 栈 队非线性结构树 图 20 6 3数据的存储 物理 结构 数据的逻辑结构在计算机存储器中的实现 逻辑结构在存储器中的映象 计算机的主存储器的特性存储空间提供了一种具有非负整数地址编码的 相邻单元的集合其基本的存储单元是字节计算机指令具有按地址随机访问存储空间内任意单元的能力 访问不同地址所需的访问时间基本相同 6 3数据的存储 物理 结构 顺序存储结构用一块无空隙的存储区域存储数据称为顺序存储借助元素在存储器中的相对位置来表示数据元素间的逻辑关系结点间的逻辑后继关系用存储单元的自然顺序关系来表达链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系两个结点的逻辑后继关系可以用指针的指向来表达 6 3数据的存储 物理 结构 6 4逻辑结构与物理结构之间的关系 7 算法描述语言 伪代码语言 不直接用于计算机 却能简单明了地描述算法本身其本身可简单 可详细可以将其翻译为能够在不同编译环境下运行的计算机程序 8 算法分析技术 空间复杂度 Spacecomplexity 当问题的规模以某种单位从1增加到n时 解决这个问题的算法在执行时所占用的存储空间也以某单位由1增加到S n 则称此算法的空间复杂度为S n 时间复杂度 Timecomplexity 当问题的规模以某种单位从1增加到n时 解决这个问题的算法在执行时所耗费的时间也以某单位由1增加到T n 则称此算法的空间复杂度为T n 26 8 算法分析技术 渐进 时间复杂度fori 1tonforj 1tonB i j 0 频度n2 fork 1tonB i j B i j A i k A k j 频度n3 end k end j end i 时间复杂度以算法中频度最大的语句来度量 又称渐进时间复杂度 记作 T n O F n 较常见的时间复杂度 O 1 常量型O n O n2 O nk 多项式型O log2n O log2n 对数型O en 指数型 8 算法分析技术 空间复杂度算法运行过程中所需的辅助空间单元 不包括问题的原始数据占用的空间 9 补充 类的定义 classPerson public 构造 析构函数Person name 构造函数 age 0 height 0 0f 自定义构造函数 Person 析构函数 动态分配内存的释放 如动态数组 public 复制构造函数与赋值运算符Person constPerson 9 补充 类的定义 public 属性 年龄的存取voidsetAge constintgetAge const 名字的存取void