学数据结构之前必备基础知识列表
（部分摘抄自《大话数据结构》如果有不清楚的地方可以参看原书第一章）
-
数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。
- 可以输入到计算机中
- 能被计算机程序处理
-
数据元素：是组成数据的，有一定意义的基本代为，在计算机中通常作为整体处理，也被称为记录，如鸡，鸭，人，都是数据元素
-
数据项： 一个数据元素可以由若干个数据项组成，数据项是数据结构中不可分割的最小单位， 如眼，耳，鼻等。
-
数据对象：性质相同的数据元素的集合，是数据的子集，有时也简称数据或等同于数据
-
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合，在计算机中，数据元素并不是孤立，杂乱无序的，而是具有内在联系的数据集合，数据元素之间存在的一种或多种特定的关系，也是数据的组织形式。
-
逻辑结构：数据对象中数据元素之间的相互关系，种类如下
- 集合结构：处于同一个集合中
- 线性结构：一对一线性结构（列表等 ）
- 树形结构：二叉树等一对多关系
- 图形结构：多对多结构（有向图）
-
物理结构：数据的逻辑结构在计算机中的存储形式，种类如下：
- 顺序存储结构： 是吧数据元素存放在地址连续的存储单元里，其数据的逻辑关系核物理关系是一致的
- 链式存储结构： 把数据存储在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，这就需要一个指针指向存放的地址，通过地址找到相应的元素
-
算法的定义： 解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法的简单案例 1-100求和：
- 算法一：
int sum = 0,n=100;
for(int i=1;i<=n;i++){
sum += i;
}
print("%d",sum); //5050
- 算法二：
int sum=0,n=100;
sum = (1 + n) * n / 2;
print("%d",sum);
从简单的案例可以看出两种算法结果虽然是一样的，可是算法一执行了n次， 算法二却只执行了三句，不同的算法之间的效率显而易见，算法二极大提高了效率，减少了计算机资源的消耗，让程序更加精简，高效。这也是我们学习数据结构与算法最直接的目的。
- 算法的特性：
- 输入：输入零个，一个或多个
- 输出：一定要有一个或多个输出
- 有穷性：指算法在执行有限的步骤之后自动结束而不会出现无限循环
- 确定性：算法的每一步都具有确定含义
- 可行性:算法的每一步必须是可行的
- 算法的设计要求：
- 正确性：没有语法错误，对于正确的输入数据能够产生满足要求的输出结果，对非法的输入数据能够得出满足规格说明的结果
- 可读性：便于阅读，理解和交流
- 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
- 时间效率高和存储量低：及花费时间越少，占用空间越少
-
算法效率的度量方法(重点)：时间复杂度
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
网友评论