还剩31页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
第一章数据结构与算法
一、算法、算法是指解题方案的准确而完整的描述
1、算法不等于程序，也不等计算机方法，程序的编制不也许优于算法的设计
2、算法的基本特性是一组严谨地定义运算顺序的规则，每一个规则都是有效的，3是明确的，此顺序将在有限的次数下终止特性涉及（）可行性；1（）拟定性，算法中每一环节都必须有明拟定义，不充许有模棱两可的解释，不允2许有多义性；（）有穷性，算法必须能在有限的时间内做完，即能在执行有限个环节后终止，涉3及合理的执行时间的含义；（）拥有足够的情报
4、算法的基本要素一是对数据对象的运算和操作；二是算法的控制结构
4、指令系统一个计算机系统能执行的所有指令的集合
5、基本运算和操作涉及算术运算、逻辑运算、关系运算、数据传输
6、算法的控制结构顺序结构、选择结构、循环结构
7、算法基本设计方法列举法、归纳法、递推、递归、减斗递推技术、回溯法
8、算法复杂度算法时间复杂度和算法空间复杂度9■算法时间复杂度是指执行算法所需要的计算工作量■算法空间复杂度是指执行这个算法所需要的内存空间
二、数据结构的基本基本概念■、数据结构研究的三个方面■）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；1步将逐渐减小，并逐次比较与直到发现一个为止，将♦4j Pj T,PjT
①移到⑴位置上P P将逐渐减小，并逐次比较与直到发现一个为止，将♦5i Pi T,P6T⑴移到
①位置上P P上述两个操作交替进行，直到指针与指向同一个位置即为止，此时将♦i ji=j Pi的位置上分割需要记忆，用栈来实现、插入类排序法2简朴插入排序法1所谓插入排序，是指将无序序列中的各元素依次插入到已有序的线性表中一般来说，假设线性中前元素已有序，现在要将线性表中第个元素插入到前面的有j-1j序子表中，插入过程如下将第个元素放到一个变量中，然后从有序子表的最后一个元素即线性表中第j Tj-1个元素开始，往前逐个与进行比较，将大于的元素均依次向后移动一个位置，直到T T发现一个元素不大于为止，此时就将即原线性表中的第个元素插入到刚移出的T Tj空位置上，有序子表的长度就变为了效率与冒泡法相同j在最坏情况下，简朴插入排序需要次比较nn-l/2希尔排序法2基本思想如下将整个无序序列分割成若干小的子序列分别进行插入排序子序列的分割方法如下将相隔某个增量的元素构成一个子序列在排序过程中，逐次减小这个增量,最H后当减到时，进行一次插入排序，排序就完毕增量序列一般取H1h=n/2kk=l,2,…[k g2n],其中为待排序序列的长度n其效率与增量序列有关在最坏情况下，需要的比较次数为O N
15、选择类排序法3简朴选择排序法1基本思想扫描整个线性表，从中选出最小的元素，将它互换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止简朴选择排序法在最坏情况下需要比较/次nn-l/2堆排序法2方法一方面将一个无序序列建成堆♦然后将堆顶元素序列中的最大项与堆中最后一个元素互换最大项应当在序♦列的最后不考虑已经换到最后的那个元素，只考虑前个元素构成的子序，n-1显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆反复做第步，真到剩下的子序列为空为止合用规模较大的线性表，♦2在最坏情况下，堆排序需要比较的次数为O nlog2n第章程序设计基础2
一、程序设计方法与风格就程序设计方法和技术的发展而言，重要通过了结构化程序设计和面向对象的程序设计阶段一程序设计风格一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思绪程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应当强调得意和清楚，程序必须是可以理解的要形成良好的程序设计风格，重要应注重和考虑下述一些因素、源程序文档化
1、源程序文档化应考虑如下几点2符号名的命名符号名的命名应具有一定的实际含义，以便于对程序功能的理解1程序注释下克的注释可以帮助读者理解程序2礼堂组织为使程序的结构一目了然，可以在程序中运用空格、空行、缩进待技3巧使程序层次清楚二数据说明的方法在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护一般应注意如下几点数据说明的顺序规范化鉴于程序理解、新闻记者和维护的需要，使数据说明顺序1固定，可以使数据的发生容易查找，也有助于测试、排错和维护说明语句中变量安排有序化当一个说明语句说明多个变量时，变量按照字母2顺序为好使用注释来说明复杂数据的结构3三语句的结构程序应当简朴易懂，语句构造应当简朴直接，不应当为提高效率而把语句复杂化一般应注意如下在一行内只写一条语句；1程序编写应优先考虑清楚性；2除非对效率有特殊规定，程序编写要做清楚第一，效率第二；3一方面要保证程序对的，然后才规定提高速度；4避免使用临时变量而使程序的可读性下降；5避免不必要的转移；6尽也许使用库函数；7避免采用复杂的条件语句；8尽量减少使用“否认”条件的条件语句；9数据结构要有助于程序的简化;10（）要模块化，使模块功能尽也许单一化；11（）保证每一个模块的独立性；12（）从数据出发去构造程序；13（）不要修补不好的程序，要重新编写；14
（四）输入和输出无论是批解决的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应当考虑如下原则（）对所有的输入数据都要检查数据的合法性；1（）检查输入项的各种重要组合的合理性；2（）输入格式要简朴，以使得输入的环节和操作尽也许简朴；3（）输入数据时，应允许使用自由格式；4（）应允许缺省值；5（）输入一批数据时，最佳使用输入结束标志；6（）在以交互式输入/输出方式进行输入时，要在屏幕上使用提醒符明确提醒输入的7请求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息（）当程序设计语言对输入格式有严格规定期，应保持输入格式与输入语句的一致8性；给所有的输入出加注释，并设计输出报表格式
二、结构化程序设计
（一）构化程序设计的原则结构化程序设计方法的重要原则可以概括为自顶向下，逐步求精，模块化，限制使用语句goto、自顶向下程序设计时，应先考虑总体，后考虑细节；先考虑全局目的，后1考虑局部目的不要一开始就过多追求众多的细节，先从最上层总目的开始设计，逐步使问题具体化、逐步求精对复杂问题，应设计一些子目的作过渡，逐步细化
2、模块化一个复杂问题，肯定是由若干稍简朴的问题构成模块化是把程序要解3决的总目的分解为分目的，再进一步分解为具体的小目的，把每个小目的称为一个模块、限制使用语句4goto
（二）结构化程序的基本结构与特点、顺序结构顺序结构是简朴的程序设计，它是最基本、最常用的结构，所谓顺序1执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序、选择结构选择结构又称为分支结构，它涉及简朴选择和多分支选择结构，这种2结构可以根据设定的条件，判断应当选择哪一条分支来执行相应的语句序列、反复结构反复结构又称为循环结构，它根据给定的条件，判断是否需要反复执3行某一相同的或类似的程序段，运用反复结构可简化大量的程序行分为两类一是先判断后执行，一是先执行后判断优点一是程序易于理解、使用和维护二是编程工作的效率，减少软件开发成本
（三）结构化程序设计原则和方法的应用要注意把握如下要素、使用程序设计语言中的顺序、选择、循环等有限的控制结构表达程序的控制逻辑
1、选用的控制结构只准许有一个入口和一个出口；
2、程序语句组成容易辨认的块，每块只有一个入口和一个出口;
3、复杂结构应当嵌套的基本控制结构进行组合嵌套来实现;
4、语言中所没有的控制结构，应当采用前后一致的方法来模拟；
5、严格控制语句的使用其意思是指6GOTO（）用一个非结构化的程序设计语言去实现一个结构化的构造；1（）若不使用语句会使功能模糊；2GOTO（）在某种可以改善而不损害程序可读性的情况下3
三、面向对象的程序设计
（一）关于面向对象方法面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来结识、理解和描述客观事物，强调最终建立的系统可以映射问题域，也就是说，系统中的对象以及对象之间的关系可以如实地反映问题域中固有事物及其关系优点、与人类习惯的思维方法一致
1、稳定性好
2、可重用性好3软件重用是指在不同的软件开发过程中反复作用相同或相似软件元素的过程重用是提高软件生产率的最重要的方法、易于开发大型软件产品
4、可维护性好5（）用面向对象的方法开发的软件稳定性比较好1（）用面向对象的方法开发的软件比较容易修改；2（）用面向对象的方法开发的软件比较容易理解3（）易于测试和调试4
（二）面向对象方法的基本概念对象（）1object对象是面向对象方法中最基本的概念对象是对问题域中某个实体的抽象，设立某个对象就反映软件系统保存有关它的信息并具有与它进行交互的能力对象可以做的操作表达它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务属性即对象所包含的信息，它在设计对象时拟定，一般只能通过挂靠对象的操作来改变操作描述了对象执行的功能，若通过消息传递，还可认为其他对象使用操作的过程对外是封闭的，即用户只能看到这一操作实行后的结果这相称于事先已经设计好的各种过程，只需要调用就可以了，用户不必去关心这一过程是如何编写的事实上，这个过程已经封装在对象中，用户也看不到对的这一特性即是对象的封装性、类（）和实例（）2Class Instance类是具有共同属性、共同方法的对象的集合所以,类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其相应类的一个实例例如是一个整数类，它描述了所有整数的性质因此任何整数都是整数类Integer的对象，而一个具体的整数是类的实例“123”Integer由类的定义可知，类是关于对象性质的描述，它同对象同样，涉及一组数据属性和在数据上的一组合法操作、消息（）3Message消息是一个实例与另一个实例之间传递信息,它请示对象执行某一解决或回答某一规定的信息，它统一了数据流的控制流消息的使用类似于函数调用，消息中指定了某一个实例，一个操作名和一个参数表（可空）接受消息的实例执行消息中指定的操作，并将形式参数数与参数表中相应的值结合起来消息传递过程中，由发送消息的对象（发送对象）的触发操作产生输出结果，作为消息传送至接受消息的对象（接受对象），引发接受消息的对象一系列的操作所传送的消息实质上是接受对象所具有的操作/方法名称，有时还涉及相应参数通常，一个消息由下述三部分组成（）接受消息的对象的名称；1（）消息标记符（也称为消息名）；2（）零个或多个参数
3、继承（）4Inheritance继承是面向对象的方法的一个重要特性广义地说，继承是指可以直接获得已有的性质和特性，而不必反复定义它们继承具有传递性，假如类继承类类继承类则类继承类因此一个类C B,B A,C A事实上继承了它上层的所有基类的特性，也就是说，属于某类的对象除了具有该类所定义的特性外，还具有该类上层所有基类定义的特性继承分为单继承与多重继承单继承是指，一个类只允许有一个父类，即类等级为树形结构多重继承是指，一个类允许有多个父类多重继承的类可以组合多个父类的性质构成所需要的性质、多态性（）5Polymorphism对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性第章软件工程基础3
一、软件工程基本概念
（一）软件定义与软件特点计算机软件是计算机系统中与硬件互相依存的另一部分，是涉及程序、数据及相关文档的完整集合基中，程序是软件开发人员根据用户需求开发的用程序设计语言描述的、适合计算机执行的指令（语句）序列数据是使程序能正常操纵信息的数据结构文档是与程序开发、维护和使用有关的图文资料可见软件由两部分组成一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运营、维护、使用等有关的文档软件按功能可以分为应用软件、系统软件、支撑软件（或工具软件）应用软件为解决特定领域的应用而开发的软件系统软件计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件支撑软件介于系统软件和应用软件之间，协助用户开发软件的工具性软件，涉及辅助和支持开发和维护应用软件的工具软件
（二）软件危机与软件工程软件工程概念的出现源自软件危机所谓有软件危机四伏是泛指在计算机软件开发和维护过程中所碰到的严重问题具体地说，在软件开发和维护过程中，软件危机重要表现在（）软件需求的增长得不到满足用户对系统不满意的情况经常发生1（）软件开发成本和进度无法控制开发成本超过预算，开发周期大大超过规定2（）在对数据进行解决时，各数据元素在计算机中的存储关系，即数据的存储结2构;（）对各种数据结构进行的运算
3、数据结构是指互相有关联的数据元素的集合
2、数据的逻辑结构包含3（）表达数据元素的信息；1（）表达各数据元素之间的前后件关系
2、数据的存储结构有顺序、链接、索引等
4、线性结构条件5（）有且只有一个根结点；1（）每一个结点最多有一个前件，也最多有一个后件
2、非线性结构不满足线性结构条件的数据结构6
三、线性表及其顺序存储结构、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的1相对位置是线性的、在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构2成的线性表又称为文献、非空线性表的结构特性3（）且只有一个根结点它无前件；1al,（）有且只有一个终端结点它无后件；2an,（）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后3件结点个数称为线性表的长度，当时，称为空表n n=
0、线性表的顺序存储结构具有以下两个基本特点:日期的情况经常发生4（）软件质量难以保证3（）软件不可维护或护限度非常低4（）软件的成本不断提高5（）软件开发生产率的提高赶不上硬件的发展和应用需求的增长6总之，可以将软件危机归结为成本、质量、生产率等问题软件工程就是试图用工程、科学和数学的大批量与方法研制、维护计算机软件的有关技术及管理方法软件工程涉及个要素即方法、工具和过程方法是完毕软件工程项目的技术手3段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理软件工程的核心思想是把软件产品看作是一个工程产品来解决
（三）软件生命周期通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期软件生命周期分为软件定义、软件开发及软件运营维护三个阶段软件生命周期的重要活动阶段是（）可行性研究与计划制定拟定待开发软件系统的开发目的和总的规定，给出它1的功能、性能、可靠性以及接口等方面的也许方案，制定完毕开发任务的实行计划（）需求分析对待开发软件提出的需求进行分析并给出具体定义编写软件规格2说明书及初步的用户手册，提交评审（）软件设计系统设计人员和程序设计人员应当在反复理解软件需求的基础上,3给出软件的结构、模块和划分、功能的分派及解决流程在系统比软件复杂的情况下,设计阶段可分解成概要设计阶段和具体设计阶段编写概要设计说明书、具体设计说明书和测试计划初稿，提交评审（）软件实现把软件设计转换成计算机可以接受的程序代码即完毕源程序的编4码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划（）软件测试在设计测试用例的基础上，检查软件的各个组成部分编写测试分析5报告（）运营和维护将已交付的软件投入运营，并在运营使用中不断地维护，根据新6进出的需求进行必要并且也许的扩充和删改
（四）软件工程的目的与原则、软件工程的目的1软件工程的目的是，在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品软件工程需要达成的基本目的应是付出较低的开发成本；达成规定的软件功能;取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能准时完毕开发,及时交付使用、软件工程的原则2为了达成上述的软件工程目的，在软件开发过程中，必须遵循软件工程的基本原则这些基本原则涉及抽象、信息隐蔽、模块化、局部化、拟定性、一致性、完备性和可验证性（）抽象抽取事物最基本的特性和行为，忽略非本质细节采用分层次抽象，自顶1向下，逐层细化的办法控制软件开发过程的复杂性（）信息隐蔽采用封闭技术，将程序模块的实现细节隐藏起来，使模块接口尽量2简朴（）模块化模块是程序中相对独立的成分，一个独立的编程单位，应有良好的接口3定义模块的大小要适中，模块过大会使模块内部的复杂性增长，不得对模块的理解和个性也不得模块的调试和重用模块太小会导致整个系统表达过于复杂，不利于控制系统的复杂性（）局部化规定在一个物理模块内集中逻辑上互相关联的计算资源，保证模块间4具有松散的耦合关系，模块内部有较强的内骤性，这有助于控制角的复杂性（）拟定性软件开发过程中所有概念的表达应是拟定的、无歧义且规范的这有助于5人与人的交互不会产生误解和漏掉，以保证整个开发工作的协调一致（）一致性指程序、数据和文档的整个软件系统的各模块应使用已知的概念、符6号和术语；程序内外部接口应保持一致，系统规格说明与系统行为应保持一致（）完备性软件系统不丢失任何重要成分，完全实现系统所需的功能7（）可验证性开发大型软件系统需要对系统自顶向下，逐层分解系统分解应遵8循容易检查、测评、评审的原则，以保证系统的对的性
二、结构化分析方法、关于结构化分析方法1结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用对于面向数据流的结构化分析方法，按照的定义，”结构化分析就是使用DeMarco数据流图（）、数据字典（）、结构化英语、鉴定表和羊定树等工具，来建立一种DFD DD新的、称为结构化规格说明的目的文档”结构化分析方法的实质是着眼于数据流、自顶向下，逐层分解，建立系统的解决流程，以数据流图和数据字典为重要工具建立系统的逻辑模型、结构化分析的常用工具2数据流图1DFD—Data FlowDiagram数据流图是描述数据解决过程的工具，是需求理解的逻辑模型的图形表达，它直接支持系统的功能建模数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程数据流图中的重要图形元素与说明如下加工转换输入数据经加工变换产生输出数据字典2DD—Data Dictionary数据字典是结构化分析方法的核心数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解数据字典中有中类型的条目数据流、数据项、数据存储和加工4鉴定树3使用鉴定树进行描述时，应先从问题定义的文字描述中分清哪些是鉴定的条件，哪些是鉴定的结论，根据模仿材料中的连接词找出鉴定条件之间的从属关系、并列关系、选择关系，根据它们构造鉴定树鉴定表4鉴定表与鉴定树相似，当数据流图中的加工要依赖于多个逻辑条件的联欢会，即完毕该加工的一组动作是由于某一组条件联欢会的组合而引发的，使用鉴定表描述比较适宜鉴定表由四部分组成，基本条件，条件项，基本动作，动作项三软件需求规格说明书软件需求规格说明书是需求分析阶段SRS,software RequirementSpecification的最后成果，是软件开发中的文档之一软件需求规格说明书的特点
①对的性体现待开发系统的真实规定
②无歧义性对每一个需求只有一种解释，其陈述具有惟一性
③完整性涉及所有故意义的需求，功能的、性能的、设计的、约束的，属性或外部接口等方面的需求
④可验证性描述的每一个需求都是可以验证的，即存在有限代价的有效过程验证确认
⑤一致性各个需求的描述不能矛盾
⑥可理解性需求说明书必须简明易懂，尽量少包含计算机的要领和术语，以便用户和软件人员都能接受它
⑦可修改性和课追踪性每一个需求的来源、流向是清楚的，当产生和改变文献编制时，可以方便地引证每一个需求
三、软件设计
（一）软件设计的基本概念、软件设计的基础1软件设计是软件工程的重要阶段，软件设计是拟定系统的物理模型■从技术观点来看，软件设计涉及软件结构设计、数据设计、接口设计、过程设计结构设计是定义软件系统各重要部件之间的关系;■数据设计是将分析时创建的模型转化为数据结构的定义；■接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信;■过程设计则是把系统结构部件转换成软件的过程性描述、从工程管理角度来看，软件设计分两步完毕概要设计和具体设计2概要设计（又称结构设计）将软件需求转化为软件体系结构、拟定系统级接旦、♦全局数据结构或数据库模式;具体设计确立每个模块的实现算法和局部数据结构,用适当方法表达算法和数据结♦构的细节
（二）软件设计的基本原理、软件设计遵循软件工程的基本目的和原则，建立了合用于在软件设计中应当遵循1的基本原理和与软件设计有关的概念（）抽象1软件设计中考虑模块化解决方案时，可以定出多个抽象级别抽象的层次从概要设计到具体设计逐步减少（）模块化2模块化是指把一个待开发的软件分解成若干个小的简朴的部分模块化是指解决一个复杂问题时自顶向下逐层把软件系统划提成若干模块的过程（）信息隐蔽3信息隐蔽是指，在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的（）模块独立性4模块独立性是指，每个模块只完毕系统规定的独立的子功能，并且与其他模块的联系最少且接口简朴是评价设计好坏的重要度量标准、衡量软件的模块独立性作用耦合性和内聚性两个定性的度量标准2（）内聚性内聚性是一个模块内部各个元素间彼此结合的紧密限度的度量内聚是1从功能角度来度量模块内的联系内聚有如下的种类，它们之间的内聚性由弱到强排列为偶尔内聚逻辑内聚时间内聚过程通信内聚顺序内聚功能内聚（）耦合性耦合性是模块间互相连接的紧密限度的度量2耦合性取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口耦合可以分为下列几种，它们之间的耦合度由高到低排列为内容耦合公共耦合外部耦合控制耦合标记耦合数据耦合非直接耦合在程序结构中，各模块的内聚性越强，则耦合性越弱一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有得提高模块的独立性
四、软件测试
（一）软件测试的目的给出了软件测试的目的软件测试是为了发现程序中的错误而执行Grenford J.Myers程序的过程；一个好的测试用例子指很也许找到迄今为止尚未发现的错误的用例；一个成功的测试是发现了至今尚未发现的错误的测试的观点告诉人们测试要以查找错误为中心，而不是为了演示软件的对的功能Myers
（二）软件测试的准则、所有测试都应追溯到需求1软件测试的目的是发现错误，而最严惩的错误不外乎是导致程序无法满足用户需求的错误、严格执行测试计划，排除测试的随意性2软件测试应当制定明确的测试计划并按照计划执行测试计划应涉及所测软件的功能、输入和输出、测试内容、各项测试的目的和进度安排、测试资料、测试工具测试用例的选择、资源规定、测试的控制方式和过程等、充足注意测试中的群集现象3经验表白，程序中存在错误的概率与该程序中已发现的错误数成正比这一现象说明，为了提高测试效率，测试人员应当集中对付那些错误群集的程序、程序员应避免检查自己的程序4为了达成好的测试效果，应当由独立的第三方来构造测试由于从心理学角度讲,程序人员或设计方在测试自己的程序，要采用客砚的态度是程序不同地存在障碍的、穷举测试不也许5所谓穷举测试是指把程序所有也许的执行途径都进行检查的测试但是，即使规模较小的程序，其途径排列数也是相称大的，在实际测试过程中不也许穷尽每一种组合这说明，测试只能证明程序中有错误，不能证明程序中没有错误、妥善保存测试计划、测试用例、犯错记录和最终分析报告，为维护提供方便6三软件测试技术与方法综述若从是否需要执行被测软件的角度，可以分为静态测试和动态测试方法若按照功能划分可以分为白盒测试和黑盒测试方法、静态测试与动态测试1静态测试1静态测试涉及代码检查、表态结构分析、代码质量度量等代码检查涉及代码审查、代码走查、桌面检查、静态分析等具体方式动态测试2静态测试不实际运营软件，重要通过人工进行动态测试是基于计算机的测试，是为了发现错误而执行程序的过程设计高效、合理的测试用例是动态测试的关键测试用例是为测试设计的数据测试用例由测试输入数据和与之相应的预期输出结果两部分组成测试用例的格式为［（输入值集），（输出值集）］、白盒测试方法2白盒测试方法也称结构测试或逻辑驱动测试它是根据软件产品的内部工作过程，检查内部万分，以确认每种内部操作符合设计规格规定白盒测试把测试对象看作一个打开的盒子，允许测试人员运用程序内部的逻辑结构及有送信息来设计或选择测试用例，对程序所有的逻辑途径进行测试通过在不同点检查程序的状态来了解实际的运营状态是否与预期的一致所以，白盒测试是在程序内部进行，重要用于完毕软件内部操作的验证白盒测试的基本原则是保证所测模块中每一独立途径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性白盒测试的重要方法有逻辑覆盖、基本途径测试等黑盒测试方法与测试用例设计
3.黑盒测试方法也称功能测试或数据驱动测试黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明所以，黑盒测试是在软件接口处进行，完毕功能验证黑盒测试只检查程序功能是否按照需求规格说明书的规定政党使用，程序是否能适本地接输入数据而产生对的的输出信息并且保持外部信息（如数据库或文献）的完整性黑盒测试重要诊断功能不对或漏掉、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错黑盒测试方法重要有等价类划分法、边界值分析法、错误推测试法、因果图等.
（四）软件测试的实行软件测试过程一般按个环节进行，即单元测试，集成测试、验收测试（确认测试）4和系统测试、单元测试1单元测试是对软件设计的最小单位——模块（程序单元）进行对的性检查的测试单元测试的目的是发现各模块内部也许存在的各种错误单元测试的依据是具体设计说明书和源程序单元测试的技术可以采用静态分析和动态测试对动态测试通常以白盒动态测试为主，辅之以黑盒测试集成测试
2.集成测试是测试和组装软件的过程它是把模块在按照设计规定组装起来的同时进行测试，重要目的是发现与接口有关的错误集成测试的依据是概要设计说明书集成测试所涉及的内容涉及软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试等集成测试时效模块组装成程序通常采用两种方式非增量方式组装与增量方式组装非增量方式也称为一次性组装方式将测试好的每一个软件单元一次组装在一起再进行整体测试增量方式是将已经测试好的模块逐步组装成较大系统，在组装过程中边连接边测试，以发现连接过程中产生的问题最后通过增殖，逐步组装至所规定的软件系统（）线性表中所有元素的所占的存储空间是连续的;1（）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的2的存储地址为（）（）（）（）为第一个元素的地址，代表每个ai ADRai=ADR al+i-l k,,ADR alk元素占的字节数、顺序表的运算插入、删除（详见页）514-16
四、栈和队列、栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶,不1允许插入与删除的另一端称为栈底、栈按照“先进后出”（）或“后进先出（）组织数据，栈具有记忆作用2FILO LIFO用表达栈顶位置，用表达栈底top bottom、栈的基本运算（）插入元素称为入栈运算；（）删除元素称为退栈运算；（）3123读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化、队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表4指针指向队尾，指针指向队头Rear front、队列是“先进行出（）或“后进后出”（）的线性表5FIFO LILO队列运算涉及（）入队运算从队尾插入一个元素；（）退队运算从队头删除一个元12素、循环队列表达队列空，且表达队列满6s=0s=l front=rear
五、线性链表、数据结构中的每一个结点相应于一个存储单元，这种存储单元称为存储结点,简1称结点结点由两部分组成（）用于存储数据元素值，称为数据域；（）用于存放指针,称12为指针域，用于指向前一个或后一个结点增量方式涉及自顶向下、自底向上、自顶向下与自底向上相结合的混合增量方法确认测试
3.确认测试的任务是验证软件功能和性能及其他特性是否满足了需求规格说明中拟定的各种需求，以及软件配置是否完全、对的确认测试的实行一方面运用黑盒测试方法，对软件进行有效性测试，即验证被测试软件是否满足需求规格说明确认的标准复审的目的在于保证软件配置齐全、分类有序，以及软件配置所有成分的完备性、一致性、准确性和可操作性，并且涉及软件维护所必需的细节、系统测试4系统测试是将通过测试确认的软件，作为整个基于计算机系统的一个元素，与计算机硬件、外设、支持软件、数据和人员等其他系统元素组合在一起，在实际运营（使用）环境下对计算机系统进行一系列的集成测试和确认测试由此可知，系统测试必须在目的环境下运营，其功用在于评估系统环境下软件的性能，发现和捕获软件中潜在的错误系统测试的目的是在真实的系统工作环境下检查软件是否能与系统对的连接，发现软件与系统需求不一致的地方系统测试的具体实行一般涉及功能测试、性能测试、操作测试、配置测试、外部接□测试、安全性测试等
五、程序的调试
（一）基本概念在对程序进行了成功的测试之后将进入程序调试（通常称即排错）Debug,程序调试的任务是诊断和改正程序中的错误调试重要在开发阶段由程序调试的概念可知，程序调试活动由两部分组成，其一是根据错误的迹象拟定程序中错误的确切性质、因素和位置其二，对程序进行修改，排除这个错误
（二）程序调试的基本环节、错误定位1从错误的外部表现形式入手，研究有关部分的程序，拟定程序中犯错位置，找犯错误的内在因素拟定错误位置占据了软件调试绝大部分的工作量、修改设计和代码，以排除错误
2、进行回归测试，防止引进新的错误3
（三）软件调试方法调试的关键在于推断程序内部的错误位置及因素从是否跟踪和和执行程序的角度，类似于软件测试，软件调试可以分为静态调试和动态调试软件测试中讲座的表态分析方法同样合用静态调试静态调试重要指通过人的思维来分析源程序代码和排错，是重要的调试手段，而动态调试是辅助静态调试的重要的调试方法可以采用、强行排错法
1、回溯法
2、因素排除法
3、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺2序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来拟定的、链式存储方式即可用于表达线性结构，也可用于表达非线性结构
3、线性链表，称为头指针，（或）称为空表，假如是两指针4HEAD HEAD=NULL0左指针（）指向前件结点，右指针（）指向后件结点Llink Rlink线性链表的基本运算查找、插入、删除
六、树与二叉树、树的基本概念1■在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根■在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点没有后件的结点称为叶子结点■在树结构中，一个结点所拥有的后件个数称为该结点的度■叶子结点的度为0■树的最大层次称为树的深度、在一个算术表达式中，有运算符和运算对象一个运算符可以有若干个运算对象2例职，取正（+）等只有一个运算对象，称为单目运算符；二个运算对象称为双目运算符，三目运算符用树来表达算术表达式的原则如下■表达式中的每一个运算符在树中相应一个结点，称为运算符结点■运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）■运算对象中的单变量均为叶子结点、二叉树及其基本性质3（）什么是二叉树1二叉树是一种很有用的非线性结构二就树具有以下两个特点非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树由以上特点可以看出，在二叉树中，每一个结点的度最大为即所有子树（左子树2,或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的此外，二叉树中的每一个结点的子树被明显地分为左子树与右子树可以没有其中的一个，也可以全没有（）二叉树的基本性质2性质在二叉树的第层上，最多有（）个结点1K KN1性质浓度为的二叉树最多有个结点2M2m-l深度为的二叉树是指二叉树共有层m m性质在任意一棵二叉树中度为的结点（即叶子结点）总是比度为的结点多302一个性质具有个结点的二叉树，其深度至少为［］其中［）］表达取的整数4n log2n+l,k g2n部分（）满二叉树与完全二叉树3满二叉树与完全二叉树是两种特殊形态的二叉树满二叉树所谓满二叉树是指这样的一种二叉树；除最后一层外，每一层上的所有结点都有两个子结点这就是说，在满二叉树中，每一层上的结点数都达成最大值，即在满二叉树的第层上有个结点，且深度为的满二叉树有个结点K2K-1m2m-1完全二叉树4所谓完全二叉树是指这样的二叉树，除最后一层外，每一层上的结点数均达的最大值；在最后一层上只缺少右边的若干结点确切地说，假如从根结点起，对二叉树的结点自上而下、自左至右用自然数进行边疆编号，则深度为、且有个结点的二叉树，当且仅当其每一个结点都与深度为的m nm满二叉树中编号从到的结点一一相应时，称之为完全二叉树1n对于完全二叉树来说，叶子结点只也许在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为则其左分支下的子孙结点的最大层次或为p,，或为P p+1由满二叉树与完全二叉树的特点可以看出,满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树完全二叉树还具有以下两个性质性质具有个结点的完全二叉树的深度为[5n log2n]+l性质设完全二叉树共有个结点假如从根结点开始，按层序每一层从左到右6n用自然数，给结点进行编号，则对于编号为的结点有以下结论1,2,…n kk=l,2,...n若则该结点为根结点，它没有父结点；若则该结点的父结点编号为k=l,kl,INTk/20若则编号为的结点的左子结点编号为；否则该结点无左子结点显然也2kSn,k2k没有右子结点若则编号为的结点的右子结点编号为；否则该结点无右子结点2k+lSi,k2k+l二叉树的存储结构5（）二叉树的遍历6二叉树的遍历是指不反复地访问二叉树的所有结点在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树前序遍历（）♦DLR所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，一方面访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树F,C,A,D,B,E,G,H,P中序遍历（）♦LDR所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，一方面遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树A,C,B,D,F,E,H,G,P后序遍历（）♦LRD所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，一方面遍历左子树，然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点
七、查找技术A,B,D,C,H,P,G,E,F、顺序查找1顺序查找又称顺序搜索顺序查找一般是指在线性表中查找指定的元素，其基本方法如下从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较,若相等则表达找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表达线性表中没有要找的元素（即查找失败）顺序查找的效率是很低的以下两种情况只能采用顺序查找假如线性表无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找即使是有序线性表，假如采用链式存储结构，也只能用顺序查找、二分法查找2二分法查找只合用于存储的有序表在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，但允许相邻元素值相等）设有序线性表的长度为被查元素为则对分查找的方法如下n,x,将与线性表的中间项进行比较♦x若中间项的值等于则说明查到，查找结束；♦x,若小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同♦x的方法进行查找；若大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同♦x的方法进行查找这个过程一直进行到查找成功或子表长度为（说明线性表中没有这个元素）为♦0止显然，当有序线性表为顺序存储时才干采用二分查找，并且，二分查找的效率要比顺序查找高得多可以证明，对于长度为的有序线性表，在最坏情况下，二分查找只n需要比较次，而顺序查找需要比较次log2n n
八、排序技术、互换类排队序法1所谓互换类排序法是指借助数据元素之间的互相互换进行排序的一种方法冒泡排序法与快速排序法都属于互换类的排序方法（）冒泡排序法1基本过程如下:一方面，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的♦大小若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序放最大值然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元♦素的大小若相邻两个元素中，后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序放最小值反复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序♦假设线性表的长为则在最坏情况下，冒泡排序需要通过遍的葱馨往后的扫描n,n/2和遍的从后往前的扫描，需要的比较的次数为n/2nn-l/2o快速排序法2快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快，因此称之为快速排序法基本思想如下从线性表中选取一个元素，设将线性表后面小于的元素移到前，而前大于的T,T T元素移支后面，结果就将线性表提成了两部分称为两个子表，插入到其分界线的位T置处，这个过程称为线性表的分割通过对线性表的一次分割，就以为分界线，将线T性表提成了前后两个子表，且前面子表中的所有元素均不大于而后面子表中的所有元T,素均不小于T如此反复，则此时的线性表就变成了有序表环节一方面，在表的第一个，中间一个与最后一个元素中选取中项，设为并将♦PK,赋给再将表中的第一个元素移到的位置上P KT,P K然后设立两个指针和分别指向表的起始与最后的位置反复操作以下两♦i j。
个人认证
优秀文档
获得点赞 0
