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

《第二部分 常用数据结构及其运算》由会员分享，可在线阅读，更多相关《第二部分 常用数据结构及其运算（293页珍藏版）》请在金锄头文库上搜索。

1、第二部分 常用数据结构及运算,中国矿业大学环境与测绘学院 2018/10/22,测绘软件设计与实现,内容概要,概述 线性表 栈与队 树与二叉树 图 查找 排序,一、概述,1 引例,在测量上，控制点的坐标通常用(x, y, z)进行表示，现在有1000个控制点坐标，要在程序中实现对其的读取、管理、存取等操作，请问：用于存储该控制点坐标的变量该如何定义？,1、引例问题求解,方法一：定义3个数组，分别存储每个控制点的x，y，z坐标； float xArray1000; float yArray1000; float zArray1000；,方法二：首先定义一个结构体变量类型，并基于此结构体变量类型定

2、义1个数组，用于存储各控制点的x，y，z坐标； tpyedef Struct float x;float y;float z; SC; SC cArray1000;,2、控制网与数据结构的关系,测量平差程序处理的对象是程序所适应的各种测量控制网问题。因此，这类程序总是同一定的网形相联系的。 一个具体的控制网通常是以图形方式直接绘出的，为了用计算机进行控制网的平差计算，就需要将具体的网形转化为一系列的数据，然后才能输入计算机进行处理。这种将网形转化为一系列数据的工作和过程称为“网形数字化”。网形数字化所得到的一组数据就是控制网的数据结构。,2、数据结构讨论的范畴,程序=数据结构+算法 数据结构：

3、问题的数据模型 数据的逻辑结构与物理结构及其二者之间的相应关系 数据的运算：对每种结构定义相适应的各种运算 分析算法的效率 算法：求解问题的策略 查找 排序,3、数据结构的学科性质,“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科 为了研究非数值运算的程序设计问题而对数据进行合理组织的方法学,4、学习数据结构的目的,了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理 通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高,“学生”表格,“课程”表格,学生选课,“选课单”包含如下

4、信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系,学生 (学号,姓名,性别,籍贯),课程 (课程号,课程名,学分),选课 (学号,课程号,成绩),？数据库逻辑设计,5、数据结构的概念及其基本术语,数据（data) 信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据,5、数据结构的概念及其基本术语,数据元素（data element） 数据结构中讨论的基本单位，也称结点（node）或记录（record） 是数据（集合）中的一个“个体” 例如：学生信息检索系统中学生信息表中的一个记录、称为一个数据元素,5

5、、数据结构的概念及其基本术语,数据项（data item） 有独立含义的数据最小单位，也称域(field) 数据元素可以是数据项的集合 数据对象 是性质相同的数据元素的集合 是数据的一个子集； 数据元素是数据对象的一个实例 例如整数数据对象是集合N=-2, -1, 0, 1, 2,“学生”表格,5、数据结构的概念及其基本术语,数据结构（data structure) 由某一数据对象及该对象中所有数据成员之间的关系组成的集合例：在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系| i=1, 2, 3, 4, 5,6、数据结构的三个方面,数据的逻辑结构从具体

6、问题抽象出来的数学模型，它与数据的存储无关 线性结构：线性表、栈、队列 非线性结构：树、图,6、数据结构的三个方面,数据的物理结构数据结构在计算机中的标识（又称映像）称为数据的物理结构，数据的逻辑结构在计算机存储器中的实现 顺序存储 链式存储 数据的运算 检索、排序、插入、删除、修改等,6.1 数据的逻辑结构,数据的逻辑结构可以用一组数据（表示为结点集合D），以及这些数据之间的一组二元关系（关系集合S）来表示：( D ，S )其中 D 是数据元素的有限集，是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据 S 是 D上关系的有限集，是定义在集合D上的一组关系，用它描述结点

7、数据之间的逻辑关系,Data_Structures = (D, S),6.2 数据的存储（物理）结构,数据的逻辑结构在计算机存储器中的实现（逻辑结构在存储器中的映象） 计算机的主存储器的特性 存储空间提供了一种具有非负整数地址编码的，相邻单元的集合 其基本的存储单元是字节 计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同,6.2 数据的存储（物理）结构,顺序存储结构 用一块无空隙的存储区域存储数据称为顺序存储 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 结点间的逻辑后继关系用存储单元的自然顺序关系来表达 链式存储结构 借助指示元素存储地址的

8、指针表示数据元素间的逻辑关系 两个结点的逻辑后继关系可以用指针的指向来表达,6.2 数据的存储（物理）结构,6.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),较常见的

9、时间复杂度,O(1)：常量型 O(n), O(n2), O(nk)：多项式型 O(log2n), O(log2n)：对数型 O(log2n)，O(en)：指数型,8、算法分析技术,空间复杂度 算法运行过程中所需的辅助空间单元（不包括问题的原始数据占用的空间）,9、补充：类的定义,class Person public: / 构造、析构函数Person() :_name(“”) / 构造函数,_age(0),_height(0.0f) / 自定义构造函数 Person() ; / 析构函数（动态分配内存的释放，如动态数组） public: / 复制构造函数与赋值运算符Person(const P

10、erson / 赋值运算符 / 其它运算符+，-，*，/ 等,9、补充：类的定义,public: / 属性/ 年龄的存取void setAge();const int getAge() const;/ 名字的存取void setName(string name);const string getName() const; private: / 成员变量string _name; / 姓名int _age; / 年龄float _height; / 身高 ;,9、补充：类的实现,复制构造函数 Person:Person(const Person ,二、线性表,1、定义与运算,定义 n（ 0）个数

11、据元素的有限序列 存储结构 向量，链表 特点 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,1、定义与运算,基本运算 插入：在两个确定元素之间插入一个新元素 删除：删除线性表中某个元素 查找：按某种要求查找线性表中一个元素 排序：按给定要求对表中元素重新排序,2、顺序存储线性表,顺序存储结构/向量式存储结构 将线性表中的元素相继存放在一个连续的存储空间中。 可利用一维数组描述存储结构设：已知线性表中每个元素占l个单元，线性表内存首地址为：adr(a1)=b，则线性表中第i个元素的存储地址为adr(ai)=adr(a1)+(

12、i-1)l,2.1 顺序表（SeqList）类的定义,template class SeqList Type *data; / 顺序表存储数组int MaxSize; / 最大允许长度 int last; / 当前最后元素下标 public:SeqList ( int MaxSize = defaultSize );SeqList ( ) delete data; int Length ( ) const return last+1; ,2.1 顺序表（SeqList）类的定义,int Find ( Type ,2.2 顺序存储结构的插入、删除,插入 线性表的插入是指在第i（1i n+1）个元

13、素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表操作：将第i至第n共（n-i+1)个元素后移,2.2.1 顺序表的插入算法,Step1：将第n至第i+1个元素后移一个存储位置; Step2：将x插入到ai-1之后; Step3：表的长度+1。 伪代码描述,Insert(int i, int ,2.2.2 顺序表的删除算法,Remove(int i) / 删除i位置的元素int k;if( i last ) / 下表以1作为起始索引printf(“表中不存在位置为i的元素 n”);exit(-1);for(k= i; k=last-1; k+) / 后面元素前移listk

14、 = lastk+1;last-; ,2.2.3 顺序表插入、删除算法的时间复杂度,顺序表的插入和删除算法，其运算时间主要消耗在移动元素上，因此，移动元素所耗费的时间，可以看做是顺序表插入和删除算法所消耗的时间。时间复杂度 T(n)=O(n),Edel=1/n*(n-1)+(n-2)+2+1+0)=(n-1)/2,2.3 顺序表的查找,25 34 57 16 48 09,0 1 2 3 4 5,data,搜索 16,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,搜索成功,2.3.1 顺序表的查找算法的伪代码,该如何写

15、？请大家自行完成 int Find ( Type& x ) / 第一步：顺序比较/ 第二步：若找到，返回/ 第三步：若线性表遍历完成，仍未找到，查找失败 ,2.2.4 顺序存储结构的优缺点,优点 直观、数据连续存放、随机存取 逻辑上相邻，物理上也相邻 存储结构简单、易实现 存储密度大，空间利用率高 缺点 插入、删除操作需要移动大量的元素 在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低 预先分配空间需按最大空间分配，利用不充分 线性表容量难以扩充 结论 顺序存储结构适合于表中元素变动较少的情况,2.3 顺序表的应用集合“并”运算,void Union ( SeqList ,2.4 顺序表的应用集合“交”运算,void Intersection(SeqList / 未找到在A中删除它 ,3、单链表,特点 每个元素(表项)由结点(Node)构成：在内存中利用存贮单元（可以不连续）来存放元素值及它在内存的地址。线性结构：逻辑相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址（指针）才能实现结点可以不连续存储 表可扩充,data link,