算法

  • 算法是解决问题的操作步骤。不等于程序，不等于数学上的计算方法。

  • 算法的基本特征：可行性、确定性、有穷性（有限时间）、拥有足够的情报。

  • 算法要求有0个及以上输入，1个及以上输出。

  • 算法的基本要素：对数据对象的运算和操作、控制结构。

  • 算法复杂度：

    • 时间复杂度 执行算法所需要的计算工作量（最坏情况可=平均情况）（控制结构可计算时间复杂度）
    • 空间复杂度 执行算法所需内存空间

    两者独立，无直接或间接关系

  • 数据的逻辑结构和存储结构不是一一对应的。

  • 算法的基本运算次数与特定的输入有关。

  • 算法的工作量与计算机、程序设计语言、编制者、实现细节无关。

  • 算法的效率与问题的规模和数据的存储结构都有关。

  • 程序可以作为算法的一种表达方式

数据

  • 数据结构 相互之间有关联的数据元素的集合
  • 数据的基本单位 数据元素
  • 数据的最小单位 数据项
  • 表示数据结构的方法
    • 二元关系表示法
    • 图形表示法
      • 数据结点 标有元素值的方框表示数据元素
      • 元素前后关系 有向线段从前件指向后件结点
  • 数据的逻辑结构（与存储无关）
    • 线性结构 有且只有一个根节点
      • 常见线性结构 线性表、栈（先进后出）、队列（先进先出）、向量、矩阵、二维表
    • 非线性结构 树、图形结构
  • 数据的存储结构 逻辑结构在存储空间的存放形式
    • 分类：顺序、链式、索引、散列存储方式

非空数据结构可以是线性结构也可以是非线性结构
非空数据结构可以没有根节点

线性表

  • 线性表是n个元素的有限序列（n=0为空表）。
  • 对线性表可进行查找、删除、插入等操作。
  • 线性表中各元素具有相同的数据性，所有线性表都可采用顺序存储。
  • 非空线性表满足的条件：
    • 只有一个根节点，且无前件；
    • 只有一个终端店，且无后件；
    • 除根节点和终端点之外，其他节点只有一个前件和后件。
  • 线性表的顺序存储结构：
    • 元素所占的空间是连续的；
    • 各数据元素在存储空间中的存放顺序是按照逻辑顺序依次存放的。
  • 线性表的链式存储结构
    • 存储空间可连续也可以不连续；
    • 每个元素占有相同的存储单元；
    • 数据的插入和删除不需要移动元素，只需要改变结点的指针域。
  • 循环链表和双向链表为线性结构的数据结构
  • 循环队列为队列的顺序存储结构（循环链表不是链表的顺序存储结构）
    • 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。
    • 线性结构的存储结点可以有多个指针

栈与队列（线性表）

  • 栈是一种先进后出表，队列是一种先进先出表（操作系统中的作业调用就是队列）。
  • 栈只允许在栈顶（top）进行插入和删除操作，不允许在栈底进行操作（bottom）。

栈支持子程序调用。

  • 队列只允许在队头（front）进行删除，在队尾（rear）进行插入。
  • 存储结构:
    • 栈的存储结构：
      • 相当于是一个一维数组，m为栈的最大容量， 当top=0时，栈为空栈；
      • 发生上溢错误，表明栈已满；发生下溢错误，表明栈已空；
      • 读栈顶元素=将值赋给一个变量。
    • 队列的存储结构：
      • 用一维数组作为顺序存储空间；
      • rear=front=m时，队空或队满；

      front>rear时，元素个数=m-（front-rear）;
      front<rear时，元素个数=rear-front      。

  • 带链的队列:
    • 一个单链表表示队列
    • 队列空 头尾指针为NULL
    • 队列一个元素 头尾指针都指向它
  • 链式存储结构：
    • 每个结点由数据域（元素值）和指针域（指针）构成；
    • 存储节点不一定连续，结点存储顺序与数据元素之间1的逻辑可以不一致；
    • 链式存储的可以是线性结构，也可以是非线性结构。
  • 线性链表
    • 是线性表的链式存储结构；
    • head不得丢失，最后一个结点指针域为空NULL/0；
    • head=NULL/0是空表；
    • 不一定连续，逻辑顺序不一致。
  • 单链表
    • 缺点：找到后件，找不到前件。
  • 循环链表 指针域指向线性表的第一个元素结点
    • 至少有一个节点存在（表头结点）；
    • 实现空表和非空表1的运算的统一；
    • 可以实现从任意结点无重复地扫描到所有节点。

二叉树（非线性结构）

  • 存储结构：
    • 顺序存储结构：连续存储单元 从上至下，从左到右（满二叉树和完全二叉树可按层次进行顺序存储）
    • 链式存储结构
    • 二叉树分为完全二叉树和满二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
    • 遍历 （不重复地访问所有结点）：
      • 前序：根 左 右
      • 中序：左 根 右
      • 后序：左 右 根

查找技术与排序技术

  • 顺序查找 从线性表的第一个元素开始
    • 只能采用顺序查找：

      • 无序线性表（顺序结构、链式结构）

      • 有序线性表（链式结构）

    • 最坏情况下需要比较n次
  • 二分法
    • 最坏情况下需要比较log2n2^n次
    • 适用于顺序存储的有序表（已对顺序存储结构排序，但相邻元素值可相等）
  • 排序
    • 冒泡排序、直接插入排序、快速排序和简单选择排序法最坏情况下需要比较次数为n(n-1)/2；
    • 希尔排序 （n^1.5次）;
    • 堆排序 时间复杂度为o(n〖log〗_2n) 最坏情况下堆排序比较次数最少

    快速排序适用于顺序存储的线性表
    冒泡排序是相邻元素进行交换

程序设计

  • 定义 是设计、编制、调试程序的方法和过程

  • 设计风格

    • 源程序文档化
    • 数据说明方法
    • 语句的结构（清晰第一，效率第二）
    • 程序的输入和输出

    高内聚，低耦合

  • 结构化程序设计

    • 基本原则
      • 自顶向下
      • 逐步求精
      • 模块化
      • 限制使用goto语句
    • 基本结构 顺序结构、选择结构（分支结构）、循环结构（重复结构）
    • 结构化方法软件需求分析工具
      • 数据流程图（DFD） 数据存储间无数据流，支持软件系统功能建模
        • 椭圆 表示加工（转换）
        • 箭头 表示数据流
        • 双杠 表示存储文件（数据源）
        • 矩形 表示源、潭
      • 数据字典（DD） 解释DFD图形元素
      • 判定树
      • 判定表

  • 面向对象的程序设计

    • 组成
      • 对象 描述客观事物的一个实体，实构成软件系统的基本单位。 对象=数据（属性）+方法（操作）
        • 标识唯一性
        • 分类性
        • 多态性
        • 封装性
        • 模块独立性好

        对象是类的一个实例

      • 类 具有相同属性和服务的一组对象的集合 可用于创建对象
      • 封装 目的是为了实现信息隐蔽
        • 向外部提供外部接口，降低对象间耦合度。对象间的紧密程度越高，耦合度越高，可维护性越低。
      • 继承 多个类之间共享属性和操作的机制
        • 对象不一定具有继承性
      • 消息 统一数据流和控制流 对象间通信靠消息传递
      • 多态性 指同一个操作可被不同对象接收导致不同行为

软件工程

  • 软件
    • 概念 包括程序、数据及文档的完整集合（逻辑产品）
    • 分类
      • 应用软件 解决特定领域（office 杀毒软件 浏览器）
      • 系统软件管理计算机本身（数据库管理系统 操作系统 unix系统）
      • 支撑软件 为开发、维护软件的软件（编译软件 如DevC++）
    • 特点
      • 是逻辑实体，有抽象性
      • 生产没有明显的制作过程
      • 运行使用期间不存在磨损、老化问题
      • 开发、运行对计算机系统依赖性高
  • 软件危机（成本、质量、生产率）
    • 产生原因：软件开发、维护方法不当
  • 软件工程
    • 三要素 方法、工具、过程
    • 核心思想 工程产品
    • 原则
      • 抽象
      • 信息隐蔽 封装
      • 模块化
      • 局部化
      • 确定性
      • 一致性
      • 完备性
      • 可验证性、自顶向下、逐层分解
    • 研究内容
      • 软件开发技术
      • 软件工程管理
    • 软件生命周期
      • 定义：从提出、实现、使用维护到停止使用退役的过程
      • 阶段
        • 软件定义阶段
          • 问题定义
          • 可行性研究
          • 需求分析
        • 软件开发期
          • 概要设计
          • 详细设计
          • 实现和测试
        • 运行维护期
          • 运行维护阶段
    • 软件需求分析
      • 内容： 需求获取、需求分析、编写需求规格说明书、需求评审
      • 方法：结构化分析方法&面向对象的分析方法
      • 需求规格说明书的作用
        • 便于用户、开发人员理解和交流
        • 反映出用户问题的结构，可以作为软件开发工作的基础和依据
        • 作为确认测试和验收测试的依据
      • 软件设计
        • 工程管理角度
          • 概要设计
            • 设计软件系统结构
            • 设计数据结构及数据库
            • 编写设计概要文档
            • 概要设计文档审评
          • 详细设计（过程设计）
            • 图形工具：程序流程图、N-S、PAD、HIPO
            • 表格工具：判定表
            • 语言工具：PDL（伪码）

          • 程序流程图中图形的含义：箭头——控制流、矩形——加工、菱形——判断

        • 技术观点分析
          • 结构设计
          • 数据设计
          • 过程设计
        • 基本原理
          • 抽象
          • 模块化
          • 信息隐蔽
          • 模块独立性
            • 评价设计好坏的重要标准
            • 衡量方法 高内聚低耦合
      • 软件测试
        • 目的：查找错误
        • 分类方法
          • 是否执行被测试软件
            • 静态测试 不执行（人工）
            • 动态测试 执行（计算机测试发现错误）
          • 功能
            • 白盒测试（结构设计、逻辑驱动测试） 程序内部进行（逻辑覆盖、基本路径测试）
            • 黑盒测试 （功能测试、驱动测试）（等价类划分法、边界分析法、错误推测法、因果图）