数据结构与算法笔记（代码部分）
笔记部分：https://www.jianshu.com/p/773b0850b1aa
1.五子棋中二维数组转稀疏数组代码
public static void main(String[] args) {
int chessArr[][] = new int[11][11]; //首先创建一个11*11的二维数组
chessArr[1][2] = 1;
chessArr[2][3] = 2; 和2分别代表白棋和黑棋
System.out.println("先打印出原始的二维数组");
for(int[] row:chessArr) {
for(int data:row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
//下面我们要开始创建稀疏数组了，先遍历获取到不为零值的个数
int sum = 0; //获取不为零的值的个数
for(int i=0;i<11;i++) {
for(int j=0;j<11;j++) {
if(chessArr[i][j]!=0) {
sum++;
}
}
}
int count = 0; //工具数
int sparseArray[][] = new int[sum+1][3]; //创建稀疏数组
for(int i=0;i<11;i++) {
for(int j=0;j<11;j++) {
if(chessArr[i][j]!=0) {
count++;
sparseArray[count][0] = i; //行数
sparseArray[count][1] = j; //列数
sparseArray[count][2] = chessArr[i][j]; //值
}
}
}
//然后再把二维数组信息存进去
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//下面我们打印出稀疏数组
System.out.println("打印出稀疏数组");
for(int[] row:sparseArray) {
for(int data:row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
2.用数组模拟环形队列代码
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(3); //测试，创建一个队列
boolean loop = true;
Scanner s = new Scanner(System.in);
char a = ' ';
while(loop) {
System.out.println("s：列出队列数据");
System.out.println("a：添加数据到队列");
System.out.println("g：从队列中取出数据");
System.out.println("h：查看队列头的数据");
System.out.println("e：退出程序");
a = s.next().charAt(0); //接收一个字符
switch(a){
case 's':
arrayQueue.listQueue();
break;
case 'a':
System.out.println("输入一个数");
int v = s.nextInt();
arrayQueue.addQueue(v);
break;
case 'g':
arrayQueue.getQueue();
break;
case 'h':
arrayQueue.frontData();
break;
case 'e':
s.close();
loop = false;
System.out.println("退出程序");
}
}
}
private int maxSize; //数组的最大容量
private int front; //队列头,指向队列第一个元素
private int rear; //队列尾，指向队列最后一个元素
private int arr[]; //用于存放数据，模拟队列
//创建队列的构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = 0; //指向队列头部
rear = 0; //指向队列尾部,即数据部位
}
//判断队列是否满
public boolean isFull() {
return (rear+1)%maxSize == front;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//向队列中添加数据
public void addQueue(int n) {
if(isFull()) {
System.out.println("队列已满");
return;
}
arr[rear] = n;
rear = (rear+1)%maxSize;
}
//向队列中获取数据
public int getQueue() {
if(isEmpty()) {
throw new RuntimeException("队列空，不能取数据");
}
int value = arr[front];
front = (front+1)%maxSize;
return value;
}
//获取队列中的所有数据
public void listQueue() {
if(isEmpty()) {
System.out.println("队列为空");
return;
}
for(int i=front;i<front+size();i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//打印出队列的头数据
public int frontData() {
if(isEmpty()) {
System.out.println("数据不存在");
}
return arr[front];
}
//求出当前队列有效数据的个数
public int size() {
return (rear+maxSize-front)%maxSize;
}
