文档介绍：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量。。一种数据的逻辑结构根据需要可以表示成多种存储结构。而采用不同的存储结构,其数据处理的效率是不同。・线性结构又称线性表,线性结构与非线性结构都可以是空的数据结构。线性表的顺序存储结构具有以下两个基本特点:①线性表中所有元素所占的存储空间是连续的;②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。栈是一种特殊的线性表,在这种线性表的结构中,一端是封闭的,不允许进行插入与删除元素;另一端是开口的,允许插入与删除元素。先进后出或后进先出。(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。后进后出或先进先出。。元素变动频繁的大线性表不宜采用顺序存储结构,而是采用链式存储结构。在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。(tree)是一种简单的非线性结构。属于层次模型。,最多有2k-1(k^1)个结点。性质2深度为in的二叉树最多有2"-1个结点。性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。15・二叉树的遍历可以分为三种:前序遍历(中前后)、中序遍历(前中后)、后序遍历(前后中)。16・下列两种情况只能用顺序查找:1)如果线性表是无序表(即表中的元素是无序的),则不管是顺序存储结构还是链式存储结构,都只能容书讯查找。2)即使是有序线性表,如果采用的是链式存储结构,也只能用顺序查找。二分法查找只能在顺序存储的结构的有序表中进行(也就是只适用于顺序存储的线性表,且表中元素必须按关键字有序排列一一允许相邻元素相等)。对于无序线性表和线性表的链式存储结构只能用顺序查找。,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。在最坏情况下,冒泡排序需要比较次数为n(n-l)/2o在最坏情况下,简单插入排序需要n(「I)/2次比较。在最坏情况下,堆排序需要比较的次数为0(nlog2n)。著名的“清晰第一,效率第二”的论点已成为当今主导的程序设计风格。结构化程序设计方法的主要原则可以概括为自顶向下,逐步求精,模块化,限制使用goto语句。结构化程序设计的三种基本结构分别是:顺序结构、选择结构和循环结构。25・对象的基本特征有:乩标识惟一性;b•分类性;c•多态性;d•封装性;。软件工程的核心思想是把软件产品看做是一个工程产品来处理。软件的三个要素:程序、数据和文档。软件工程的三个要素:方法、工具和过程。软件生命周期就是软件产品从提出、实现、。三个阶段:软件生命周期包括软件定义、软件开发及软件维护三个阶段。软件工程管理包括软件管理学、软件工程经济学、软件心理学。(设计、编码、测试):(DFD)、数据字典(DD)、判定树需求分析方法有:①结构化分析方法②面向对象的分析方法从需求分析建立的模型的特性来分,需求分析方法又分为静态分析方法和动态分析方法。和判定表。其中最重要的工具是数据流图。数据流图中的主要图形元素与说明如下:力口工数据流存储文件源、潭O加工(转换):输入数据经加工变换产生输出。数据流:沿箭头方向传送数据的通道,一般在旁边标注数据流名。存储文件(数据源):表示处理过程中存放各种数据的文件。源,潭:表示系统和环境的接口,属系统之外的实体。软件需求规格说明书(SRS)是需求分析阶段的最后结果,是软件开发中的重要文档之一。:是一个模块内部各个元素间彼此结合的紧密程度的度量;耦合IKl=J三i性:是多个模块之间互相连接的紧密程度的度量。一般较优秀的软件设计,应尽量做到高内聚,低耦合,有利于提高模块的独立性。。:图形工具:程序流程图,N-S,PAD,HIPOo表格工具:判定表。语言工具:PDL(伪码)。。。、静态结构分析、,发现错误而执行程序的过程。,方法有逻辑覆盖测试和基本路径测试