相关连接

• link:https://blog.csdn.net/gulang0309/article/details/88657633
• link:https://www.bilibili.com/video/BV1cx411V7D3/?spm_id_from=333.788.videocard.1
• link:https://www.icourse163.org/course/QDU-1206503801

绪论

数据结构

1. 数据结构是指数据元素之间存在的关系,
2. 数据结构包含三个方面:数据的逻辑结构,数据的存储结构和数据的操作
3. 数据的逻辑结构是指数据元素之间的逻辑关海,可分为三种
   1. 线性结构: 除第一个元素和最后一个元素外,每一个都有且仅有一个前驱元素和一个后继元素
   2. 树结构: 根结点没有前驱结点,其他元素仅有一个前驱结点,所有结点可有0个或多个子结点
   3. 图结构:每个元素可有多个前驱元素和多个后继无素
4. 数据的存储结构,也称物理结构,基本形式有两种:
   1. 线性存续,用一组连续的存储单元依次存放数据
   2. 链式存储,使用若干地址分散的存储单元存储数据,元素之间的关系采用附加信息特别指定.内存数据通常采用指针变量记载前驱或后继元素的存储地址
5. java的基础数据类型有整数类型,浮点数类型,字符类型,布尔类型,引用类型有数组,类和接口
6. 抽像数据类型(Abstract Data Type,ADT)是指一个数学模型以及定在该模型上的一组操作
7. 通常使用抽象数据类型描述 数据 结构,将线性表,树,图等 数据结构分别定义为各抽像数据类型 ,
8. java的接口提供方法声明与方法实现相分离的机制,使实现指定接口的多个类之间表现出共同的行为能力
9. java可通过泛型,实现数据结构算法在数据型类上的抽象

##　算法

1. 算法是一个有穷规则的集合，其规则　确定一人解决某一特定问题的操作序列．
2. 算法的规则满足以下５个特性(其中有穷性和可行性最重要):
   1. 有穷性,操作序列有限
   2. 确定性,在任何条件下算法都只有一条执行路径
   3. 可行性,可实现
   4. 有输入
   5. 有输出
3. 算法的设计目标：
   1. 正确性
   2. 健壮性
   3. 有时间效率(首要考虑因素)
   4. 有空间效率
   5. 可读
4. 算法可以通过自然语言或码代码来描述　，但必须借助程序设计语言来实现
5. 算法与数据结构的关系：算法建立在数据结构基础上，对于数据结构的操作需要算法来描述,算法的设计依赖与数据的逻辑结构，算法的实现依赖于数据的存储结构
6. 算法的本质是：无论多么复杂的算法，都可以分解成一些简单的基本操作运算

算法分析

1. 时间复杂度是指算法的执行时间随问题规模的增长而增长的趋势
2. 通常用大Ｏ表示法来表示时间复杂度的上界(即可坏的情况下)，算法执行耗费时间T(n) = O(f(n))
3. 时间复杂度函数按数量级数递增排列如下：
   1. 常数级别:O(1),比如简单语句
   2. 对数级别:$O(\log_2n)$,指数为２递进循环,二分法（通常底数会被省略写为$O(logn)$
   3. 线性级别: O(n),单层循环
   4. 线性对数级别: $O(n\log_2n)$,双层循环，一层指数递进，另一层执行n次,分治法，快速排序
   5. 平方级:$O(n^2)$，双层循环
   6. 立方级:$O(n^3)$
   7. 指数级:$O(2^n)$，穷举
   8. 阶乘级:$O(n!)$
4. 影响算法时间复杂度的主要因素是：
   1. 数据的规模n
   2. 输入数据的初始分布D,由于输入数据非算法可控，我们通常5
5. 算法的空间代价是指算法执行时所占用的存储空间量，由于输入数据和程序指令所占用的存储空间与算法无关，因此度量算法空间代价的依据为辅助变量占用的存储空间

线性表

线性表是组成元素间具有线性关系的一种线性结构,线性表可以采用顺序存储结构和链式存储结构表示.

顺序表

链表

算法示例

1. 汉诺塔问题