测绘软件设计和实现重点

1、5测绘软件设计和实现第一部分 绪论和软件工程概述1、软件危机的定义： 在计算机软件的开发和维护过程中遇到的一系列严重问题以及软件开 发的高成本与低质量之间的矛盾。1）与软件本身的特点有关； （ 2）与软件开发与维护的方法不正2、软件危机产生的原因： 确有关。1）用现代工程的概念、原理、技术和方法进软件开发、管理和 （ 3）技术措施（方法、工具） 。（概括其任务）3、克服软件危机的途径： 维护；（2）组织管理措施；4、软件生命周期的阶段划分（1）问题定义： 通过调研，写出关于问题性质、工程目标和工程规模的书面报告，并得到 客户的确认；（2）可行性研究： 研究并论证软件系统的可行性， 对方案进行选

2、择并形成可行性分析报告， 包括：技术、经济、操作、调度、社会可靠性；总体设计： 设计程序的体系结构，确定程序由哪些模块组成以及模块间的关系详细设计： 解法具体化，模块详细设计，编制模块的详细规格说明； 编码和单元测试： 详细设计的结果翻译成用选定的语言书写的程序，对模块程序进行 验证模块功能及接口与详细设计文档的一致性，并形成单元测试报告综合测试： 通过各种类型的测试（及相应的调试）使软件达到预定的要求 运行与维护： 通过各种必要的维护活动使系统持久地满足用户的需要。（3）需求分析： 以一种清晰、简洁、一致且无二义性的方式，对一个待开发系统中各个有 意义方面的陈述的一个集合，建立逻辑模型，书写

3、规格说明书；（4）（5）（6） 测试，（7）（8）5、黑盒测试白盒测试比较（1）综合测试中包括： 黑盒测试、白盒测试 。（2）黑盒测试®是功能测试，通过测试来检测每个功能是否都能正常使用。在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试， 它只检查程序功能是否按照需求规格说明书的规定正常使用， 程序是否能适当地接收输入数据而产生正 确的输出信息。3 黑盒测试着眼于程序外部结构，不考虑内部逻辑结构， 主要针对软件界面和软件功能进行测试。（3）白盒测试1 结构测试、逻辑驱动测试。检验程序中2 通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行， 的每条通路是否都

4、能按预定要求正确工作。3 测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例， 对程序所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。6、软件测试方法的分类综合测试分为：集成测试、验收测试、现场测试和平行运行。第二部分 常用数据结构及其运算1、程序 =数据结构 +算法。 数据结构：问题的数据结构（1）数据的逻辑结构与物理结构及其二者之间的相应关系；（2）数据的运算：对每种结构定义相适应的各种运算;（3）分析算法的效率。 数据结构概念：由某一数据对象及该对象中所有数据成员之间的关系组成的集合。2、数据结构的分类：（1）逻辑结构： 从具体问题抽象出来的数

5、学模型，它与数据的存储无关。 线性结构：线性表、栈、队列非线性结构：树、图（2）物理结构： 数据结构在计算机中的标识（又称映像）称为数据的物理结构，是数据的 逻辑结构在计算机存储器中的实现。包括顺序存储和链式存储。（3）两者之间的关系算法设计7逻辑结构算法实现7存储结构逻辑结构属于用户的视图， 是面向对象的; 物理结构属于具体实现的视图， 是面向计算机的。3、数据的存储（物理）结构（ 1） 顺序存储结构1 用一块无空隙的存储区域存储数据称为顺序存储;2 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系;3 结点间的逻辑后继关系用存储单元的自然顺序关系来表达。（ 2） 链式存储结构1 借助

6、指示元素存储地址的指针表示数据元素间的逻辑关系;2 两个结点的逻辑后继关系可以用指针的指向来表达。4、线性表：n （仝0）个数据元素的有限序列 比较顺序存储线性表和链式存储线性表（单链表）（1）顺序存储结构 / 向量式存储结构1 将线性表中的元素相继存放在一个连续的存储空间中；2 可利用一维数组描述存储结构。1 直观、数据连续存放、随机存取；2 逻辑上相邻，物理上也相邻；3 存储结构简单、易实现；4 存储密度大，空间利用率高。1 插入、删除操作需要移动大量的元素；在顺序表中插入或删除一个元素，平均移动表的一半元素，当n很大时，效率很低;3 预先分配空间需按最大空间分配，利用不充分；4 线性表容

7、量难以扩充。 顺序存储结构适合于表中元素变动较少的情况。优点：缺点：特点：结论：（2）单链表（链式存储）特点：每个元素（表项）由结点（Node）构成：在内存中利用存贮单元（可以不连续）来存放 元素值及它在内存的地址；从一个元素找下一个线性结构：逻辑相邻的元素存放到计算机内存后不一定相邻， 元素必须通过地址（指针）才能实现；3 2 数据非连续存放、顺序存取；4 表可扩充。5 逻辑上相邻，物理上不一定相邻。优点：插入、删除操作极为方便无需事先了解线性表的长度，允许线性表的长度有很大变化当读操作比插入删除操作频率大时，缺点： 存储结构较复杂、需要额外的存储空间 结论：链表存储结构适合于表中元素频繁变

8、动的线性表； 不适合使用链表。5、链表（单链表、循环链表、双循环链表）有无头结点（1）单链表（ 59）：表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。（2）循环链表循环链表为空的条件：headf .next=head（3）双循环链表双循环链表为空的条件head t .prior = head t .next = head6、栈与队： 栈和队列是两种特殊的线性表，是操作受限的线性表，是限定插入和删除只能 在表的“端点”进行的线性表。7、栈 （1）只允许在一端插入和删除的线性表（2） 允许插入和删除的一端称为栈顶（ top），另

9、一端称为栈底（bottom）（3）特点：先进后出（FILO）;后进先出（LIFO）。8、栈的表达式求值 一个表达式由操作数 （亦称运算对象 ）、操作符 （亦称运算符 ） 和分界符组成。 算术表达式有三种表示：（ 1）中缀（ infix ）表示A+B；操作数 操作符 操作数 ，如（ 2）前缀（ prefix ）表示+AB；操作符 操作数 操作数 ，如（ 3）后缀（ postfix ）表示AB+；操作数 操作数 操作符 ，如9、中缀、后缀转换（ 1）后缀转中缀。后缀表达式： ABCD-*+EFAG/宀中缀表达式：A+B*（C-D）-（EAF）/G算法：顺序扫描表达式的每一项。如果是操作数（如 A、

10、B）,进栈；如果是操作符0p （如 +、-）则依次退栈两个操作数丫和X,形成XopY,再将计算结果进栈。（ 2）利用栈将中缀表示转换为后缀表示中缀表达式： A+B*（C-D）-（EF）/G 7后缀表达式：ABCD-*+EFG/-isp 叫做栈内（ in stack priority ）优先数icp 叫做栈外（ in coming priority ）优先数。操作符ch;(A*, /, %+,-)isp(栈内)017538icp (栈外)086421算法：(1) 操作符栈初始化，将结束符;进栈。然后读入中缀表达式字符流的首字符(2) 重复执行以下步骤，直到ch =，;同时栈顶的操作符也是；停止循

11、环。若ch是操作数直接输出，读入下一个字符ch。若ch是操作符，判断ch的优先级icp和位于栈顶的操作符 op的优先级isp：1)2)3)符ch。若 若 若 ch。icp (ch) > isp (op)令ch进栈，读入下一个字符 icp (ch) < isp (op)退栈并输出。icp (ch) = isp (op),退栈但不输出，若退出的是"('号读入下一个字ch。(3 )算法结束，输出序列即为所需的后缀表达式。10、顺序栈的约束机制(1)(2)(3)链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头适合于多栈操作若base的值为NULL

12、,则表明栈结构不存在若top=base可作为栈空的标志栈顶指针top 初值为-1to p=-1,栈空，此时出栈，则下溢( undeflow) top=M-1,栈满，此时入栈，则上溢( overflow)非空栈中的栈顶指针始终在栈顶元素的下一个位置上 插入新的栈顶元素时，指针top增1删除栈顶元素时，指针top减111、链式栈存储结构(1)(2)(3)(4)12、 队列：队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表 的后端(rear)进行插入操作。队尾(rear)允许插入的一端队头(front)允许删除的一端13、假溢出(顺序队列)(1) 概念：随着元素不断入队列

13、、出队列，rear和front指针会不断向后移动，最终会指向数组的最大下标位置。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置，这种情况称为假溢出。当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front -1,rear=M-1时，再有兀素入队发生溢出假溢出(2) 避免假溢出的方法当rear = MAXSIZE+1时，即超过队列末端时，令rear = 1;从而使队列的首尾相连接。用表达式描述:if (rear > MAXSIZE rear = 1 ;elserear = rear + 1 ;使用循环队列可以避免假溢出入队：

14、rear=(rear+1)%M; sqrear=x; 出队：fron t=(fro nt+1)%M;x=sqfro nt;14、数与二叉树树：一类重要的非线性数据结构，以分支关系来定义的层次结构。 树的术语：(1)(2)(3)(4)(5)(6)(7)(8)结点：表示树中的元素，包括数据项+若干指向其子树的分支。例如:结点的度(degree)：结点拥有的子树数(如 A的结点度为3)。 叶子(leaf):度为0的结点(无后继结点)(如K，L，M)。 孩子(child):结点子树的根称为该结点的孩子。例：结点 双亲(Parents)：孩子结点的上层结点。例：子结点兄弟(sibling):同一双亲的孩

15、子。例：A, B,C等。树的度：一棵树中最大的结点度数。例：树的度为 结点的层次(level):从根结点算起，根为第一层，A的子结点为C, B, D的父结点为 H, I, J互为兄弟3它的孩子为第二层(如阶层B，C,A有结点A,阶层2有结点B, C, D)(9) 树的深度(depth)：树中结点的最大层次数。例如 的树深度为1，图中树的深度为4(10) 根结点：无前趋结点(或无父结点)的结点。例：:空树的深度为0，只有一个根结点A结点(11) 森林(forest): m(m仝0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合 即为森林(12) 和C(13)(14)(15)祖先：由某结点

16、到根结点之路径上的所有结点均为该结点的祖先。例:支结点：度不为0的结点为支结点。例：B，C，D等路径：结点的序列n1, n2,nk(K仝1)是一条路径 有序：如果将树中结点的各子树看成从左至右是有顺序的(即不能互换)为有序树。否则，称为无序树。(16) 有序树：如果将树中结点的各子树看成从左至右是有顺序的 树为有序树。否则，称为无序树。(17) 有向树：有确定的根，树根和子树根之间为有向关系(18) 无序树：子树之间不存在确定的次序关系(即不能互换)G祖先为A，则称该树，则称该:数组表示法、链表表示法、二叉链表表示法。15、树的表示(树的存储结构) 要求：能够实现树的表示法与树的图形结构之间的

17、转换。(1)数组表示法：用数组存储树的结点信息，在每个结点中附设一个指示器指示其双亲结【9点在数组中的位置。结点序号123456789双亲011223555特点：找根容易，找子结点难，要遍历整个数组（2）链表表示法（孩子表示法）把每个结点的孩子结点排列起来，组成一个线性表且以单链表作为存储结构。 n个结点有n个孩子链表。Qh7 1-4_心 1*1£.4)特点：便于实现对孩子的操作 ，却不便于对父亲的操作。（3）二叉链表实现方式（孩子兄弟表示法）553<6特点:便于实现各种树的操作16、二叉树的性质（结点的度为性质1: 二叉树的第i层上至多有2i-1个结点（i性质2：深度为k的二

18、叉树上至多含性质3:对任何一棵二叉树，若它含有系式：n0 = n2+1。性质4：具有n个结点的完全二叉树的深度为Llog2n+1性质5 （完全二叉树）如果将一棵有n个结点的完全二叉树从上到下，0、 1、 2)1）2k-1个结点（k> 1）n0个叶子结点、n271个度为2的结点，则必存在关从左到右对结点编号1 ,2 ,n,然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简 称编号为j的结点为j （ lWj勺，！则有如下结论成立：若j=1，则结点j为根结点，无双亲，否则 j的双亲为b/2若2j 则结点j的左孩子为2j,否则无左孩子。即满足2j>n的结点为叶子结点若2j+1

19、W,则结点j的右孩子为2j+1，否则无右孩子若结点j序号为奇数且不等于1，则它的左兄弟为j-1若结点j序号为偶数且不等于n,它的右兄弟为j+1结点j所在层数（层次）为log2j +117、满二叉树：是深度为k且含有2k-1个结点的二叉树。必须是二叉树的每一层上的结点 数都达到最大，否则就不是满二叉树。18、完全二叉树：深度为k的二叉树T每层结点数目若满足：第i层（1 <i <k-1）上的结点个数均为2i-1（非叶结点）;第k层从右边连续缺若干个结点（即只能从右至左不间断缺少）特点（1）叶子结点只可能在层次最大的两层上出现（2） 对任一结点，若其右分支下子孙的最大层次为I，则其左分支

20、下子孙的 最大层次必为I或1+1。完全.二支树0满二叉树19、满二叉树 VS完全二叉树（1）满二叉树- 1定是一 -棵完全二叉树，反之完全二叉树不- 定是 -棵满二叉树（2）满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层20、二叉树的遍历方法（1 ）先序遍历先访问根结点，然后分别先序遍历左子树、右子树 根结点最先遍历（2 ）中序遍历先中序遍历左子树，然后访问根结点，最后中序遍历右子树 根在中间（3 ）后序遍历例题：如图 先序遍历： 中序遍历： 后序遍历： 给定中序，先后序遍历左、右子树，然后访问根结点 根在最后A B D E H I J K C F GD B H E

21、 J I K A F C G D H J K I E B F G C A先序或后序中的一个，将树画出来。21、二叉排序树 概念（1）（2）（3）中序所得到的所有结点从小到大的结果 （理解）：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树22、哈夫曼树：带权路径长度最短的树。树的带权路径长度：树中所有带权结点的路径长度之和构造哈夫曼树。23、图的特点图是对结点的前趋和后继个数不加限制的数据结构，是一种更为复杂的非线性数据结构。图中

22、各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。24、有向图与无向图的区别有向图：一条边x, 丫与y, x表示的结果不相同，用尖括号表示x, y表示从顶点x发向顶点y的边，x为始点，y为终点有向边也称为弧，则 x, y表示为x为弧尾，y为弧头的一条弧，而y, x表示y为弧尾，x 为弧头的另一条弧无向图：一条边（x, 丫）与（y, X）表示的结果相同，用圆括号表示25、图的遍历：深度优先搜索遍历、广度优先搜索遍历【例】深度优先搜索遍历V1个邻接点V2个邻接点V1已访问，取下一个邻接点V4个邻接点V2已访问，取下一个邻接点V8个邻接点V4已访问，取下一个邻接点V51111起始顶点V1的

23、第V2的第V4的第V8的第回退到V8,V4,V2,V1,回退到，回退到，回退到V3未被访问V1已被访问，V6未被访问 回退到 V3V7未被访问 回退到 V3 回退到 V1V5的两个邻接点均被访问，V8的邻接点均被访问，V4的邻接点均被访问V2的邻接点均被访问V1的另一个邻接点V3的第一个邻接点V6的邻接点被访问，V3的另一个邻接点V7的邻接点被访问，V3的邻接点被访问，回退到V1，返回到出发点，遍历结束深度优先遍历结果：V1, V2,V4, V8 ,V5 ,V3 ,V6 ,V7【例】广度优先搜索遍历起始顶点V1访问V1的未被访问过的所有邻接点访问V2的未被访问过的所有邻接点访问V3的未被访问过

24、的所有邻接点访问V4的未被访问过的所有邻接点访问V5的未被访问过的所有邻接点所有顶点已被访问，结束广度优先遍历结果：V1,V2,V3,V4,V5,V6,V7,V826、图的应用最小生成树Kruskal算法和 Prim算法（书 P371）表述过程，基于此算法算例子。27、平均查找长度 ASL为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值，对含有n个数据元素的查找表，查找成功时的平均查找长度为ASL =2 PC。其中：n为表长，Pi为查找表中第i个记录的概率，且",C为找到该记录时，曾和£ P1给定值比较过的关键字的个数。28、查找算法 折半查找（二分查找）（

25、书P302）可以明显减少比较次数，提高查找效率二分查找的先决条件是查找表中的数据元素必须有序二叉查找树（书 P308）29、排序交换（冒泡）排序：是依次两两比较待排序元素若为逆序（递增或递减）则进行交换，每趟冒泡都将待排序列中的最大关将待排序元素从左至右比较一遍称为一趟“冒泡”键字交换到最后（或最前）位置直到全部元素有序为止快速排序（P405）基本思想：通过一趟排序，将一个无序区分割成两个独立的无序子区，其中，前一部分子区中所有元素关键字均不大于后一部分子区中元素关键字，然后对每一个子区再进行分割，直到整个线性表有序为止。第三部分常用数值计算方法1、数值计算的若干原则（不背）当消元按自然顺序进行时， 称为高斯顺2、高斯顺序消去法（不背，思想） 消去法就是按特定的顺序进行的矩阵初等