01、数据结构——数组-创新互联

一、数据结构与算法

• 数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构。学好数据结构可以编写出更加漂亮、更加有效率的代码。
• 程序=数据结构+算法
• 数据结构是算法的基础

二、稀疏数组：

1、基本介绍：

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

2、稀疏数组的处理方法是

（1）记录数组一共有几行几列，有多少个不同的值

（2）把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

3、应用实例

（1）使用稀疏数组来保留类似前面的二维数组（棋盘、地图等等）

（2）把稀疏数组存盘，并且可以重新恢复原来的二维数组数

（3）整体思路分析

二级数据转稀疏数组的思路：

• 遍历原始的二维数组，得到有效数据的个数sum
• 根据sum就可以创建稀疏数组sparseArr int[sum + 1][3]
• 将二维数组的有效数据存入到稀疏数组

稀疏数组转原始二维数组的思路：

• 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
• 在读取稀疏数组后几行的数据，并赋给原始的二维数组即可

（4）代码实现

package com.atguigu.sparse.array;

public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0：表示没有棋子，1：表示黑子，2：表示蓝子
        int chessArr1[][]=new int[11][11];
        chessArr1[1][2]=1;
        chessArr1[2][3]=2;
        //输出原始的二维数组
        System.out.println("原始的二维数组:");
        for(int[] row:chessArr1){
            for(int data:row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

        //将二维数组转稀疏数组的思路：
        //1、先遍历二维数组，得到非0数据的个数
        int sum=0;
        for(int i=0;i<11;i++){
            for(int j=0;j<11;j++){
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

        //2、创建对应的稀疏数组
        int sparseArr[][]=new int[sum+1][3];
        //给稀疏数组赋值
        sparseArr[0][0]=11;
        sparseArr[0][1]=11;
        sparseArr[0][2]=sum;

        //遍历二维数组，将非0的值存放到sparseArr中
        int count=0;//count用于记录是第几个非0数据
        for(int i=0;i<11;i++){
            for(int j=0;j<11;j++){
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0]=i;
                    sparseArr[count][1]=j;
                    sparseArr[count][2]=chessArr1[i][j];
                }
            }
        }

        //输出稀疏数组的形式
        System.out.println();
        System.out.println("得到的稀疏数组：");
        for(int i=0;i

4、练习

三、数组模拟队列

1、基本介绍：

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

（2）遵循先入先出的原则

2、数组模拟队列

（1）队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 maxSize是该队列的大容量

（2）因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变

（3）addQueue：将数据存入队列。思路：

1）将尾指针往后移：rear+1，当front=rear [ 空 ]

2）若尾指针rear小于队列的大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据，rear==maxSize-1 [ 队列满 ]

3）注：

rear是队列最后 [ 含 ]

front是队列最前元素 [不含]

4）代码实现：

package com.atguigu.sparse.queue;

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        char key=' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop=true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出队列");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列中取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key=scanner.next().charAt(0);//接收一个字符
            switch(key){
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数：");
                    int value=scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res=queue.getQueue();
                        System.out.printf("取出的数据：%d\n",res);
                    } catch (Exception e) {
                        //TODO：handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res=queue.headQueue();
                        System.out.printf("队头的数据：%d\n",res);
                    } catch (Exception e) {
                        //TODO：handle exception
                        System.out.println(e.getMessage());
                    }
                    break;

                case 'e':
                    scanner.close();
                    loop=false;
                    break;

                default:
                    break;
            }

        }
    }
}
//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue{
    private int maxSize;//表示数组的大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//存放数据

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr=new int[maxSize];
        front=-1;//指向队列头的前一个位置
        rear=-1;//指向队列尾的最后一个数据
    }

    //判断队列是否满
    public boolean isFull(){
        return rear==maxSize-1;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，不能加入数据！");
            return;
        }
        rear++;//让rear后移
        arr[rear]=n;
    }

    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

（4）问题分析并优化

1）目前数组使用一次就不能用，没有达到利用的效果

2）使用算法将这个数组，改进成一个环形的队列

四、数组模拟环形队列

1、思路：

（1）调整front变量的含义：front指向队列的第一个元素

（2）调整rear变量的含义：rear指向队列最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值=0

（3）队列为满时的条件，(rear+1)%maxSize=front 

尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定

（4）队列为空时的条件，rear=front 

（5）队列中有效的数据的个数 (rear+maxSize-front)%maxSize

package com.atguigu.sparse.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        System.out.println("测试数组模拟环形队列的案例");
        CircleArray queue = new CircleArray(4);//队列的有效数据大是3
        char key=' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop=true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出队列");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列中取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key=scanner.next().charAt(0);//接收一个字符
            switch(key){
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数：");
                    int value=scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res=queue.getQueue();
                        System.out.printf("取出的数据：%d\n",res);
                    } catch (Exception e) {
                        //TODO：handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res=queue.headQueue();
                        System.out.printf("队头的数据：%d\n",res);
                    } catch (Exception e) {
                        //TODO：handle exception
                        System.out.println(e.getMessage());
                    }
                    break;

                case 'e':
                    scanner.close();
                    loop=false;
                    break;

                default:
                    break;
            }

        }
    }
}
class CircleArray{
    private int maxSize;//表示数组的大容量
    private int front;//指向队列的第一个元素
    private int rear;//指向队列最后一个元素的后一个位置
    private int[] arr;//存放数据

    public CircleArray(int arrMaxSize){
        maxSize=arrMaxSize;
        arr=new int[maxSize];
    }

    //判断队列是否满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，不能加入数据");
            return;
        }
        //直接将数据加入
        arr[rear]=n;
        //将rear后移，考虑取模
        rear=(rear+1)%maxSize;
    }

    //获取队列的数据
    public int getQueue(){
        //判断队列是否为空
        if (isEmpty()) {
            //抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        //front指向队列的第一个元素
        //1、先把front对应的值保留到一个临时变量
        //2、将front后移，考虑取模
        //3、将临时保存的变量返回
        int value=arr[front];
        front=(front+1)%maxSize;
        return value;
    }

    //显示队列的所有数据
    public void showQueue(){
        //遍历
        if (isEmpty()) {
            System.out.println("队列空的，没有数据");
            return;
        }

        //从front开始遍历
        for(int i=front;i

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧