导图社区 A计算机软件
- 54
- 2
- 1
- 举报
A计算机软件
江苏专转本计算机大类复习导图，计算机软件是以电子格式存储的程序、数据和相关的文档以文件的形式存储在外存中，即软件（软件系统）=程序+数据+相关文档。
编辑于2023-03-24 11:58:05 江苏省- 江苏专转本计算机
- 相似推荐
- 大纲
A计算机软件
计算机软件
软件基本概念
软件定义
以电子格式存储的程序、数据和相关的文档以文件的形式存储在外存中，即软件（软件系统）=程序+数据+相关文档
用户文档内容
安装说明
使用说明
功能说明
在Windows中，对用户新建的文档，系统默认的属性为存档
软件版权
受到知识产权法的保护（不是知识产权），用户仅仅得到了该软件的使用权
软件的特性
不可见性
易复制性
适用性
依附性
复杂性
脆弱性
无磨损性
不断演变性
延长软件的生命周期
有限责任
软件厂商无法给出承诺
若某单位的多台计算机需要安装同一软件，则比较经济的做法是购买该软件的多用户许可证
软件许可证规定的计算机软件使用方式的法律合同
软件产品的设计报告，维护手册和用户使用指南也属于计算机软件
软件虽然不是物理产品而是一种逻辑产品，但通常必须使用物理载体进行存储和分发，通常以电、磁、光等形式存储和传输
软件分类
从软件用途和功能分类
系统软件（与具体应用领域无关）
（核心 ）操作系统(OS)
Windows
Unix
Linux
安卓
iOS
Windows Phone
MAC OS
DOS
数据库管理系统(DBMS)
MySQL
特点
体积小
成本低
速度快
SQL Server
NoSQL
Oracle
Access
Sybase
VFP
POSTGRES
程序设计语言处理系统
语言编译器
实用程序
磁盘清理程序
备份程序
杀毒软件
汇编程序
解释程序
防火墙
无编辑程序
BIOS
应用软件
从应用角度分类
通用应用软件
使用广泛
常见通用应用软件
Powerpoint
不属于网络应用软件
Photoshop
CorelDraw
Word
WPS
Notepad（记事本）
Acrobat Reader
属于文字处理软件
定制应用软件
专门设计开发，成本相对较高
常见的定制应用软件
户籍系统
档案管理系统
银行内部使用的交易系统
为解决各类应用问题而编写的程序称为应用软件
应用软件以系统软件为基础
其它软件
商品软件
需付费才能获得其使用权，这类软件的升级不总是免费的
例如Windows操作系统
共享软件
用于销售，允许拷贝，传播和免费试用
不允许修改
例如微软Visio
自由/开源软件
允许随意拷贝和修改其源代码
允许销售和自由传播
对源代码的修改必须向所有用户公开
倡导“非版权”原则
理查德·斯塔尔曼是自由软件的创始人
GNU——自由软件工程
FSF——自由软件基金会
GPL——自由软件的通用公共许可证
例如
Linux操作系统
TCP/IP协议
MySQL
Apache服务器软件
FireFox浏览器
LibreOffice办公套件
免费软件
自由软件通常都是免费软件，免费软件不一定是自由软件
例如QQ，微信，PDF阅读器
网页制作软件
常见
Front Page 2000
Web Page Maker
ASP Make
Dreamweaver
操作系统(OS)
作用
20世纪50年代后期出现，作为计算机运行配置必不可少的底层系统软件，承担着用户与硬件（计算机）之间接口的任务，也是硬件和其它软件之间的接口
未安装操作系统的计算机称为裸机，是无法使用的
类型
实时操作系统
对计算机完成任务有严格的时间约束，对外部事件能快速作出反应
分时操作系统
采用时间片轮转的方式有效增加资源的使用率
例：一台计算机有30个终端用户同时使用c语言系统。该计算机使用的是分时操作系统
分布式操作系统
批处理操作系统
基本功能
操作系统的启动
BIOS→CPU→硬盘→操作系统
作用
为计算机中运行的程序管理和分配各种软硬件资源
为应用程序的开发和运行提供一个高效的平台
为用户操作使用计算机提供友善的人机界面
如Windows的GUI——图形用户界面
采用图标来形象的表示系统中的文件，程序，设备的对象
辅助用户操作，保护系统安全
任务
定义
已经启动执行的一个应用程序
结束任务：从内部存储设备上结束（非删除）任务所对应的程序
操作系统只把用户输入的信息传送到活动窗口所对应的前台任务中
操作系统对用户屏蔽了实现具体设备I/O操作的细节
操作系统管理用户数据的单位是文件
操作系统必须提供的功能是处理中断
功能
多任务处理和处理器（CPU）管理
提高CPU和其它计算机资源的利用率
任务分类
前台任务（只能有一个）
能接受用户输入的窗口只能有一个，称为活动窗口
并发多任务
任何时刻只有一个任务正在被CPU执行
多任务处理并不一定需要多核CPU的硬件支撑
进程与线程
进程（“爹”）
定义
操作系统对处理器进行管理的最基本单位
指在系统中正在运行的一个应用程序
程序一旦运行就是进程
一个进程只能对应一个应用程序，而一个应用程序可以有多个进程
线程（“儿”）
定义
系统分配处理器时间资源的最小单位
多线程的目的
充分利用CPU的资源，提高程序执行效率
进程与线程的关系
一个线程只能属于一个进程，而一个进程可以有多个线程（至少一个线程）
资源分配给进程，处理器分配给线程
进程与线程的根本区别
进程是操作系统资源分配的基本单位
线程是处理器任务调度和执行的基本单位
文件管理(外存)
功能
实现按文件名存取
文件名的组成
主文件名.扩展名，主文件名不可以省略，扩展名可以省略
文件名的命名原则
不可以使用系统保留的关键字CON、PRN
文件名最多有255个字符（中文或西文字符）
Windows中文件名不区分大小写
文件名中可以使用空格，文件名开头不保留空格
应用程序扩展名
.exe（Windows）
.ipa（iOS）
.apk（安卓）
文件的组成
文件说明信息
存放在文件的目录中
文件内容
存放在磁盘的数据区中
对外存的管理，通常采用文件目录来组织和管理外存中的信息
Windows文件目录采用多层次树状结构
Windows中物理硬盘能建立多个根目录，不同的根目录对应的是不同的逻辑分区，且根目录不可以删除
回收站
回收站的内容占用硬盘空间
软盘和U盘上被删除的文件或文件夹不可以用回收站将其恢复
存储管理(内存)
操作系统中解决存储管理的有效方案是虚拟存储器技术(VM)， 虚拟存储器技术：把内存和外存(硬盘)结合起来管理
虚拟存储器技术是扩充逻辑地址空间技术
虚拟存储器是由物理内存和硬盘上的虚拟内存(一个名为pagefile.sys(隐藏文件)的大文件，称为“页面文件”)联合组成的，用户可以修改其文件名，但因为虚拟内存是系统默认的，所以不可选择不使用
虚拟内存=物理内存+硬盘的虚拟内存
虚拟内存是硬盘上的一块区域，虚拟内存大小可由用户自定义，可以比实际内存小，大或相等
虚拟存储系统容量大小受到硬盘容量和CPU寻址能力的影响
页面调度算法采用"最近最少使用(LRU)"算法，调度的单位：页
内存储器空间组成
系统区
用户区
用来存放正在运行的应用程序
功能
主存空间的分配和回收
主存空间的共享和保护
实现地址转换
设备管理(I/O设备)
设备驱动程序
使用U盘一般不需要专门安装相应的驱动程序
打印机驱动程序一般由操作系统自带，或由打印机厂商提供
驱动程序是操作系统和硬件之间的接口
作业管理
作业的输入和输出
作业的调度和控制
特征
并发性
共享性
虚拟性
异步性
内核
Windows 10操作系统的内核是NT内核
iOS操作系统的内核是Darwin内核
CentOS7的内核是Linux内核
常用操作系统
个人计算机操作系统
单用户多任务
Windows 桌面版
Windows XP
Windows 10
多用户多任务
Windows服务器版
Windows 2003 Server
网络操作系统
多用户多任务
Linux （具有开放性）
原创者是芬兰的青年学者林纳斯·托瓦兹，开源，目前互联网服务器使用的最多的操作系统
linux和Unix也可以用于智能手机和平板电脑
UNIX （以树型目录结构的文件系统为基础）
Linux和Unix均可用于便携机
不开源
Windows Server
Windows NT
NetWare
Windows 7, Windows 10, Windows 11（只是多用户多任务，并不是网络操作系统）
普通操作系统不能作为网络操作系统安装在服务器上使用
网络操作系统都具备网络通信功能，使得计算机能够接入网络并正常工作
服务器操作系统
也可用于PC机
Linux
Unix
OS/2
Mac OS操作系统
由苹果公司自行开发，基于Unix内核，一般情况下，在普通PC机上无法安装
Windows XP（单用户多任务）只能作为网络客户机的操作系统（非网络操作系统），而不能作为服务器的操作系统
在使用Windows 98操作系统的PC机上第一次使用U盘时必须安装驱动程序
Windows Vista一般用于家庭娱乐，不属于网络操作系统
程序设计语言
分类
机器语言（现在已经不直接用机器语言编写程序）
用二进制表示，计算机可以直接识别执行
特点
不易记忆和理解
难于修改和维护
可移植性差
依赖于硬件
执行速度最快
汇编语言
用助记符来代替机器指令的操作码和操作数，可移植性差
汇编程序：从汇编语言到机器语言的翻译程序
机器语言和汇编语言都是面向机器的语言
高级语言
接近人们的自然语言，具有通用性，可移植性最强
为了提高软件开发效率，开发软件时应尽量采用高级语言
高级语言的翻译程序
解释程序（相当于口译）
特点
适用于程序调试，程序交互等
算法简单，灵活
便于查错
占用内存少
运行效率低
逐条解释，运行效率低
不产生目标程序
解释型语言
BASIC
Java
Python
PHP
VBS
编译程序（相当于笔译）
特点
适用于翻译规模大，结构复杂，运行时间长的大型应用程序
将高级语言源程序转换为目标程序的是编译程序
产生目标程序
编译型语言
C语言
C++
C＃
高级程序设计语言的编译程序和解释程序属于语言处理程序
运行效率：机器语言>汇编程序>高级语言
高级语言的解释程序，翻译程序，编译程序也属于系统软件
机器语言程序与高级语言程序的比较
机器语言程序比高级语言程序占用的存储空间小
机器语言程序比高级语言程序难于编写和调试
机器语言程序比高级语言程序可移植性差
机器语言程序比高级语言程序可读性差
机器语言程序比高级语言程序执行速度快
组成
运算成分
运算
算术表达式
逻辑表达式
传输成分
数据传输
赋值语句
输入/输出语句
例如scanf和printf
控制成分
控制构造
条件语句if
循环语句for和while
数据成分
数据对象
数据类型
以C语言为例
基本数据类型
整型（int）
字符型（char）
实型（float，double）
特殊类型
空类型（void）
用户定义类型
枚举类型（enum）
数据结构
程序的控制结构(易读性)
基本结构
顺序结构
选择结构(判断结构)
条件选择结构由条件和选择组成
循环结构
三种基本控制结构的共同特点是单入口和单出口
仅由顺序、选择和循环结构构成的程序是结构化程序
具体方法
自顶向下
规划与设计
逐步求精
模块化
限制使用goto语句
源程序执行方式
源程序
通过编译程序的处理，可以一次性的产生高效运行的目标程序，并把它保存在磁盘上，已备多次执行
高级语言编写的源程序被保存为文本文件
负责完成这些功能的软件(统称：程序设计语言处理系统，即翻译程序)
汇编程序
编译程序
不参与用户程序的运行控制
解释程序
参与用户程序的运行控制
执行过程
编辑源程序
编译源程序
进行连接处理
运行可执行程序并获得运行结果
编辑→编译→连接→运行
常用程序设计语言
FORTRAN语言
面向过程
用于科学与数值计算
BASIC语言
面向过程
C语言
C语言
面向过程
适合于开发系统软件，效率高
C＋＋
面向对象
面向对象程序方法的三个重要特征
封装性
继承性
多态性
对象的三要素
属性
方法
事件
C＃语言
面向对象
面向对象方法是20世纪90年代以来发展最快，使用最普遍的软件开发方法
运行于.NET平台，可跨平台运行
Java语言
面向对象
适用于网络环境编程，可跨平台运行，与使用任何操作系统无关
Python语言
面向对象
特点
用于web编程
可用于科学计算
属于自由软件（开源）
VB语言
定义
基于BASIC语言开发的一种程序设计语言
面向对象
可视化，事件处理
算法和数据结构
算法
概念
尼·沃思提出“数据结构＋算法＝程序” “计算机科学就是研究算法的学问”
软件的主体是程序，程序的核心是算法，数据结构能使算法有效的实现
不同的算法来求解同一问题，结果相同
不一定要用高级语言描述，算法的表示不一定能让计算机理解
数据的存储结构也会影响算法的效率
同一个算法，语言级别越低，执行效率就越高
相关问题
如何确定算法(算法设计)
由粗到细，由抽象到具体
如何表示算法(算法表示)
自然语言文字说明
流程图
伪代码（PDL）
程序设计语言
如何使算法更有效(算法的复杂性分析)
计算机资源
时间资源
空间资源
复杂度
时间复杂度：指执行这个算法所需要的计算工作量
空间复杂度：指执行这个算法所需要的内存空间，和求解问题的规模关系密切
时间复杂度和空间复杂度并不相关
算法分析的目的是分析算法的效率以求改进
组成
数据对象的运算与操作
控制结构
基本运算和操作
算术运算
逻辑运算
关系运算
数据传输
基本设计方法
列举法
归纳法
递归法
评价算法优劣的主要因素
算法复杂度
执行算法所占用的时间资源
执行算法所占用的空间资源
正确性
可读性
健壮性
指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性
基本要求
输入
一个算法中有0个或多个输入
输出
一个算法中有1个或多个输出
确定性
无二义性
有穷性
指算法必须在有限时间内完成，必须在有限步后终止
能行性
可执行
查找分类
顺序查找
效率最低
长度为n的线性表最坏查找次数为：n次
最大值或最小值的比较次数为n-1次
折半查找（二分查找）
效率最高
只适用于顺序存储的有序表
最坏比较次数：㏒2底n次
分块查找
效率居中，需要有序且最好为动态
补充
程序可以是死循环的（无限循环）
程序定义
错误分类
语法错误
例如
表达式缺少操作数
括号不匹配
关键词拼写错误
标点符号错误
语义错误
静态语意错误
定义
刚开始编译时就会报错
例如
10/0
b+a（a为数组名）
％运算对象类型不符
动态语义错误
定义
运行时报错
例如
a/0
a/b（b运算过程中被赋值为0）
死循环
数组下标越界
指针异常
实参传递问题
算法和程序是相应的，但不一一对应
程序是算法的具体代码实现
算法是程序设计的核心，算法的好坏直接决定了程序的效率
程序中的语句必须是机器可执行的，算法中的操作无此限制
数据结构
定义
指相互有关联的数据元素的集合
数据结构在计算机内存中的表示是指数据的存储结构
分类
线性结构(与数据的存储无关，独立于计算机)
特点
有且只有一个根节点
除了最后一个结点外，每个节点最多有一个前件，也最多有一个后件
所有的线性结构都可以采用顺序存储结构
研究数据元素之间的一对一关系
分类
线性表
基本概念：由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的
位序：数据元素在线性表中的位置
表项：表中的元素
空表：长度为0的表
基本运算
在线性表中查找某个特定元素
在线性表中查找某个元素的前驱元素
在线性表中查找某个元素的后继元素
判别一个线性表是否为空表
创建空线性表
在线性表中插入一个元素
插在第i个节点之前，移动（n-i+1）次（n为结点数，i为第i个结点）
在线性表中删除某个元素
删除第i个节点，移动（n-i）次
特点
数据元素都是整数
存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
复杂线性表中
由若干数据项组成的数据元素称为记录
由多个记录构成的线性表称为文件
存储结构
顺序存储结构
定义
用一组地址连续的存储单元及一维数组来存储
线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置上也相邻
优点
静态操作容易实现
可顺序/随机存取
缺点
动态操作实现效率较低
扩展不灵活，容易造成空间浪费
插入/删除不方便
链式存储结构
特点
插入删除不需要移动元素
不必事先估计存储空间
所需空间与线性长度成正比
缺点
不能随机访问任意元素
因为链式存储结构由指针域和数据域组成，还需要存储指针域，因此链式存储结构需要的存储空间比顺序存储大
链式存储可连续可不连续
线性表的链式表示和实现
顺序表
缺陷：插入/删除耗费大量时间
例：设顺序表的表长为n，则删除一个元素在最坏情况下元素移动次数为n+1
线性链表
节点
最后一个节点没有直接后继，其指针域为“空”(NULL)
指针域 ：存储直接后继的存储位置（地址）
数据域：存储数据元素信息
基本运算
查找
插入
删除
单链表
每个结点只包含一个指针域，若L==NULL,则表示单链表为空表，长度为0
带头结点的单链表
若头结点的指针域为“空”，即L→next==NULL，表示该链表为空表
头结点：位于首元节点的前面，是一个辅助结点
结构
data：数据域
next：指针域
动态建立单链表的常用方法
采用头插法
尾插法
循环链表(首尾相连)
优点
从表中任何一个节点位置出发，就可以不重复的访问到表中其他所有节点
基本运算
判断是否是空链表
head→next == head
判断是否是表尾结点
p→next == head
循环链表与单链表的区别
单链表存放的是空指针
循环链表最后一个结点的指针域存放的是指向第一个节点的指针
双向链表
优点
既可以找前驱，也可以找后继
方便数据插入和删除
两个指针
左指针（Llink）指向前件结点
右指针（Rlink）指向后件结点
采用链式存储，因为双向链表中有两个指针域，所以不能节约存储空间
栈
概念
仅能在表的一端进行插入和删除操作的线性表，具有记忆功能
特点
先进后出，后进先出
支持子程序调用
基本运算
入栈运算
退栈运算
读栈顶元素
操作
压入（PUSH）：S【top++】
s→top==0，栈空，此时出栈则下溢
s→top==MAXSIZE，栈满，此时入栈则上溢
弹出（POP）：e=S【--top】
层次
栈底：不允许进行插入及删除操作的一端
栈顶：允许进行插入及删除操作的一端
空栈：不含数据元素的栈
栈的链表存储
链栈：以栈底作为链尾，栈顶作为链头
队列
定义
所有的插入操作限定在表的一段进行，所有的删除操作限定在表的另一段进行的线性表
特点
先进先出
层次
队头：允许删除的一端
出队：在队头删除元素
队尾：允许插入的一端
入队：在队尾插入元素
队列的顺序存储
顺序队
利用内存中的一组地址连续的存储单元来存储队列中的数据元素
利用一维数组来实现队列的顺序存储
需设头、尾两个“指针”front和rear来分别指示队列的队头、队尾
顺序循环队
目的：避免“假溢出”
方法：形成一个环形的顺序表
链队列
队列的链式存储
是单链表，同时带有头指针和尾指针
栈和队列属于限制存取点的线性结构
字符串
数组
定义
一组相同类型数据元素的有序集合
特点
占有一片连续地址，顺序存储结构
指针
指针变量是存放某个数据对象地址的变量
用户定义类型
用户可以自己定义新的数据类型
广义表
非线性结构
具有两个根节点的数据结构一定是非线性结构
如果有两个节点的同一个指针域相等，则该链表一定是非线性结构
树结构
树
由n(n>＝0)个结点组成的有限集合，若n=0，称为空树
分类
根节点：最上面的结点（无前驱元素）
叶子结点：没有子结点的结点
度：某结点子结点数量(可为0)
树的度：子结点最多的度
结点的深度：结点所在层数
树的深度：总层数
树的总结点数的算法
所有不同度数的结点数之和
二叉树
定义
由1个根节点加上2棵分别称为左子树和右子树的、互不相交的二叉树组成
在具备n个节点二叉查找树上进行查找运算，最坏状况下算法复杂度为O(n)
在一棵二叉树中，最多有1个根节点以及2个后继节点
分类
满二叉树：深度为k的满二叉树，有2的k次方-1个结点
完全二叉树：区别于满二叉树，在最后一层上只缺少右边的若干结点
性质
非空二叉树的第k层上最多有2的(k-1)次方个结点
树的深度为k的二叉树最多有2的k次方-1个结点
具有n个结点的二叉树，树的深度最多为【㏒2底n】+1(【】意为取整)
非空二叉树中，叶子结点数(度为0的结点)等于度为2的结点数＋1，即N0＝N2＋1
遍历
前序遍历(VLR)
方法
访问根节点 (V)
前序遍历左子树(L)
前序遍历右子树(R)
中序遍历(LVR)
方法
中序遍历左子树(L)
访问根节点(V）
中序遍历右子树(R)
特点
得到一种节点元素递增序列
后序遍历(LRV)
方法
后序遍历左子树(L)
后序遍历右子树(R)
访问根节点(V)
层次遍历
方法
自顶向下，自左向右
任何一棵二叉树度为0的节点在前序、中序和后序三种遍历中的相对次序都是不变的
前序遍历和后序遍历可以唯一确定一颗二叉树
森林结构
图结构
例：使用导航软件规划交通线路时，相关地点之间需要用一种数据结构来描述他们之间的关系，这种数据结构是图
分类
有向图
无向图
三要素
数据的逻辑结构
常见的逻辑结构
集合结构
线性表结构
树形结构
网状结构
一个逻辑结构可以有多种存储结构
数据的逻辑结构与数据元素本身的内容和形式无关
数据的存储结构
定义
数据的存储结构是数据的逻辑结构在计算机中的表示
常见的存储结构
顺序
链式
索引
不同的存储结构通常数据处理的效率也不同
数据的运算
计算机基本的数据表示方法
线性表
栈
队列
树
图
软件工程基础
基础概念与生命周期
软件的发展
第一阶段：主要是科学与工程计算，使用机器(或汇编)语言编制程序
第二阶段：第一个高级程序语言FORTRAN及其翻译程序出现，出现“软件危机”，导致软件危机产生的原因有
用户需求不明确
缺乏正确的理论指导
软件文档不完整，不一致
软件生产率偏低
软件开发规模越来越大
软件开发复杂度越来越高
第三阶段：出现了“软件工程”的概念
三要素
方法
完成软件工程项目的技术手段，为软件开发提供“如何做”的技术
工具
支持软件的开发、管理、文档生成，提供自动或半自动的软件工程的支撑环境
过程
这是软件开发的各个环节的控制、管理，获得高质量的软件所需要完成的一系列任务的框架
软件的可靠性
正确性
健壮性
是非常重要的软件外部度量标准，软件设计的健状与否直接反映了分析设计和编码人员的水平
例：当用户使用某软件时，有一些错误输入，此时软件并没有出错，而是给出提示信息并允许重新输入，反应的就是该软件的健壮性
研究的内容
软件开发技术
软件工程管理等
目标
软件开发工程化
软件开发的原则与策略
软件工程技术
软件工程的四个基本活动
P(plan)——软件规格说明
D(do)——软件开发
C(check)——软件确认
A(action)——软件演变
软件工程的七大特性
可靠性
可移植性
可理解性
可维护性
可重用性
可追踪性
可修改性
软件工程的八大原则
抽象
模块化
模块的独立性
耦合度和内聚度是衡量软件模块独立性的主要标准
耦合度：指模块间互相连接的紧密程度的度量
内聚度：指模块内部各个元素之间连接的紧密程度的度量
设计时应最大限度地追求高内聚，低耦合
局部化
确定性
一致性
完备性
可验证性
信息隐蔽
与模块独立性相关
软件生存周期
软件定义期
可行性分析
任务
确定软件开发费用
需求分析
需求分析阶段的工作
需求获取
需求分析
需求评审
编写规格说明书
软件需求规格说明书是需求分析阶段得出的最主要的文档
作用
便于用户、开发人员进行理解和交流
反映出用户问题的结构，可以作为软件开发工作的基础和依据
作为确认测试和验收的依据
软件可靠性
指软件在给定时间间隔内，按规格说明书的规定成功运行的概率
软件的可靠性一般由两次故障平均间隔时间和故障平均恢复时间来度量
任务
确定软件系统功能
结构化需求分析方法
面向数据结构的结构化分析方法 （ISD）
面向数据流的结构化分析方法（SA）
数据字典DD和数据流图DFD共同构成的系统的逻辑模型，是需求规格说明书的主要组成部分
数据字典定义了数据流图中的每个图形元素
面向数据结构的结构化数据系统开发方法（DSSD）
输出
数据流图
数据字典
实体联系图
状态迁移图
常用工具
数据流图DFD常用
数据字典DD
判定表
判定树
伪代码PDL
UML
画用例图属于需求分析阶段的工作
软件开发期
概要设计
任务
确定软件开发方法
属于逻辑结构设计阶段
主要工作就是编写程序
详细设计
任务
确定每个模块的算法和使用的数据结构
属于物理结构设计阶段
编码
测试
软件使用期优先级低
软件运行维护期
运行与维护
分类
预防性维护
是占软件维护阶段整个工作量比例最小的维护
适应性维护
改正性维护
完善性维护
提高软件运行的性能
在软件生命周期中，工作量所占比例最大的阶段是维护阶段
实现阶段的任务是确定软件开发工具
为了提高软件的可维护性，在编码阶段应注意养成良好的程序设计风格
退役
软件工程的目的
提高软件的开发效率
提高软件产品的质量
降低软件产品的开发成本
没有提高软件产品的智能这个目的
软件工程的典型模型 （结构化方法）
瀑布模型
需求比较明确，推迟实现
本质上是一种线性顺序模型
每个阶段都会生成相应的文档
不适应用户需求的变动
原型模型
适用于那些需求不明确的软件系统的开发
增量模型
进行已有产品升级或新版本开发的时候比较合适
喷泉模型
以用户需求为动力，以对象为驱动的模型，适用于面向对象的软件开发过程。
V模型
瀑布模型的变种，一般适用于一些传统信息系统应用的开发
螺旋模型
具有风险分析功能
软件设计
组成
结构设计
定义软件系统各主要部件之间的关系
数据设计
将分析时创建的模型转换为数据结构的定义
接口设计
描述软件内部、软件和操作系统之间及软件与人之间如何通信
过程设计
把系统结构部件转换成软件的过程性描述
分类
概要设计（总体设计）
设计过程
系统设计，确定系统的具体实现方案
概要设计阶段须进行结构设计，确定软件结构
软件功能分解
具体指标
深度
表示模块之间控制的层数
宽度
表示同一层次上模块的总数
扇出
表示模块直接控制其他模块的数量
扇入
表示模块直接受到其他模块控制的数量
不宜片面追求高扇入
工具
结构图（程序结构图）
面向数据流设计
产物
概要设计说明书
详细设计
原则
为后续具体编程实现做准备
处理过程应简明易懂
选择恰当的描述工具描述模块算法
图形结构中的数据元素之间是一种多对多关系
工具
图形工具
N－S图
为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，这种图称为N-S图
PAD图
HIPO图
表格工具
判定表
语言工具
PDL（过程设计语言）
产物
详细设计说明书
结构化设计
结构化方法
定义
属于早期的软件工程方法
分类
结构化设计方法
结构化分析方法
结构化编程方法
结构化程序设计主要强调程序的可读性
结构化分析的常用工具
数据流图（DFD）
DFD要求每个数据处理至少需要一个输入数据流和一个输出流
数据字典（DD）
存储有关数据库的定义信息，如数据类型，模式结构，使用权限的这些数据的集合称为数据字典
判定树（决策树）
判定表
好的软件结构准则
顶部宽度小，中部宽度大，底部宽度居中
面向对象分析与设计 （OOAD）
面向对象分析（OOA）
五个活动
定义对象内部信息
确定对象的操作
描述对象的相互作用
认定对象
组织对象
面向对象设计（OOD）
基本原理
使用现实世界的概念抽象的思考问题从而自然的解决问题，他强调模拟现实世界中的概念而不强调算法，他鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考
在面向对象的程序设计中对象之间的相互作用是通过消息传递来实现
对OOA模型进行调整并补充与实现有关的部分，形成OOD模型
四个部件
人机交互部件
问题域部件
任务管理部件
数据管理部件
面向对象方法
类
对象
封装
继承
多态
消息
工具
UML
定义
用于系统的可视化建模语言，不是一种方法，不包括过程的概念，本身独立于过程
作用
为软件系统建立可视化模型
为软件系统建立构件
为软件系统建立文档
组成
模型元素
类
类与对象的关系是抽象与具体
对象
消息
组成
接收消息的对象名称
消息标识符（也称消息名）
零个或多个参数
图
元素集图形表示
视图
系统的抽象表示
通用机制
注释
模型元素的语义
常见关系
泛化（继承）
实现（接口）
组合（比如公司和部门）
聚合（比如汽车、引擎和轮胎）
关联（比如学生、课程和课程表）
依赖（比如现代人和计算机之间）
主要的模型
对象模型
对象图
类图
功能模型
用例图
动态模型
顺序图
活动图
状态图
软件测试（贯穿于软件开发的整个生命过程）
定义
为了发现错误，成功的测试是发现了至今尚未发现的错误的测试
目的
希望能以最少的人力和时间发现潜在的各种错误
组成
模块测试（单元测试）
是对软件设计的最小单元
集成测试
用于验证概要设计阶段的成果是否具有可行性
为了发现接口错误
系统测试
验收测试
分类
从是否需要执行被测软件的角度分类
静态测试
定义
不实际运行软件，主要通过人工进行
组成
静态结构分析
代码检查
代码质量度量
动态测试
上机调试，通过“分段隔离”、“设置断点”、“跟踪打印”进行程序的调试
黑盒测试和白盒测试均有静态和动态两种
按功能分类
白盒测试（也称为结构测试或逻辑测试）
按照程序内部的结构测试程序来检测产品内部动作是否按照设计规格说明书的规定正常进行，测试者完全了解程序的结构和处理过程，测试者完全了解程序的结构和处理过程
方法
逻辑覆盖
语句覆盖（最弱）
每条语句至少执行一次
判定覆盖
每个判定的每个分支至少执行一次
路径覆盖（又称条件组合覆盖，最强）
每条可能的路径至少执行一次
条件覆盖
设计若干测试用例，执行被测程序以后要使每个判定的每个条件应取到各种可能的值
基本路径测试
例：白盒测试法可用于测试程序的内部结构，此方法将程序看做是路径的集合
白盒法是穷举路径测试
黑盒测试(也称为功能测试或数据驱动测试)
方法
等价划分法
有效等价类
无效等价类
边界值分析法
例如：手机号的位置是11位
因果分析法
错误推测法
极限值设计
特殊值设计
特殊组网考虑
端到端用例考虑
测试者完全不了解程序的结构和处理过程
黑盒测试在设计测试用例时，主要需要研究
需求规格说明
概要设计说明
程序调试（处于开发阶段）
任务
诊断和改正程序中的错误
基本步骤
错误定位
必要步骤
修改设计和代码
排除错误
回归测试
指软件被修改后，为保证其修正的正确性，重新使用原有测试用例执行的测试方法，用来发现在变更时可能引起的其它错误
主要的调试方法
强行排除法
原因排除法
演绎法
归纳法
二分法
回溯法
程序调试通常称为Debug
浮动主题
A计算机软件
计算机软件
软件基本概念
软件定义
以电子格式存储的程序、数据和相关的文档以文件的形式存储在外存中，即软件（软件系统）=程序+数据+相关文档
用户文档内容
安装说明
使用说明
功能说明
在Windows中，对用户新建的文档，系统默认的属性为存档
软件版权
受到知识产权法的保护（不是知识产权），用户仅仅得到了该软件的使用权
软件的特性
不可见性
易复制性
适用性
依附性
复杂性
脆弱性
无磨损性
不断演变性
延长软件的生命周期
有限责任
软件厂商无法给出承诺
若某单位的多台计算机需要安装同一软件，则比较经济的做法是购买该软件的多用户许可证
软件许可证规定的计算机软件使用方式的法律合同
软件产品的设计报告，维护手册和用户使用指南也属于计算机软件
软件虽然不是物理产品而是一种逻辑产品，但通常必须使用物理载体进行存储和分发，通常以电、磁、光等形式存储和传输
软件分类
从软件用途和功能分类
系统软件（与具体应用领域无关）
（核心 ）操作系统(OS)
Windows
Unix
Linux
安卓
iOS
Windows Phone
MAC OS
DOS
数据库管理系统(DBMS)
MySQL
特点
体积小
成本低
速度快
SQL Server
NoSQL
Oracle
Access
Sybase
VFP
POSTGRES
程序设计语言处理系统
语言编译器
实用程序
磁盘清理程序
备份程序
杀毒软件
汇编程序
解释程序
防火墙
无编辑程序
BIOS
应用软件
从应用角度分类
通用应用软件
使用广泛
常见通用应用软件
Powerpoint
不属于网络应用软件
Photoshop
CorelDraw
Word
WPS
Notepad（记事本）
Acrobat Reader
属于文字处理软件
定制应用软件
专门设计开发，成本相对较高
常见的定制应用软件
户籍系统
档案管理系统
银行内部使用的交易系统
为解决各类应用问题而编写的程序称为应用软件
应用软件以系统软件为基础
其它软件
商品软件
需付费才能获得其使用权，这类软件的升级不总是免费的
例如Windows操作系统
共享软件
用于销售，允许拷贝，传播和免费试用
不允许修改
例如微软Visio
自由/开源软件
允许随意拷贝和修改其源代码
允许销售和自由传播
对源代码的修改必须向所有用户公开
倡导“非版权”原则
理查德·斯塔尔曼是自由软件的创始人
GNU——自由软件工程
FSF——自由软件基金会
GPL——自由软件的通用公共许可证
例如
Linux操作系统
TCP/IP协议
MySQL
Apache服务器软件
FireFox浏览器
LibreOffice办公套件
免费软件
自由软件通常都是免费软件，免费软件不一定是自由软件
例如QQ，微信，PDF阅读器
网页制作软件
常见
Front Page 2000
Web Page Maker
ASP Make
Dreamweaver
操作系统(OS)
作用
20世纪50年代后期出现，作为计算机运行配置必不可少的底层系统软件，承担着用户与硬件（计算机）之间接口的任务，也是硬件和其它软件之间的接口
未安装操作系统的计算机称为裸机，是无法使用的
类型
实时操作系统
对计算机完成任务有严格的时间约束，对外部事件能快速作出反应
分时操作系统
采用时间片轮转的方式有效增加资源的使用率
例：一台计算机有30个终端用户同时使用c语言系统。该计算机使用的是分时操作系统
分布式操作系统
批处理操作系统
基本功能
操作系统的启动
BIOS→CPU→硬盘→操作系统
作用
为计算机中运行的程序管理和分配各种软硬件资源
为应用程序的开发和运行提供一个高效的平台
为用户操作使用计算机提供友善的人机界面
如Windows的GUI——图形用户界面
采用图标来形象的表示系统中的文件，程序，设备的对象
辅助用户操作，保护系统安全
任务
定义
已经启动执行的一个应用程序
结束任务：从内部存储设备上结束（非删除）任务所对应的程序
操作系统只把用户输入的信息传送到活动窗口所对应的前台任务中
操作系统对用户屏蔽了实现具体设备I/O操作的细节
操作系统管理用户数据的单位是文件
操作系统必须提供的功能是处理中断
功能
多任务处理和处理器（CPU）管理
提高CPU和其它计算机资源的利用率
任务分类
前台任务（只能有一个）
能接受用户输入的窗口只能有一个，称为活动窗口
并发多任务
任何时刻只有一个任务正在被CPU执行
多任务处理并不一定需要多核CPU的硬件支撑
进程与线程
进程（“爹”）
定义
操作系统对处理器进行管理的最基本单位
指在系统中正在运行的一个应用程序
程序一旦运行就是进程
一个进程只能对应一个应用程序，而一个应用程序可以有多个进程
线程（“儿”）
定义
系统分配处理器时间资源的最小单位
多线程的目的
充分利用CPU的资源，提高程序执行效率
进程与线程的关系
一个线程只能属于一个进程，而一个进程可以有多个线程（至少一个线程）
资源分配给进程，处理器分配给线程
进程与线程的根本区别
进程是操作系统资源分配的基本单位
线程是处理器任务调度和执行的基本单位
文件管理(外存)
功能
实现按文件名存取
文件名的组成
主文件名.扩展名，主文件名不可以省略，扩展名可以省略
文件名的命名原则
不可以使用系统保留的关键字CON、PRN
文件名最多有255个字符（中文或西文字符）
Windows中文件名不区分大小写
文件名中可以使用空格，文件名开头不保留空格
应用程序扩展名
.exe（Windows）
.ipa（iOS）
.apk（安卓）
文件的组成
文件说明信息
存放在文件的目录中
文件内容
存放在磁盘的数据区中
对外存的管理，通常采用文件目录来组织和管理外存中的信息
Windows文件目录采用多层次树状结构
Windows中物理硬盘能建立多个根目录，不同的根目录对应的是不同的逻辑分区，且根目录不可以删除
回收站
回收站的内容占用硬盘空间
软盘和U盘上被删除的文件或文件夹不可以用回收站将其恢复
存储管理(内存)
操作系统中解决存储管理的有效方案是虚拟存储器技术(VM)， 虚拟存储器技术：把内存和外存(硬盘)结合起来管理
虚拟存储器技术是扩充逻辑地址空间技术
虚拟存储器是由物理内存和硬盘上的虚拟内存(一个名为pagefile.sys(隐藏文件)的大文件，称为“页面文件”)联合组成的，用户可以修改其文件名，但因为虚拟内存是系统默认的，所以不可选择不使用
虚拟内存=物理内存+硬盘的虚拟内存
虚拟内存是硬盘上的一块区域，虚拟内存大小可由用户自定义，可以比实际内存小，大或相等
虚拟存储系统容量大小受到硬盘容量和CPU寻址能力的影响
页面调度算法采用"最近最少使用(LRU)"算法，调度的单位：页
内存储器空间组成
系统区
用户区
用来存放正在运行的应用程序
功能
主存空间的分配和回收
主存空间的共享和保护
实现地址转换
设备管理(I/O设备)
设备驱动程序
使用U盘一般不需要专门安装相应的驱动程序
打印机驱动程序一般由操作系统自带，或由打印机厂商提供
驱动程序是操作系统和硬件之间的接口
作业管理
作业的输入和输出
作业的调度和控制
特征
并发性
共享性
虚拟性
异步性
内核
Windows 10操作系统的内核是NT内核
iOS操作系统的内核是Darwin内核
CentOS7的内核是Linux内核
常用操作系统
个人计算机操作系统
单用户多任务
Windows 桌面版
Windows XP
Windows 10
多用户多任务
Windows服务器版
Windows 2003 Server
网络操作系统
多用户多任务
Linux （具有开放性）
原创者是芬兰的青年学者林纳斯·托瓦兹，开源，目前互联网服务器使用的最多的操作系统
linux和Unix也可以用于智能手机和平板电脑
UNIX （以树型目录结构的文件系统为基础）
Linux和Unix均可用于便携机
不开源
Windows Server
Windows NT
NetWare
Windows 7, Windows 10, Windows 11（只是多用户多任务，并不是网络操作系统）
普通操作系统不能作为网络操作系统安装在服务器上使用
网络操作系统都具备网络通信功能，使得计算机能够接入网络并正常工作
服务器操作系统
也可用于PC机
Linux
Unix
OS/2
Mac OS操作系统
由苹果公司自行开发，基于Unix内核，一般情况下，在普通PC机上无法安装
Windows XP（单用户多任务）只能作为网络客户机的操作系统（非网络操作系统），而不能作为服务器的操作系统
在使用Windows 98操作系统的PC机上第一次使用U盘时必须安装驱动程序
Windows Vista一般用于家庭娱乐，不属于网络操作系统
程序设计语言
分类
机器语言（现在已经不直接用机器语言编写程序）
用二进制表示，计算机可以直接识别执行
特点
不易记忆和理解
难于修改和维护
可移植性差
依赖于硬件
执行速度最快
汇编语言
用助记符来代替机器指令的操作码和操作数，可移植性差
汇编程序：从汇编语言到机器语言的翻译程序
机器语言和汇编语言都是面向机器的语言
高级语言
接近人们的自然语言，具有通用性，可移植性最强
为了提高软件开发效率，开发软件时应尽量采用高级语言
高级语言的翻译程序
解释程序（相当于口译）
特点
适用于程序调试，程序交互等
算法简单，灵活
便于查错
占用内存少
运行效率低
逐条解释，运行效率低
不产生目标程序
解释型语言
BASIC
Java
Python
PHP
VBS
编译程序（相当于笔译）
特点
适用于翻译规模大，结构复杂，运行时间长的大型应用程序
将高级语言源程序转换为目标程序的是编译程序
产生目标程序
编译型语言
C语言
C++
C＃
高级程序设计语言的编译程序和解释程序属于语言处理程序
运行效率：机器语言>汇编程序>高级语言
高级语言的解释程序，翻译程序，编译程序也属于系统软件
机器语言程序与高级语言程序的比较
机器语言程序比高级语言程序占用的存储空间小
机器语言程序比高级语言程序难于编写和调试
机器语言程序比高级语言程序可移植性差
机器语言程序比高级语言程序可读性差
机器语言程序比高级语言程序执行速度快
组成
运算成分
运算
算术表达式
逻辑表达式
传输成分
数据传输
赋值语句
输入/输出语句
例如scanf和printf
控制成分
控制构造
条件语句if
循环语句for和while
数据成分
数据对象
数据类型
以C语言为例
基本数据类型
整型（int）
字符型（char）
实型（float，double）
特殊类型
空类型（void）
用户定义类型
枚举类型（enum）
数据结构
程序的控制结构(易读性)
基本结构
顺序结构
选择结构(判断结构)
条件选择结构由条件和选择组成
循环结构
三种基本控制结构的共同特点是单入口和单出口
仅由顺序、选择和循环结构构成的程序是结构化程序
具体方法
自顶向下
规划与设计
逐步求精
模块化
限制使用goto语句
源程序执行方式
源程序
通过编译程序的处理，可以一次性的产生高效运行的目标程序，并把它保存在磁盘上，已备多次执行
高级语言编写的源程序被保存为文本文件
负责完成这些功能的软件(统称：程序设计语言处理系统，即翻译程序)
汇编程序
编译程序
不参与用户程序的运行控制
解释程序
参与用户程序的运行控制
执行过程
编辑源程序
编译源程序
进行连接处理
运行可执行程序并获得运行结果
编辑→编译→连接→运行
常用程序设计语言
FORTRAN语言
面向过程
用于科学与数值计算
BASIC语言
面向过程
C语言
C语言
面向过程
适合于开发系统软件，效率高
C＋＋
面向对象
面向对象程序方法的三个重要特征
封装性
继承性
多态性
对象的三要素
属性
方法
事件
C＃语言
面向对象
面向对象方法是20世纪90年代以来发展最快，使用最普遍的软件开发方法
运行于.NET平台，可跨平台运行
Java语言
面向对象
适用于网络环境编程，可跨平台运行，与使用任何操作系统无关
Python语言
面向对象
特点
用于web编程
可用于科学计算
属于自由软件（开源）
VB语言
定义
基于BASIC语言开发的一种程序设计语言
面向对象
可视化，事件处理
算法和数据结构
算法
概念
尼·沃思提出“数据结构＋算法＝程序” “计算机科学就是研究算法的学问”
软件的主体是程序，程序的核心是算法，数据结构能使算法有效的实现
不同的算法来求解同一问题，结果相同
不一定要用高级语言描述，算法的表示不一定能让计算机理解
数据的存储结构也会影响算法的效率
同一个算法，语言级别越低，执行效率就越高
相关问题
如何确定算法(算法设计)
由粗到细，由抽象到具体
如何表示算法(算法表示)
自然语言文字说明
流程图
伪代码（PDL）
程序设计语言
如何使算法更有效(算法的复杂性分析)
计算机资源
时间资源
空间资源
复杂度
时间复杂度：指执行这个算法所需要的计算工作量
空间复杂度：指执行这个算法所需要的内存空间，和求解问题的规模关系密切
时间复杂度和空间复杂度并不相关
算法分析的目的是分析算法的效率以求改进
组成
数据对象的运算与操作
控制结构
基本运算和操作
算术运算
逻辑运算
关系运算
数据传输
基本设计方法
列举法
归纳法
递归法
评价算法优劣的主要因素
算法复杂度
执行算法所占用的时间资源
执行算法所占用的空间资源
正确性
可读性
健壮性
指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性
基本要求
输入
一个算法中有0个或多个输入
输出
一个算法中有1个或多个输出
确定性
无二义性
有穷性
指算法必须在有限时间内完成，必须在有限步后终止
能行性
可执行
查找分类
顺序查找
效率最低
长度为n的线性表最坏查找次数为：n次
最大值或最小值的比较次数为n-1次
折半查找（二分查找）
效率最高
只适用于顺序存储的有序表
最坏比较次数：㏒2底n次
分块查找
效率居中，需要有序且最好为动态
补充
程序可以是死循环的（无限循环）
程序定义
错误分类
语法错误
例如
表达式缺少操作数
括号不匹配
关键词拼写错误
标点符号错误
语义错误
静态语意错误
定义
刚开始编译时就会报错
例如
10/0
b+a（a为数组名）
％运算对象类型不符
动态语义错误
定义
运行时报错
例如
a/0
a/b（b运算过程中被赋值为0）
死循环
数组下标越界
指针异常
实参传递问题
算法和程序是相应的，但不一一对应
程序是算法的具体代码实现
算法是程序设计的核心，算法的好坏直接决定了程序的效率
程序中的语句必须是机器可执行的，算法中的操作无此限制
数据结构
定义
指相互有关联的数据元素的集合
数据结构在计算机内存中的表示是指数据的存储结构
分类
线性结构(与数据的存储无关，独立于计算机)
特点
有且只有一个根节点
除了最后一个结点外，每个节点最多有一个前件，也最多有一个后件
所有的线性结构都可以采用顺序存储结构
研究数据元素之间的一对一关系
分类
线性表
基本概念：由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的
位序：数据元素在线性表中的位置
表项：表中的元素
空表：长度为0的表
基本运算
在线性表中查找某个特定元素
在线性表中查找某个元素的前驱元素
在线性表中查找某个元素的后继元素
判别一个线性表是否为空表
创建空线性表
在线性表中插入一个元素
插在第i个节点之前，移动（n-i+1）次（n为结点数，i为第i个结点）
在线性表中删除某个元素
删除第i个节点，移动（n-i）次
特点
数据元素都是整数
存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
复杂线性表中
由若干数据项组成的数据元素称为记录
由多个记录构成的线性表称为文件
存储结构
顺序存储结构
定义
用一组地址连续的存储单元及一维数组来存储
线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置上也相邻
优点
静态操作容易实现
可顺序/随机存取
缺点
动态操作实现效率较低
扩展不灵活，容易造成空间浪费
插入/删除不方便
链式存储结构
特点
插入删除不需要移动元素
不必事先估计存储空间
所需空间与线性长度成正比
缺点
不能随机访问任意元素
因为链式存储结构由指针域和数据域组成，还需要存储指针域，因此链式存储结构需要的存储空间比顺序存储大
链式存储可连续可不连续
线性表的链式表示和实现
顺序表
缺陷：插入/删除耗费大量时间
例：设顺序表的表长为n，则删除一个元素在最坏情况下元素移动次数为n+1
线性链表
节点
最后一个节点没有直接后继，其指针域为“空”(NULL)
指针域 ：存储直接后继的存储位置（地址）
数据域：存储数据元素信息
基本运算
查找
插入
删除
单链表
每个结点只包含一个指针域，若L==NULL,则表示单链表为空表，长度为0
带头结点的单链表
若头结点的指针域为“空”，即L→next==NULL，表示该链表为空表
头结点：位于首元节点的前面，是一个辅助结点
结构
data：数据域
next：指针域
动态建立单链表的常用方法
采用头插法
尾插法
循环链表(首尾相连)
优点
从表中任何一个节点位置出发，就可以不重复的访问到表中其他所有节点
基本运算
判断是否是空链表
head→next == head
判断是否是表尾结点
p→next == head
循环链表与单链表的区别
单链表存放的是空指针
循环链表最后一个结点的指针域存放的是指向第一个节点的指针
双向链表
优点
既可以找前驱，也可以找后继
方便数据插入和删除
两个指针
左指针（Llink）指向前件结点
右指针（Rlink）指向后件结点
采用链式存储，因为双向链表中有两个指针域，所以不能节约存储空间
栈
概念
仅能在表的一端进行插入和删除操作的线性表，具有记忆功能
特点
先进后出，后进先出
支持子程序调用
基本运算
入栈运算
退栈运算
读栈顶元素
操作
压入（PUSH）：S【top++】
s→top==0，栈空，此时出栈则下溢
s→top==MAXSIZE，栈满，此时入栈则上溢
弹出（POP）：e=S【--top】
层次
栈底：不允许进行插入及删除操作的一端
栈顶：允许进行插入及删除操作的一端
空栈：不含数据元素的栈
栈的链表存储
链栈：以栈底作为链尾，栈顶作为链头
队列
定义
所有的插入操作限定在表的一段进行，所有的删除操作限定在表的另一段进行的线性表
特点
先进先出
层次
队头：允许删除的一端
出队：在队头删除元素
队尾：允许插入的一端
入队：在队尾插入元素
队列的顺序存储
顺序队
利用内存中的一组地址连续的存储单元来存储队列中的数据元素
利用一维数组来实现队列的顺序存储
需设头、尾两个“指针”front和rear来分别指示队列的队头、队尾
顺序循环队
目的：避免“假溢出”
方法：形成一个环形的顺序表
链队列
队列的链式存储
是单链表，同时带有头指针和尾指针
栈和队列属于限制存取点的线性结构
字符串
数组
定义
一组相同类型数据元素的有序集合
特点
占有一片连续地址，顺序存储结构
指针
指针变量是存放某个数据对象地址的变量
用户定义类型
用户可以自己定义新的数据类型
广义表
非线性结构
具有两个根节点的数据结构一定是非线性结构
如果有两个节点的同一个指针域相等，则该链表一定是非线性结构
树结构
树
由n(n>＝0)个结点组成的有限集合，若n=0，称为空树
分类
根节点：最上面的结点（无前驱元素）
叶子结点：没有子结点的结点
度：某结点子结点数量(可为0)
树的度：子结点最多的度
结点的深度：结点所在层数
树的深度：总层数
树的总结点数的算法
所有不同度数的结点数之和
二叉树
定义
由1个根节点加上2棵分别称为左子树和右子树的、互不相交的二叉树组成
在具备n个节点二叉查找树上进行查找运算，最坏状况下算法复杂度为O(n)
在一棵二叉树中，最多有1个根节点以及2个后继节点
分类
满二叉树：深度为k的满二叉树，有2的k次方-1个结点
完全二叉树：区别于满二叉树，在最后一层上只缺少右边的若干结点
性质
非空二叉树的第k层上最多有2的(k-1)次方个结点
树的深度为k的二叉树最多有2的k次方-1个结点
具有n个结点的二叉树，树的深度最多为【㏒2底n】+1(【】意为取整)
非空二叉树中，叶子结点数(度为0的结点)等于度为2的结点数＋1，即N0＝N2＋1
遍历
前序遍历(VLR)
方法
访问根节点 (V)
前序遍历左子树(L)
前序遍历右子树(R)
中序遍历(LVR)
方法
中序遍历左子树(L)
访问根节点(V）
中序遍历右子树(R)
特点
得到一种节点元素递增序列
后序遍历(LRV)
方法
后序遍历左子树(L)
后序遍历右子树(R)
访问根节点(V)
层次遍历
方法
自顶向下，自左向右
任何一棵二叉树度为0的节点在前序、中序和后序三种遍历中的相对次序都是不变的
前序遍历和后序遍历可以唯一确定一颗二叉树
森林结构
图结构
例：使用导航软件规划交通线路时，相关地点之间需要用一种数据结构来描述他们之间的关系，这种数据结构是图
分类
有向图
无向图
三要素
数据的逻辑结构
常见的逻辑结构
集合结构
线性表结构
树形结构
网状结构
一个逻辑结构可以有多种存储结构
数据的逻辑结构与数据元素本身的内容和形式无关
数据的存储结构
定义
数据的存储结构是数据的逻辑结构在计算机中的表示
常见的存储结构
顺序
链式
索引
不同的存储结构通常数据处理的效率也不同
数据的运算
计算机基本的数据表示方法
线性表
栈
队列
树
图
软件工程基础
基础概念与生命周期
软件的发展
第一阶段：主要是科学与工程计算，使用机器(或汇编)语言编制程序
第二阶段：第一个高级程序语言FORTRAN及其翻译程序出现，出现“软件危机”，导致软件危机产生的原因有
用户需求不明确
缺乏正确的理论指导
软件文档不完整，不一致
软件生产率偏低
软件开发规模越来越大
软件开发复杂度越来越高
第三阶段：出现了“软件工程”的概念
三要素
方法
完成软件工程项目的技术手段，为软件开发提供“如何做”的技术
工具
支持软件的开发、管理、文档生成，提供自动或半自动的软件工程的支撑环境
过程
这是软件开发的各个环节的控制、管理，获得高质量的软件所需要完成的一系列任务的框架
软件的可靠性
正确性
健壮性
是非常重要的软件外部度量标准，软件设计的健状与否直接反映了分析设计和编码人员的水平
例：当用户使用某软件时，有一些错误输入，此时软件并没有出错，而是给出提示信息并允许重新输入，反应的就是该软件的健壮性
研究的内容
软件开发技术
软件工程管理等
目标
软件开发工程化
软件开发的原则与策略
软件工程技术
软件工程的四个基本活动
P(plan)——软件规格说明
D(do)——软件开发
C(check)——软件确认
A(action)——软件演变
软件工程的七大特性
可靠性
可移植性
可理解性
可维护性
可重用性
可追踪性
可修改性
软件工程的八大原则
抽象
模块化
模块的独立性
耦合度和内聚度是衡量软件模块独立性的主要标准
耦合度：指模块间互相连接的紧密程度的度量
内聚度：指模块内部各个元素之间连接的紧密程度的度量
设计时应最大限度地追求高内聚，低耦合
局部化
确定性
一致性
完备性
可验证性
信息隐蔽
与模块独立性相关
软件生存周期
软件定义期
可行性分析
任务
确定软件开发费用
需求分析
需求分析阶段的工作
需求获取
需求分析
需求评审
编写规格说明书
软件需求规格说明书是需求分析阶段得出的最主要的文档
作用
便于用户、开发人员进行理解和交流
反映出用户问题的结构，可以作为软件开发工作的基础和依据
作为确认测试和验收的依据
软件可靠性
指软件在给定时间间隔内，按规格说明书的规定成功运行的概率
软件的可靠性一般由两次故障平均间隔时间和故障平均恢复时间来度量
任务
确定软件系统功能
结构化需求分析方法
面向数据结构的结构化分析方法 （ISD）
面向数据流的结构化分析方法（SA）
数据字典DD和数据流图DFD共同构成的系统的逻辑模型，是需求规格说明书的主要组成部分
数据字典定义了数据流图中的每个图形元素
面向数据结构的结构化数据系统开发方法（DSSD）
输出
数据流图
数据字典
实体联系图
状态迁移图
常用工具
数据流图DFD常用
数据字典DD
判定表
判定树
伪代码PDL
UML
画用例图属于需求分析阶段的工作
软件开发期
概要设计
任务
确定软件开发方法
属于逻辑结构设计阶段
主要工作就是编写程序
详细设计
任务
确定每个模块的算法和使用的数据结构
属于物理结构设计阶段
编码
测试
软件使用期优先级低
软件运行维护期
运行与维护
分类
预防性维护
是占软件维护阶段整个工作量比例最小的维护
适应性维护
改正性维护
完善性维护
提高软件运行的性能
在软件生命周期中，工作量所占比例最大的阶段是维护阶段
实现阶段的任务是确定软件开发工具
为了提高软件的可维护性，在编码阶段应注意养成良好的程序设计风格
退役
软件工程的目的
提高软件的开发效率
提高软件产品的质量
降低软件产品的开发成本
没有提高软件产品的智能这个目的
软件工程的典型模型 （结构化方法）
瀑布模型
需求比较明确，推迟实现
本质上是一种线性顺序模型
每个阶段都会生成相应的文档
不适应用户需求的变动
原型模型
适用于那些需求不明确的软件系统的开发
增量模型
进行已有产品升级或新版本开发的时候比较合适
喷泉模型
以用户需求为动力，以对象为驱动的模型，适用于面向对象的软件开发过程。
V模型
瀑布模型的变种，一般适用于一些传统信息系统应用的开发
螺旋模型
具有风险分析功能
软件设计
组成
结构设计
定义软件系统各主要部件之间的关系
数据设计
将分析时创建的模型转换为数据结构的定义
接口设计
描述软件内部、软件和操作系统之间及软件与人之间如何通信
过程设计
把系统结构部件转换成软件的过程性描述
分类
概要设计（总体设计）
设计过程
系统设计，确定系统的具体实现方案
概要设计阶段须进行结构设计，确定软件结构
软件功能分解
具体指标
深度
表示模块之间控制的层数
宽度
表示同一层次上模块的总数
扇出
表示模块直接控制其他模块的数量
扇入
表示模块直接受到其他模块控制的数量
不宜片面追求高扇入
工具
结构图（程序结构图）
面向数据流设计
产物
概要设计说明书
详细设计
原则
为后续具体编程实现做准备
处理过程应简明易懂
选择恰当的描述工具描述模块算法
图形结构中的数据元素之间是一种多对多关系
工具
图形工具
N－S图
为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，这种图称为N-S图
PAD图
HIPO图
表格工具
判定表
语言工具
PDL（过程设计语言）
产物
详细设计说明书
结构化设计
结构化方法
定义
属于早期的软件工程方法
分类
结构化设计方法
结构化分析方法
结构化编程方法
结构化程序设计主要强调程序的可读性
结构化分析的常用工具
数据流图（DFD）
DFD要求每个数据处理至少需要一个输入数据流和一个输出流
数据字典（DD）
存储有关数据库的定义信息，如数据类型，模式结构，使用权限的这些数据的集合称为数据字典
判定树（决策树）
判定表
好的软件结构准则
顶部宽度小，中部宽度大，底部宽度居中
面向对象分析与设计 （OOAD）
面向对象分析（OOA）
五个活动
定义对象内部信息
确定对象的操作
描述对象的相互作用
认定对象
组织对象
面向对象设计（OOD）
基本原理
使用现实世界的概念抽象的思考问题从而自然的解决问题，他强调模拟现实世界中的概念而不强调算法，他鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考
在面向对象的程序设计中对象之间的相互作用是通过消息传递来实现
对OOA模型进行调整并补充与实现有关的部分，形成OOD模型
四个部件
人机交互部件
问题域部件
任务管理部件
数据管理部件
面向对象方法
类
对象
封装
继承
多态
消息
工具
UML
定义
用于系统的可视化建模语言，不是一种方法，不包括过程的概念，本身独立于过程
作用
为软件系统建立可视化模型
为软件系统建立构件
为软件系统建立文档
组成
模型元素
类
类与对象的关系是抽象与具体
对象
消息
组成
接收消息的对象名称
消息标识符（也称消息名）
零个或多个参数
图
元素集图形表示
视图
系统的抽象表示
通用机制
注释
模型元素的语义
常见关系
泛化（继承）
实现（接口）
组合（比如公司和部门）
聚合（比如汽车、引擎和轮胎）
关联（比如学生、课程和课程表）
依赖（比如现代人和计算机之间）
主要的模型
对象模型
对象图
类图
功能模型
用例图
动态模型
顺序图
活动图
状态图
软件测试（贯穿于软件开发的整个生命过程）
定义
为了发现错误，成功的测试是发现了至今尚未发现的错误的测试
目的
希望能以最少的人力和时间发现潜在的各种错误
组成
模块测试（单元测试）
是对软件设计的最小单元
集成测试
用于验证概要设计阶段的成果是否具有可行性
为了发现接口错误
系统测试
验收测试
分类
从是否需要执行被测软件的角度分类
静态测试
定义
不实际运行软件，主要通过人工进行
组成
静态结构分析
代码检查
代码质量度量
动态测试
上机调试，通过“分段隔离”、“设置断点”、“跟踪打印”进行程序的调试
黑盒测试和白盒测试均有静态和动态两种
按功能分类
白盒测试（也称为结构测试或逻辑测试）
按照程序内部的结构测试程序来检测产品内部动作是否按照设计规格说明书的规定正常进行，测试者完全了解程序的结构和处理过程，测试者完全了解程序的结构和处理过程
方法
逻辑覆盖
语句覆盖（最弱）
每条语句至少执行一次
判定覆盖
每个判定的每个分支至少执行一次
路径覆盖（又称条件组合覆盖，最强）
每条可能的路径至少执行一次
条件覆盖
设计若干测试用例，执行被测程序以后要使每个判定的每个条件应取到各种可能的值
基本路径测试
例：白盒测试法可用于测试程序的内部结构，此方法将程序看做是路径的集合
白盒法是穷举路径测试
黑盒测试(也称为功能测试或数据驱动测试)
方法
等价划分法
有效等价类
无效等价类
边界值分析法
例如：手机号的位置是11位
因果分析法
错误推测法
极限值设计
特殊值设计
特殊组网考虑
端到端用例考虑
测试者完全不了解程序的结构和处理过程
黑盒测试在设计测试用例时，主要需要研究
需求规格说明
概要设计说明
程序调试（处于开发阶段）
任务
诊断和改正程序中的错误
基本步骤
错误定位
必要步骤
修改设计和代码
排除错误
回归测试
指软件被修改后，为保证其修正的正确性，重新使用原有测试用例执行的测试方法，用来发现在变更时可能引起的其它错误
主要的调试方法
强行排除法
原因排除法
演绎法
归纳法
二分法
回溯法
程序调试通常称为Debug
浮动主题