数据结构
数据结构分为线性结构和非线性结构。
线性结构
-
顺序存储
顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。 -
链式存储
链式存储的线性表称为链表，存储元素不一定是连续的，元素节点中存放是数据元素以及相邻元素的地址信息。
常见的线性结构有：数组，队列，链表和栈。
稀疏数组
当一个数组大部分元素是0时，可以使用稀疏数组压缩数据。
一个二维数组：
压缩为系数数组后：
import java.util.Arrays;
public class ArrayUtil {
public static void main(String[] args) {
/**
* 原始二维数组定义
* 11行11列的棋盘，1表示白子，2表示黑子，0表示无子
*/
int[][] chessArr1 = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
chessArr1[4][5] = 2;
printArray(chessArr1);
int sum = 0;
for (int[] ints : chessArr1) {
for (int anInt : ints) {
sum = anInt == 0 ? sum : sum + 1;
}
}
/**
* 压缩为稀疏数组
*/
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
int x = 1;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
sparseArr[x][0] = i;
sparseArr[x][1] = j;
sparseArr[x][2] = chessArr1[i][j];
x++;
}
}
}
printArray(sparseArr);
/**
* 稀疏数组恢复为原始数组
*/
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
printArray(chessArr2);
}
public static void printArray(int[][] array) {
for (int[] row : array) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
### 队列
先入先出
```JAVA
import java.util.Scanner;
public class ArrayQueue {
private int maxSixe;
private int front;//队列头
private int rear;//队列尾
private int[] arr;//存储数据，模拟队列
public ArrayQueue(int arrMaxSize) {
maxSixe = arrMaxSize;
arr = new int[arrMaxSize];
front = -1;
rear = -1;
}
/**
* 判断队列已满
*
* @return
*/
public boolean isFull() {
return rear == maxSixe - 1;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列已满，不能加入数据");
return;
}
rear++;
arr[rear] = n;
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
front++;
return arr[front];
}
/**
* 显示队列数据
*/
public void list() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = front + 1; i <= rear; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
/**
* 闲时是队列的头数据
*
* @return
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front + 1];
}
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(5);
Scanner scanner = new Scanner(System.in);
flag:
while (true) {
System.out.println("l: 显示队列");
System.out.println("e：退出程序");
System.out.println("a：添加数据");
System.out.println("g：取出数据");
System.out.println("h：查看队列头的数据");
char key = scanner.next().charAt(0);
switch (key) {
case 'l':
arrayQueue.list();
break;
case 'e':
scanner.close();
break flag;
case 'a':
System.out.println("请输入一个数字");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
System.out.println("取出的数据是：" + arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
System.out.println("队列头的数据是：" + arrayQueue.headQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
环形队列
import java.util.Scanner;
public class CircleArrayQueue {
private int maxSixe;
private int front;//队列的第一个元素,初始值为0
private int rear;//队列最后一个元素的后一个位置
private int[] arr;//存储数据，模拟队列
public CircleArrayQueue(int arrMaxSize) {
maxSixe = arrMaxSize;
arr = new int[arrMaxSize];
}
/**
* 判断队列已满
* (rear + 1) % maxSixe == front
*
* @return
*/
public boolean isFull() {
return (rear + 1) % maxSixe == front;
}
/**
* 判断队列是否为空
* rear == front
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列已满，不能加入数据");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSixe;
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
int value = arr[front];
front = (front + 1) % maxSixe;
return value;
}
/**
* 显示队列数据
*/
public void list() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = front; i <= front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSixe, arr[i % maxSixe]);
}
}
/**
* 元素个数
*
* @return
*/
public int size() {
return (rear + maxSixe - front) % maxSixe;
}
/**
* 闲时是队列的头数据
*
* @return
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front];
}
public static void main(String[] args) {
CircleArrayQueue queue = new CircleArrayQueue(4); //说明设置4, 其队列的有效数据最大是3
Scanner scanner = new Scanner(System.in);
flag:
while (true) {
System.out.println("l: 显示队列");
System.out.println("e：退出程序");
System.out.println("a：添加数据");
System.out.println("g：取出数据");
System.out.println("h：查看队列头的数据");
char key = scanner.next().charAt(0);
switch (key) {
case 'l':
queue.list();
break;
case 'e':
scanner.close();
break flag;
case 'a':
System.out.println("请输入一个数字");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g':
try {
System.out.println("取出的数据是：" + queue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
System.out.println("队列头的数据是：" + queue.headQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
链表示范代码：
public class LinkedList {
/**
* 先初始化一个头结点，头结点不要动，不存放数据
*/
private HeroNode head = new HeroNode(0, null, null);
public void add(HeroNode node) {
HeroNode tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = node;
}
public void list() {
if (head.next == null) {
System.out.println("链表为空");
}
HeroNode tmp = head;
while (tmp.next != null) {
System.out.println(tmp);
tmp = tmp.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add(new HeroNode(1, "宋江", "及时雨"));
list.add(new HeroNode(2, "卢俊义", "玉麒麟"));
list.add(new HeroNode(3, "吴用", "智多星"));
list.list();
}
}
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 +
'}';
}
}
非线性结构
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
