目录
1、绪论
2、线性表
3、栈、队列和数组
4、串
5、树与二叉树
6、图
7、查找
8、排序
1、绪论什么是数据结构?
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三个方面:逻辑结构、存储结构、数据的运算。
逻辑结构有:集合(数据元素除属于“同一个集合”外,别无其他关系);
线性结构(数据元素之间只存在一对一的关系);
树形结构(数据元素之间存在一对多的关系);
图状结构或网状结构(数据元素之间存在多对多的关系)。
存储结构有:顺序存储、链式存储、索引存储、散列存储。
四种存储结构的优缺点是什么?
顺序存储:
优点:可以实现随机存取,每个元素占用最少的存储空间;
缺点:只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
链式存储:
优点:不会出现碎片现象,能充分利用所有存储单元;
缺点:每个元素因存储指针而占用额外的存储空间,且只能实现顺序存取。
索引存储:
优点:检索速度快;
缺点:附加的索引表额外占用存储空间。另外,增加和删除数据时也要修改索引表,
因而会花费较多的时间。
散列存储:
优点:检索、增加和删除结点的操作都很快;
缺点:若散列函数不好,则可能出现存储单元的冲突,而解决冲突会增加时间和空间的开销。
算法的基本概念?
算法(Algorithm)是对特定问题求解步骤的一种描述。
算法的五个特性:
有穷性、确定性、可行性、输入、输出。
“好”算法应达到以下目标:
正确性、可读性、健壮性、高效率与低存储量需求。
时间复杂度的计算?
点击跳转到时间复杂度的计算
常见的渐近时间复杂度为
O(1)