十二、软件系统分析与设计

发表于 分类于

1 结构化分析与设计

结构化分析关注数据和处理过程，DFD 是建模工具，通过分层展示系统输入输出及处理过程。还需结合数据字典和加工说明。

结构化分析步骤：

  1. 确定系统边界，画出系统环境图 ：明确系统范围和交互。
  2. 自顶向下画出各层数据流图 ：分解系统功能。
  3. 定义数据字典 ：定义数据流、存储和项。
  4. 定义加工说明 ：描述加工操作。
  5. 将图、字典以及加工组成分析模型 ：形成完整模型。

使用 DFD 进行数据流建模原则：

  1. 加工和数据流正确使用 ：加工需有输入输出，数据流与加工相关。
  2. 数据流和存储定义清晰 ：所有元素在数据字典中定义。
  3. 最低层加工有说明 ：用结构化语言等描述。
  4. 父图子图平衡 ：输入输出一致。
  5. 元素保持一致 ：加工说明与数据流图元素对应。
  6. 控制图元数量 ：每幅图 7±2 个图元。

1.1 需求说明

以图书管理系统为例。

  1. 管理功能
  • 图书购入 ：为新书编制卡片，信息写入图书目录文件。
  • 读者借书 ：检查读者号和借书限制，登记借书信息。
  • 读者还书 ：更新借阅记录，逾期则罚款。
  • 图书注销 ：清理无价值图书，删除记录。
  1. 查询功能
    • 查询读者、图书和借阅统计信息。

1.2 结构化分析

结构化分析旨在得到系统的数据流图、数据字典和加工说明。通过分析需求确定系统边界，绘制不完整的第 0 层 DFD 数据流图，补充数据流后得到完整的 0 层 DFD 图。

对系统进一步细化，将主要任务分为管理任务和查询任务，细化为多个处理流程，分解管理处理和查询处理，形成多层 DFD 图。

对底层处理进行加工说明，定义输入输出和处理逻辑。

1.3 总体设计

由于数据流呈现事务型特性，采用事务型变换方式将数据流转换为模块调用关系，形成系统总体结构。总体设计展示了模块间的调用关系，为后续详细设计提供基础。

1.4 详细设计

以借书为例，采用程序流程图描述借书模块的详细设计。分析借书的输入是读者信息和借书信息，处理逻辑包括判断读者是否合法、是否超出借阅限制，若合法则更新借书文件。完成各模块的详细设计后，可将详细设计转换为程序代码，实现管理系统。

2 数据库分析与设计

2.1 数据库设计的策略与步骤

数据库设计策略包括自顶向下（Top Down）和自底向上（Bottom Up）。自顶向下从企业高层管理层入手，逐步细化；自底向上从各种基本业务赫尔数据处理入手，综合集成。实际常综合使用。

数据库设计分为四个阶段：

  1. 用户需求分析 ：科学分析应用对象的功能、性能和限制等要求。
  2. 概念设计 ：采用 E-R 方法对信息进行分析和定义，形成独立于计算机系统的企业信息模型。
  3. 逻辑设计 ：转化为逻辑模型，是物理设计基础，包括模式初始设计、子模式设计、应用程序设计、模式评价及模式求精。
  4. 物理设计 ：确定逻辑模型在计算机中的具体实现方案。

不满足需求时，需返回修正，直至达标。

2.2 需求分析

需求分析任务是综合用户需求，了解现行系统，确定新系统功能。方法有自顶向下和自底向上。

需求分析内容包括：

  • 信息要求 ：用户要保存和期望得到的信息及完整性要求。
  • 处理要求 ：用户期望的处理功能、过程方式及其它要求。
  • 系统要求 ：安全性、使用方式和可扩充性要求。

成果是系统需求说明书，是后续过程的重要依据。

2.3 概念结构设计

概念结构设计是在需求分析基础上，对用户信息分类、聚集和概括，建立信息模型，转换为数据逻辑结构，最终实现数据合理存储。其目标是产生反映系统信息需求的概念模式，独立于 DBMS 和硬件环境。

2.3.1 概念结构设计策略与方法

概念结构设计策略包括自顶向下、自底向上、逐步扩张和混合策略。实际应用中可依业务特点选择。常用方法是 E-R 方法，用 E-R 模型描述现实世界信息结构。

2.3.2 用 E-R 方法建立概念模型

工作步骤

  1. 选择局部应用 ：依据数据流程图选择局部应用。
  2. 逐一设计分 E-R 图 ：依数据字典和数据流程图，确定局部应用的实体、属性和联系。
    • 属性不可再分。
    • 属性不能与其他实体发生联系。
  3. E-R 图合并 ：合并各分 E-R 图，解决冲突和信息冗余。
    • 合并方法：将相同实体的分 E-R 图合并，合成后实体属性为各分图属性并集。
    • 冲突类型：
      • 属性冲突：同一属性在不同分图中类型、取值范围等不一致。
      • 命名冲突：相同意义属性命名不同或同名属性意义不同。
      • 结构冲突：同一实体在不同分图中属性不同或对象抽象为实体与属性不一致。
    • 优化方面：
      • 实体型合并：合并具有 1:1 或 1:n 联系的实体。
      • 冗余属性消除：去除合并后可能出现的冗余属性。
      • 冗余联系消除：消除实体间环状结构中的直接联系。

2.4 逻辑结构设计

  1. 确定数据模型：基于全局 E - R 图进行关系模型设计。
  2. 转换 E - R 图：将 E-R 图转换为关系模型。每个实体转为一个关系模式和根据联系类型进行转换。
  3. 规范化关系模式：消除数据冗余和更新异常。
  4. 确定完整性约束：参照 SQL 标准，确保数据正确性。
  5. 确定用户视图：基于数据流图和用户信息，提高数据安全性和独立性。

2.5 数据库的物理设计

2.5.1 工作过程

  1. 确定数据库的物理模式 ：依据逻辑设计阶段的模型和 DBMS 特征，确定物理结构。
  2. 评价物理模式 ：对存储结构、存取路径等进行评价和优化。

2.5.2 主要工作内容

  1. 确定数据分布 ：根据企业应用环境和处理要求，确定数据集中或分布管理。考虑部门数据关联、处理要求和数据分布对逻辑结构的影响。
  2. 确定数据的存储结构 ：依据数据处理要求和变更特点，选择顺序存储、哈希存储、堆存储或 B+ 树存储等结构。常用数据可水平分割、分布存储以提高性能。使用索引技术提高访问速度。
  3. 确定数据的访问方式 ：根据存储结构选择访问方式，包括存储记录结构设计、存储记录布局和存取方法设计。
    • 存储记录结构设计 ：设计记录组成和数据项特性，考虑数据分布和存储介质。
    • 存储记录布局 ：确定数据存放位置，利用聚簇功能提高查询效率。
    • 存取方法设计 ：建立索引作为主要手段，确定索引属性和类型，平衡查询和存储性能。

2.6 数据库的实施与维护

2.6.1 数据库的实施

  1. 建立数据库结构 ：用 DBMS 的 DDL 编写程序，生成实际数据库结构，涵盖模式、子模式、完整性、安全性及物理存储参数。
  2. 数据加载 ：设计加载程序，整理数据，排除不合格数据，可手工输入或用数据转换工具。
  3. 试运行和评价 ：加载部分数据后联合调试，测试功能和效率，发现问题以改进设计。

2.6.2 数据库的维护

  1. 性能监测与改善 ：DBA 利用工具分析运行情况，依用户反馈改进。
  2. 备份与故障恢复 ：制定备份方案，快速恢复数据。
  3. 重组与重构 ：去除数据库碎片，必要时修改数据库结构。

3面向对象分析与设计

3.1 设计步骤

面向对象分析

  1. 建模系统功能 ：通过需求分析产生用例图，确定参与者、用例，构造用例模型，记录需求。
  2. 定义领域模型 ：确定业务对象及其关系，形成领域模型。
  3. 定义交互、行为和状态 ：确定设计类及其属性、行为，用交互图描述对象协作。

面向对象设计

面向对象设计定义软件对象及其协作，强调软件对象的属性、行为和责任。设计类图展示类的属性和方法。

3.2 建模用例

用例图描述系统与外部交互，用例是行为步骤序列。参与者是与系统交互的实体。用例之间可存在多种关系。用例模型是系统功能的基础。

3.3 建模活动

活动图描述业务过程或用例活动的顺序，展示对象活动机制，适用于建模操作正在执行时的活动及其结果。

3.4 设计类图

类图展示系统对象类及其关系，根据需求描述抽象类及其属性、行为。

3.5 建模对象状态

状态图表示对象生命周期中的状态变化，展现对象状态及其转换。

3.6 建模交互

交互图描述用例执行中对象间的协作，序列图展示消息交互和方法调用顺序。

4 算法分析与设计

算法在计算机软件系统中具有重要地位，随着计算机性能提升，其重要性愈发凸显。算法研究有助于高效利用资源和解决复杂问题。

4.1 C 程序设计语言与实现

4.1.1 指针类型

由于篇幅有限，本节只介绍C 语言的一个核心概念-指针。指针用于指向变量地址，实现间接访问。通过指针可操作复杂数据结构、提升效率。

  1. 变量和指针
  • 定义变量和指针，指针存放变量地址。
  • 示例：int a; int *ptr; ptr = &a;，ptr 指向变量 a。
  1. 指针与数组
  • 一维数组：指针指向数组首元素，通过指针访问数组元素。
  • 二维数组：指针指向数组行首地址，通过指针访问二维数组元素。
    3 指针与函数
  • 函数参数为指针：函数通过指针参数修改调用处变量。
  • 函数返回值为指针：函数返回指针，指向数据或函数。
  • 函数指针：类型说明符 (*函数指针变量名)(参数列表)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

char* get_str(void){
    char *str = {"testing local pointer"};
    return str;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    // 一级指针 和 二级指针
    int a, *ptr = &a, **mulptr = &ptr;
    a = 123;
    printf("a = %d, *ptr = %d, **mulptr = %d\n", a, *ptr, **mulptr);
    
    // ptr 为一维数组指针，指向数组的第一个元素
    int b[10] = {1,2,3,4,5,6,7,8,9,10};
    ptr = b;
    printf("*ptr = %d\n", *ptr);
    
    // p 为二维数组指针，指向包含 4 个元素的一维数组
    int c[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
    int (*p)[4] = c;
    printf("*p = %d\n", *(*(p+2)+1));
    
    // 函数参数为指针
    swap(ptr, ptr + 1);
    printf("*ptr = %d, *(ptr + 1) = %d\n", *ptr, *(ptr + 1));
    
    // 函数返回值为指针
    char *q = get_str();
    for (int i = 0; *(q + i); i++){
        putchar(*(q + i));
    }
    printf("\n");
    
    // funptr 为函数指针，可通过函数指针变量调用函数
    int(*funptr)(int, int) = max;
    int z = (*funptr)(1, 3);
    printf("max(1,3) = %d\n", z);
    return 0;
}

4.1.2 指针与数据结构

  1. 单链表的实现和应用
  • 栈的链式存储结构 ：通过指针实现链表结点之间的联系。栈的类型定义包括栈的容量、栈顶指针等。提供了如 NewStack、IsEmpty、Top、Push、Pop 等操作来管理栈。其中，Push 操作用于将数据压入栈，Pop 操作用于将栈顶元素出栈。
  1. 二叉链表和多叉链表的设计和应用
  • 二叉树的存储结构 ：采用二叉链表存储时，结点类型定义包括数据和指向左右孩子的指针。对于特殊二叉树（如哈夫曼树），采用三叉链表表示，结点类型定义包括数据、父结点指针、左右孩子指针。
  • 其他树结构的存储结构 ：树的孩子兄弟表示法采用二叉链表作为存储结构，结点类型定义包括数据、第一个孩子指针、下一个兄弟指针。B 树适用于外部查找，其存储结构类型定义包括关键字个数、父结点指针、子结点指针数组等。
  1. 邻接表的设计和应用
  • 邻接表用于存储图，其类型定义包括图的顶点数和边数、邻接表头指针。邻接表存储结构可以表示有向图等图结构。
  1. 散列表的设计和应用
  • 散列表采用拉链法解决冲突，其类型定义包括基表和溢出桶的数目、基表和溢出桶的存储结构。散列函数为 Hash（Key）= Key mod 7，可设计不同数据存储结构。

4.2 算法设计与实现

4.2.1 算法设计过程

  1. 理解问题：准确理解算法的输入和输出，这是设计算法的切入点。
  2. 确定相关因素 ：
    • 预测程序可能输入，包括合法和非法输入。
    • 根据问题实例选择数据结构和算法设计技术。
  3. 确定数据结构 ：数据结构对算法设计至关重要，直接影响算法效率。
  4. 确定设计技术 ：运用分治法、动态规划等常用算法设计技术。
  5. 设计算法：根据前面步骤的结果设计算法，并描述求解步骤。
  6. 证明算法正确性 ：可使用循环不变式等方法证明。
  7. 分析算法效率 ：主要分析时间效率和空间效率，时间效率通常更重要。
  8. 根据算法编写代码

4.2.2 算法问题类型

  • 查找问题
  • 排序问题
  • 图问题：用于建模复杂关系，应用广泛：
    • 模型应用：社交网络等。
    • 复杂性差异：如最短路径与最长路径问题难度不同。
    • 部分问题难解：如 TSP 等尚无高效算法。
  • 组合问题：是优化问题，寻找极值组合对象：
    • 困难原因 ：组合对象数量指数增长。
    • 无通用解决方案 ：多数组合问题难高效解决。
  • 几何问题：处理几何对象，有独特难度
    • 研究历史 ：数字化处理几何问题较新。
    • 应用领域 ：图形图像处理等。
    • 典型问题 ：最近点、凸包问题。

4.2.3 典型实例

4.2.3.1 循环赛日程安排

目标是为 m 位选手安排比赛日程，每位选手与其他选手各比赛一场，不轮空。日程表是 n 行 n - 1 列的表，n = 2^m。初始日程表左上角填 1、2，通过分治法填充其余位置，直到所有比赛日程排好。

4.2.3.2 矩阵链问题

给定 n 个矩阵的序列，确定加括号方式使矩阵链乘法次数最少。用动态规划解决，步骤包括特征刻划、最优子结构定义、递归定义最优值、自底向上计算最优值和构造最优解。

4.2.3.3 多机器调度问题

将 n 个作业分配给 m 台机器处理，使总加工处理时间最短。用贪心算法，按作业处理时间从大到小排序，依次分配给最早完成任务的机器。

5 面向对象的程序设计与实现

5.1 设计与实现方法

面向对象的程序设计与实现主要关注如何将面向对象设计转化为代码。这包括理解类和对象的关系，并将设计模式应用到代码实现中。

5.2 设计模式的应用

设计模式是经过验证的解决方案，能够帮助我们更好地组织代码。例如，模板方法模式通过定义算法的骨架并允许子类重新定义某些步骤，来实现代码的复用和扩展。

示例：Application 和 Document 类

  1. Application 和 Document 的关系：Application 类负责打开和管理 Document 对象。当打开一个文档时，Application 创建一个 Document 对象并将其加入到文档集合中。
  2. 模板方法模式在 openDocument 方法中的应用：openDocument 方法定义了打开文档的主要步骤，具体实现由子类提供。这包括检查文档是否可打开、创建文档对象、打开和读取文档等步骤。

代码实现：

以下用 Java 代码展示了 Application 和 Document 类的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
abstract class Document {
    // 存储文档数据，此处代码省略
    public  void save(){
       ...
    }
    // 关闭文档，此处代码省略
    public  void close(){
      ...
    }
    // 打开文档，此处代码省略
    public void open(String docName) {
      ...
    }
    public abstract void read(String docName);
}

abstract class Application {
    // 文档对象集合
    private Vector<Document> docs = new Vector<Document>();

    public boolean canOpenDocument(String docName) {
        // 判断是否可以打开指定文档
        // 此处代码省略
        return true;
    }

    // 将文档添加到文档对象集合中
    public void addDocument(Document adoc) {
        docs.add(adoc);
    }

    // 创建一个文档对象，需要子类实现
    public abstract Document doCreateDocument();

    // 模板方法，打开文档
    public final void openDocument(String docName) {
        if (!canOpenDocument(docName)) {
            System.out.println("不能打开文档！");
            return;
        }
        Document adoc = doCreateDocument();
        // 打开文档
        adoc.open(docName);
        // 读取文档内容
        adoc.read(docName);
        // 将文档加入 application 的文档集合中
        addDocument(adoc);
    }
}

6 考试重点

  1. 结构化分析与设计中的数据流图
  2. 数据库分析与设计中的 E-R 图
  3. 面向对象分析与设计的类图
  4. 算法设计的代码
  5. 面向对象程序实现（java 或 c++ 代码）