稀疏数组：
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
二维数组转稀缺数组：
- 遍历原始的二维数组，得到有效数据个数sum;
- 根据Sum 创建sparsearray数组
- 遍历二维数组，将非0值存放到sparsearray中（用count记录一下第n个非0值）
//二维数组转稀疏数组sparsearray
//1.记录有效值
int sum=0;//
for (int arr[]:array)
for (int data:arr)
if (data!=0){
sum++;
}
System.out.println(sum);
//2.建立sparsearray数组
int[][] spaersearry=new int[sum+1][3];
spaersearry[0][0]=11;
spaersearry[0][1]=11;
spaersearry[0][2]=sum;
//3.遍历二维数组，将非0值存放到sparsearray中
int count=0;//记录第n个非0值
for (int i=0;i<11;i++)
for(int j=0;j<11;j++)
if(array[i][j]!=0){
count++;
spaersearry[count][0]=i;
spaersearry[count][1]=j;
spaersearry[count][2]=array[i][j];
}
for (int i=0;i<spaersearry.length;i++)
System.out.println(spaersearry[i][0]+" "+spaersearry[i][1]+" "+spaersearry[i][2]);
稀缺数组转二维数组
- 先读取稀缺数组的第一行，根据第一行的数据，创建原始的二维数组。
- 读取稀缺数组后几行的数据，赋值给原始的二维数组。
//将原始数组还原。
int array2[][]=new int[spaersearry[0][0]][spaersearry[0][1]];
//读取稀缺数组后几行的数据，赋值给原始的二维数组。
for(int i=1;i<spaersearry.length;i++){
array2[spaersearry[i][0]][spaersearry[i][1]]=spaersearry[i][2];
}
for(int arr[]:array2) {
for (int data : arr) {
System.out.print(data);
}
System.out.println();
}
队列：
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出。
思想：rear（上端，尾部）控制输入，front（下端，头部）控制输出，从而实现先进先出。
数组实现队列：
-
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 maxSize是该队列的最大容量。
-
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front 及 rear分别记录队列前后端的下标，
front会随着数据输出而改变，而rear 则是随着数据输入而改变，如图所示:
-
当我们将数据存入队列时需要有两个步骤:
-
将尾指针往后移:rear+1 ，当front ==rear时为【空队列】
-
若尾指针rear小于队列的最大下标 maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear== maxSize-1 【队列满】
-
-
代码实现：
public class Queue {
int maxSize;//表示队列的长度
int front;//队列头
int rear;//队列尾
int[] arr; //模拟队列
//创建队列
public Queue(int maxSize){
this.maxSize=maxSize;
arr=new int[maxSize];
front=-1;//指向队列头部，front指向队列头的前一个位置
rear=-1; //指向队列尾，指向队列最后一个数据
}
//判断队列是否为空
public boolean isEmpty(){
if (front==rear)
return true;
else
return false;
}
//判断队列是否已满
public boolean isFull(){
if (rear==maxSize-1)
return true;
else
return false;
}
//入队
public void addQueue(int data){
if(isFull()){
System.out.println("队列已满");
}else {
rear++;
arr[rear]=data;
}
}
//出队
public int getQueue(){
if(isEmpty())
throw new RuntimeException("队列为空");
front++;
return arr[front];
}
//遍历所有数据
public void showQueue(){
if (isEmpty()){
System.out.println("数据为空");
return;
}
for (int i=0;i<arr.length;i++){
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
//显示头元素
public int getFront(){
return arr[front+1];
}
}
问题分析并优化
上面代码实现完成后运行，会发现添加输入后取出，取出的位置不能再进行添加了，也就是添加完取出就不能再用了，没达到复用的效果
-
目前数组使用一次就不能用，没有达到复用的效果
-
将这个数组使用算法，改进成一个环形的队列取模:%
数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组，因此将数组看作一个环形的。（通过取模来实现）即当front上移时，rear可以将front 曾指向的位置填满。
分析：
- 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(rear + 1 ) % maxSize == front 满
- rear == front[空]
思路如下：
- front 变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0。
- rear做一个调整：rear指向队列的最后一个元素后一个位置（空出一个空间作为约定）初始值=0。
- 当队列满的时候，条件是（rear+1) % maxSize=front【满】
- 对队列为空的条件，rear==front 空
- 队列中的有效个数为（rear-front+maxSize)%maxSize 【防止出现rear=1 front=0 即尾指针跑到头部的出现负数情况。
注意：申请长度时应多申一位，因为rear指向的是当前值的下一个位置，因此要多申请一位。
代码实现：
public class CircleQueue {
int maxSize;
int front;
int rear;
int arr[];
public CircleQueue(int maxSize){
this.maxSize=maxSize;
arr=new int[maxSize];
}
public boolean isEmpty(){
return front==rear;
}
public boolean isFull(){
return (rear+1)%maxSize==front;
}
public void addQueue(int data) {
if (isFull()){
System.out.println("队列满");
return;
}
arr[rear] = data;
System.out.println("rear: "+rear);
rear = (rear + 1) % maxSize;
}
public int getQueue(){
if (isFull()){
throw new RuntimeException();
}
int value=arr[front];
front=(front+1)%maxSize;
return value;
}
public void showQueue(){
if (isEmpty()){
System.out.println("空队列");
}else {
for (int i=front;i<front+(rear+maxSize-front)%maxSize;i++){
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
}
//显示头元素
public int getFront(){
return arr[front];
}
//获取有效个数
public int getSum(){
return (rear-front+maxSize)%maxSize;
}
}
栈（stack）
-
栈是一个先进后出的有序列表。
-
栈是限制线性表中元素插入和删除只能在同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端，称为栈顶，固定的一段称为栈底。
-
数组模拟入栈出栈：
1. 定义一个数组来模拟栈。
2. 定义一个top来表示栈顶。
3. 入栈的操作，当有数据加入到栈时，top++；stack[top]=data;
4. 出栈的操作，int value=stack[top];top--;
5. 实战分析，多位数字的复合运算
1. 将数组跟操作符分别放入栈中。
2. 数字直接入栈。
3. 创建方法 1.判断为字符为数字还是操作符。2.规定操作符的优先级。3. 计算方法注意减法跟除法的顺序
4. 操作符需要提前比较一下，若为空栈，则直接入栈。否则需要与栈顶元素比较，若优先级等于或者小于栈顶元素，则把栈顶操作符取出，并在数字栈取出两元素进行计算（减法除法时注意顺序，后取出的减先取出的）计算完后将新元素、新操作符入栈。
5. 多位运算时，采用字符串拼接法：
6. 规定一个字符串进行拼接 String +=char
7. 判断是否为最后一个元素 i<demo.length(); 是则直接入栈
8. 否则，则进行下一个判断，下一个元素是否为字符，是则入栈，并将字符串制空 String=""; 否则不做处理。
```java
public class Stack {
public static void main(String[] args) {
//用栈来处理复合运算
//1.数字直接入栈
//2.操作符需要提前比较一下，若为栈空，则直接入栈，否则需要比较一下，若优先级等于或者小于，
// 则将栈内操作符出来计算，然后入栈，否则直接入栈（操作符优先级大的先计算）
String demo="3+7*2/2-10";
//存放数字
ArrayStack numberStack=new ArrayStack(10);
//存放符号
ArrayStack charStack=new ArrayStack(10);
//存放多为数字
String numbers="";
//扫描字符串 数字则入栈，字符另作处理
for (int i=0;i<demo.length();i++) {
char s = demo.substring(i, i + 1).charAt(0);
//首先判断字符为数字还是操作符
if (isNumber(s)){
//如果栈为空则直接放入
if(charStack.isEmpty()){
charStack.addStack(s);
}else {
//判断栈顶与此操作符的优先级
if(operator(s)>operator(charStack.showTop())){
//此操作符优先级大于栈顶入栈
charStack.addStack(s);
}else {
//此操作符小于等于栈顶则拿出计算后入栈 "3+7*2/2-1"
int value1=numberStack.getStack();//2
int value2=numberStack.getStack();//7
numberStack.addStack(count(value1,value2,charStack.getStack()));
//新操作符入栈
charStack.addStack(s); }
}
}else{
//31+2
numbers+=s;
if (i==demo.length()-1){
numberStack.addStack(Integer.parseInt(numbers));
}else {
if(isNumber(demo.substring(i+1,i+2).charAt(0))){
numberStack.addStack(Integer.parseInt(numbers));
numbers="";
System.out.println(numberStack.showTop());
}
}
}
}
//经过for循环处理后的运算符只有加减，从顶一次计算，计算完再入栈与下一个元素计算依次循环。
System.out.println(numberStack.showTop());
while (true){
if(numberStack.isEmpty()||charStack.isEmpty())break;
else {
numberStack.addStack(count(numberStack.getStack(),numberStack.getStack(),charStack.getStack()));
}
}
System.out.println("计算完成："+numberStack.showTop());
}
//判断切割的字符为数字还是符号
public static boolean isNumber(char s){
return s=='+'||s=='-'||s=='/'||s=='*';
}
//判断操作符的优先级
public static int operator(int s){
if (s=='+'||s=='-')
return 1;
else
return 2;
}
//负责计算
public static int count(int value1,int value2,int operator){
int res=0;
switch(operator){
case '+':
res=value1+value2;
break;
case '-':
res=value2-value1;
break;
case '*':
res=value1*value2;
break;
case '/':
res=value2/value1;
break;
}
return res;
}
}
//数组模拟栈
class ArrayStack{
int nums;
int []stack;
int top=-1;
ArrayStack(int nums){
this.nums=nums;
stack=new int[nums];
}
//判断栈空
public boolean isEmpty(){
if (top==-1)
return true;
else
return false;
}
//入栈
public void addStack(int data){
top++;
stack[top]=data;
}
//出栈
public int getStack(){
int value=stack[top];
top--;
return value;
}
//显示栈顶元素
public int showTop(){
return stack[top];
}
//遍历
public void showStack(){
for (int i=0;i<nums;i++)
System.out.println(stack[i]);
}
}
```
### **逆波兰表达式：**
后缀表达式，操作符的优先级已经划分完成，只创建一个数字栈，将两个元素计算完放入栈中即可。
例如（3+4）X5 -6 对应的后缀表达式为：3 4 + 5 X 6 -
1. 从左到右扫描，将3和4压入栈中。
2. 遇到+运算符，取出4和3，计算，将结果放入栈中 依次进行...
### **中缀表达式变后缀表达式：**
步骤如下：
1. 初始化两个栈：运算符栈s1 和存储中间结果的栈s2。
2. 从左到右扫描中缀表达式。
3. 遇到操作数压入s2中。
4. 遇到运算符时，比较其与s1栈顶运算符的优先级。
1. 如果s1为空，或栈顶运算符为左括号 "("，则直接将此运算符入栈。
2. 否则，若优先级比栈顶元素优先级高，也将运算符压入s1。
3. 若优先级比栈顶元素低，则将s1栈顶的运算符压入到s2中，再次与新栈顶的元素比较。
2. 遇到括号：
1. 如果为左括号"(''，则直接压入s1。
2. 如果是右括号")"，则依次弹出s1栈顶的元素，并压入s2，直到遇见左括号"("。
3. 当表达式遍历到最右端，将s1中剩余的运算符依次弹出并压入s2。
4. 依次弹出s2中的元素并输出，结果的逆序即位中缀表达式对应的后缀表达式。
**总结：**创建两个栈，数字直接放入s2中，运算符放入s1中，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
链表
单向链表
-
链表是有序的列表，它在内存中的存储如下图
- 链表是以节点（对象）的方式来存储，是链式存储。
- 每个节点包含data域，next域：下一个节点。
- 链表的各个节点不一定是连续存储。
- 链表分带头节点的链表和没有头节点的链表。
-
单链表（带头节点）的逻辑结构示意图如下：
-
单链表代码逻辑：
-
增（直接添加到尾部）
- 通过辅助变量遍历整个链表找到尾指针。
- 将新节点插到尾节点上。
-
插入
-
1. 通过辅助变量找到要插入的位置。
2. 先处理新节点的下一个节点，新节点.next=temp.next。
3. 再将新节点插入，temp.next=新节点。
-
改
- 通过辅助变量找到该节点。
- 将该节点的信息修改。
-
删
1. 通过辅助变量找到该节点（temp.next）。
2. 该节点的前一个节点指向该节点的下一个节点即可(temp.next==temp.next.next)
-
代码演示：
public class LinkedList { public static void main(String[] args) { HeroNode node = new HeroNode(1, "s1", "ss1"); HeroNode node1 = new HeroNode(2, "s2", "ss2"); HeroNode node2 = new HeroNode(3, "s3", "ss3"); HeroNode node3 = new HeroNode(4, "s4", "ss4"); HeroNode node6 = new HeroNode(7, "s7", "ss7"); SingleLinkedList list=new SingleLinkedList(); list.insertLinkedList(node); list.insertLinkedList(node2); list.insertLinkedList(node1); list.showLinkedList(); } } class SingleLinkedList{ //先初始化一个头节点 private HeroNode headNode=new HeroNode(0,"",""); //在链表尾部添加,即在当前节点中 利用next存放下一个节点 public void addLinkedList(HeroNode node){ //使用一个辅助节点来遍历链表找到尾节点 HeroNode temp=headNode; //找到尾节点，在尾节点的next域存放新节点即可 while (true){ if(temp.next==null) break; //temp后移继续遍历 temp=temp.next; } //此时temp.next为空，即是尾节点插入即可 temp.next=node; } //根据排名进行插入 public void insertLinkedList(HeroNode node){ //思路：1.通过辅助变量（指针）找到新添加节点的位置 HeroNode temp=headNode; //判断一下编号是否重复，重复则丢弃 boolean flag=false; while (true){ if (temp.next==null){ break; } else if (temp.next.no>node.no){ break; }else if (temp.next.no==node.no){ flag=true; break; } temp=temp.next; } if (flag){ System.out.println("编号已存在"); }else{ //temp为符合的节点，应在此添加新节点，并处理新节点的下一个节点 //2. 先将新节点的下一个节点连接 node.next=temp.next; //3. 然后将新节点加入 temp.next=node; } } //修改 public void updataLinkedList(HeroNode node){ //1.先找到该节点的位置 HeroNode temp=headNode; //判断是否找到 boolean flag=false; while (true){ if (temp.next==null){ break; }else if(temp.next.no==node.no){ flag=true; break; } temp=temp.next; } //此时temp.next为要找的节点 if(flag){ temp.next.name=node.name; temp.next.nickname=node.nickname; }else System.out.println("未找到此编号"); } //删除 public void deleteLinkedList(int no){ //与修改类似，找到要删除的节点 HeroNode temp=headNode; boolean flag=false;//标记是否找到 while (true){ if (temp.next==null){ break; }else if(temp.next.no==no){ flag=true; break; } temp=temp.next; } //temp.next为要删除的节点 if(flag){ temp.next=temp.next.next; }else System.out.println("未找到"); } //显示 public void showLinkedList(){ //设置一个辅助变量（指针）来遍历 HeroNode temp=headNode; if (headNode.next==null){ System.out.println("空列表"); return; } while (true){ if (temp==null){ break; }else System.out.println(temp); temp=temp.next; } } } class HeroNode{ public int no; public String name; public String nickname; public HeroNode next;//指向下一个节点 public HeroNode (int no,String name, String nickname){ this.no=no; this.name=name; this.nickname=nickname; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + ", next=" + next + '}'; } }
双向链表
单向链表的缺点：
-
单向链表查找时，只能是一个方向，而双向链表则可以前后查找。
-
单向链表不能自我删除，需要依靠辅助节点，双向链表可以自我删除。
1. 遍历方法跟单链表一样，只是可以向前，页可以向后查找。
2. 添加（默认添加到双向链表的最后）
1. 找到最后节点
2. temp.next=newNode;
3. newNode.pre=temp;
3. 修改，与单链表一致。
4. 删除，由于是双向链表，因此可以实现自我删除某个节点。
1. 找到要删除的节点，如temp。
2. 将本节点覆盖掉，temp.pre.next=temp.next。
3. 将覆盖后的节点与上一个节点连接，temp.next.pre=temp.pre。
### 环形链表
1. 原理，尾部节点的next指向头部节点。
2. 实现：
1. 设置一个头节点指向第一个小孩。
-
设置一个辅助节点，让辅助节点指向头节点，然后把头节点的next赋值（对象引用），辅助节点依次往后移动。
-
当前节点设置下一个节点为头节点。
-
//使用for循环来创建环形链表 for (int i = 1;i <= nums;i ++){ //根据编号，创建小孩节点 Boy boy = new Boy(i); //如果是第一个小孩 if (i == 1){ first = boy; first.setNext(first);//构成环状 curBoy = first;//让curBoy指向第一个小孩 }else { curBoy.setNext(boy);//前面的指向新来的小孩 boy.setNext(first);//新添加的小孩指向开头，构成环形 curBoy = boy;//后移 } }
-
约瑟夫环问题：
- 创建环形链表如上图。遍历时需要一个辅助变量curBoy指向first 通过while()当curBoy.next=first时跳出。
- 根据输出生成环状若：n=5(总人数) k=2 (从第二个人开始数) m=3(数到3出圈)
- 创建辅助指针helper指向尾部节点(靠尾指针进行删除即出圈操作) 可在while中进行helper=helper.next 当helper.next=first时跳出。
- 当小孩报数前，将first指向开始报数的小孩，即first跟helper向前移动k-1次。
- 小孩开始报数时，first跟helper向前移动m-1次，此时first指向的为要出圈的小孩，此时 first=first.next ; helper.next=first;