- 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
- 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。 链式存储的线性表称为链表 ，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
- 线性结构常见的有数组，队列，链表和栈
非线性结构包括:二维数组，多维数组，广义表，树结构，图结构。
当一个数组中大部分元素是0，或者为同一个值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法:
- 记录数组有几行几列，有多少不同的值 。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序规模。
- 遍历原始的二位数组，得到有效数据的个数
sum。 - 根据
sum就可以创建稀疏数组SparseArr int[sum+1][3]。 - 将二维数组的有效数据存入到稀疏数组 。
- 读取第一行，根据第一行数据创建原始二维数组 。
- 继续读取稀疏数组后几行数据，并赋值给原始的二维数组 。
队列是个有序列表，可以用数组或者链表来实现，队列遵循FIFO原则，即先入先出，后入后出
- 若使用数组的结构来存储队列数据，则队列数组的声明如下图，其中
maxSize是该队列的最大容量 。 - 因为队列的输出，输入分别从前后端来处理，因此需要两个变量
front及rear分别记录前后端的下标，front会随着数据输出改变，而rear则随着数据输入而改变 - 将数据存入队列称为
addQueue,addQueue的处理需要两个步骤:
- 将尾指针后移，
rear+1,当front=rear,空 - 若尾指针
rear小于队列最大下标maxSize-1，则将数据存入rear所指的数据元素中，否则无法存入数据。rear == maxSize-1，队列满。
- 代码
- 目前的数组只可使用一次，没有达到复用的效果
- 将这个数组使用算法，改进成一个环形的队列，取模: %
- 对
front变量的含义做调整:front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front初始值为0。 - 对
rear变量的含义做调整:rear指向队列最后一个元素的后一个位置，空出空间作为约定，rear初始值为0 。 - 当队列满时，条件为:
(rear+1)%maxSize=front - 当队列为空的条件:
rear = front - 队列中有效数据的个数
(rear+maxSize-front)%maxSize
链表是有序的列表，在内存中存储方式如下:
- 链表是以节点的方式来存储，是链式存储
- 每个节点包含data域，next域: 指向下一个节点
- 链表的各个节点不一定是连续存储
- 链表分带头节点的链表和不带头节点的链表
- 先创建一个
head头节点，作用为表示链表的头 - 依次添加后续节点到链表最后遍历
- 通过遍历以及辅助变量
temp找到新添加节点的位置 新节点.next = temp.nexttemp.next = 新节点
- 通过遍历找到该节点
- 修改节点信息
- 找到需要删除的节点的前一个节点
temp temp.next = temp.next.next- 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收
单链表缺点分析:
- 单链表只能从一个方向进行查找，双向链表可以前向或者后向进行查找
- 单项链表不能自我删除，需要依靠辅助节点，双向可以自我删除
- 遍历方法与单链表一致，区别:可以前向，也可后向查找
- 添加:默认添加到双向链表最后
- 找到双向链表的最后节点
temp.next = newHeroNodenewHeroNode.pre = temp
- 修改的思路及原理与单向链表一致
- 删除:
- 双向链表可实现自我删除
- 直接定位到待删除节点
temp temp.pre.next = temp.nexttemp.next.pre = temp.pre
Josephu问题:编号为1,2,...,n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的人出列，m的下一位继续从1开始报数。 依次类推，直到所有人出列为止，由此产生一个出列编号的序列。
示例:
- n=5,共有5人
- k=1,从第一人开始报数
- m=2,数两次
- 出队列顺序:
- 2=>4=>1=>5=>3
- 创建一个单向环形链表
- 创建第一个节点，让first指针指向该节点，并形成环形
- 之后每创建一个新节点，就把该节点加入到已有的环形链表即可
- 遍历单向环形链表
- 先让一个辅助指针指向first节点
- 后通过一个while循环遍历该链表即可(
cur.next == first)
- 栈是一个先入先出的有序列表
- 栈是限制线性表中元素的插入与删除只能在线性表同一端进行的一种特殊线性表。允许插入与删除的一段，为变化的一端，称为栈顶(Top),另一端为固定的一端，称为栈底(Bottom)。
- 由栈的特性可知，最先放入栈的元素在栈底，最后放入栈的元素在栈顶。而删除元素恰好相反，最后放入的元素最先删除，最先放入的元素最后删除。
- 子程序的调用:在跳往子程序前，会将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来程序。
- 处理递归调用:与子程序的调用类似，除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值
- 二叉树的遍历
- 图形的深度优先(depth-first)搜索法
- 定义一个
top来表示栈顶，初始化为-1 - 入栈的操作，当有数据加入到栈时，
top++;stack[top] = data - 出栈的操作，
int value = stack[top];top--; return value - 代码
- 通过一个
index值遍历表达式 - 如果是一个数字，就直接入数栈
- 如果是一个符号，分如下情况处理:
- 如果当前的符号栈为空，就直接入栈
- 如果符号符号栈有操作符，就进行比较，如当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，从符号栈中pop出一个符号，进行运算。将得到的结果入数栈，后将当前的符号入符号栈。**
如果当前操作符的优先级大于栈中的操作符**，就直接入符号栈。
- 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号,并运行。
- 最后在数栈只有一个数字，就是表达式的结果。
- 代码: 以栈为底的计算器
- 前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前
- 示例: (3+4)*5-6对应的前缀表达式为-*+3456
- 前缀表达式的计算机求值: 从右到左扫描表达式，遇到数字式时，将数字压入堆栈，遇到运算符时，弹出栈顶两个数，用运算符对他们作相应的运算(栈顶元素和次顶元素) ，将结果入栈。重复上述过程直到到大表达式最左端，最后运算出的值即为表达式的结果。
- 中缀表达式就是最常见的表达式，如(3+4)*5-6
- 人类习惯于中缀表达式，但其不利于计算机操作。因此在计算机运行时会将中缀表达式转换成其他表达式来操作。 一般为后缀表达式。
-
后缀表达式又称逆波兰表达式，与前缀表达式相似,但运算符位于操作数之后
-
示例: (3+4)*5-6对应的后缀表达式为: 34+5*6-
-
后缀表达式的计算机求值: 从左到右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶两个数，用运算符对他们左相应的计算(次顶元素和栈顶元素) ，并将结果入栈;重复上述过程直至表达式最右端，最后运算得出的值即为表达式的结果。
-
示例:
| 正常表达式 | 逆波兰表达式 |
|---|---|
| a+b | ab+ |
| a+(b-c) | abc-+ |
| a+(b-c)*d | abc-d*+ |
| a+d*(b-c) | adbc-*+ |
| a=1+3 | a13+= |
代码: 逆波兰计算器
1. 初始化两个栈，运算符栈`s1`以及存储中间结果的栈`s2`
2. 从左到右扫描中缀表达式
3. 遇到操作数时，将其压入`s2`
4. 遇到运算符时，比较其与`s1`栈顶运算符的优先级
1. 如果`s1`为空，或栈顶运算符为左括号"("，则直接将此运算符入栈;
2. 若优先级比栈顶运算符高，也将运算符压入`s1`
3. 若优先级不高于栈顶运算符，将`s1`栈顶运算符弹出并压入`s2`中，重复上述比较
5. 遇到括号时:
1. 如果左括号"("，则直接压入`s1`
2. 如果是右括号")"，则依次弹出`s1`栈顶运算符，并压入`s2`，直到遇到左括号为止，丢弃括号
6. 重复步骤2-5，直到表达式最右端。
7. 将`s1`剩余运算符依次弹出并压入`s2`
8. 依次弹出`s2`中元素并输出，结果的逆序为重缀表达式的后缀表达式
9. 代码: [中缀表达式转后缀表达式](src/com/yijie/stack/ReversePolishNotation.java)
递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题。同时可以让代码变得简洁。
- 当程序执行到一个方法时，就会开辟一个独立的空间。（栈）
- 每个空间的数据（局部变量）是独立的，不会相互影响
- 如果方法中使用的是引用类型变量（如数组），就会共享该引用类型的数据。
- 递归必须向退出条件逼近，否则会无限递归，出现
StackOverFlowError - 当一个方法执行完毕，或者遇到
return，就会返回，遵守谁调用将结果返回给谁的原则。同时，当方法执行完毕或者返回时，该方法也执行完毕。
代码: 迷宫问题代码
八皇后问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出： 在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以编程解决此问题。
- 第一个皇后放第一行第一列
- 第二个皇后放在第二行第一列，判断是否符合条件。如果不符合，继续放到第二行第二列，第三列...直至第二个皇后处于符合条件的位置上
- 将第三个皇后置于第三行第一列，第二列...依次判断是否符合条件，直至其处于符合条件位置上。重复同样的步骤，直至第八个皇后处于正确位置。
- 当取得第一个正确解时，当栈回退到上一个栈时，就会开始回溯。即获取当第一个皇后处于第一列时的所有正确解。
- 将第一个皇后置于第一行第二列，重复执行步骤1至4，
排序也称排序算法，是将一组数据按照指定的顺序进行排列的过程。
- 内部排序:指将需要排序的数据加载到内部存储器中进行排序。
- 外部排序:数据量过大，无法全部加载到内存中，他需要借助外部存储进行排序。
- 事后统计的方法: 该方法可行，但面临两个问题:
- 需要实际运行该程序
- 所得时间的统计量依赖于计算机硬件，软件等环境因素
- 事先估计的方法: 通过计算算法的时间复杂度来判断算法的优劣
时间频度(Temporal Frequency): 一个算法所需时间与算法中语句执行的次数成正比。算法中语句执行次数多，花费时间就多。算法中语句执行次数称为语句频度或时间频度，记为T(n)。
计算1-100之间所有数之和，设计两种算法:
- 使用for循环，T(n) = n + 1 :
int total=0;
int end=100;
for(i=0;i<end; i++){
total+=i;- 直接计算，T(n) = 1:
int total=0;
int end=100;
total=(1+end)*end/2随着n的变大时间频度有3个特点(3种可以忽略的项):
- 常数项可忽略
- 低次项可忽略
- 高次项系数可忽略
- 一般情况下，算法的时间频度是问题规模n的某个函数, 用T(n)表示。 若有某辅助函数f(n)，使得n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，记作T(n)=O(f(n)), O(f(n)) 为算法的渐进时间复杂度, 简称时间复杂度。
- T(n)不同，但时间复杂度可能相同。
- 计算时间复杂度的方法:
- 用常数1代替所有常数
- 只保留最高阶项
- 去除最高阶项的系数
- 常见的时间复杂度，由小到大排列如下。随着n的不断增大, 算法的执行效率会随时间复杂度的不断增大而越来越低。
- 常数阶O(1)
- 对数阶O(log2n)
- 线性阶O(n)
- 线性对数阶O(nlog2n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^k)
- 指数阶O(2^n)
- 平均时间复杂度是指，所有输入实例等概率出现情况下，该算法的运行时间。
- 最坏情况下时间复杂度称为最坏时间复杂度，一般讨论的时间复杂度均为最坏时间复杂度。最坏时间复杂度确定了算法在任何输入实例上运行时间的上限，保证了算法运行时间不会比最坏情况更长。
- 平均时间复杂度与最坏时间复杂度是否一致，取决于算法。
- 一个算法的空间复杂度定义为算法所耗费的存储空间，是问题规模n的函数。
- 算法的空间复杂度是一个对算法在运行过程中临时占用存储空间大小的量度。
- 在做算法分析时，主要讨论的是时间复杂度。从用户体验角度，更看重程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)的本质即为空间换时间。
对待排序数列从前向后，依次比较相邻元素的值。若发现逆序则交换，使值较大的元素向后移动。重复遍历要排序的数列，直至数列排序已完成。
- 优化: 冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。
选择排序是一种简单的排序方法。它的基本思想是，第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换。第二次从arr[1]-arr[n-1]选取最小值，与arr[1]交换。第三次...
第i次从arr[i-1]-arr[n-1]选取最小值，与arr[i-1]交换...第n-1次从arr[n-2]-arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
把n个待排序的元素看作一个有序表和一个无序表。开始时有序表值包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出一个元素，插入到有序表的相应位置。
希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。 希尔排序先将整个待排序的序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
快速排序的基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，使整个数据变成有序序列。
归并排序(Merge Sort)是利用归并思想实现的排序方法。该算法采用经典的分治策略(divide and conquer)，将问题分(divide)成小问题递归求解，在治(conquer)阶段则将分阶段得到的各答案修补在一起，分而治之。
- 基数排序(Radix Sort)属于分配式排序，又称桶子法或bin sort，顾名思义，它是通过键值各个位的值，将要排序的元素分配到某些桶中，达到排序的作用。
- 基数排序法属于稳定性的排序，基数排序法是效率高的稳定性排序法。
- 基数排序是桶排序的扩展。
- 基数排序的实现:将整数按位数切割成不同的数字，然后按每个位数分别比较。
- 基数排序是经典的空间换时间的方式，占用空间很大，当对海量数据排序时，容易造成OutOfMemoryError。
- 稳定: 如果a原本位于b之前且a=b，排序之后a仍然在b之前
- 不稳定: 如果a原本位于b之前且a=b，排序之后a可能出现在b之后
- 内排序: 所有排序过程都在内存中完成
- 外排序: 由于数据量过大，因此把数据存入磁盘中，排序需通过磁盘和内存间的数据传输才能进行。
- 时间复杂度: 一个算法执行所耗费的时间。
- 空间复杂度: 运行一个程序所需内存的大小。
- n: 数据规模
- k: "桶"的个数
- In-place: 不占用额外内存
- Out-place: 占用额外内存
线性查找或顺序查找是搜索某一特定值的搜索算法。线性查找按一定顺序检查数组中每一个元素，直到找到索要搜寻的特定值为止。
二分查找的思路:
- 首先确定该数组中间值的下标:
mid = (left + right) / 2 - 然后比较待查找数
findVal与arr[mid]findVal > arr[mid]递归向右查找findVal < arr[mid]递归向左查找findVal == arr[mid]找到待查数，返回
- 递归完整个数组，仍未找到
findVal，结束递归 (left > right)
哈希表，也称散列表，是根据关键码值直接进行访问的数据结构。哈希表通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫散列表。
- 优点: 通过下标方式访问元素，速度快。对于有序数组，可使用二分查找提高检索速度。
- 缺点: 如果要检索具体值或插入值，会整体移动，效率较低
- 优点: 在一定程度上对数组存储方式有优化(如:插入某数值，只需将该数值链接到链表中即可，删除效率也较高)
- 缺点: 进行检索时效率较低，需从头节点开始遍历
提高数据存储及读取效率，如利用二叉排序树，即可保证数据检索速度，也可保证数据的插入，删除和修改速度。
- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点(没有子节点的节点)
- 节点的权(节点值)
- 路径(从root节点找到该节点的路线)
- 层
- 子树
- 树的高度(最大层数)
- 森林(多颗子树都成森林)
- 创建二叉树
- 前序遍历
- 输出当前节点(初始root节点)
- 如果左子节点不为空，递归前序遍历
- 如果右子节点不为空，递归前序遍历
- 中序遍历
- 如果当前节点左子节点不为空，递归中序遍历
- 输出当前节点(root节点)
- 如果当前节点的右子节点不为空，递归中序遍历
- 后序遍历
- 如果当前节点左子节点不为空，递归后序遍历
- 如果当前节点的右子节点不为空，递归后序遍历
- 输出当前节点(root节点)
- 前序查找
- 判断当前节点的no是否等于待查找值，若相等，返回，若不相等:
- 如果左子节点不为空，递归前序查找，若找到节点，返回，若未找到:
- 如果右子节点不为空，递归前序查找
- 中序查找
- 如果左子节点不为空，递归中序查找，若找到节点，返回，若未找到:
- 判断当前节点的no是否等于待查找值，若相等，返回，若不相等:
- 如果右子节点不为空，递归中序查找
- 后序查找
- 如果右子节点不为空，递归后序查找，若找到节点，返回，若未找到:
- 如果右子节点不为空，递归后序查找，若找到节点，返回，若未找到:
- 判断当前节点的no是否等于待查找值，若相等，返回，若不相等，返回
null
- 若待删除的节点是叶子节点，则删除该节点
- 若待删除的节点是非叶子节点，则删除该子树
考虑: 如果树为空树，只有root节点，将二叉树置空。
- 由于二叉树是单向的，因而需判断当前节点的子节点是否需要删除节点，而非判断当前节点是否为待删除节点。
- 若当前节点左子节点不为空，且为待删除节点，
this.left = null，返回 - 若当前节点右子节点不为空，且为待删除节点，
this.right = null，返回 - 若第二三步没有删除节点，则向左子树进行递归删除
- 若第四步未删除节点，向右子树进行递归删除
- 堆排序是利用堆这种数据结构而设计的一种排序算法。堆排序是一种选择排序，其最好，最坏，平均时间复杂度均为O(nlogn)，它是不稳定排序。
- 堆是完全二叉树且具有如下性质:
- 每个节点的值都大于等于其左右子节点的值，称为大顶堆。
- 每个节点的值都小于等于其左右子节点的值，称为小顶堆。
- 将待排序序列构成一个大顶堆
Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Corresponding Complete Binary Tree is:
1 3 5 / \ / \ 4 6 13 10 / \ / \ 9 8 15 17The task to build a Max-Heap from above array.
Total Nodes = 11.
Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.
To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.
Heapify 6: Swap 6 and 17.
1 / \ 3 5 / \ / \ 4 17 13 10 / \ / \ 9 8 15 6Heapify 4: Swap 4 and 9.
1 / \ 3 5 / \ / \ 9 17 13 10 / \ / \ 4 8 15 6Heapify 5: Swap 13 and 5.
1 / \ 3 13 / \ / \ 9 17 5 10 / \ / \ 4 8 15 6Heapify 3: First Swap 3 and 17, again swap 3 and 15.
1 / \ 17 13 / \ / \ 9 15 5 10 / \ / \ 4 8 3 6Heapify 1: First Swap 1 and 17, again swap 1 and 15, finally swap 1 and 6.
17 / \ 15 13 / \ / \ 9 6 5 10 / \ / \ 4 8 3 1
- 此时整个序列的最大值为堆顶根节点
- 将其与末尾元素进行交换，此时末尾元素即为最大值
- 后将剩余n-1个元素重新构造堆，重复步骤三，得到n-1元素的最大值
- 重复执行步骤三四，得到有序序列