C语言基础知识.doc

基本数据结构与算法算法是应用项目研制软件的基础，也可以是计算机系统中为解决某个具体问题而建立的一套方法，即对解题方案的准确而完整的描述。算法分为数值型算法与非数值型算法。算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。基本的算法（操作）有插入、删除、替换、查找和排序。数据结构的运算（操作）时通过算法描述的。算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的特征：可行性、确定性、有穷性、输入、输出。算法若用机器可执行语言来描述，则是一个程序。算法的基本要素包括两点，一是对数据对象的运算和操作，二是算法的控制结构。对数据的运算和操作有算术运算、逻辑运算、关系运算和数据传输。算法的描述可以采用语言、图形和表格方式。每个算法是计算机可以执行的以指令的形式描述的基本操作。一个计算机系统能执行的所有指令的集合，称为指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。算法的控制结构是指算法中各操作之间的执行顺序。一个算法一般都可以由顺序、选择和循环三种基本控制结构组合而成。描述算法的工具通常有传统的流程图、结构化流程图和算法描述语言等。判断算法性能的标准是：正确性；可使用性；可读性；健壮性；效率。算法设计基本方法包括以下几点：列举法、归纳法、递推法、减半递推技术、回溯法。算法分析的目的是确定一个算法的优劣。算法的分析主要是分析算法所占用的计算机资源，即算法在计算机上运行时所占用的时间和存储空间的度量。算法分析的结果一般是一个复杂的表达式。算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。对于算法所需存储空间的量度称为空间复杂度。是指执行这个算法所需要的内存空间，包括算法程序、输入的初始数据以及算法执行过程中所需要的附加空间。附加空间是指算法程序执行过程中的工作单元以及某种数据结构所需要的空间。通常采用压缩存储技术，以便尽量减少不必要的附加空间。数据是描述客观事物的数、字符以及所有能被计算机识别、存储和加工处理的符号集合。数据元素是数据的基本单位，即数据集合中的个体。在不同的条件下，数据元素有可称为元素、结点、顶点和记录等。一个数据元素可由若干个数据项组成，数据项是具有独立含义的数据的最小单位，有时也把数据项称为域或字段等。有记录所组成的线性表称为文件。数据对象是具有相同特征的数据元素的集合，是数据的子集。数据结构就是带有结构特性的数据元素的集合。数据结构概念一般包括三个方面的内容：数据之间的逻辑结构、数据在计算机中的存储方式（也称为存储结构或物理结构）以及在这些数据上定义的运算的集合。数据结构可以看作是相互间存在特定关系的数据元素的集合。根据数据元素之间的关系的不同特性，数据的逻辑结构可分为线性结构和非线性结构。线性结构：数据元素之间的关系是一对一的，可用一个线性序列表示出来。线性表、数组、堆栈、队列等属于线性结构。非线性结构：树、二叉树和图等都属于非线性结构。数据元素之间的逻辑关系，即为前后件关系。数据的存储结构是数据逻辑结构在计算机存储器里的实现。在数据的存储结构中，不仅哟啊存放各数据元素的信息，还需要存放各数据之间的前后件关系的信息。最主要的存储结构：顺序存储结构（数据元素之间的关系由存储单元的邻接关系来体现。）链式存储结构（每个数据元素中至少包含两个域，一个存放数据值的数据域，另一个是指针域，用指针来体现呢数据元素之间的逻辑关系。）有时为了查找的方便还采用索引存储和散列存储。数据的运算定义在数据的逻辑结构上，而实现是在存储结构上。主要的运算包括插入、删除、排序和查找等。常用的各种数据结构有线性表、堆栈、队列和链表等。实现这些数据结构的各种算法几乎都立足于计算机系统结构只提供按地址访问的一维线性存储器以及最基本、最简单的数据表示，数据表示指的是能有硬件直接辨认的数据类型。、 数据结构的二元组表示法、 图形表示法（在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称叶子结点）。数据结构中除了根结点与终端结点外其他结点一般称为内部结点。数据结构的基本运算：插入、删除、查找、分类、合并、分解、复制和修改等。计算机的基本数据类型有逻辑数、定点数、浮点数、十进制数、字符串和数组等。在线性结构中，开始结点和终端结点都是唯一的，除了开始结点和终端结点外，其余结点都有且仅有一个前件，有且仅有一个后件，数据元素之间为一对一的关系。非线性结构又可以细分为树形结构和图形结构两类。在树形结构中，每个结点最多只有一个前件，但可以由多个后件，数据元素之间为一对多的关系，可以由多个终端结点。非线性结构的树形结构称为树。在图形结构中，每个结点的前件和后件的个数都可以是任意的，数据元素之间为多对多的关系。因此，可能没有开始结点和终端结点，也可能有多个开始结点、多个终端结点。图形结构简称为图。线性结构是树形结构的特殊情况，而树形结构又是图形结构的特殊情况。没有一个数据元素的数据结构称为空的数据结构。线性结构与非线性结构都可以是空数据结构。线性表是一类数据结构的统称，栈结构、队列结构和链表结构等都是线性表。同一线性表中的元素必定具有相同特征，属于同一数据对象。线性表中所含元素的个数叫做线性表的长度。对于一个非空线性表有如下一些结构特征：、 有且只有一个跟结点，它无前件；、 有且只有一个终端结点，它无后件；、 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表是一个具有相同特征的个数据元素的有限序列。线性表是最简单、最基本、最常用的一类线性数据结构。它的基本操作树插入、删除、检索和排序等。线性表的顺序存储用一段地址连续的存储单元，依次存储线性表里各元素的存储结构，称作线性表的顺序存储结构。它的特点是线性表的元素的逻辑顺序与其各元素的存储顺序是一致的。在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有：插入、删除、查找、排序、分解、合并、复制和逆转等。顺序表的插入与删除运算。栈是限定仅在表的一端（表尾）进行插入或删除操作的线性表，该端称为栈顶；另一端为栈底。不含数据元素的栈称为空栈。先进后出“栈基本运算：入栈运算；退栈运算；读栈顶元素。队列简称队，队列是一种允许在表的一端进行插入，而在另一端进行删除的线性表。允许插入的一端为队尾，常用队尾指针的指针指向队尾元素，即队尾指针总是指向最后被插入的元素；允许删除的一端称为排头，常用一个排头指针指向排头元素的前一个位置。“先进先出“在实际应用中，队列的顺序存储结构一般采用循环队列的形式。若队列元素长度为，队列最多容纳个元素。循环队列是指将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。循环队列的初始状态为空，即循环队列主要有两种基本运算：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。当时，则置每进行一次退队运算，排头指针就进一。当时，则置在循环列队中，当时，不能确定是队列满还是队列空。队列空的条件为；队列满的条件为，而且假设循环队列的初始状态为空，即，而线性表的链式存储结构称为线性链表。数据结构中的每一个数据结点对应于一个存储结点，简称结点。每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。链式存储结构既可用于表示线性结构，也可用于表示非线性结构。在用链式存储结构表示较复杂的非线性结构时，其指针域的个数要多一些。线性表中最后一个结点没有后件，因此，线性链表中最后一个结点的指针域为空，表示链表终止。在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向前件结点；另一个称为右结点，用以指向其后件结点，这样的线性链表称为双向链表。链表的优点是插入、删除等操作不需要移动元素，只需要修改指针，比较灵活，缺点是不可随即存取。栈也是线性表，也可以采用链式存储结构，链式存储的栈也叫链式栈或带链的栈。带链的栈可用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。可利用栈是动态的。树是一种简单的非线性结构。数据元素之间的关系具有明显的层次特征。在树结构中，每一个结点只有一个前件，称为父结点。在树中，没有前件的结点只有一个，称为树的根结点，简称为树的根。每一结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度。叶子结点的度为零。树中所有结点的度的最大值称之为树的度。度大于的结点称之为分支结点或非终端结点。度为的结点称为叶子结点或终端结点。一个结点的后件结点称之为该结点的孩子结点。一个结点称为其后件结点的双亲结点。具有同一双亲的结点互称为兄弟结点。树中结点的最大层数称为树的深度或高度。个或多个不相交的树的集合称为森林。树的表示有树表示法（这是树的最基本表示，用一棵倒置的树表示树结构非常直观和形象。）、文氏图表示法（使用集合以及集合的包含关系描述树结构）、凹入表示法（使用线段的伸缩描述树结构）和括号表示法（将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号隔开来描述树结构）。算法分析的目的是分析算法的效率以求改进算法。对算法的分析主要是分析算法所占用的计算机资源（时间代价和空间代价）。它们反映的是算法在计算机上运行时所占用的时间和存储空间的度量。程序=数据结构+算法，可读性与可移植性一般是对程序而言；改进算法，提高效率是算法设计基本思想。算法设计的核心是提高算法效率，而算法分析的目的正是分析算法的效率，以求改进得到最优算法。衡量算法空间复杂度主要是看算法运行时数据所占的存储空间 。数据元素是数据的基本单位，即数据集合中的个体。在不同的条件下，数据元素又可称为元素、结点、顶点或记录等。一个数据元素可由若干个数据项组成，数据项是具有独立的数据的最小单位，有时也把数据项称为域、字段等。由记录所组成的线性表称为文件。数据结构的基本任务：定义数据的逻辑结构（数据之间的逻辑关系）；定义数据的存储结构（也称物理结构）；定义数据的运算（也称为操作）。算法和程序是不同的，程序不一定能满足动态有穷，有可能不会终止，如操作系统。数据的存储结构是逻辑结构在计算机存储器中的存储方式，它包括数据结构中元素的表示及元素间关系的表示，正是数据的物理结构。程序不等于算法，程序只是算法的一种实现，由于程序依赖于一定的运行环境，因此不可能优于算法。数据的存储结构是数据在计算机中的存储方式。对于不同的存储方式，数据的访问速度差异很大，因此数据处理的效率与存储结构密切相关。数据的存储结构在计算机中所占的空间与采用算法有关，所占的空间不一定是连续的。数据的逻辑结构是各数据元素之间的逻辑关系，在计算机中可以采用多种存储方式。在查找数据时，顺序存储比链式存储的速度要快很多。一种逻辑结构可以对应多种存储结构。例如，线性表，可以采用顺序存储也可以采用链式存储来实现。常用的线性结构：线性表、数组、堆栈、队列、串。非线性结构：树（二叉树）、图。线性表可以采用链式存储，各个结点之间通过指针保证逻辑上的线性关系。线性表可以采用链式存储，各个结点之间通过指针保证逻辑上的线性关系。而物理上各个结点的存储位置是随机的，可能是连续的，也可能不是连续的。线性表采用顺序存储时，地址必须是连续的；线性表 采用顺序存储时线性链表中的表头元素一定存储在其他元素的前面；在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的。采用链表来表示线性表时，链表的各元素之间逻辑上市线性的，但在具体的存储位置上是随机的。栈具有记忆作用。栈由于是“后进先出”，因此在操作系统中，使用栈来处理各种中断，响应中断前系统将各种状态值压入栈，中断执行结束后，从栈中读出系统状态值，恢复中断前的工作。栈和队列都具有插入、删除操作，并且在插入数据前要判断还是链式存储都需要考虑栈或队列是否为空（下溢）。常见的采用链式存储的线性结构有：线性链表、带链的队列和带链的栈等；而非线性结构一般都采用链式存储。树是最典型的描述层次关系的数据结构。在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，则要在该线性表中查找某一个元素是方便的。树中结点个数等于各结点度数之和加1；二叉树中各结点的度最大为2，叶子结点的度为0；二叉树中，叶子结点个数比2度点个数多1.满二叉树就是非结点都是2度的二叉树，即每一层的元素个数都达到最大。完全二叉树中，兄弟结点之间的关系满足：编号连续，左兄弟为偶数，右兄弟为奇数。完全二叉树中第i个结点若存在子结点，则两个子结点的编号为2i和 2i+1。各种排序算法的复杂度如下表：冒泡排序 快速排序 简单插入排序 希尔排序 简单选择排序 堆排序 O(n*n) O(n*n)O(n*n) O(n*1.5) O(n*n) O(n2n)冒泡排序是通过相邻数据元素的交换逐步将线性表变成有序。快速排序是快速分区交换排序，选择分区元素，将待排序序列分为两部分。插入排序是将无序序列中的各元素依次插入到已经有序的线性表中。堆排序是采用二叉树结构，保证父结点大于子女结点。程序设计基础应试指导程序设计的最终产品是程序。程序设计的基本风格是“清晰第一，效率第二”。良好的程序设计风格主要表现在设计的风格、语言运用的风格、程序文本的风格以及输入输出的风格四个方面。程序设计的根本目标是要降低程序的复杂性和提高程序的可读性。程序的复杂性主要来自于：问题固有的复杂性和人为地设计不良风格。好的设计风格是好的程序风格的基本保证。设计的风格主要体现在以下三个方面：1、结构要清晰。为了达到这个目标，要求程序是模块化结构，并且是按层次组织各模块，每个模块内部都是由顺序、选择和循环三种基本结构组成的。、 思路要清晰。为了达到这个目标，要求在程序设计的过程中遵循自顶向下、逐步细化的原则。、 在设计程序时应遵循“简短朴实”的原则。语言运用的风格主要体现在：选择合适的程序设计语言和语言中的某些特色的应用两个方面。1、选择合适的程序设计语言。选择程序设计语言的原则有以下三点：、 符合软件工程的要求；、 符合结构化程序设计的基础；、 使用要方便。2、不要滥用语言中的某些特色特别要注意，尽量不用灵活大、不易理解的语句成分。程序文本的风格主要体现在以下四个方面：、 注意程序文本的易读性；、 符号要规范化；、 在程序中加必要的注释；、 在程序中要合理的使用分隔符。输入输出的风格主要体现在以下三个方面：、 对输出的数据应该加上必要的说明；、 在需要输入数据时，应该给出必要地提示。提示的内容主要有数据的范围和意义、输入的结束标志等。、 以适当的方式对输入数据进行检验，以确认其有效性。程序设计的方法：结构化程序设计方法。结构化程序设计方法的四条原则是：自顶向下、逐步求精、模块化和限制使用GOTO语句。结构化 程序设计是程序设计的先进方法和工具，采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解和易维护。结构化程序设计要求把程序的结构限制为顺序、选择和循环三种基本结构，以便提高程序的可读性。其特点是以控制结构为单位，只有一个入口和一个出口。在进行模块化程序设计是，应重点考虑模块划分原则和组织各模块之间的联系。划分模块的基本原则是使每个模块都易于理解。按功能来划分模块最为自然。在按功能划分模块时，要求各模块的功能尽量单一，各模块之间的联系尽量少。按层次组织模块时，一般上层模块只能指出“做什么”，只有在最底层的模块中才精确的描述“怎么左”。抽象是软件工程的基本思想之一。面向对象技术是对问题领域实行自然分割，按人类习惯的思维方式建立问题领域的模型，设计尽可能直接自然地表现问题求解的软件。因此，面向对象技术成为构造复杂软件系统的一种重要技术。面向对象技术主要包括三个方面：面向对象的分析（OOA）、面向对象的设计（OOD）及面向对象的实现（OOI）。面向对象设计的主要任务是设计软件的对象模型。对象是面向对象方法和设计的核心。对象是数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象可以用来表示客观世界中的任何实体，它既可以是具体的物理实体的抽象，也可以是人为的概念。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。对象的一些基本特点：标识唯一性；分类性；多态性；封装性；模块性。类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是对应类的一个实例。类描述的是具有相似性质的一组对象。方法是允许作用于某个对象上的各种操作。消息用来请求对象执行某一处理或回答某些信息的要求。或者消息是对象之间通信的方式。继承是一种 信息隐藏技术，目的在于将对象的使用者和对象的设计者分开。封装一方面通过数据抽象，把相关的信息结合在一起，另一方面也简化了接口。对象根据所接受的消息而做出动作，同样的消息被不同的对象接受是可导致完全不同的行动，该现象称为多态性。多态性机制不仅增加了面型对象软件系统的灵活性，进一步减少了信息冗余，而且显著的提高了软件的可重用性和可扩充性。面向对象技术具有优点体现在以下三个方面：可重用性；可维护性；表示方法的一致性。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。结构化程序设计的主要特点，即每个控制结构的特征（每个控制结构只有一个入口和一个出口。）良好的程序设计风格是：程序简单、清晰和可读性好。面向对象的程序设计方法的主要的优点是：与人类习惯的思维方式一致；稳定性和可重用性好；可维护性好。面向对象的程序设计方法开发软件的主要优点是稳定、容易理解、容易修改易测试和调试。面向对象的程序设计方法中，一个对象请求另一个对象为其服务的方式是通过发送消息来实现的。对象的基本特点之一是标志唯一性。它是指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分的。消息是面向对象方法中对象间的通信方式。传统的程序设计方法是面向过程的，其方法和技术的核心是算法。面向过程程序设计方法的核心技术是算法，而面向对象程序设计方法的核心技术是对象。源程序文档要求程序应加注释。注释一般分为序言性注释和功能性注释。面向对象的程序设计中，类描述的是具有相似性质的一组对象，是对象的抽象。面向对象程序设计方法中，继承是类之间共享属性和操作的机制。软件工程计算机是由软件系统和硬件系统组成。硬件是基础，软件是灵魂，相互依存。计算机软件是指在硬件上运行的程序和相关的数据及其文档。一般软件分为应用软件和系统软件。系统软件是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务而编制的程序的总称。软件的发展，大体上经历了程序、软件和软件产品三个阶段。软件是一种逻辑实体，具有抽象性。软件着重于软件开发方面下功夫。在软甲开发和维护过程中，软件危机主要表现在：软件需求的增长得不到满足；软件生产 的高成本；软件生产的进度难以控制；软件的需求难以准确定义；软件的质量不易保证和软件可维护性差等。软件危机可归结为成本、质量和生产率等问题。其根本原因是软件生产本身的复杂性，并且与软件开发方法和技术有关。软件工程就是寻找有效的软件开发方法和技术，从而克服软件危机。软件工程是以工程化的方法阻止软件开发和生产的一门学科和技术。软件工程学的主要研究对象包括软件开发技术和软件工程管理。在软件管理方面包括软件管理学和软件经济学。软件开发过程中需要应用工程化原则。软件工程包括三个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具时支持软件的开发、管理和文档生成；过程是支持软件开发的各个环节的控制、管理。环境是全面支持软件开发过程的软、硬件的集合。软件生命期是指一软件提出并着手开发生产，到软件完成其使命为之的全过程。软件生命周期包括软件定义、软件开发和软件维护三个时期，以及问题定义、可行性研究、需求分析、系统设计、详细设计、编码、测试和运行维护八个阶段。软件定义包括问题定义、可行性研究和需求分析三个阶段；软件开发期包括系统设计、详细设计、编码和测试四个阶段；软件维护期即运行维护阶段。一、 软件定义期1. 问题定义主要目的是确定问题的性质、工程目标以及规模。2、可行性研究目的是进一步研究上一阶段所定义的问题是否可解。3需求分析（形成软件规格说明）软件规格说明包括系统的功能说明：系统对数据的要求；用户系统描述等。二、 软件开发期、 系统设计（系统设计的任务是划分出构成系统的各物理元素以及设计出软件的结果。）、 详细设计（详细设计的任务是对系统做出精确地描述，以便在编码阶段可直接将这一描述用程序设计语言编制称程序。）、 编码阶段（编码阶段的任务是对软件结构元素的过程描述进行编码，选区合适的程序设计语言书写程序。）、 测试阶段（测试阶段按照不同的层次，又可分为单元测试、综合测试、确认测试和系统测试等。测试工作包括两个方面：一是检查文档是否合乎要求，二是测试程序是否有逻辑和功能错误。测试是保证软件质量的重要手段，然而通过测试的软件并非没有错误。）测试和调试是软件测试阶段的两个密切相关的过程，通常是交替进行的。三、 软件维护期维护是软件生命周期中持续时间最长、付出代价最大的最后阶段。软件维护的实质是对软件不断差错、纠错和修改。软件维护不仅包括程序代码的维护，还包括文档的维护。文档和程序代码必须同时维护。四、 软件工程的目标与原则软件工程的目标，是在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可中用性、可适应性；、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程的理论和技术主要包括软件开发和软件工程管理。在软件开发过程中，必须遵循软件工程的基本原则，这些原则适用于所有的软件项目。这些基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。软件开发工具软件开发工具的发展是从单项工具的开发逐步向集成工具发展的，软件开发工具为软件工程方法提供了自动的或版自动的软件支撑环境。工具包括软件研制工具、软件维护工具和控制配置工具等。二、软件开发环境软件开发环境或称软件工程环境是全面支撑软件开发全过程的软件工具集合。用于辅助、支援其他软件的研制和维护的一组软件称为软件支援环境，它对于改进软件质量、提高软件生产率起到很重要的作用。软件支援环境包括环境数据库、接口软件和工具软件及其“组件”。计算机辅助软件工程（CASE），是当前软件开发环境中富有特色的研究工作和发展方向。工程上常用的表达工具有图形、表格和语言三类：一是用图形方式来描述一个算法的过程；二是用一张表格来列出实现算法的过程；三是用某种语言来描述算法实现的过程，这种语言一般是类似于某种程序设计语言。一、 程序流程图程序流程图又称为程序框图，它是最常用的一种算法描述工具。其优点是直观、清晰，易于学习掌握，独立于任何一种程序设计语言。流程图中的流程线用以指明程序的动态执行顺序。结构化程序设计限制流程图只能使用五种基本控制结构。（顺序结构，选择结构，当型循环结构，直到型循环结构，多情况选择结构）程序流程图有以下缺点：不是逐步求精的好工具；不易表达层次结构；不易表示数据结构和模块调用关系等重要信息；箭头代表控制流，程序员不受任何约束，随意进行转移控制。二、N-S图是一种不允许破坏结构化原则的图形算法描述工具，又称盒图。特点是：功能域可以从框中直接反映出来；不能任意转移控制，符合结构化原则；很容易确定举局部和全程数据的作用域；很容易表示嵌套关系，也可以表示模块的层次结构。三、 问题分析图（PAD）PAD图是用结构化程设计思想来表示程序逻辑结构的一种图形工具。用PAD图所表达的程序，其结构清晰，结构化程度高。在PAD图中，设置了五种基本控制结构的图式，并允许递归使用。PAD的执行顺序是从最左主干线的上端结点开始，自上而下依次执行。四、 判定表以图形描述数据流图的逻辑加工，结构简单，易读易懂。当算法中包含多重嵌套的条件选择时，用程序流程图、N_S图都不易清楚描述，而利用判定表就能够清晰的表示复杂的条件组合与功能之间的对应（逻辑）关系。五、 过程设计语言（PDL）PDL又称伪码或结构化语言。具有严格的关键字外部语法，用于定义控制结构和数据结构。一般来说，是一种过程设计语言也称为结构化的英语和伪码“混合”语言，采用英语的词汇和结构化程序设计语言的语法来描述算法，类似编程语言。优点：可以作为注释直接插在源程序中间，PDL的书写和编辑工作方便；利用已有的处理程序生成程序代码。缺点：不如图形工具形象直观；描述复杂的关系时，不如判定表清晰简单。应用软件开发的基本原则、 自顶向下的系统结构开发原则。、 模块化结构开发原则。软件的开发方法是保证软件生产过程的一套规范。主要体现在软件生产的三个方面：明确的操作步骤；具体的文档格式；确定的评价标准。开发方法第一类，人工的开发方法（也称非自动法）、 系统流程图法。（优点：既反映了系统的逻辑结构，有反应了数据与加工的某些物理特征，因而十分简练、直观明确。缺点：开发工作量大，不易维护）、 结构化分析方法（SA方法）这种方法主要用于系统分析。、 结构化设计方法（SD方法）。、 数据结构法。、 层次输入处理输出方法（HIPO方法）。第二类，半自动形式的开发方法（部分使用软件开发工具）、 SREM方法称为软件需求工程法，主要使用与系统分析。、 方法。第三类，自动形式的系统开发方法。软件开发方法是软件开发过程所遵循的方法和步骤，其目的在于有效的得到一些程序和文档，并且满足质量要求。软件开发方法包括分析方法、设计方法和程序设计方法。结构化方法包括结构分析方法、结构化设计方法和结构化编程方法，其核心和基础是结构化程序设计理论。软件需求是指用户对目标软件系统在功能、行为、性能和设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将创建所需的数据、功能和控制模型。需求分析阶段的工作：需求获取、需求分析、编写说明书和需求评审。常见的需求分析方法有：结构化分析方法和面向对象的分析方法（）。结构化分析方法包括：面向数据流的结构化分析方法（），面向数据结构的（）方法，面向数据结构的结构化数据系统开发方法（）。需求分析方法有分为静态分析方法和动态分析方法。结构化分析方法采用自顶向下的数据流分割技术，采用数据流图、数据字典、判定表以及结构化的规范化工具来描述现行系统或新建系统的逻辑结构。结构化分析方法的特点：分解和抽象在软件工程中，控制复杂性的基本手段是分解和抽象。文档的规范化面向用户系统的逻辑设计和物理设计分开进行数据流图和数据字典结合构成了系统的逻辑模型。数据流图是一种最常用的结构化分析工具，它从数据传递和加工的角度，以图形的方式来刻画系统内数据流动情况。数据流图中具有四种基本成分：圆框（表示加工，代表接收输入，经过变换，继而产生输出的处理过程），箭头（表示数据流，代表数据的路径和流向，沿箭头方向传送数据的通道，一般在旁边标注释数据流名），直线（表示数据存储，代表数据处理过程中存放各种数据的地方），方框（表示外部实体，代表图中出现数据源点或终点，数据源点指提供数据输入的地方，数据终点指接收系统所产生的输出结果的地方。）数据字典是对数据流图中的数据元素加以定义。数据字典主要是给数据流图中的每一个数据流名、文件名以及处理名建立一个条目。在数据字典中，通常有四种类型的条目：基本数据项条目、数据流条目、文件条目和加工条目。软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的重要文档之一。软件需求规格说明书的作用 便于用户、开发人员进行理解和交流。 反映出用户问题的结构，可以作为软件开发工作的基础和依据。 作为确认测试和验收的依据。软件需求规格说明书是作为需求分析的一部分而制定的可交付文档。软件需求规格说明书所包括的内容和书写框架如下：、 概述；2、数据描述；3、功能描述；4、性能描述；5、参考文献目录；6、附录。软件需求规格说明书是确保软件质量的有力措施，衡量软件需求规格说明书质量好坏的标准、标准的优先级及标准的内涵包括以下几点。、 正确性；2、无歧义性；3、完整性；4、可验证性；5、一致性；6、可理解性；7、可修改性；8、可追踪性。软件设计是软件需求分析完成后的后续任务。结构化设计是运用结构化的方法进行软件设计的实现，它将软件的设计分解为总体设计和详细设计两个阶段。总体设计是进行软件设计的第一个阶段，它包含了系统设计和结构设计两方面的内容。系统设计，确定软件系统的总体方案；结构设计，确定软件系统的具体结构。总体设计归纳成以下9个步骤：1、设想可能的方案。2、选择合适的方案；3、选择最佳方案；4、功能分解；5、软件结构设计；6、数据库设计；7、制定测试计划；8、编制文档；9、审查与复审。详细设计的任务是具体考虑每一个模块内部采用什么算法、模块的输入输出以及该模块的功能。详细设计要确定软件结构图中每一个模块所采用的算法和数据结构，并产生详细设计说明书。具体内容包括模块的算法、数据结构和接口细节。一般在设计时采用结构化设计方法，它具有自顶向下、先整体后局部和逐步求精的特点，能使软件结构清晰，容易理解和编码。常见的详细设计工具有以下三种：图形工具：程序流程图，N_S，。表格工具：判定表。语言工具：（伪码）。软件设计规格说明书是软件设计阶段的最终结果，是编码的依据，是测试、维护的指南。软件设计规格说明书包括：总体设计阶段的软件结构描述和详细设计阶段的软件元素的细节。软件结构化设计术语：深度、宽度、扇入数、扇出数、上级模块、从属模块、软件设计的准则：提高模块独立性；模块规模适度；深度、宽度、扇出数和扇入数适当；保持模块的作用范围；降低模块接口的复杂性和冗余度；保持模块的单入和单出口；模块的功能可预测；软件根据设计约束和移植需要组装。结构图是描述软件结构的图形工具。结构图SC的基本元素是模块，一般用矩形框表示。结构图包括以下内容：模块；调用；模块键信息传递（其中带有空心圆圈的小箭头来表示数据的传递。）；辅助符号。结构图通常是描述系统逐层分解的过程，即一个个具体的任务。数据流图表达了问题中的数据流与加工之间的关系，加工对应处理模块。由数据流图导出结构图的关键是找出中心加工。中心加工有两种典型的结构形式：一种是变换型，另一种是事务性。变换型的中心加工业称为主加工，一般他位于逻辑输入与逻辑输出之间。一个变换型数据流图可以明显的分为输入、变换和输出三部分。事务性的中心加工称为事务中心。对于一个大型系统，可以把变换型与事务型分析应用在同一个数据流图的不同部分。一般来说，所有的数据流图都可以认为是变换型的。但当遇到有明显事物特征的数据流图，建议采用事务性分析方法，而对于不具有明显事物特征的数据流图，一般采用变换型分析方法。软件模块化是软件的 重要特征。系统设计的质量主要反映在模块的独立性上，评价模块独立性的主要标准有两个：一是模块之间的耦合，它表明两个模块之间互相独立的程度；二是模块内部之间的关系是否紧密，称为内聚。一般来说，要求低耦合，高内聚。耦合性是模块之间相互连接的紧密程度的度量。耦合性反映了系统分解后的复杂程度、调用方式以及各模块之间的相互影响。影响模块之间耦合的主要因素有两个：一是模块之间的连接形式，二是模块接口的复杂性。按照耦合程度从弱到强，可以将模块的耦合分为下下五级：数据耦合；同构耦合；控制耦合；公用耦合；内容耦合。内聚性是一个模块内部各元素 之间彼此结合的紧密程度的度量。一个模块的内聚度越高，与其他模块之间的耦合程度也就越弱。内聚度从高到底可以由以下七类：偶然内聚；逻辑内聚；时间内聚；过程内聚；通信内聚；顺序内聚；功能内聚。测试的目的是在软件投入生产性运行之前，尽可能多的发现软件中的错误。测试是对软件规格说明、设计和编码的最后审查，测试贯穿在软件开发期的全过程。测试只能证明错误的存在，但不能证明错误不存在。好的测试方案是尽可能多的发现至今尚未发现的错误；成功的测试是发现至今尚未发现的错误。测试任务：预防软件发生错误；发现改正程序错误；提供错误诊断信息。原则：测试贯穿软件开发始终，程序员应避免只有自己检查程序；合理的设计测试实例；全面检查每一测试结果检查程序应完成的任务和不应该做的事情。方法：动态测试：一般采用“黑箱测试法”和“白箱测试法”；静态测试：由人工来评审文档和检查程序；程序正确性证明。软件测试技术是实施软件测试的基本保证。测试的基本技术是实施“黑箱测试”和“白箱测试”。黑箱测试即对程序的功能进行测试，又称功能测试，其特点是测试时完全不考虑程序内部细节、结构和实现方式，进检验程序结果与说明书的一致性。黑箱测试的方法：等价分类法；边缘值分析法；因果图法；错误推测法。白箱测试即对程序的结构进行测试，又称结构测试，其特点是测试时将涉及程序结构的实现细节，如程序风格、控制方法、源程序、数据库设计和编码细节。白箱测试的内容包括：语言测试，分支测试，路径测试。白箱测试时应考虑到对程序内部逻辑的覆盖程序，并将覆盖程度从底到高分为：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖和条件组合覆盖。测试的基本策略：应用黑箱测试设计基本的测试方案，再用白箱测试座必要的补充。测试的基本方法：设计测试实例来实现对程序的测试。黑箱测试不关心程序内部逻辑，进根据程序的功能说明来设计测试实例；白箱测试与程序的内部相关，要利用程序结构的实现细节设计测试实例。调试的关键在于推断程序内部的错误位置及原因。调试也称为排错，它是一个与测试既有联系又有区别的概念。测试的母的是暴露错误，评价程序的可靠性，而调试的目的是发现错误的位置，并改正错误。一般的调试过程分为错误侦查、错误诊断和改正错误。常用的调试技术有以下五种：输出存储器内容；在程序中插入调试语句；调试用例；经静态分析、动态测试或自动测试，都会得到大量与程序错误有关的信息，这些信息都可以在调试时加以利用；借助调试工具。常用的调试策略包括以下五个方面：试探法；回溯法；对分查找法；归纳法演绎法。软件开发是一自顶向下逐步分解和细化的过程，而软件的的测试则是一自下而上逐步集成的过程，它由单元测试、集成测试和系统测试组成，其中还包括有效性测试和验收测试。单元是程序的最小的有独立意义的部分，它由数据输入、加工和输出组成，是可正式说明的程序段。单元测试则是对程序的最小独立的部分进行