算法
算法是解决问题的操作步骤。不等于程序，不等于数学上的计算方法。
算法的基本特征：可行性、确定性、有穷性（有限时间）、拥有足够的情报。
算法要求有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次
- 只能采用顺序查找：
- 二分法
- 最坏情况下需要比较log次
- 适用于顺序存储的有序表（已对顺序存储结构排序，但相邻元素值可相等）
- 排序
- 冒泡排序、直接插入排序、快速排序和简单选择排序法最坏情况下需要比较次数为
n(n-1)/2； - 希尔排序
（n^1.5次）; - 堆排序 时间复杂度为
o(n〖log〗_2n)最坏情况下堆排序比较次数最少
快速排序适用于顺序存储的线性表
冒泡排序是相邻元素进行交换 - 冒泡排序、直接插入排序、快速排序和简单选择排序法最坏情况下需要比较次数为
程序设计
定义 是设计、编制、调试程序的方法和过程
设计风格
- 源程序文档化
- 数据说明方法
- 语句的结构（清晰第一，效率第二）
- 程序的输入和输出
高内聚，低耦合
结构化程序设计
- 基本原则
- 自顶向下
- 逐步求精
- 模块化
- 限制使用goto语句
- 基本结构 顺序结构、选择结构（分支结构）、循环结构（重复结构）
- 结构化方法软件需求分析工具
数据流程图（DFD）数据存储间无数据流，支持软件系统功能建模- 椭圆 表示加工（转换）
- 箭头 表示数据流
- 双杠 表示存储文件（数据源）
- 矩形 表示源、潭
- 数据字典（DD） 解释DFD图形元素
- 判定树
- 判定表
- 基本原则
面向对象的程序设计
- 组成
对象描述客观事物的一个实体，实构成软件系统的基本单位。 对象=数据（属性）+方法（操作）- 标识唯一性
- 分类性
- 多态性
- 封装性
- 模块独立性好
对象是类的一个实例
- 类 具有相同属性和服务的一组对象的集合 可用于创建对象
- 封装 目的是为了实现信息隐蔽
- 向外部提供外部接口，降低对象间耦合度。
对象间的紧密程度越高，耦合度越高，可维护性越低。
- 向外部提供外部接口，降低对象间耦合度。
- 继承 多个类之间共享属性和操作的机制
对象不一定具有继承性
- 消息 统一数据流和控制流 对象间通信靠消息传递
- 多态性 指同一个操作可被不同对象接收导致不同行为
- 组成
软件工程
- 软件
- 概念 包括
程序、数据及文档的完整集合（逻辑产品） - 分类
应用软件解决特定领域（office 杀毒软件 浏览器）系统软件管理计算机本身（数据库管理系统 操作系统 unix系统）支撑软件为开发、维护软件的软件（编译软件 如DevC++）
- 特点
- 是逻辑实体，有抽象性
- 生产没有明显的制作过程
- 运行使用期间不存在磨损、老化问题
- 开发、运行对计算机系统依赖性高
- 概念 包括
- 软件危机（成本、质量、生产率）
- 产生原因：软件开发、维护方法不当
- 软件工程
- 三要素
方法、工具、过程 - 核心思想 工程产品
- 原则
- 抽象
- 信息隐蔽 封装
- 模块化
- 局部化
- 确定性
- 一致性
- 完备性
- 可验证性、自顶向下、逐层分解
- 研究内容
- 软件开发技术
- 软件工程管理
- 软件生命周期
- 定义：从
提出、实现、使用维护到停止使用退役的过程 - 阶段
- 软件定义阶段
- 问题定义
- 可行性研究
- 需求分析
- 软件开发期
- 概要设计
- 详细设计
- 实现和测试
- 运行维护期
- 运行维护阶段
- 软件定义阶段
- 定义：从
- 软件需求分析
- 内容： 需求获取、需求分析、编写需求规格说明书、需求评审
- 方法：结构化分析方法&面向对象的分析方法
- 需求规格说明书的作用
- 便于用户、开发人员理解和交流
- 反映出用户问题的结构，可以作为软件开发工作的基础和依据
- 作为确认测试和验收测试的依据
- 软件设计
- 工程管理角度
概要设计- 设计软件系统结构
- 设计数据结构及数据库
- 编写设计概要文档
- 概要设计文档审评
详细设计（过程设计）- 图形工具：程序流程图、N-S、PAD、HIPO
- 表格工具：判定表
- 语言工具：PDL（伪码）
程序流程图中图形的含义：箭头——控制流、矩形——加工、菱形——判断
- 技术观点分析
- 结构设计
- 数据设计
- 过程设计
- 基本原理
- 抽象
- 模块化
- 信息隐蔽
- 模块独立性
- 评价设计好坏的重要标准
- 衡量方法
高内聚低耦合
- 工程管理角度
- 软件测试
- 目的：查找错误
- 分类方法
- 是否执行被测试软件
- 静态测试 不执行（人工）
- 动态测试 执行（计算机测试发现错误）
- 功能
白盒测试（结构设计、逻辑驱动测试） 程序内部进行（逻辑覆盖、基本路径测试）黑盒测试（功能测试、驱动测试）（等价类划分法、边界分析法、错误推测法、因果图）
- 是否执行被测试软件
- 三要素
