一、数据结构的基本概念1基本概念和术语数据数据是对客观事物的符号表示数据元素是数据的基本单位数据对象具有相同性质的数据元素的集合数据对象集合⊇数据元素个体⊇数据项属性)2数据结构三要素2.1三要素逻辑结构、物理结构(存储结构)、数据运算和实现2.2逻辑结构线性结构数据元素之间存在一对一的关系除了第一个元素所有元素都有唯一前驱除 了最后一个元素所有元素都有唯一后继。树形结构数据元素之间存在一对多的关系。图形结构数据元素之间存在多对多的关系。集合数据元素属于一个集合除此之外别无其他关系。2.3存储结构顺序存储把逻辑上相邻的数据元素存放在一段连续物理存储单元中链式存储逻辑上相邻的数据元素存储在任意的一组物理存储单元中数据元素之间的逻辑关系用指针来表示索引存储存储元素信息的同时还建立了索引表索引表中的每项称为索引项索引项的一般形式为(关键字地址)散列存储根据数据元素中的关键字计算出该数据元素的存储地址举例贪吃蛇逻辑结构线性结构存储结构顺序存储效率较低/链式存储3数据类型和抽象数据类型3.1数据类型原子类型原子类型的值是不可以再分解的。如C语言的int、double、char等基本数据类型结构类型结构类型的值是由若干成分按某种结构组成是可以分解的。如C语言中定义的⼀个结构体类型。3.2抽象数据类型是⼀种数学模型加上在该模型上定义的一组操作的集合它定义了数据对象、数据关系以及对数据的操作但隐藏了具体实现细节。4总结二、算法的基本概念1算法和数据结构算法(Algorithm)是解决特定问题的求解步骤的⼀种描述是⼀系列解决问题指令的有限序列。算法数据结构程序举例贪吃蛇洗牌算法2算法的特征有穷性确定性可行性输入输出3算法设计的要求正确性可读性健壮性高效率和低存储三、算法的时间复杂度1 如何分析算法的时间效率1.事后统计需要先实现算 法且严重依赖环境。2.事前估算Ci是每条代码语句消耗的时间Ni是每条语句执行的次数。Ci和环境有关一般假设为1。如Summation函数的时间 效率就可以用一个函数 f(N) 1 1 (N1) N N 1 3*N 4 来表示。2时间复杂度渐进表示法*简便方法3时间复杂度经典样例分析例1由于换底公式所以底数不同时量级相同所以底数可以省略。例2例3存在最好和最坏情况存在多种情况这种情况下关注最坏情况递归4空间复杂度渐进表示法和时间复杂度类似我们使用的方法是事前估算跟时间复杂度度分析类似我们关注的是随着问题规模N趋于很大时空间占用的增长量级所以也使用渐进时间复杂度表示找到跟变量个数相关的同阶函数 S(N) O(f(N)) S(N) O(f(N)) O(N) 方法类似找到最高阶项忽略常数和系数等。则Func函数的空间复杂度为S(N) O(f(N)) O(N)。空间复杂度是算法因设计思路所需的额外开辟的空间。若算法在执行过程中额外需要常数级别的额外空间 一般称这样的算法为原地算法。5空间复杂度经典样例分析例一旋转数组可以多看几遍存在最好和最坏情况存在多种情况这种情况下关注最坏情况例二旋转数组以上代码考试可以校招的话需要优化例三旋转数组 最终优化 把时间复杂度和空间复杂度降到最低