[数据结构与算法]计算机公共基础

算法的基本特征

• 算法：是指解题方法的准确而完整的描述（算法不等于程序）
• 算法的基本特征：

1. 可行性
2. 确定性
3. 有穷性
4. 足够的情报

• 算法的基本要数

1. 对数据对象的运算和操作：s算数运算，逻辑运算，关系运算，数据传输

• 算法的控制结构

1. 算法中各种炒作之间的执行顺序
2. 描述算法的工具通常有传统流程图，n-s结构化流程图，算法描述语言等
3. 一个栓发一般可以用顺序，选择，循环三种基本结构组合而成

• 算法的时间复杂度：算法的时间复杂度：是指执行算法所需要的计算工作量，可以用算法所执行的基本运算度量
• 算法的空间复杂度：是指执行算法所需要的内存空间，包括算法程序，输入的出是数据以及执行过程中需要的额外空间
• 算法的时间复杂度和空间复杂度相互独立

数据结构

1. 数据：需要处理的元素数据的集合，一般来说，这些数据元素，具有某个相同的特征

2. 数据元素是数据的基本单位，数据项是数据的最小单位

3. 结构：所谓结构，是集合中各个元素之间存在的某种关系或联系

4. 数据结构：是指互相有关联的数据元素的集合

• 数据结构的分类

• • 逻辑结构
    1. 线性结构：线性表，栈，队列
    2. 非线性结构：树，图
  • 存储结构
    1. 顺序结构
    2. 链式存储
  • 运算
    1. 插入
    2. 删除
    3. 查找
    4. 排序

• 线性结构与非线性结构

• 线性结构（线性表 ）

1. 有且只有一个根节点，它没有前件
2. 每一个节点最多有一个前件，也最多有一个后件

• 非线性结构：不满足以上两个条件的数据结构就称之为非线性结构，非线性结构主要是指树形结构和网状结构

• 数据结构的存储结构：又称数据的物理结构在计算机存储空间的存放方式

存储接口

• 顺序存储结构;这种存放方式主要用于线性的数据及结构，它把逻辑上相邻的数据袁术存储在维利尚相邻的存储单元里
• 链式存储结构：每一个节点至少包含一个指针域，用指针的指向来体现数据元素之间的逻辑联系
• 一种逻辑结构可以有多种存储结构
• 不同的存储结构其数据的处理效率不同

线性表

• 线性表是n(n>=0)个袁术构成的有限序列，表中处读一个元素外的每一个元素，有且就只有一个前件，除最后一个元素外，只有一个后件；
• 通常，线性表采用顺序存储结构，但一般都使用顺序存储结构
• 线性表的顺序储存又叫顺序表
• 特点

1. 线性表中所有袁术所占的存储空间是连续的
2. 线性表中数据元素在存储空间中按逻辑顺序依次存放的
3. 可以瞬即访问数据元素
4. 做插入，删除时需移动大量元素，因此不便与插入和删除元素

栈

• 栈是限定在一端进行插入删除操作的

特点：

1. 栈是只能在栈顶进行插入和删除

2. 栈的修改原则是先进后出或者后进先出

3. 栈是限定在一端进行插入和删除的线性表

4. 栈只能在栈顶进行插入和删除

5. 栈低指针不变，栈中元素随着栈顶指针的变化而变化

6. 栈具有记忆功能

7. 栈支持子程序的调用

8. 栈顶指针，栈底指针，入栈，栈满，出栈

队列

• 队列是指允许在一端进行插入，而在另一端经行删除的线性表，原则是：先静进先出或者后经后出
• 队头指针
• 队尾指针

队列的特点

1. 队列只允许在队尾进行插入，而在队头进行删除
2. 队列的修改原则是先进先出或后经后出
3. 队列中元素随对头指针和队尾指针的变化而变化

线性链表

• 线性表可以采用顺序储存和链式储存
• 线性表的顺序储存叫做顺序表，线性表的链式储存叫做线性链表
• 线性表的顺序储存结构

1. 通常，线性表可以采用顺序和链式储存，但一般都是用顺序

• 特点

1. 线性表中所有的袁术所占储存空间是连续的
2. 线性表中数据袁术在储存空间中是按逻辑顺序依次存放的
3. 可以随机访问数据元素
4. 做插入，删除时需要移动大量元素，因此线性表不便于插入和删元素

• 线性链表的特点

1. 各数据的存储空间不连续‘
2. 各数据元素的存储顺序与逻辑顺序可以不一致
3. 线性链表存储所占的存储空间大于顺序存储结构
4. 查找结点时链式比顺序存储慢
5. 链式存储插入和删除比顺序灵活

• 双向链表
• 循环链表

树与二叉树

树是n(n>0)个元素的有限集合，它只有一个称为根的元素，其余元素是互不相交的子数

• 常用术语

1. 父节点，子结点
2. 根节点，叶子结点
3. 结点的度，树的度，度->有几个子女就是几，最大的度称为树的度
4. 树的深度，有几层深度就是多少
5. 子树

• 二叉树：是一个有限的结点集合该集合可以为空，或者由一个根结点以及两颗互不相交的左右二叉子叶所组成
• 二叉树具有以下两个特点

1. 非空二叉树只有一个根结点
2. 每一个结点最多有两颗子树，且分别称为该结点的左子树与右子树

• 特殊的二叉树

1. 满二叉树：除最后一层外，每一层的节点数均达到最大值（2）；
2. 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边是若干结点

• 二叉树的特点

1. 在二叉树的第k层上，最多2^（k-1）个结点
2. 深度为m的二叉树最多有2^(m-1)个结点
3. 度为0的结点（叶子结点）总比度为2的结点多一个
4. 有n个结点的二叉树的深度至少为[log2n]+1

二叉树的遍历

• 前序遍历（根左右）

1. 访问根结点

2. 前序遍历左子树

3. 前序遍历右子树

• 中序遍历（左根右）

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

• 后序遍历（左右根）

1. 左子树
2. 右子树

查找技术

顺序查找：

• 对于长度为n的线性表，平均要比较n/2次，追怀情况下比较n次

• 顺序查找适用于无序表或者链式存储（不管是有序还是无序）

二分查找

• 适用于顺序存储的有序表，对长度为n的线性表，在最坏的情况下经行log2n次比较

排序

n（n-1）/2

程序设计基础

• 良好的程序设计风格：清晰第一，效率第二

如何形成良好的程序设计风格？

1. 源程序内部文档化：悬着标识符的名字。注释。程序的视觉组织
2. 数据说明
3. 语句的结构
4. 输入和输出

• 结构化程序设计原则

1. 自顶向下
2. 逐步求精
3. 模块化
4. 限goto，程序的质量与goto成反比

• 结构化程序的基本结构

1. 顺序结构

2. 选择结构

3. 循环结构

   面向对象程序设计

4. 对象

5. 属性:描述对象的状态

6. 方法：描述对象的行为

7. 类：具有相同属性相同操作的对象集合

• 对象的特点

1. 标识唯一性
2. 分类性
3. 封装性
4. 多态性
5. 模块独立性好

• 继承
• 消息
• 多态性

软件工程基础

• 软件是程序，数据，文档的集合

• 软件的分类

1. 系统软件：操作系统，编译系统，数据库管理系统
2. 应用软件，事务处理软件，工程与科学计算软件
3. 支撑软件(工具软件)，需求分析工具软件，编译工具软件

• 软件工程:应用于计算机软件的定义，开发和维护一整套方法，工具，文档，时间标准和工序

• 其核心思想是吧软件当做一个工程产品来处理

• 方法

• 工具

• 过程

• 软件的生命周期：将软件产品从提出，实现，使用维护到停止使用退役的过程称为软件的生命周期

• 分为软件定义，软件开发，软件维护3个时期

结构化分析方法

需求分析的方法有

1. 结构化分析方法：使用数据流图（DFD),数据字典（DD）判定表和判定树等工具，来奖励系统的逻辑模型
2. 面向对象分析方法

• 数据流图

1. 加工
2. 数据流
3. 储存文件
4. 源（潭）

• 数据字典是结构化分析的核心

结构化设计方法

• 软件设计的基本原理

1. 抽象：在软件设计中，可以定出多个抽象级别，抽象层次从概要设计到详细设计逐步降低，
2. 模块化：把一个待开发的软件分解成若干个小的简单部分，把软件分成若干模块
3. 信息屏蔽：一个模块化的信息。对于不需要这些信息的其他模块来说不能访问
4. 模块独立性，每个模块只能完成独立子功能

• 高内聚（模块内部），低耦合（模块之间）

软件测试

软件测试的目的是发现程序中的错误

软件测试分为静态测试和动态测试

静态测试：软件不需要被执行

动态测试：需要

白盒测试：逻辑覆盖测试，基本路径测试（根据内部逻辑结构）

黑盒测试：1.等价类划分法，2.边界值分析法，3.错误推测法（程序外部功能）

• 软件测试步骤

1. 单元测试
2. 集成测试
3. 确认测试
4. 系统测试

程序的调试

对程序进行成功的测试之后将进入程序的调试，通常称为debug（排错），主要在开发阶段进行

程序调试的任务是诊断和改正程序的错误

• 基本步骤

1. 错误定位
2. 修改设计和代码，以排除错误
3. 进行回归测试，防止引进新的错误

软件调试和方法

1. 强行排除法
2. 回溯法
3. 原因排除法

数据库系统的基本概念

数据（data)

描述事物的符号记录称为数据，软件中的数据一定是结构的，有型与值（类型）两个概念

数据库（BD）

特点1. 集成，2.共享

• 数据库管理系统(DBMS)
• 数据库管理系统是数据库系统的核心

数据的定义语言ddl：数据模式的定义，数据存取的物理构建

数据操纵语言dml：包括查询与增删改等操作

数据的控制语言dcl：并发控制与故障恢复，数据的完整性

• 数据库管理员DBA

主要工作包括

1. 数据库设计
2. 数据库维护
3. 改善系统性能，提高系统效率

• 数据库系统DBS

1. 数据库（数据）：集成，共享
2. 数据库管理系统DBMS软件:定义，构建，操作。检查。控制。服务，ddl，dml，dcl
3. 数据库管理员DBA：设计，维护，改善
4. 软件平台：操作系统，开发工具，接口软件
5. 硬件平台：计算机，网络

数据库应用系统（DBAS)

数据库应用系统包括：数据库系统，应用软件以及应用界面

• 数据库管理的三个阶段

1. 人工管理
2. 文件系统
3. 数据库系统

• 数据库的根本目标是：解决数据共享问题

数据库特点

• 集成性，高共享，低冗余，独立性。统一管理控制

三级模式和两极映射

1. 概念模式：是全局数据逻辑结构的描述，是全体用户的公共数据视图，中层
2. 外模式：又称子模式或者用户模式。是用户的数据视图，外层
3. 内模式：给出数据库物理存储结构与存取方法，底层

• 两极映射保证了数据库中具有较高的逻辑独立性和物理独立性

数据模型

数据模型的三要素：数据结构，数据操作，数据约束

数据模型分为

• 概念模型：e-r模型

• 逻辑数据模型：层次模型，网状模型，关系模型，面向对象模型

• 物理数据模型

• E-R模型（实体联系模型）

1. 实体
2. 属性
3. 联系
4. 连接关系

关系代数

关系模型的基本操作

• 插入，删除，修改，查询
• 查询运算

1. 投影运算
2. 选择运算
3. 笛卡尔运算（连接运算）

• 关系代数中扩充运算
• 交运算，除运算，连接运算，自然连接运算

数据库设计与管理

数据库设计概述

• 基本任务，根据用户对象的信息需求，处理需求和数据库的支持华宁设计出数据模式

两种方法

1. 以信息需求位置，兼顾处理需求（面向数据的方法）
2. 以处理需求为主，兼顾信息需求（面向过程的方法）
3. 面向数据的设计方法已成为主流方法

数据库设计前四个重要的阶段

1. 需求分析：建立数据字典
2. 概念设计：设计e-r图
3. 逻辑设计：把e-r图转换为关系模式
4. 物理设计