一 线性结构
数据元素之间存在一对一的线性关系
顺序存储结构
顺序表中的存储元素是连续的
链式存储结构
链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
二 非线性结构
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
三 稀疏数组
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
- 记录数组一共有
几行几列，有多少个不同的值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
image.png
image.png
实战
- 使用稀疏数组，来保留类似前面的
二维数组(棋盘、地图等等) - 把稀疏数组
存盘，并且可以从新恢复原来的二维数组数 -
整体思路分析
image.png
思路
二维数组转稀疏数组
- 遍历原始数组，得到
有效数据的个数sum - 创建一个稀疏数组
int[sum+1][3]（如果值只有0，1；则可以省略第三列。第一行可以放默认值,规则自定义）。这里放第一行二维数组的行列数以及sum - 将二维数组的有效数据依次记录
稀疏数组还原二维数组
- 根据第一行
创建一个默认值的二维数组 - 从第二行开始遍历，
还原有效数值
代码
/**
* 获得一个原始二维数组
* @return
*/
public int[][] getOriginArray(){
int[][] origin = new int[10][12];
origin[2][8] = 1;
origin[9][11] = 90;
origin[8][5] = 123;
origin[6][6] = 99;
origin[7][4] = 6;
origin[3][1] = 618;
origin[5][9] = 111;
return origin;
}
/**
* 转换成稀疏数组
* @param origin
* @return
*/
public int[][] tranSparseArray(int[][] origin){
int sum = 0;
int rows = origin.length;
int columns = origin[0].length;
for(int i=0;i<rows;i++){
int[] row= origin[i];
for(int j=0;j<columns;j++){
if(row[j]!=0){
sum++;
}
}
}
int[][] sparseArray = new int[sum+1][3];
sparseArray[0][0] = sum;
sparseArray[0][1] = rows;
sparseArray[0][2] = columns;
int index = 1;
for(int i=0;i<rows;i++){
int[] row= origin[i];
for(int j=0;j<columns;j++){
if(row[j]!=0){
sparseArray[index][0] = i;
sparseArray[index][1] = j;
sparseArray[index][2] = row[j];
index ++;
}
}
}
return sparseArray;
}
/**
* 稀疏数组还原
* @param sparseArray
* @return
*/
public int[][] recovery(int[][] sparseArray){
int rows = sparseArray[0][1];
int columns = sparseArray[0][2];
int[][] orgins = new int[rows][columns];
for(int index=1;index<sparseArray.length;index++){
int row = sparseArray[index][0];
int column = sparseArray[index][1];
int value = sparseArray[index][2];
orgins[row][column] = value;
}
return orgins;
}
工具方法
/**
* 打印二维数组
* @param array
*/
public static void printTwoDimArray(int[][] array){
for(int i = 0;i<array.length;i++){
System.out.print("[");
for(int j=0;j<array[i].length;j++){
System.out.print("\t"+array[i][j]);
}
System.out.println("\t"+"]");
}
}
测试
@Test
public void test() {
int[][] origin = getOriginArray();
ArrayUtils.printTwoDimArray(origin);
System.out.println("-----------");
int[][] sparseArray = tranSparseArray(origin);
ArrayUtils.printTwoDimArray(sparseArray);
System.out.println("-----------");
int[][] recoverys = recovery(sparseArray);
ArrayUtils.printTwoDimArray(recoverys);
}
四 队列
队列是一个有序列表，可以用数组或是链表来实现
遵循先入先出的原则
数组实现
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中
maxSize是该队列的最大容量 - 因为队列的
输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示:
我的定义和图不同，front（rear）指向下一个要取（加）得元素得前一个下标
image.png
思路
- 取数据后，front+1；加数据后，rear+1（
rear总是大于等于front） - 封装一个数据机构
- 当
front=maxSize-1时，队列满了
代码
package com.zyc;
import org.junit.Test;
/**
* @author zhuyc
* @create 2019-07-13 16:25
*/
public class ArrayQueue {
private int front;//下一个坐标就是要取得元素坐标
private int rear;//下一个坐标就是增加元素得坐标
private int maxSize;
private int[] array;
public ArrayQueue(int maxSize){
front = -1;
rear = -1;
this.maxSize = maxSize;
array = new int[maxSize];
}
public boolean isFull(){
return rear == maxSize-1;
}
public boolean isEmpty(){
return front==rear;//一样表示放的都取出来了
}
public void push(int value){
if(isFull()){
throw new RuntimeException("队列已满");
}
array[++rear] = value;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("空队列");
}
return array[++front];
}
public void showValidQueue(){
if(isEmpty()){
System.out.println("空队列");
}else{
for(int i = front;i<rear;i++){
System.out.printf("数组[%d]=%d",i+1,array[i+1]);
}
System.out.println();
}
}
public void showQueue(){
if(isEmpty()){
System.out.println("空队列");
}else{
for(int i = 0;i<maxSize;i++){
System.out.printf("数组[%d]=%d",i,array[i]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("空队列");
}
int index = front +1;
return array[index];
}
}
测试
@org.junit.Test
public void test(){
ArrayQueue queue = new ArrayQueue(10);
queue.push(23);
queue.push(28);
queue.push(1);
queue.push(3);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.head());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
}
数组模拟环形队列
上面的队列的空间是不可复用，下面我们要进行优化
思路分析
- front和rear对maxSize取模后的值范围
[0,maxSize-1]正好是数组的有效下标范围 -
rear-front<maxSize,否则就超出了容量(这样就处理了覆盖的问题) - 取下标时我们需要对
front(rear)取模 - 当front和rear
同时超过maxSize时，作一次重置操作(两者都等于取模后的值，这样可以避免无限增长) - 当maxSize=2的n次方时，可以用
&maxSize-1操作代替取模
代码
package com.zyc;
import org.junit.Test;
/**
* @author zhuyc
* @create 2019-07-13 16:25
*/
public class ArrayQueue {
private int front;//下一个坐标就是要取得元素坐标
private int rear;//下一个坐标就是增加元素得坐标
private int maxSize;
private int[] array;
public ArrayQueue(int maxSize){
front = -1;
rear = -1;
this.maxSize = maxSize;
array = new int[maxSize];
}
public boolean isFull(){
return rear-front==maxSize;
}
public boolean isEmpty(){
return front==rear;//一样表示放的都取出来了
}
public void push(int value){
if(isFull()){
throw new RuntimeException("队列已满");
}
int index = ++rear%maxSize;
array[index] = value;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("空队列");
}
if(front==maxSize){//重置
front = front%maxSize;
rear = rear%maxSize;
}
int index = ++front%maxSize;
return array[index];
}
public void showValidQueue(){
if(isEmpty()){
System.out.println("空队列");
}else{
for(int i = front;i<rear;i++){
int index = (i+1)%maxSize;
System.out.printf("数组[%d]=%d",index,array[index]);
}
System.out.println();
}
}
public void showQueue(){
if(isEmpty()){
System.out.println("空队列");
}else{
for(int i = 0;i<maxSize;i++){
System.out.printf("数组[%d]=%d",i,array[i]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("空队列");
}
int index = (front +1)%maxSize;
return array[index];
}
}
测试
@Test
public void testArrayQueue2(){
ArrayQueue queue = new ArrayQueue(4);
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.head());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
queue.push(5);
queue.push(6);
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
queue.push(7);
queue.push(8);
queue.push(9);
queue.push(10);
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println("-------");
queue.showQueue();
queue.showValidQueue();
System.out.println("-------");
queue.push(11);
System.out.println(queue.pop());
System.out.println("end");
}
