公共基础知识

关于公共基础知识的思维导图，汇总了数据库设计基础、软件工程基础、数据结构和算法、程序设计基础的知识，大家可以学起来哦。

公共基础知识

1.4数据库设计基础

1.基本概念

数据库

长期存储在计算机内的，有组织的、可共享的数据集合

数据库管理系统

是数据库机构，是一个系统软件，负责数据库中的数据组织、数据操控、数据维护、控制及保护和数据服务等

功能

数据模式定义

数据存取的物理构建

数据操纵

数据的完整性

安全性的定义与检查

数据库的并发控制与故障恢复

数据的服务

数据语言

为满足以上6个功能，GBMS提供了相应的数据语言

数据定义语言

数据操纵语言

数据控制语言

数据库管理员

数据库设计

数据库维护

改善系统性能

提高系统效率

数据库系统

数据库

数据库管理系统

数据库管理员

系统平台1—硬件平台

系统平台2—软件平台

数据库应用系统

数据库

数据库管理系统

人员（数据库管理员和用户）

硬件平台

软件平台

应用软件

应用界面

数据库技术的发展

人工管理阶段

在这个阶段，没有专门的软件对数据进行管理

文件系统阶段

数据库系统阶段

数据库系统的基本特点

数据的集成性

数据的高共享性和低冗余性

数据的独立性

物理独立性

逻辑独立性

数据统一管理与控制

数据库系统的内部结构体系

三级模式

概念模式

概念模式是数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图。

外模式

外模式（子模式、用户模式），是用户的数据视图，也是用户所能够看见和使用的局部数据的逻辑结构和特征的描述，是与某一应用有关的数据逻辑表示。

内模式（物理模式）

内模式（物理模式），是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。

两级映射

两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性

外模式/概念模式的映射

概念模式/内模式的映射

2.数据模型

数据模型

概念

三要素

数据结构

数据操作

数据约束

类型

概念模型

数据模型

物理模型

E-R模型

基本概念

实体

属性

联系 

基本概念之间的连接关系

一对一

一对多

多对多

E-R图

关系模型

数据结构

常用术语

关系

属性

值域

元组

候选码

主键或主码

外键或外码

性质

元组个数的有限性

元组的唯一性

元组分量的原子性

属性名唯一性

属性的次序无关性

分量值域的统一性

完整性约束

实体完整性约束

参照完整性约束

用户定义的完整性约束

3.关系代数

差运算

交运算

并运算

笛卡尔积运算

投影运算

选择运算

除运算

连接运算

4.数据库设计

概述

基本思想

过程迭代

逐步求精

方法

面向数据的方法

面向过程的方法

设计过程

需求分析

概念设计

逻辑设计

物理设计

编码

测试

运行

进一步修改

需求分析

方法

结构化分析法（自顶向下、逐层分解）

面向对象的方法

主要工作

绘制数据流程图

数据分析

功能分析

确定功能处理模块

数据间关系

设计

数据库概念设计

数据库逻辑设计

数据库物理设计

范式

p28 右下

第一范式

第二范式

第三范式

1.3软件工程基础

1.基本概念

定义

（1）计算机软件是由程序、数据及相关文档构成的完整集合，与计算机硬件组成计算机系统

（2）程序和数据是机器可执行的，文档是不可执行的

特点

<ul><li>软件是一种逻辑实体、具有抽象性</li></ul>

<ul><li>软件没有明显的制作过程</li></ul>

<ul><li>软件在使用期间不存在磨损、老化问题</li></ul>

<ul><li>对硬件和环境具有依赖性</li></ul>

<ul><li>软件复杂性高、价格昂贵</li></ul>

<ul><li>软件开发涉及诸多社会因素</li></ul>

软件的分类

系统软件

管理计算机的资源，提高计算机的使用效率，为用户提供各种服务的软件

应用软件

为了应用于特定的领域而开发的软件

支撑软件

介于系统软件和应用软件之间，协助用户开发软件的工具型软件

软件工程

软件工程是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术和管理方法，是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

要素

方法

工具

过程

原则

抽象

信息隐蔽

模块化

确定性

一致性

完备性

可验证性

软件过程

把输入转化为输出的一组彼此相关的资源和活动

进行的基本活动

软件规格说明

软件开发或软件设计与实现

软件确认

软件演进

软件的生命周期

周期

软件定义期

问题定义

可行性研究

需求分析

软件开发期

概要设计

详细设计

实现

测试

运行维护期

使用和维护

2.需求分析及其方法

需求分析

需求分析相关概念

需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将创建所需的数据模型、功能模型和控制模型。

需求获取

需求分析

编写需求规格说明书

需求评审

需求规格说明书

重点描述软件的目标，软件的功能需求、性能需求、外部接口、属性及约束条件

特点：正确性；无歧义；完整性；可验证性；一致性；可理解性；可修改性；可追踪性

需求分析方法

结构化分析方法

面向数据流的结构化方法

面向数据结构的Jackson系统开发方法

面向数据结构的结构化数据系统开发方法

面向对象分析方法

静态分析方法

动态分析方法

结构化分析方法常用工具

数据流图、数据字典、结构化英语、判定表、判定树等

数据流图&nbsp; 的构造规则和注意事项

（1）数据流图上的每个元素必须命名

（2）对加工处理建立唯一、有层次性的编号，且每个加工处理既有输出也有输入

（3）数据存储之间没有数据流

（4）数据流图的一致性

（5）父图、子图关系与平衡规则

3.软件设计及其方法

基本概念

软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务（软件设计是确定系统的物理模型）

从工程管理角度划分

概要设计

（1）概要设计的主要任务：将软件按功能分解为组成模块 （2）划分模块的原则：提高独立性 （3）模块独立程度的两个定性标准度量：内聚性、耦合性 （4）好的软件设计应做到（高内聚、低耦合

内聚性

耦合性

详细设计

从技术观点划分

软件结构设计

数据设计

接口设计

过程设计

概要设计

任务

设计软件系统结构

数据结构及数据库设计

编写概要设计文档

概要设计文档评审

结构图（程序结构图）

p21 左上

详细设计

常用设计工具

程序流程图（PFD）

N-S图

PAD图

HIPO图

判定表

PDL

4.软件测试

目的和准则

目的：发现软件中的错误

准则

（1）所有软件都应追溯到用户需求

（2）在测试之前指定测试计划，并严格执行

（3）充分注意测试中的群集现象

（4）避免由程序的编写者测试自己的程序

（5）不可能进行穷举测试

（6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便

方法

按是否被执行划分

静态测试

不实际运行代码，主要通过人工进行分析

代码检查

代码审查

代码走查

桌面检查

静态分析

静态结构分析

代码质量度量

动态测试

设计高效、合理的测试用例

测试输入数据

预期输出结果

按功能划分

白盒测试

逻辑覆盖测试

语句覆盖

路径覆盖

判定覆盖

条件覆盖

判断—条件覆盖

基本路径测试

黑盒测试

设计测试用例的根据是 软件要完成的功能

等价类划分法

边界值分析法

错误推测法

因果图

软件测试实施的步骤

单元测试

单元测试是代码编写阶段可进行的软件测试

集成测试

确认测试（验收测试）

系统测试

5.程序调试

程序调试的任务是诊断和改正程序中的错误

程序调试活动

根据错误的迹象确定程序中错误的确切性质、原因和位置

对程序进行修改，排除这个错误

调试方法

静态调试

静态调试是主要的调试手段，通过人的思维来分析源程序代码和排错

动态调试

动态调试是静态测试的辅助

强行排错法

回溯法

原因排除法

二分法

归纳法

演绎法

1.1数据结构和算法

1.算法

（1）算法是指对解题方法的准确而完整的描述。 （2）算法不等于数学上的计算方法，也不等于程序。 （3）程序可以描述算法。

基本特征

可行性

确定性

有穷性

拥有足够的情报

算法复杂度

算法复杂度用于衡量算法的优劣

时间复杂度

指执行算法所需要的计算工作量

空间复杂度

指执行这个算法所需要的内存空间

2.数据结构基本概念

数据结构

数据结构 是指相互有关联的数据元素的集合。包含“数据”与“结构”两个要素。 （1）数据是需要处理的数据元素集的集合，这些数据元素具有某个共同的特征。 （2)结构就是关系，是集合中各个数据元素之间存在的某种关系（联系）。

逻辑结构

逻辑结构指反映数据元素之间的逻辑关系（即前后件关系）的数据结构

存储结构

存储结构又称数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式

数据结构的表示

二元关系表示

图形表示

由前后件引出的三个概念

（1）根节点

没有前件的节点

（2)终端节点（叶子节点）

没有后件的节点

（3）内部节点

数据结构中，除了根节点和终端节点以外的节点

线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，将数据结构划分为两大类型

线性结构

（1）有且只有一个根节点 （2）每一个节点最多一个前件，也最多一个后件

非线性结构

不满足线性结构的两个条件即为非线性结构

3.线性表及其顺序存储结构

（1）线性表是n（n>=0）个数据元素组成的有限序列。 （2）非空线性表可表示为（a1,a2,a3,…,an），其中a为线性表的数据元素，也称为线性表的一个节点，同一线性表中元素一定含有相同特性，即属于同一数据对象。 （3）数组、矩阵、向量等都属于线性表。

非空线性表结构特征

<span style="font-size: inherit;">（1）只有一个根节点</span><br>

（2）有且只有一个终端节点

（3）除根节点与终端节点外，所有节点有且只有一个前件，也有且只有一个后件

顺序存储结构

（1）顺序表可以采用顺序存储和链接存储两种方式。 （2）顺序存储是最简单的一种方式。 （3）具体做法：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。

基本特征

（1）线性表中所有元素所占的存储空间都是连续的

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

4.栈和队列

栈与其基本运算

先进后出

栈顶指针top反映栈的状态变化

栈的三种基本运算

入栈

退栈

读栈顶元素

队列及其基本运算

先进先出

队尾指针rear和队头指针front共同反映队列元素的动态变化

循环队列及其运算

front=rear=m，循环队列初始状态为空

s=0，队列为空

s=1且front=rear表示队满

5.线性链表

线性链表的基本概念

线性链表

线性链表的存储单元是任意的，即各数据节点的存储序号可以是连续的，也可以是不连续的

带链的栈

把栈组织成一个单链表

带链的队列

顺序表和链表的比较

循环链表

6.树与二叉树

树的基本概念

树的节点数=树中所有节点的度之和+1

父节点（根）

子节点和叶子节点

度

深度

子树

二叉树基本性质

定义

二叉树的特点： （1）二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点。 （2）每个节点最多有两棵子树，即二叉树中不存在度大于2的节点。 （3）二叉树的子树有左右之分，次序不能颠倒。

性质

（1)在二叉树的第k层上，最多有2^k-1(k>=1)个节点

（2）深度为m的二叉树中，最多有（2^m ）-1个节点

（3）任何一颗二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个

（4）具有n个节点的二叉树，其深度至少为(log2n)+1,其中log2n取整数部分

（5）具有n个节点的完全二叉树深度为（log2n）+1

满二叉树和完全二叉树

（1）满二叉树：除最后一层外，每一层的所有节点都有两个子节点。eg：深度为4的满二叉树 （2）完全二叉树：除叶子节点外，每一个节点的度都为2

二叉树存储结构

（1）通常采用链式存储结构，又称为二叉链表； （2）二叉树的一个存储节点包括：左指针域L（i)、数据域Data(i)、右指针域R(i);

二叉树的遍历

先序遍历（前序遍历）

根左右

中序遍历

左根右

后序遍历

左右根

7.查找技术

顺序查找

最好情况下：1次

最坏情况下：n次

平均情况下：n/2次

二分法查找

最坏情况下：log2n次

8.排序技术

交换类排序

冒泡排序

最坏情况下：n(n-1)/2次

快速排序

最坏情况下：n(n-1)/2次

插入类排序

简单插入排序

最坏情况下：n(n-1)/2次

希尔排序

最坏情况下：n^r (1<r<2)

选择类排序

简单选择排序

最坏情况下：n(n-1)/2次

堆排序

最坏情况下：nlog2n次

1.2程序设计基础

1.程序设计风格

“清晰第一，效率第二”

源程序文档化

数据说明风格

语句的结构

输入和输出

2.结构化程序设计

原则

自顶向下、逐步求精、模块化及限制使用goto语句

基本结构

顺序结构

选择结构

循环结构

三种结构共同特征：严格地只有一个入口和一个出口

优点

程序易于理解、使用和维护

提高了编程的工作效率，降低软件开发成本

3.面向对象的程序设计

面向对象方法的优点

与人类习惯的思维方法一致

稳定性好

可重用性好

容易开发大型软件产品

可维护性好

面向对象方法的基本概念

对象

数据（属性）：对象所包含的信息，表示对象的状态

方法（操作）；对象所能执行的功能、所能具有的行为

类和实例

消息

继承

多态性