算法

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

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

  • 算法要求有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(伪码)
          • 程序流程图中图形的含义:箭头——控制流、矩形——加工、菱形——判断

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