软件工程 学习笔记 知识梳理

Chapter 1 绪论

软件开发知识体系

• 项目管理开发: 软件工程
• 软件逻辑设计: 数据结构与算法
• 程序编程编译: 编译原理
• 软件运行环境: 操作系统/数据库

软件开发过程

1. 问题理解
2. 算法设计
3. 数据结构设计
4. 算法分析
5. 程序设计
6. 程序实现

操作系统

操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

主要功能

• 处理机管理: 进程管理
  • 控制: 程序的创建, 撤销, 状态转换
  • 调度: CPU分配
  • 同步: 多个进程协调
  • 通信: 进程信息交换
• 储存器管理: 内存管理
  • 分配: 为每个作业分配内存 静态分配 动态分配
  • 保护: 确保用户程序只在自己内存内运行 互不干扰
  • 映射: 地址空间 内存空间 地址映射
  • 扩展: 虚拟储存技术扩充内存容量 请求调入, 置换
• 设备管理: I/O管理
  • 缓冲: 缓和CPU和I/O速度不匹配矛盾
  • 分配: 根据进程I/O请求, 为之分配所需设备
  • 驱动: 设备处理, 实现CPU与设备控制器之间的通信
• 文件管理: 用户文件, 系统文件管理
  • 储存: 储存空间分配 回收
  • 组织: 建立目录项, 按名存取
  • 读写: 外村读写数据
  • 安全: 放置未核准用户存取, 防止不正确使用文件
• 用户接口: 提供有好的接口, 方便用户使用
  • 图形用户接口
  • 命令接口
  • 程序接口

软件程序编译

1. 操作系统依赖: 高级语言 –> 翻译程序 –> 机器码
2. 不依赖操作系统: 高级语言 –> 翻译程序 –> 中间语言 –> 执行虚拟机

编译步骤

源程序字符串 –> 词法分析器 –> 单词流 –> 词法分析器 –> 语法树 –> 语义分析器 –> 中间代码序列 –> 代码优化器 –> 目标代码生成器 –> 目标程序

计算机软件数据管理

位于用户与操作系统之间的数据管理软件

功能

• 数据定义
• 数据操作
• 数据库运行管理
• 数据组织, 储存, 管理
• 数据库建立维护
• 数据通信接口

SQL

1. DDL definition
2. DML manipulation

Chapter 2 数据结构

线性表

1. 数据元素一一对应, 顺序关系
2. 位序, 表长, 前驱, 后继, 除第一个和最后一个, 唯一前驱和后继

顺序储存结构

1. 地址连续 依次存放 起始地址
2. 随机存取
3. 定义{基址, 长度length, 容量size}
4. 插入操作: $E=n/2$ $O(n)$

5. 删除操作: $E=\frac{n?1}{2}$ $O(n)$

链式储存结构

1. 数据域+指针=节点
2. 头指针 带不带头结点皆可
3. 查找

4. 插入

5. 删除

6. 创建

• 建立一个“空表”
• 输入数据元素an，建立结点并插入到单链表；
• 输入数据元素an-1，建立结点并插入到单链表；
• 依次类推，直至输入a1为止
  p->next=L->next;
  L->next=p;

顺序储存链式储存对比

顺序插入删除不方便 适宜查找静态操作 容量固定 额外内存申请开销
长度变化大 链表

渐进复杂度

$O(g(n))\to 0\le f(n)\le cg(n)$
$$a_0+a_{1}n+...+a_d{n}^d=\Theta (n^d)$$

分治

1. 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
2. 问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

归并排序

树

1. 一对多 根节点没有前驱 其他只有一个前驱 叶子没有后继
2. 深度

二叉树

1. 左右子树不能颠倒
2. 满二叉树: 深度为k 有2^k-1个节点
3. 完全二叉树: 每个节点都与深度相同的满二叉树一一对应
4. 顺序储存: 必须为完全二叉树 i左孩子下标为2i 添加虚节点转为完全二叉树
5. 链式储存: {data, *lc, *rc} 三叉{data , lc,rc,parent}
6. 遍历
   • 先序, 中序, 后序

• 层次
  • 初始化队列，根节点入队列
  • 如果队列不空，则出队列并访问该节点；该节点左孩子入队列，右孩子入队列；如果队列为空，则层次遍历结束

7. 树的存储结构
   • 双亲表示法
   • 孩子表示法
   • 孩子兄弟表示法
8. 二叉树与树互换

图

1. 树的存储

   • 邻接矩阵
   • 邻接表
     • 无向图: n顶点 e条边 需要n个头结点和2e个链表节点 顶点Vi的度=链表中链表节点数
     • 有向图: 逆邻接表 邻接表

2. 一个图的邻接矩阵表示是唯一的；邻接表表示不唯一。邻接表中各边表结点的次序取决于建立算法和及输入边的次序.

3. 邻接表（逆邻接表）中，每个边表对应邻接矩阵中的一行(或一列）；边表中结点的个数等于邻接矩阵中的一行(或一列)非0元素的个数。

4. 邻接表或逆邻接表的空间复杂度为S(n,e)=O(n+e)。若图中的边数e远远小于n2,称为稀疏图，其邻接表比邻接矩阵要节省存储空间。当边数e接近n2 （无向图:e接近n(n-1)/2;有向图:e接近n(n-1)）时，称为稠密图,考虑链域占空间，应选择邻接矩阵存储为宜。

5. 求有向图顶点的度，采用邻接矩阵比邻接表结构方便。在邻接表结构中，求顶点的出度容易，入度困难。逆邻接表中，求顶点的入度容易，出度困难。

6. 判断边，邻接矩阵比邻接表容易；求边数：邻接矩阵中花费的时间复杂度为O(n2),邻接表中花费的时间复杂度为O(n+e)

7. 图的遍历

   • 深度优先遍历
   • 广度优先遍历: 栈

贪心算法

1. 简单, 高校, 可能不是最优解
2. 活动安排