二级公共基础知识总结
下个学期就要开始我的计算机双学位就读了。在此之前，我打算先考几个证来过渡一下，像二级的C、C++、VB、Java、Python、Office都考一下。其中我比较熟悉的只有C和Python，其他的编程语言就要自己突击一下了。3月我报的是C、C++和VB。为此还买了几本书。这里总结一下考点，做一下笔记。之后书就不重要了，可以丢了。再刷一些题目，做一些记录就可以了。开始笔记吧。
第一部分 数据结构和算法
1.1 算法
定义：对解决方案的操作步骤的准确而完整的描述。(是数学计算方法和程序间的一个过渡)
基本特征：可行性(可以在实际计算工具上执行)；确定性(算法每一步的表述没有歧义)；有穷性(操作步骤有限，在有限时间内完成)；有足够的输入。
总之，算法是指一组严谨地定义操作步骤的可以在有限的次数中终止的规则，每一个规则都是可行的、明确的。
基本要素：
(1). 对数据对象的运算和操作(由不同计算机系统的指令集规定其基本运算和操作)；
(2). 控制结构(就是顺序、选择、循环三种)；
算法基本设计方法：列举法、归纳法、递推法、递归法、减半递推法、回溯法
算法复杂度：体现在运行该算法所需的计算机的时间和空间资源上，越多则算法复杂度越高。
(1). 时间复杂度：执行算法所需的计算工作量，用算法所执行的基本运算次数来度量(注意: 不是具体的执行时间)。常用大O表示法表示。我们经常用平均复杂度和最坏情况复杂度来分析算法的工作量。
(2). 空间复杂度：执行这个算法所需的内存空间。包括3个部分。为降低空间复杂度，主要应减少输入数据所占的空间和额外空间。如果额外空间不随问题规模变化，称该算法in place原地工作。
a. 输入数据所占的存储空间 b. 程序本身所占的存储空间 c. 算法执行过程中所需要的额外空间，包括算法执行过程中的工作单元和某种数据结构所需要的附加存储空间
1.2 数据结构
- 数据结构：是数据+结构(即有关联的数据元素集合)。数据是需要处理的数据元素(数据的基本单位)的集合，具有共同特征。结构就是关系，是数据集合中各个数据元素之间存在的某种关系。
结构又可以分为逻辑结构——数据集合中各数据元素之间固有的逻辑关系；存储结构——各数据元素在计算机中的存储关系。此外，数据结构还研究对各种数据结构的运算。
所以，数据结构=数据+逻辑结构+存储结构+运算。 - 数据元素间的结构根据不同的特性，分为线性结构、树形结构、网状结构(图形结构)、集合。
- 两两数据元素的关系常常用前后件(前驱后继关系)描述。B=(D+R)，D={数据元素集合}，R={前后件关系的集合}。
如：B=D+R，D={早餐，中餐，晚餐}，R={(早餐，午餐)，(午餐，晚餐)}。 - 节点：数据结构的图形表示中引出的概念，根节点——没有前驱的节点，叶子节点——没有后继的节点，内部节点——除了根节点和叶子节点之外的节点的统称。
- 存储结构：包括顺序存储结构和链式存储结构。
- 逻辑结构：包括线性结构和非线性结构。如果数据结构没有数据元素，称其为空的数据结构。
| 基本概念 | 含义 | 例子 |
|---|
| 线性结构 | 一个非空的数据结构，满足一下两个条件：有且只有一个根节点；每个节点最多只有一个前驱，也最多只有一个后继 | (早餐，午餐), (午餐，晚餐） |
| 非线性结构 | 不满足以上两个条件的数据结构称为非线性结构，主要是指树和图形结构 |
|
1.3 线性表
- 定义：表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。
- 结构特征：只有一个根节点，它无前件；有且只有一个终端节点，它无后件；除根节点与终端节点外，其他所有节点有且只有一个前件，有且只有一个后件。节点个数n就是线性表的长度，n=0时称为空表。
- 顺序表：线性表的顺序存储结构，所有元素所占的存储空间是连续的，按逻辑顺序依次存放。此时逻辑结构与存储结构是一致的。顺序表中前后件两个元素在存储空间中紧邻，前件元素一定存储在后件元素的前面。只要确定了首地址，顺序表中任意元素的地址都可以方便地计算出来。
- 线性表的插入运算：在第i个元素之前插入一个新元素，需要把原来的第i个节点至第n个节点依次往后移一个元素位置，把新节点放在第i个节点位置上。其时间耗费在节点的移动上，所需移动节点的次数不仅与表的长度有关，还与插入的位置有关。
- 线性表的删除运算：将表的第i个节点删除，应将第i+1个元素至第n个元素依次向前移一个元素位置，共移动n-i个元素。所需移动节点的次数不仅与表的长度有关，还与删除的节点位置有关。
- 综上所述，线性表的顺序存储结构适用于建立之后其中元素不经常变动的情况，而不适用于经常需要进行插入和删除的线性表。
1.4 栈和队列
1.4.1 栈
- 定义：特殊的线性表，所有的插入和删除操作限定在表的同一端(栈顶top)进行，另一端(栈底bottom)是封闭的，既不允许插入元素，也不运行删除元素。栈中没有元素时称为空栈。
- 设有栈
S=(a1, a2, a3, a4)，则a1为栈底元素，a4为栈底元素。按照a1,a2,a3,a4的顺序入栈，a4,a3,a2,a1的顺序出栈。 - 特点：Last In First Out，后进先出。即栈顶元素总是最后被插入的元素，也是最早被删除的元素，栈底元素总是最早被插入的元素，也是最晚被删除的元素。在顺序存储结构中，栈的插入和删除不需要移动表中的其他元素。
- 栈的运算之入栈：在栈顶插入一个新元素。
- 栈的运算之出栈：取出栈顶元素并赋予指定变量。
- 栈底运算之读取栈顶元素：读取栈顶指针所指向的元素并赋予指定变量。
1.4.2 队列
- 定义：特殊的线性表，允许在一段(队尾rear)进行插入，而在另一端(队头front)进行删除的线性表。与生活中的排队现象是一样的。
- 设有队列
Q=(q1,q2,q3,q4)，则q1为队头元素，q4为队尾元素。按照q1,q2,q3,q4的顺序进入，也按照这个顺序退出。 - 队列运算之入队：队头指针front指示当前执行退队运算的队头位置(即当前队头元素的前一个位置)，队尾指针rear指向当前执行入队运算的队尾位置，往队列的队尾插入一个元素称为入队，
首先队尾指针进1，然后在rear指针指向的位置插入新元素。 - 队列运算之出队：从队列的排头删除一个元素称为退队运算。
排头指针front+1，然后删除front指针指向的位置上的元素。队头指针始终指向当前执行退队操作的队头位置。 - 循环队列及其运算：为充分地利用数组的存储空间而把数组的前端和后端连接起来，形成一个环形的表，就是循环队列，是队列的一种顺序存储结构。常用取余运算来实现循环顺序队列的“循环”。为区分队空和队满的情况可以设置标志。
1.5 线性链表(线性表的链式存储)
1.5.1 线性链表的概念及基本运算
- 概念：用一组不连续的存储单元存储线性表中的各个元素，数据元素间的逻辑关系不能依靠数据元素的存储单元之间的物理关系来表达，因此每个元素除了存储自身的信息外，还要存储一个指示其后件的信息。
- 存储节点：线性表链式结构的基本单位成为存储节点，包括数据域(存储数据元素本身的信息)和指针域(存储一个指向后继的指针，即存放下一个数据元素的存储地址)
- 单链表：这种链表中，每一个节点只有一个指针域。是最基本的链表。其中第一个元素没有前驱，可以是一个指向链表中第一个节点的特殊指针，即头指针
HEAD，最后一个元素没有后继，其指针域为空，用NULL表示。更加直观的表示是用箭头相链接的节点序列。在单链表中，只能顺时针向链尾方向进行扫描。 - 双向链表：在实际应用中有时还会用到每个存储节点有两个指针域的链表，一个存放前驱的地址，称为左指针(Llink)，一个指针域存放后继的地址，称为右指针(Rlink)。双向链表的第一个元素左指针为空，最后一个元素的右指针为空。由于有两个指针，可以从任一节点出发找到其他节点。
- 链栈：使用链式存储结构表示栈，组织成一个单链表。
- 链队列：使用链式存储结构表示队列，组织成一个单链表。
- 顺序表和链表的优缺点比较：
| 类型 | 优点 | 缺点 |
|---|
| 顺序表 | (1) 可以随机存取表中的任意节点；(2) 无需为表示节点间的逻辑关系额外增加存储空间 | (1) 其插入和删除运算效率很低；(2) 存储空间不便于扩充，不便于对存储空间的动态分配 |
| 链表 | (1) 插入和删除效率高，只需改变指针即可，不用移动元素；(2) 存储空间易于扩充且方便空间的动态分配 | (1)需要额外的空间来表示数据元素之间的逻辑关系；(2) 数据的查询效率较低 |
- 线性链表的基本运算：
(1). 查找指定元素：必须从队头指针出发，沿着指针域Next逐个节点搜索，直到找到指定元素或链表尾部返回NULL为止。
(2). 可利用栈(线性链表的存储单元是不连续的，就存在离散的空闲节点，将计算机存储空间中空闲的存储节点利用起来，把其组织成一个带链的栈，就是可利用栈)的插入和删除：线性链表执行删除时，被删除节点回收到可利用栈，即把该空闲节点放到可利用栈栈顶，执行入栈操作；线性链表执行插入运算时，
需要一个空闲节点，就在可利用栈中取栈顶节点，执行退栈操作。
(3). 插入运算：在链式存储结构下的线性表中插入一个新元素。由于新节点的存储单元取自可利用栈，只要可利用栈非空，线性链表就总能找到存储新元素的节点，因而不需要规定最大存储空间，不会发生上溢错误。
(4). 删除运算。
1.5.2 循环链表
- 概念：在单链表第一个节点之前增加一个没有元素的表头节点，HEAD指针指向表头节点，最后一个节点的指针域指向表头节点。在循环链表中，所有节点的指针构成了一个环状链。
- 与单链表的比较：
(1). 对单链表的访问是一种顺序访问，从其中一个节点出发，只能找到它的后继；在循环链表中，可以通过一个节点访问到表中的所有节点。
(2). 在单链表中空表和第一个节点的处理必须单独考虑；在循环链表中，表头节点是循环链表所固有的节点，因此即使在表中没有数据元素的情况下，表中也至少有一个节点，从而使空表与非空表的处理统一。
1.6 树与二叉树
1.6.1 树的基本概念
- 树：一种简单的非线性结构，是以分支关系定义的层次结构。在使用图形表示数据结构中元素的前后件关系时通常使用有序箭头，但是树形结构中使用无向箭头也可以，因为前后件关系很明确。
| 相关术语 | 含义 |
|---|
| 父节点和根节点 | 树结构中，每个节点只有一个直接前驱，称为父节点；没有直接前驱的节点只有一个，即树的根节点(树的根) |
| 子节点和叶子节点 | 在树结构中，每个节点可以有0、1或多个直接后继，称作该节点的子节点。没有后继的节点是叶子节点 |
| 度 | 一个节点拥有的后件(直接后继)个数就是该节点的度。所有节点中最大的度是树的度 |
| 深度 | 根节点所在的层次为1，其他节点所在的层次等于父节点的层次+1，树的最大层次称为该树的深度。 |
| 子树 | 在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树。 |
1.6.2 二叉树及其性质
二叉树(Binary Tree)定义：是一个有限的节点集合，该集合或为空，或由一个根节点及其左右不相交的左、右二叉子树所构成。与树是相似的，但又有不同。二叉树不是树的特殊情况，二者是不同的概念。
二叉树的特点：
(1). 二叉树可以为空，空的二叉树没有节点，非空二叉树只有一个根节点；
(2). 每个节点最多只有两棵子树，即二叉树中不存在度大于2的节点，二叉树中的节点可能没有子节点，可能只有一个左子节点或只有一个右子节点；
(3). 二叉树的子树有左右之分，不能任意颠倒次序。
二叉树的基本形态：5种；空，仅有根节点，左右子树均非空，左子树非空右子树为空，左子树为空右子树非空。
满二叉树：除最后一层，每一层上的所有节点都有两个子节点的二叉树，一棵平衡的二叉树。
(1). 其在第i层有2(i-1)个节点，相当于每一层的节点数都满了；
(2). 一棵深度为K的满二叉树共有2k-1个节点;
(3). 满二叉树中只有度为2和0的节点，没有度为1的节点。所有度为0的叶子节点都在最后同一层。
完全二叉树：除最后一层，每一层上的节点数均达到最大，在最后一层上只缺少右边的若干节点。
(1). 叶子节点只在最后两层出现；
(2). 对于任一节点，若其右子树的深度为m，则左子树的深度为m或m+1。
二叉树的基本性质：
(1). 二叉树的第K层上面，最多只有2k-1个节点；
(2). 深度为K的二叉树，最多有2k-1个节点(等比数列求和)；
(3). 对任何一棵二叉树，度为0的节点(叶子节点)总是比度为2的节点多一个；
(4). 具有n个节点的二叉树，其深度至少为[log2n]+1；
(5). 具有n个节点的完全二叉树，其深度为[log2n]+1。
(6). 较复杂。
1.6.3 二叉树存储结构及其遍历
- 二叉链表：二叉树常采用链式结构。由于每个元素可以有两个后件，因此每个节点有两个指针：左指针域执行左子节点，右指针域执行右子节点。因此，二叉树的链式存储结构也称为二叉链表(非线性结构，不同于双向链表)。
- 二叉树的遍历：不重复的访问二叉树中的所有节点。一般先访问左子树，在访问右子树，在先左后右的原则下，根据访问根节点的次序不同，二叉树的遍历分为前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)三种。
(1). 前序遍历：先访问根节点——> 前序遍历左子树——> 前序遍历右子树(DLR)
(2). 中序遍历：先中序遍历左子树——> 访问根节点——> 中序遍历右子树(LDR)
(3). 后序遍历：先后序遍历左子树——> 后序遍历右子树——> 访问根节点 (LRD)已知中序遍历序列和前序遍历序列(或后序遍历序列)可以唯一确认一棵二叉树，但是知道前序和后序则无法唯一确定这棵二叉树。
1.7 查找技术
查找是插入和删除等运算的基础，是数据处理的重要内容。
- 顺序查找：最好情况：1次找到；最坏情况：n次比较后找到；平均：n/2次，即O(n)的时间复杂度。特点在于：虽然效率很低，但是在线性表无序(不管使用顺序存储还是链式存储)的时候，或者在采用链式存储结构时，只能用顺序查找。
- 二分查找：条件：使用顺序存储结构；线性表是有序表。对于长度为n的有序线性表，在最坏情况下二分查找只需比较log2n次。即O(logn)的时间复杂度。
- 哈希查找：时间复杂度O(1)。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法(借助数据元素的交换来排序的方法)：冒泡排序: 最坏的情况下，对长度为n的线性表排列需要比较n(n-1)/2次。快速排序则是对冒泡排序的一种本质改进，其平均时间最佳O(nlog2n) ，最坏O(n2)。如初始序列基本有序，则蜕化为冒泡排序。
插入类排序法(每次将一个待排序元素按其大小插入到前面的有序子表中)：简单插入排序：持续不断的清空无序表，插入有序表中，其效率与冒泡排序法基本相同。希尔排序法则有较大改进。
选择类排序法(每趟从待排序的序列中选择最小的元素，顺序放在有序子表中的后面，直到全部序列满足排序要求为止)：简单选择排序，最坏的情况下要比较n(n-1)/2次。对于大量数据元素，堆排序则是很有效的。
排序方法比较：
| 方法 | 平均时间 | 最坏情况时间 | 辅助存储 |
|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) |
| 快速排序 | O(nlog2n) | O(n2) | O(log2n) |
| 简单插入排序 | O(n2) | O(n2) | O(1) |
| 简单选择排序 | O(n2) | O(n2) | O(1) |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(1) |
第二部分 程序设计基础
2.1 程序设计方法与风格
- 程序设计：指设计、编制、调试程序的方法与过程。不等同于编程。程序设计的方法和风格显著影响程序的质量。良好的程序设计风格可以使程序结构清晰，便于维护。
- 程序设计规范：
(1). 源程序文档化：在源程序中包含一些内部文档，以帮助人们理解和阅读源程序。考虑符号名的命名、程序注释(包括序言性注释和功能性注释)、视觉组织(空行、空格和缩进)。
(2). 数据说明的方法：词序规范化、变量安排有序化、使用注释。
(3). 语句结构：简单直接，模块化……
(4). 输入输出：方式和格式尽量方便用户使用；对所有的输入数据都要进行检验，确保输入数据的合法性；输入数据时，应允许使用自由格式，允许默认值；输入一批数据后，最好使用输入结束标志；给所有的输出加注释，并设计良好的输出报表格式……
2.2 结构化程序设计
- 原则：自顶向下； 逐步求精；模块化；限制使用goto语句。
- 基本结构：顺序结构、选择结构和循环结构。3种基本结构就足以表达各种其他形式的结构。共同特征是严格的只有一个入口和出口。
- 注意事项：使用顺序、选择、循环等有限的控制结构表示程序的控制逻辑；选用的控制结构只允许有一个入口和出口；程序语句组成容易识别的功能模块，每个模块只有一个入口和一个出口；复杂结构应该用基本控制结构进行组合嵌套来实现；语言中没有的控制结构，应采用前后一致的方法模拟；严格控制goto语句的使用。
- 总之，按结构化程序设计出的程序具有明显的优点：程序易于理解、使用和维护；提高呢编程工作的效率，降低了软件开发成本。
2.3 面向对象的程序设计
基本概念：
- 对象(Object)：系统中用于描述客观事物的一个实体，是构成系统的一个基本单位，由一组静态特征(属性)和它可执行的一系列方法(行为)组成。其中的属性即对象包含的信息，一般只能通过执行对象的操作来改变。方法则是对象的动态行为。
对象的基本特点：标识唯一性；分类性(可以将具有相同属性和操作的对象抽象成类)；多态性(同一个操作可以是不同对象的行为)；封装性(对象内部对外是不可见的)；模块独立性好(完成对象功能所需的元素都被封装在对象内部)。 - 类(Class)：具有共同属性和方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。
- 实例(Instance)：一个具体对象则是其对应类的一个实例。
- 消息(Message)：消息传递是对象间通信的手段，一个对象通过向另一个对象发送对象来请求其服务。一个消息由接受消息的对象名称、消息选择符、零或多个参数组成。消息只告知接受对象需要完成什么操作，而不指示怎样完成操作。
- 继承：直接获得已有的性质和特征，而不必重复定义它们。一个子类可以直接继承父类的全部描述，而且可以定义自己的属性和方法。其中，继承又分成单继承和多继承。
- 多态：同样的消息可以被不同的对象接受而产生不同的行为。即子类对象可以像父类对象那样使用，同样的消息既可以发给父类也可以发给子类对象。
- 优点：与人类习惯的思维方法一致；稳定性好；可重用性好；容易开发大型软件产品；可维护性好。
第三部分 软件工程基础
3.1 软件工程基本概念
3.1.1 软件
- 定义：是由
(机器可执行的)程序、数据和(不可执行的)相关文档组成的完整集合。
(1). 程序：软件开发人员依据用户需求开发的、用某种程序设计语言描述的、能够在计算机中执行的语句序列。
(2). 数据：使程序能够正常操作信息的数据结构。
(3). 文档：与程序开发维护使用相关的文件资料。 - 特点：(1). 是一种逻辑实体；(2). 没有明显的制作过程；(3). 在使用期间不存在磨损老化问题，损失方式特殊；(4). 对硬件和环境具有依赖性，给软件的移植带来问题；(5). 软件复杂性高，成本昂贵；(6). 软件开发涉及诸多社会因素。
- 分类：(1). 系统软件：管理计算机资源，提高使用效率，为用户提供各种服务的软件。(2). 支撑软件：介于系统软件和应用软件之间，辅助用户开发软件的工具型软件。 (3). 应用软件：为了应用于特定软件而开发的软件。
- 软件危机：泛指在计算机软件的开发和维护中所遇到的一系列严重问题，几乎所有软件都不同程度存在这些问题(
软件开发生产率低；软件质量难以保证；软件开发进度无法控制；软件成本不断提高；软件维护程度低下；软件需求的增长得不到满足)。主要原因在于：软件本身的特点，如复杂度高，规模庞大；人们对软件开发维护有许多错误认识和做法，对软件的特性认识不足。为此，诞生了软件工程的概念。
3.1.2 软件工程
- 软件工程：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准、工序。重要三要素是方法(技术手段)、工具、过程。
- 软件工程目标和研究内容(软件开发技术和软件工程管理)
- 软件工程的原则：
| 原则 | 具体描述 |
|---|
| 抽象 | 分层次抽象，自顶向下、逐层细分控制软件开发的复杂性 |
| 信息隐蔽 | 模块设计成黑箱，不让模块使用者直接访问 |
| 模块化 | 模块化有助于信息隐蔽和抽象，有助于表示复杂的系统 |
| 局部化 | 模块间松耦合，模块内部强内聚，有助于控制分解的复杂性 |
| 确定性 | 软件开发过程中所有概念的表述是无歧义的、确定的、规范的 |
| 一致性 | 各个模块使用一致的概念、符号；程序内外部接口一致；系统规格说明书和系统行为一致 |
| 完备性 | 软件系统不丢失任何重要成分，完全实现系统所要求的功能 |
| 可验证性 | 开发大型的软件系统需要对系统自顶向下、逐层分解，遵循系统易于检查、测试、评审的原则 |
- 软件工程过程：是使用适当的资源为开发软件进行的一组开发活动，在过程结束时将输入(用户要求)转化为输出(软件产品)。
基础活动如下：
| 活动名称 | 含义 |
|---|
| 软件规格说明 | 规定软件的功能及其运行时的限制 |
| 软件开发 | 产生满足规格说明的软件 |
| 软件确认 | 确认能够满足用户提出的要求 |
| 软件演进 | 为满足用户要求的变更，软件必须在使用的过程中不断演进 |
- 软件生命周期：一个软件从提出、实现、使用、维护和停止使用与废弃的过程称为软件生命周期。分为3个时期和8个阶段。
| 大时期 | 小阶段 | 主要任务 | 成果与文档 |
|---|
| 软件定义期 | 问题定义 | 确定要解决的问题是什么 |
|
| 可行性研究与计划制定 | 决定该问题是否存在解决方法可行，指定完成任务的实施计划 | 可行性分析报告 |
| 需求分析 | 对于开发软件提出的需求进行分析并给出详细定义 | 软件规格说明书、初步的用户手册 |
| 软件开发期 | 软件设计 | 分为概要设计和详细设计，给出软件的结构、模块划分及设计流程 | 概要和详细设计说明书、测试计划初稿 |
| 软件实现 | 在软件设计的基础上编写程序 | 用户手册、操作手册和单元测试计划 |
| 软件测试 | 在设计测试用例的基础上检验软件的各个组成部分 | 测试分析报告 |
| 运行维护期 | 运行和维护 | 将已交付的软件投入运行，同时不断地维护，进行必要而且可行的扩充和删改 |
|
- 软件开发工具：从单项工具逐步向集成工具发展；软件开发环境：是全面支持软件开发全过程的软件工具的集合。
3.2 结构化分析方法
也称传统方法学，使用结构化方法完成软件开发的各项任务。
3.2.1 需求分析
- 软件需求是用户对目标软件系统在功能、性能和设计约束上的期望。需求分析的任务是发现需求、定义需求的过程，将创建所需的数据模型、功能模型和控制模型。
- 需求分析阶段的工作：
(1). 需求获取：了解用户情况，发现用户问题和对目标系统的完整、准确和具体的需求。
(2). 需求分析：整合获得的需求，得出系统的解决方案和目标系统的逻辑模型。
(3). 编写需求规格说明书：这是需求分析的阶段性成果。
(4). 需求评审：从一致性、完整性、现实性、有效性复审软件需求规格说明书。
3.2.2 需求分析方法
- 结构化分析方法：面向数据流的结构化分析(SA)；面向数据结构的Jackson系统开发；面向数据结构的结构化数据系统开发方法。面向对象分析方法：面向对象分析是面向对象软件工程方法的第一个环节。
- 结构化分析方法：使用数据流图、数据字典、结构化英语、判定表和判定树等工具来建立一种新的称为结构化规格说明的目标文档。
3.2.3 结构化分析方法的常用工具
| 名称 | 图形 | 说明 |
|---|
| 数据流 | 有向箭头 | 沿箭头方向传输数据，在旁边标注数据流名 |
| 加工过程 | 圆形 | 转换，输入数据经过加工、交换产生输出 |
| 数据存储文件 | 类长方形 | 表示存储过程中存放各种数据的文件 |
| 源/潭 | 长方形 | 表示系统与环境的接口，属于系统之外的实体 |
- 数据字典：对数据流图中所有元素的定义的集合，是结构化分析的核心，与数据流图共同构成系统的逻辑模型。其中共有4种类型的条目，数据流、数据项、数据存储和加工。
- 判定表：如果一个加工逻辑有多个条件、多个操作并且在不同场合下执行不同的操作，可以使用判定表来描述。一个十字分成四个区域，左上部是基本条件项，列出各种可能的条件；右上部成为条件项，列出各种可能的条件组合；左下部是基本动作项，列出所有的操作；右下部是动作项，列出在对应的条件组合下所选的操作。
- 判定树：可以用判定表表示的加工逻辑都可以用判定树表示。
3.2.4 软件需求规格说明书
这是需求分析阶段的最后成果，是软件开发过程中的重要文档之一，衡量它的标准如下：
| 标准 | 内涵 |
|---|
| 正确性 | 首先正确体现系统的真实需求 |
| 无歧义性 | 对每一个需求没有两种解释 |
| 完整性 | 涵盖用户对系统的所有需求，包括功能需求、性能需求、接口需求、设计约束等 |
| 可验证性 | 每一个需求都可在有限代价的有效过程中验证确认 |
| 一致性 | 各个需求的描述之间不能有逻辑上的冲突 |
| 可理解性 | 应尽量少使用计算机的概念和术语 |
| 可修改性 | 结构风格在需要的时候不难改变 |
| 可追踪性 | 每个需求的来源和流向是清晰的 |
3.3 结构化设计方法
在需求分析阶段已经使用数据流图和数据字典等工具建立了系统的逻辑模型，即做什么，接下来解决怎么做的问题。
3.3.1 软件设计概述
- 软件设计基础：基本目标是用抽象概括的方式确定目标系统如何完成预定的任务，确定系统的物理模型，是开发阶段最重要的步骤。
| 划分 | 名称 | 含义 |
|---|
| 按工程管理角度划分 | 概要设计 | 将软件需求转化为软件体系结构，确定系统及接口、全局数据结构或数据库模式 |
| 详细设计 | 确认每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。 |
| 按技术观点划分 | 结构设计 | 定义软件系统各主要部件之间的关系 |
| 数据设计 | 将分析时创建的模型转换成数据结构的定义 |
| 接口设计 | 描述软件内部、软件和协作系统之间以及软件与人之间如何通信 |
| 过程设计 | 把系统结构部件转换成软件的过程描述 |
- 软件设计基本原理与原则：
(1). 模块化，但要避免模块的数目过多或过少；(2). 抽象；(3). 信息隐藏——指出设计和确定模块时应使得一个模块中包含的信息对不需要这些信息的模块来说是不能访问的；(4).模块独立性——每个模块完成一个相对独立的特定子功能，并且和其他模块间的关系很简单。模块的独立性是设计好坏的关键，可以用耦合和内聚两个定性指标来衡量，一般来说，要求模块之间的耦合尽可能弱，即模块尽可能独立，且模块的内聚程度尽可能高。实践表明，内聚更加重要，应把更多精力放到提高模块的内聚程度上。
3.3.2 概要设计(总体设计)
- 基本任务：
(1). 设计软件系统结构：过程如下：(2). 设计数据结构及数据库：实现需求定义和规格说明中提出的数据对象的逻辑表示。
(3). 编写概要设计文档：概要阶段的文档有概要设计说明书、数据库设计说明书、集成测试计划。
(4). 概要设计文档评审：对其进行评审。 - (程序)结构图：构成的基本形式有顺序形式、选择形式和重复形式。4种经常使用的模块类型：传入模块、传出模块、变换模块和协调模块。软件的结构是一种层次化的关系，支持了软件的各个模块之间的关系。
| 概念 | 含义 | 图符 |
|---|
| 模块 | 一个矩形代表一个模块 | 矩形 |
| 调用关系 | 矩形之间的调用关系用矩形之间的箭头表明 | 箭头或直线 |
| 信息 | 用带注释的箭头表名模块调用过程中来回传递的信息 | 数据信息是带空心圆的箭头，控制信息则是带实心箭头 |
| 协调模块 | 对所有下属模块进行协调和管理 |
|
| 传入模块 | 从下级模块取得数据，经处理传到上级模块 |
|
| 变换模块 | 从上级模块取得数据，经过特定的处理转换成其他形式，再传送给上级模块 |
|
| 传出模块 | 从上级模块取得数据，经处理传给下级模块 |
|
| 上级模块 | 控制其他模块的模块 |
|
| 从属模块 | 被另一个模块调用的模块 |
|
| 原子模块 | 树中位于叶子节点的模块，没有从属节点的模块 |
|
| 深度 | 表示控制的层数 |
|
| 宽度 | 最大模块数的层的控制宽度 |
|
| 扇入 | 调用一个给定模块的模块个数 |
|
| 扇出 | 由一个模块直接调用的其他模块个数 |
|
- 面向数据流的设计方法：在需求分析阶段产生了数据流图，而面向数据流的结构化设计能够很轻易的将数据流图转换成程序结构图。
(1). 数据流图的类型：数据流图的信息流可分为两种类型：变换流和事务流。相应地，数据流图可分为变换型和结构型两种类型。
(2). 变换型：信息沿着输入通路进入系统，从外部形式变成内部形式；然后经过变换中心(主加工)；再沿着输出通路变换成外部形式离开软件系统。这种信息流就是变换流，这种数据流图就是变换流图。
(3). 事务型：信息沿着输入通路到达一个事务中心，事务中心根据输入信息的类型在若干个处理序列中选择一个来执行。这就是事务流，有明显的事务中心，各活动流以事务为起点成辐射状流出。
(4). 面向数据流的结构化设计过程：确认数据流图的类型；说明数据流的边界；把数据流图映射为结构图，根据数据流图的类型进行事务分析或变换分析；根据设计原则进行结构优化。
(5). 结构化设计的原则：提高模块独立性；模块规模应适中；深度、宽度、扇入和扇出都适当；模块的作用域应位于控制域之内；降低模块之间接口的复杂程度；设计单入口单出口的模块；模块功能可以预测。
3.3.3 详细设计
- 任务：为软件结构图中的每一个模块确定实现算法和局部数据结构。
- 过程设计工具：
(1). 程序流程图：方框表示加工步骤；菱形表示逻辑条件；箭头表示控制流。程序流程图不便于表示数据结构。
(2). N-S图：用方框图来代替传统的程序流程图。
(3). PAD图：问题分析图，用二维树形结构表示程序的控制流，将这种图翻译成程序代码较容易。
(4). PDL：过程设计语言，也称为伪码。
3.4 软件测试
在软件投入使用之前尽可能多的发现软件中的错误，是保证软件质量、可靠性的关键步骤，是对软件规格说明、设计和编码的最后复审。
- 软件测试目的：根本目的在于尽可能多的发现并排除软件中隐藏的错误。
- 软件测试准则：
(1). 所有测试都应追溯到用户需求；
(2). 在测试之前制定测试计划，并严格执行；
(3). 充分注意测试中的群集现象；
(4). 避免由程序的编写者测试自己的程序；
(5). 不可能进行穷举测试；
(6). 妥善保存测试计划、用例、出错统计和分析报告，为维护提供方便。 - 软件测试方法：根据软件是否被执行，分为静态和动态测试。按照功能分，可以分为白盒测试和黑盒测试。
(1). 静态测试：包括代码检查、静态结构分析、代码质量度量等；不实际运行软件，而是通过人工进行分析。
(2). 动态测试：上机测试，关键在于设计合理、高效的测试用例。测试用例的设计方法分为白盒测试方法和黑盒测试方法。
(3). 白盒测试：(又称结构测试或逻辑驱动测试)把程序看成装在一只透明的白盒子里，测试者必须完全了解程序的结构和处理过程。根据程序的内部逻辑来设计测试用例。其主要是在程序内部进行，完成软件内部操作的验证。主要技术有逻辑覆盖测试和基本路径测试等。
逻辑覆盖测试：语句覆盖(选择足够多的测试用例，使被测程序中的每个语句至少执行一次，是逻辑覆盖中的基本覆盖，但是没有关注判断的条件中隐含的错误)和路径覆盖(执行足够的测试用例，使程序中所有可能的路径至少经历一次)、判定覆盖(对每个判断条件的取值分支T或F都要测试一次)、条件覆盖(设计测试用例保证程序中的每个判断的每个条件的可能取值至少执行一次，但可能忽略全面的判断覆盖的要求)、判断-条件覆盖(使判断中每个条件的所有可能取值至少执行一次，同时每个判断的所有取值分支至少执行一次)。
基本路径测试：根据控制流程确定程序的基本环路集合，由此导出一组测试用例对每一组独立执行路径进行测试。环路复杂度=程序流程图中的判断框个数+1就是要设计测试用例的基本路径数。
(4). 黑盒测试：把程序看成一只黑盒子，完全不考虑程序的结构和处理过程，根据规格说明书的程序外部功能来设计测试用例，检查是否符合规格说明的要求。常见测试法有：等价类划分法、边界值分析法(设计测试用例使之刚好运行在边界情况附近，揭露错误)、错误推测法(列出所有的错误和易错情况表，基于此设计测试用例；针对性强，非常实用，但是需要丰富经验)等。 - 软件测试的实施：过程：单元测试、集成测试、确认测试(验收测试)、系统测试。
(1). 单元测试：针对单个模块(软件设计的最小单位)测试，对软件进行正确性的检验，以尽早发现模块内部可能存在的各种错误。它在编码阶段进行，依据是源程序和详细设计说明书。采用静态或动态测试，动态以白盒测试法为主，测试其结构，黑盒测试法为辅，测试其功能。因为测试的是单模块，需要一些辅助模块去模拟与被测模块相联系的其他模块，即为测试模块设计驱动模块(相当于主程序，接收测试数据，传给被测模块，输出结果)和桩模块(虚拟子程序，代替被测模块调用的模块，接受被测模块的调用，默认被调用的子模块的功能，将结果返回被测模块)，构成其测试环境。
(2). 集成测试：组装测试，对各模块按照设计要求组装成的程序进行调试，主要目的是发现与接口有关的、设计阶段产生的错误。依据是概要设计说明书，通常采用黑盒测试。内容主要是软件单元的接口测试、全局数据结构测试、边界条件测试、非法输入测试。方式可分为非增量方式集成(先分别测试每个模块，再按设计要求组装在一起进行整体测试)和增量方式集成(把要测试的模块和已经测试的模块连接起来测试，测试完把下一个模块连接进来测试)。
(3). 确认测试：检查软件的功能、性能是否与用户需求一致，依据是需求规格说明书，常采用黑盒测试。首先测试程序是否满足规格说明书上的各种要求，然后进行软件配置复审，保证软件配置齐全、分类有序。
(4). 系统测试：在实际运行环境中进行的一系列集成测试和确认测试，目的是在真实的系统工作环境检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。
3.5 程序调试
在对软件进行成功的测试之后进行程序的调试，诊断和改正程序中的错误。
程序调试基本概念：测试发现错误，调试是在成功测试(发现了错误的测试)之后排除错误的过程。软件测试贯穿整个软件生命期，调试主要在开发阶段。
程序调试的基本步骤：
(1). 错误定位；(2). 修改设计和代码，排除错误；(3). 进行回归测试，防止引进新的错误。
程序调试的原则：
(1). 错误定性和定位的原则： 集中思考分析与错误现象有关的信息；不钻死胡同；不要过分依赖调试工具；避免用试探法；
(2). 修改错误的原则：错误可能群集；要修改错误本身；必须进行回归测试；修改源代码程序，不要改变目标代码。
软件调试方法：从是否追踪和执行程序的角度，分为静态(主要调试手段)和动态调试(通过人的思维分析代码调错，辅助手段)。
(1). 强行排错法：传统方法，很低效；设置断点，程序暂停，观察程序状态和继续运行程序。
(2). 回溯法：相当常用，适合小程序；大程序回溯可能性很低。
(3). 原因排除法：二分法，归纳法，演绎法。都可以使用调试工具来辅助完成，但是工具不能完全替代。
第四部分 数据库设计基础
4.1 数据库系统的基本概念
- 数据：描述事物的符号记录。数据库中的数据被称为持久性数据，而存放在内存的数据称为临时性数据。
- 数据库：长期存储在计算机内、有组织的、集成的、可共享的数据集合，冗余度小，数据独立性和扩展性高。
- 数据库管理系统：系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制、保护和数据服务。
- 数据语言：包括交互式命令语言和宿主型语言，用于定义、操纵和控制数据。
- 数据库管理员：管理数据库的规划、设计、维护、监视的专人。
- 数据库系统：由以上的几个部分组成。
- 数据库应用系统：在数据库系统的基础上，使用数据库管理系统软件和数据库开发工具书写出应用程序，开发出应用界面，就构成了数据库应用系统。由数据库系统、应用软件、应用界面组成。
- 数据库技术的发展阶段：
| 背景 | 人工管理阶段 | 文件管理阶段 | 数据库系统管理阶段 |
|---|
| 应用背景 | 科学技算 | 科学计算、管理 | 大规模管理 |
| 硬件背景 | 无直接存取设备 | 磁盘、磁鼓 | 大容量磁盘 |
| 软件背景 | 无操作系统 | 有文件系统 | 数据库管理系统 |
| 处理方式 | 批处理 | 联机实时处理、批处理 | 分布处理、联机实时处理和批处理 |
| 特点 |
|
|
|
| 数据管理者 | 人 | 文件系统 | 数据库管理系统 |
| 数据面向的对象 | 某个应用程序 | 某个应用程序 | 现实世界 |
| 数据共享程度 | 无共享，冗余度大 | 共享性差，冗余度高 | 共享性大，冗余度小 |
| 数据独立性 | 不独立，完全依赖于程序 | 独立性差 | 具有高度的物理独立性和逻辑独立性 |
| 数据结构化 | 无结构 | 记录内部有结构，整体无结构 | 整体结构化，用数据模型描述 |
| 数据控制能力 | 由应用程序控制 | 由应用程序控制 | 由DBMS提供数据安全性、完整性、并发控制和恢复 |
- 未来的数据库系统应支持数据管理、对象管理、知识管理，应具有面向对象的基本特征。
- 数据库系统的基本特点：数据集成性、数据共享性高，冗余性低(保证系统一致性的基础)、数据独立性高、数据统一管理与控制。
- 数据库系统体系结构：(应用——>外模式——>外模式/概念模式映射——>概念模式——>概念模式/内模式的映射——>内模式——>数据库) 三级模式和两级映射。
(1). 数据库系统的三级模式结构：
a. 外模式：也称子模式或用户模式，是用户的数据视图，是用户所能够看见和使用的局部数据的逻辑结构和特征的描述，是与某一应用有关的数据的逻辑表示。外模式通常是模式的子集，它反映了用户对数据的要求。
b. 概念模式：模式，是数据库系统中全局数据逻辑结构的描述，全体用户的公共数据视图。概念模式处于中层，反映了设计者的数据全局逻辑要求。
c. 内模式：又称物理模式，是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。内模式处于最底层，反映了数据在计算机物理结构中的实际存储方式。
三个级别的模式层次反映了它们的不同环境和要求，其中内模式处于底层，概念模式处于中层，外模式处于最外层。一个数据库只有一个内模式和概念模式，可以有多个外模式。
(2). 数据库系统的二级映射：
这是在三级模式之间提供的两级映射：外模式/概念模式的映射(使数据库中的数据具有较高的逻辑独立性)，概念模式/内模式的映射(使数据库中的数据具有较高的物理独立性)。
4.2 数据模型
现有的数据库系统都是基于某种数据模型而建立的，数据模型是数据库系统的基础。
数据模型三要素：
(1). 数据结构：对系统静态特征的描述，是数据模型的核心。
(2). 数据操作：对系统动态特征的描述，是允许的操作的集合。
(3). 数据约束：特定的语义约束条件，保证数据的正确、有效、相容。
数据模型的类型(按不同的应用层次分成三种)：
(1). 概念数据模型(概念模型)：一种面向客观世界、面向用户的模型，与具体的平台和系统无关。
(2). 逻辑数据模型(数据模型)：面向数据库系统的模型，着重与数据库系统一级的实现。
(3). 物理数据模型(物理模型)：面向计算机物理实现的模型。
E-R模型：实体联系模型。有1:1、1:n、n:m三种联系。可以直观的用E-R图表示。属于概念模型。
层次模型：用树形结构表示实体及其联系，节点是实体，树枝是联系，从上到下是一对多的联系，有且只有一个根节点。
网状模型：用网状结构表示实体及其联系，是层次模型的扩展，允许一个或多个节点无父节点，一个节点可以有多于一个的父节点。
关系模型：用二维表来表示关系，以其为基本结构建立的模型称为关系模型。
4.3 关系代数
表示关系模型的数据操作的相关理论——关系代数和关系演算。
- 关系代数的基本运算：
(1). 投影运算：从关系模式中指定若干属性组成新的关系。是对列属性的去重复。
(2). 选择运算：从关系模式中找出满足指定条件的数据项的操作称为选择。
(3). 笛卡尔积：设有n元关系R和m元关系S，它们分别有p和q个记录，则笛卡尔积为RxS，是一个m+n元关系，记录有pxq个。 - 关系代数的扩充运算：
(1). 交。集合运算之一，是两个关系的交集。
(2). 连接和自然连接。连接是从两个关系的笛卡尔积中选择满足给定属性间的一定条件的那些元组。其中的一个特例是自然连接，要求两个关系中进行比较的是相同的属性，并且进行等值连接，还有去掉重复的属性列。
(3). 除。近似于笛卡尔积的逆运算。
(4). 并。集合运算之一，是两个关系的并集。 - 关系代数的应用实例：关系代数虽然形式简单，但它足以满足对表的查询、插入、删除和修改操作。
4.4 数据库设计与管理
数据库设计是数据应用的核心，根本目标是要解决数据共享问题。
- 数据库设计：是对于一个给定的应用环境，构造最优的数据库模式，建立性能良好的数据库，满足用户的信息需求(静态要求)和处理需求(动态要求)。
- 数据库设计方法：面向数据的方法：以信息需求为主，兼顾处理需求；面向过程的方法：以处理需求为主，兼顾信息需求。面向数据的方法是主流。
- 数据库设计的步骤：
生命周期法：
(1). 需求分析阶段：成果：需求说明书。设计数据库的起点，收集到的基础数据和数据流程图是下一步设计概念结构的基础。方法主要有两种：结构化分析(SA，自顶向下，逐步分解；使用数据流程图和数据字典，数据字典包含数据项、数据结构、数据流、数据存储和处理过程)和面向对象分析。
(2). 概念设计阶段：成果：概念数据模型。分析数据间的语义关联，在此基础上建立一个数据的概念模型。方法有集中式模式设计法(设计简单方便，强调统一一致，适合小型单位)和视图集成设计法(先做局部在合并；选择局部应用，视图设计——逐一设计分E-R图，视图集成——合并E-R图，得到概念模式，常见的冲突有命名、概念、域、约束冲突；策略：自顶向下，自底向上，自内向外)。
(3). 逻辑设计阶段：成果：逻辑数据模型。将E-R图转换为关系模式(即关系数据模型)，这就是逻辑设计的主要内容。在关系模式的基础上进行关系视图设计(外模式设计，用户子模式设计)，关系视图具有优点(提供数据逻辑独立性；能够适应用户对数据的不同需求；有一定的数据保密功能)。其后还要进行规范化。
(4). 物理设计阶段：成果：数据库内模型。是为一个给定的逻辑模型选取一个最适合应用要求的物理结构的过程。一般留给用户的内容有索引设计、集簇设计、分区设计。 - 数据库管理：对数据库中的共享资源进行维护和管理，这是数据库管理员的责任。包含数据库的建立、调整、重组、安全性和完整性控制、故障恢复、数据库监控6大功能。
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
