第二部分 常用数据结构及其运算

第二部分 常用数据结构及运算中国矿业大学环境与测绘学院2012/9/20测绘软件设计与实现内容概要内容概要 概述 线性表 栈与队 树与二叉树 图 查找 排序一、概述1 引例引例 在测量上，控制点的坐标通常用 (x, y, z)进行表示，现在有 1000个控制点坐标，要在程序中实现对其的读取、管理、存取等操作，请问：用于存储该控制点坐标的变量该如何定义？1、引、引 例例 问题求解问题求解 方法一：定义 3个数组，分别存储每个控制点的 x， y， z坐标； float xArray1000; float yArray1000; float zArray1000； 方法二：首先定义一个结构体变量类型，并基于此结构体变量类型定义 1个数组，用于存储各控制点的 x， y， z坐标； tpyedef Struct float x;float y;float z; SC; SC cArray1000;2、控制网与数据结构的关系 测量平差 程序处理的对象是程序所适应的各种测量控制网问题。因此，这类程序总是同一定的网形相联系的 。 一 个具体的控制网通常是以图形方式直接绘出的，为了用计算机进行控制网的平差计算，就需要将具体的网形转化为一系列的数据，然后才能输入计算机进行处理。这种将网形转化为一系列数据的工作和过程称为 “ 网形数字化 ” 。网形数字化所得到的一组数据就是控制网的数据结构 。2、数据结构讨论的范畴、数据结构讨论的范畴 程序 =数据结构 +算法数据结构： 问题的数据模型数据的逻辑结构与物理结构及其二者之间的相应关系数据的运算：对每种结构定义相适应的各种运算分析算法的效率算法： 求解问题的策略查找排序3、数据结构的学科性质、数据结构的学科性质 “ 描述现实世界实体的数学模型 (非数值计算 )及其上的操作在计算机中如何表示和实现 ” 的学科 为了研究非数值运算的程序设计问题而对数据进行合理组织的方法学4、学习数据结构的目的、学习数据结构的目的 了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理 通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高“学生学生 ”表格表格“课程课程 ”表格表格学生选课学生选课“选课单选课单 ”包含如下信息包含如下信息学号学号 课程编号课程编号 成绩成绩 时间时间学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生(学号 ,姓名 ,性别 ,籍贯 )课程(课程号 ,课程名 ,学分 )选课(学号 ,课程号 ,成绩 )？ 数据库逻辑设计5、数据结构的概念及其基本术语、数据结构的概念及其基本术语数据（ data)信息 的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合 。数值性数据非数值性 数据5、数据结构的概念及其基本术语、数据结构的概念及其基本术语数据元素（ data element）数据结构中讨论的基本单位 ，也称结点（ node） 或记录（ record）是数据（集合）中的一个 “ 个体 ”例如：学生信息检索系统中学生信息表中的一个记录、称为一个数据 元素5、数据结构的概念及其基本术语、数据结构的概念及其基本术语 数据项（ data item）有独立含义的数据最小单位，也称域 (field)数据元素可以是数据项的集合 数据对象是 性质相同的数据元素的集合是 数据的一个子集 ； 数据元素是数据对象的一个实例例如整数数据对象是集合 N=-2, -1, 0, 1, 2“学生学生 ”表格表格5、数据结构的概念及其基本术语、数据结构的概念及其基本术语 数据结构（ data structure)由某一数据对象及该对象中所有数据成员之间的关系组成的集合例： 在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系 | i=1, 2, 3, 4, 56、数据结构的三个方面、数据结构的三个方面 数据的逻辑结构从具体问题抽象出来的数学模型，它 与数据的存储无关线性结构：线性表、栈、队列非线性结构：树、图6、数据结构的三个方面、数据结构的三个方面 数据的物理结构数据结构在计算机中的标识（又称映像）称为数据的 物理结构， 数据的逻辑结构在计算机存储器中的实现顺序存储链式存储 数据的运算检索、排序、插入、删除、修改等6.1 数据的逻辑结构数据的逻辑结构 数据的逻辑结构可以用一组数据（表示为结点集合 D），以及这些数据之间的一组二元关系（关系集合 S）来表示： ( D ， S )其中D 是数据元素的有限集， 是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据S 是 D上关系的有限集， 是定义在集合 D上的一组关系，用它描述结点数据之间的逻辑关系Data_Structures = (D, S)6.2 数据的存储（物理）结构数据的存储（物理）结构 数据的逻辑结构 在计算机存储器中的实现（ 逻辑结构在存储器中的映象 ） 计算机的主存储器的特性存储空间提供了一种具有 非负整数地址编码的，相邻单元的集合其基本的存储单元是 字节计算机的指令具有 按地址随机访问存储空间内任意单元的能力 ，访问不同地址所需的访问时间基本相同6.2 数据的存储（物理）结构数据的存储（物理）结构 顺序存储结构用一块无空隙的存储区域存储数据称为顺序存储借助元素在存储器中的相对位置来表示数据元素间的逻辑关系结点间的逻辑后继关系用存储单元的自然顺序关系来表达 链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系两个结点的逻辑后继关系可以用指针的指向来表达6.2 数据的存储（物理）结构数据的存储（物理）结构LoLo+mLo+(i-1)*mLo+（ n-1)*m存储地址 存储内容Loc(元素 i)=Lo+（ i-1)*m顺序存储元素 1元素 2元素 i元素 nhead6.3 逻辑结构与物理结构之间的关系逻辑结构与物理结构之间的关系算法 设计 逻辑 结构算法实现 存储 结构 7、算法描述语言（伪代码语言）、算法描述语言（伪代码语言） 不直接用于计算机，却能简单明了地描述算法本身 其本身可简单、可详细 可以将其翻译为能够在不同编译环境下运行的计算机程序8、算法分析技术、算法分析技术 时间复杂度for i=1 to nfor j=1 to nBi,j=0 （ 频度 n2）for k=1 to nBi,j=Bi,j+Ai,k*Ak,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(log2n)， O(en)：指数型8、算法分析技术、算法分析技术 空间复杂度算法运行过程中所需的辅助空间单元（不包括问题的原始数据占用的空间）9、补充：类的定义、补充：类的定义class Personpublic: / 构造、析构函数Person() :_name(“”) / 构造函数,_age(0),_height(0.0f) / 自定义构造函数 Person() ; / 析构函数（动态分配内存的释放，如动态数组）public: / 复制构造函数与赋值运算符Person(const Person / 复制构造函数public: / 运算符Person/ 赋值运算符 / 其它运算符 +， -， *， / 等9、补充：类的定义、补充：类的定义public: / 属性/ 年龄的存取v