目录
Note
本页偏基础知识与目录，主题关系图见 算法知识地图。
数据结构
- 线性结构
- 树形结构
- 图形结构
- 散列结构
- 特殊结构
算法
数据元素
数据元素是数据的基本单位，数据元素可由几个数据项构成，数据项是数据不可分割的最小单位
数据对象是数据元素的集合
例：
| 中国富豪榜 | 人物 | 财富 |
|---|---|---|
| 马云 | 100y | |
| 马化腾 | 300y | |
| … | … |
其中一行就是数据元素，具体马云、财富等就是数据项，整个表是数据元素
逻辑结构
集合结构：之中数据同属一个集合，之间没有另类的结构
线性结构：一对一的关系
树形结构：一对多的层次关系（金字塔关系）
图形结构：多对多关系（交际关系网络）
物理结构
- 如何把数据存储到计算机的存储器中（针对内存而言）
- 硬盘等外部存储器数据采用文件结构描述
数据存储结构形式有两种
顺序存储
- 数据存储在地址连续的存储单元，逻辑关系和物理关系一致 例：000123-000124-000125…
链式存储
- 数据存储在任意存储单元，完全随机 例:指针
数据结构与算法
例：1+2+3…+100
int i,sum = 0,n = 100;
for(i = 1;i <= n;i++)
{
sum=sum+i;
}
printf("%d",sum);or:
int i,sum = 0,n = 100;
sum=(1+n)*n/2;\\等差数列求和
printf("%d",sum);算法具有五个特征：输入，输出，有穷性1，确定性2，可行性3
算法设计要求:
- 正确性
- 没有语法错误
- 合法输入满足要求输出
- 非法输入满足规格说明
- 对故意刁难的测试输入有满足要求的输出结果
- 可读性
便于他人阅读
- 健壮性
不合法不会崩溃
- 时间效率存储效率
时间复杂度，空间复杂度
T(n)增长最慢的算法为最优算法
大O记法：
- 基本语句、加法常数记为 1
- 最高阶存在且不为 1 除于此项相乘的常数
例1：
int n=100,sum=0;
printf("666\n");
printf("666\n");
printf("666\n");
printf("666\n");
printf("666\n");
printf("666\n");
sum = (1/n)*n/2; 程序只按顺序只跑一次因此时复为O(1)
例2：
int i, n = 100, sum = 0;
for(i=0;i<n;i++){
sum=sum+i;
}以上程序时间复杂度为O(n)
例3:
for(;;)
for(;;)
body;O(n^2)
例4:
while(i<n)
{
i=i*2;
}时间复杂度 O(logn) 实际
| 例子 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| c | O(1) | 常数阶 |
| an+b | O(n) | 线性阶 |
| an^2+bn+c | O(n^2) | 平方阶 |
| alog_{b}n | O(logn) | 对数阶 |
| alog_{b}n+cn+d | O(nlogn) | nlogn阶 |
| 2^n | O(2^n) | 指数阶 |
通常耗费时间：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
算法存在最坏情况和平均情况
空间复杂度
即需要的硬盘、内存空间
抽象数据类型
C语言中抽象数据类型有两种
原子型：不可分割，如整型、浮点型、字符型
结构类型：若干类型组合而成，如各类型数组、结构体
抽象数据类型：ADT—数学抽象特性，如游戏中人物位置由x,y,z即抽象数据类型
描述抽象数据类型标准格式
Note
ADT 抽象数据类型名
Data数据元素之间逻辑关系的定义
Operation
操作
endADT