嵌入式学习--数据结构+算法
数据结构
数据的逻辑结构、存储结构、数据的操作（数据的运算）
1.1数据
数据：不再是单一的数值，类似集合
数据元素：数据的基本单位，由若干数据项组成
数据项：数据的最小单位，描述数据元素信息
节点：就是数据元素
1.2逻辑结构
逻辑结构：元素与元素之间的关系
1）线性关系 ---》线性结构 -----》一对一 ----》线性表
2）层次关系 ---》树形结构 -----》一对多 ----》树
3）网状关系 ---》图状结构 ----》多对多 ---》图
1.3存储结构
存储结构：数据的逻辑结构在内存中的具体实现
1）顺序存储结构
数组：在内存当中一段连续的内存空间中保存数据(如c语言中的一维数组)
2）链式存储结构
特点：内存不连续，通过指针进行连接
链表结构体：
struct node_t
{
int data;//数据域
struct node_t * next ;//指针域，存放下一个节点的地址
};
struct node_t A = {1,NULL};
struct node_t B = {2,NULL};
struct node_t C = {3,NULL};
- next = &B;
- next = &C;
3）索引存储结构
提高查找速度
索引表 + 数据文件
姓氏 + 地址 名字 + 电话号码
4）散列存储结构
数据在存储的时候与关键码之间存在某种对应关系
存的时候按照对应关系存
取的时候按照对应关系取
1.4操作（数据的运算）
增、删、改、查
算法
2.1算法与程序
程序：用计算机语言对算法的具体实现
2.2算法与数据结构
算法 + 数据结构 = 程序
算法的设计：取决于选定的逻辑结构
算法的实现：依赖于采用的存储结构
2.3算法的特性
1）有穷性 //算法的执行步骤是有限的
2）确定性 //每一个步骤都有明确含义，无二义性
3）可行性 //能够在有限的时间内完成
4）输入
5）输出
2.4如何评价一个算法的好坏？
正确性 :保证算法可以正确实现功能
易读性 ：容易被解读
健壮性 ： 容错处理
高效性 ：执行效率，算法执行快慢容易受到计算机性能的影响，
不可以作为评判算法高效性的标准，这通过可执行语句重复执行
次数来衡量算法是否高效 。(时间复杂度)
低存储型 ： 占用空间少
2.5时间复杂度
算法的可重复执行语句执行的次数
通常时间复杂度用一个问题规模函数来表达
T(n) = O(f(n))
T(n) //问题规模的时间函数
n //问题规模，输入量的大小
O //时间数量级
f(n) //算法的可执行语句重复执行的次数 用问题规模n的某个函数f(n)来表达
例1：
求1+2+3+..+n
方法1：
int sum = 0;
for(i=1;i<=n;i++) n==10,10次 n==10000,10000次
sum+=i;
f(n) = n
T(n) = O(n)
方法2：
等差数列{an}的通项公式为：an=a1+(n-1)d。前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2 。
int sum = n(1+n)/2; n==100 ,1次；
f(n) = 1
T(n) = O(1)
例2：
int i，j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
printf("ok\n")；
f(n) = n^2;
例3：
int i，j;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
printf("ok\n")；
i 次数
0 1
1 2
2 3
n-1 n
f(n) = 1+2+3+...+n = (1+n)n/2 = n/2+n^2/2
n^2
计算大O的方法：
(1)根据问题规模n写出表达式 f(n)
(2)只保留最高项，其它项舍去
(3)如果最高项系数不为1，除以最高项系数
(4)如果有常数项，置1
f(n) = 8; O(1)
f(n)= 3n^5 + 2n^3 + 6*n^6 + 10 ; O(n^6)
2.6空间复杂度
算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
算法占用的存储空间包括：
1）输入输出数据所占空间
2）算法本身所占空间
3）额外需要的辅助空间