【数据结构】基本概念:定义,数据之间的关系,程序的定义
【数据结构】
前言
1、定义
相互之间存在一种或多种特定关系的数据元素的集合(组织和存储数据)
程序 = 数据结构 +算法
2、数据与数据之间的关系
3、数据的类型
是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
原子类型,int,char,float
结构类型,sturct, union
4、算法
是解决特定问题求解步骤的描述,计算机中表现为指令的有限序列,每条指令表示一个或多个操作。
-
算法的设计
- 正确性
- 可读性,便于交流,阅读,理解
- 健壮性,输入非法数据,能进行相应的处理,而不是产生异常
- 高效,存储低,效率高
-
算法的特征
- 输入,输出特性,输入时可选的,输出时必须的。
- 有穷性,执行的步骤会自动结束,不能是死循环,并且每一步是在可以接受的时间内完成。
- 确定性,同一个输入,会得到唯一的输出。
- 可行性,每一个步骤都是可以实现的。
-
算法的时间复杂度
执行这个算法所花时间的度量
推导时间复杂度
- 用常数1 取代运行时间中的所有加法常数
- 在修改后的运行函数中,只保留最高阶项。
- 如果最高阶存在且不是1,则取除这个项相乘的常数。
5、小结
程序的设计:将现实中大量而复杂的问题以特定的数据类型和特定的存储结构存储在内存中,并在此基础上实现某个特定的功能的操作;
程序 = 数据结构 + 算法