大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

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

一、数据结构与算法

创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站设计、成都网站建设、外贸网站建设、平顶山网络推广、微信小程序、平顶山网络营销、平顶山企业策划、平顶山品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;创新互联为所有大学生创业者提供平顶山建站搭建服务,24小时服务热线:13518219792,官方网址:www.cdcxhl.com
  • 数据结构是一门研究组织数据方式的学科,有了编程语言也就有了数据结构。学好数据结构可以编写出更加漂亮、更加有效率的代码。
  • 程序=数据结构+算法
  • 数据结构是算法的基础

二、稀疏数组:

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元起,快前往官网查看详情吧


文章标题:01、数据结构——数组-创新互联
文章来源:http://dzwzjz.com/article/dejphh.html