发布日期: 2021-04-09

数据结构

线性结构

数据元素之间存在一对一的线性关系。

线性结构有两种不同的存储方式

线性结构常见的有：数组（稀疏数组、）、队列（单向队列，环形队列）、链表（单链表、环形链表、双链表）、栈

顺序存储方式

顺序存储的线性表称为顺序表，顺序表中存储的元素的连续的（内存分配的地址）如数组。

稀疏数组示例 围棋棋盘（二维数组转换为稀疏数组，稀疏数组转换为棋盘）

```
public class TestOne {
    @Test
    //将棋盘二维数组转换为稀疏数组
    public void test1(){
        //1.创建棋盘数组
        int[][] arr1 = new int[11][11];
        //白子(1)：2行3列
        //黑子(2)：3行4列
        arr1[1][2] = 1;
        arr1[2][3] = 2;
        //2.创建稀疏数组
        //row col value
        // 11 11    2
        //2.1遍历求得棋盘中棋子的数量
        int sum = 0;
        System.out.println("原始棋盘");
        for(int[] arr:arr1){
            for(int a:arr){
                System.out.printf("%d\t",a);
                if(a!=0){
                    sum++;
                }
            }
            System.out.println();
        }
        System.out.println("棋盘中棋子的数量"+sum);
        int[][] xs = new int[sum+1][3];
        /**
         * row col value
         * 11  11  2
         * 1   2   1
         * 2   3   2
         */
        xs[0][0] = 11;
        xs[0][1] = 11;
        xs[0][2] = sum;
        int z = 0;
        //生成稀疏数组
        for(int i = 0;i<11;i++){
            for(int j = 0;j<11;j++){
                if(arr1[i][j]!=0){
//                    System.out.println(i);
//                    System.out.println(j);
                    z++;
                    xs[z][0] = i;
                    xs[z][1] = j;
                    xs[z][2] = arr1[i][j];
                }

            }
        }

//        xs[1][0] = 1;
//        xs[1][1] = 2;
//        xs[1][2] = 1;
//
//        xs[2][0] = 2;
//        xs[2][1] = 3;
//        xs[2][2] = 2;

        System.out.println("稀疏棋盘显示");
        for(int[] x:xs){
            for(int y:x){
                System.out.printf("%d\t",y);

            }
            System.out.println();
        }


        //稀疏数组转换为棋盘二维数组
        int [][] qp = new int[xs[0][0]][xs[0][1]];
       for(int i = 1;i<xs.length;i++){
          qp[xs[i][0]][xs[i][1]] = xs[i][2];
       }
        System.out.println("稀疏数组转换完二维数组");
        for(int[] arr:qp){
            for(int a:arr){
                System.out.printf("%d\t",a);
                if(a!=0){
                    sum++;
                }
            }
            System.out.println();
        }
        
    }

}

队列

队列是一个有序列表，可以用数组或链表实现

遵循先进先出的原则，先存入队列的数据，要先取出，后存入的数据要后取出。

数组模拟队列代码实现

数组模拟队列示意图

package com.test;

import java.util.Scanner;

public class ArrayQueue {
    /**
     * 数组模拟队列
     * rear：队列后置标志 （随着队列元素增加而增加） 初始化=-1
     * front:队列前置标志（队列中头一个位置-1）（随着队列减少而增加）初始化=-1
     * 构造
     * 添加
     * maxSize:队列能够存储的最大元素
     * isMax（是否超出队列最大限制） = maxSize-1(因为数组索引从0开始)、
     * isEmpty
     * showQueue 遍历 队列
     * showHead 返回队列头部
     * getQueue
     */

    private int rear;
    private int front;
    private int maxSize;
    private int[] arr;

    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' ';//用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出菜单
        while(loop){
            System.out.println("s：显示队列");
            System.out.println("e：退出程序");
            System.out.println("a：添加队列");
            System.out.println("g：从队列中取值");
            System.out.println("h：查看队列头部");
            key = scanner.next().charAt(0);
            switch(key) {
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("please inout number");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':

                    try {
                        System.out.println("取出的数据是：" + arrayQueue.getQueue());
                    } catch (Exception e) {
                        String message = e.getMessage();
                        System.out.println(message);
                    }
                    break;
                case 'h':
                    try {
                        System.out.println("队列头的数据是：" + arrayQueue.getHeadQueue());
                    } catch (Exception e) {
                        String message = e.getMessage();
                        System.out.println(message);
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("程序退出");
    }

    public ArrayQueue(int maxSize) {
        this.rear = -1; //队列尾下表
        this.front = -1; //队列头前一个位置的下标
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }
    //队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }
    //队列是否已满
    public boolean isMax(){
        return rear == maxSize-1;
    }
    //将元素存入队列中
    public void addQueue(int num){
        if(!isMax()){
            rear++;
            arr[rear] = num;
            System.out.println("元素添加成功");
        }else{
            System.out.println("队列已满不能添加数据");
        }
    }
    //取出队列数据
    public int getQueue(){
        if(isEmpty()){
            System.out.println("队列中没有数据");
            throw new RuntimeException("队列中没有数据");
        }
        front++;
        return arr[front];
    }
    //查询队列
    public void showQueue(){
        for(int a:arr){
            System.out.println(a);
        }
    }
    //返回队列头部
    public int getHeadQueue(){
        if(isEmpty()){
            System.out.println("队列中没有数据");
            throw new RuntimeException("队列中没有数据");
        }
        return arr[front+1];
    }
}