数据结构理论知识

稀疏数组

二维数组转稀疏数组的思路

1. 遍历原始二维数组，得到有效数据的个数sum

2. 根据sum可以创建稀疏数组

sparseArr[sum+1][3] 稀疏数组行不定 列固定3列
    
row col val

1. 将二维数组有效数据存储到稀疏数组

稀疏数组转原始的二维数组的思路

1. 先读取稀疏数组第一行，根据第一行的数据，创建原始的二维数组

2. 接着再读取稀疏数组后面几行的数据，并赋给原始的二维数组即可

牢记int用throw new RuntimeException, void 用打印异常信息

类型为void时，使用return退出程序

链表

单链表

1. 先创建一个头结点，作用是表示单链表的头

2. 后面我们每添加一个结点，就直接加入到链表的后面

需要按照编号的顺序添加

1. 首先找到新添加的节点的位置，是通过辅助变量，通过遍历来搞定

2. 新的节点.next=temp.next

3. 将temp.next=新的节点

链表是以节点的方式来存储，是链式存储

每个节点包含data域，next域：指向下一个节点

链表的各个节点不一定是连续存储

对于单向链表增加删除通常设置临时变量temp=head

对于双向链表删除设置临时变量temp=head.next

单向环形链表

1. 先创建第一个节点，让first指向该节点，并形成环形

2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可

遍历环形链表

1. 先让一个辅助指针（变量）curBoy，指向first节点

2. 然后通过一个while循环遍历该环形链表即可 curBoy.next==first结束

栈 

使用栈完成表达式的计算思路

1. 通过一个index值（索引），来遍历我们的表达式

2. 如果我们发现是一个数字，就直接入数栈

3. 如果发现扫描到是一个符号，分情况如下：

   • 如果发现当前的符号栈为空，就直接入栈

   • 如果符号栈中有符号，就进行比较；如果当前的符号优先级小于或等于栈中符号，就需要从数栈中pop出两个数，从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的符号入符号栈；如果当前符号的优先级大于栈中符号，则直接入栈

4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行

5. 最后在数栈只有一个数字，就是表达式的结果

验证3+2*6-2

后缀表达式

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的运算，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

正则表达式："\\d+"代表多位数

中缀表达式转换为后缀表达式

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2

2. 从左到右扫描中缀表达式

3. 遇到操作数时，压入s2

4. 遇到运算符时，比较s1栈顶运算符的优先级

   • 如果s1为空，或者s1栈顶为左括号，则直接将该运算符入栈

   • 如果该运算符优先级大于s1栈顶运算符优先级，则直接将该运算符入栈

   • 否则，将s1栈顶运算符弹出并压入s2栈中，再次回到步骤4起点判断

5. 遇到括号时，

   • 如果是左括号，则直接压入s1栈

   • 如果是右括号，则依次弹出s1栈顶的运算符，并压入到s2栈中，直到遇到左括号为止，这对括号便不存在了

6. 一直重复步骤2到5直到表达式结束

7. 将s1中剩余的运算符依次弹出并压入s2

8. 依次弹出s2中的元素并输出，结果的逆序即为后缀表达式

递归调用规则

1. 当程序执行到一个方法时，就会开辟一个独立的空间（栈）

2. 每个空间的数据（局部变量），是独立的

八皇后问题（7k7k小游戏）

一维数组解决问题：arr[8]={0,4,7,5,2,6,1,3}//对应arr下标 表示第几行，即第几个皇后，arr[i]=val,表示第i+1个皇后，放在第i+1行的第val+1列

内部排序

内部排序

1. 冒泡排序（比较相邻位置）稳定

2. 选择排序（比较所有数）最小值 最小值索引 不稳定

3. 直接插入排序 插入值 插入索引 稳定

4. 希尔排序 数组长度/2=步长 比较步长之间的数 不稳定

5. 快速排序 找到一个基准arr【（0+arr.length-1)/2】小于等于放在基准左边，大于等于放在基准右边 不稳定

6. 归并排序 找到mid=（0+arr.length-1)/2 分解递归后接着合并 稳定

7. 基数排序 稳定

   • 第一轮排序

   • 将每个元素的个位数取出来，然后看这个数应该放在哪个一维数组

   • 按照一维数组的下标依次取出数据，放入原来数组

   • 第二轮排序

   • 将每个元素的十位数取出来，然后看这个数应该放在哪个一维数组

   • 按照一维数组的下标依次取出数据，放入原来数组

   • 第三轮排序

   • 将每个元素的百位数取出来，然后看这个数应该放在哪个一维数组

   • 按照一维数组的下标依次取出数据，放入原来数组

   • 直到每个元素的n位数取出来都是0时即为排序后的数组

查找

1. 顺序查找（线性查找）

2. 二分查找/折半查找

3. 插值查找

   int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
   注意事项，
   1.对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
   2.关键字分布不均匀的话，不一定比二分查找好

4. 斐波那契查找