数据结构与算法

算法的概念

解题方案的准确而完整的描述.

算法:

1. 运行有限的时间
2. 有限的存储空间
3. 得到正确的结果

算法不等于程序,也不等于计算方法,是两者的结合。

特征：

1. 可行性
2. 确定性（并且在任何条件下，算法都只有一条执行路径）
3. 有穷性
4. 拥有足够的情报

算法的基本结构：

对数据的运算操作(算数，逻辑)

算法的控制结构：

1. 顺序结构
2. 条件结构（分支结构）
3. 循环结构

描述算法：

1. 传统流程图
2. N-S结构化流程图（盒图）
3. 自然语言
4. 伪代码

一个算法可以用三种基本控制结构组合而成

算法设计方法

1. 列举法：列举所有可能
2. 归纳法：从特殊到一般
3. 递归法：函数的自调用
4. 递推法：从条件到结论
5. 减半递推：分治
6. 回溯：反证

算法的复杂度

算法复杂度可以分为：

1. 时间复杂度
2. 空间复杂度

算法的时间复杂度（和时间没有关系）

算法的计算工作量： 用算法所执行的基本运算次数来度量。

基本运算次数：是问题规模的函数

算法的计算工作量= f ( n )，其中n是问题的规模

分析算法工作量的方法：

1. 平均性态（把每次运行程序执行的基本次数平均下来）
2. 最坏情况复杂性（可能选最小，也可能选最大）

算法的空间复杂度

执行这个算法所需要的存储空间或者内存空间。

数据结构的基本概念

数据元素之间固有的逻辑关系，既数据的逻辑结构

数据中出现物理两个字,说明数据和计算机中的存放位置或地址有关系

数据的逻辑结构

数据结构是指带有结构的数据元素集合

结构是指数据元素之间前后件关系

一个数据结构包含两种信息：

1. 数据元素的信息
2. 数据元素之间的前后件关系。

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

数据的存储结构

数据的逻辑结构在计算机存储空间中存放的形式称为存储结构（也称数据的物理结构）

数据的存储结构存放：

1. 数据元素的信息
2. 数据元素之间的前后件关系

一种数据的逻辑结构,可以拥有多种物理结构（存储结构）

数据的物理结构不会影响数据本身的逻辑结构

采用不同的存储结构，则数据处理的效率是不同的

数据结构的表示：

1. 二元关系表示
2. 图形表示

数据结构分为线性结构和非线性结构。

数据元素有时候也称为节点或结点

最后一个节点称为叶子节点

线性结构（线性表）：

1. 有且只有一个根节点
2. 有且只有一个叶子节点
3. 除根节点外，其他节点均只有一个前件（前继）
4. 除叶子节点外，其他节点均只有一个后件（后继）

线性表示指n个数据元素的有限序列。

当n=0时，称为空表

线性表的顺序存储结构：

1. 存储空间是连续的
2. 按逻辑顺序依次存放的

在长度为n的线性表顺序存储结构中插入一个数,最坏情况下需要移动n个数

在长度为n的线性表顺序存储结构中删除一个数,最坏情况下需要移动n-1个数

考题

算法的空间复杂度与算法所处理的数据存储空间有关。

设数据集合为D={1,2,3,4,5,6}。

B=（D,R）中为非线性结构的是 R={（1,2），（2,3），（4,3），(3,5) }

其中R代表关系

数据的存储结构会影响算法的效率。

线性表的顺序存储结构中，其存储空间连续，各个元素所占字节数相同，元素的存储顺序与逻辑顺序一致。

时间复杂度与所用的计算工具无关。

算法设计必须考虑算法的复杂度。

算法必须能在有限个步骤之后终止。

算法强调动态的执行过程，不同于静态的计算公式。