数据结构之数组

一.稀疏数组

package com.bzw.array.sparseArray;  import java.io.*;  //用二维数组表示棋盘。“1” 表示 黑子，2表示白子。 public class sparseArray {     public static void main(String[] args) throws IOException {         int[][] array1 = new int[11][11];         array1[1][2] = 1;         array1[2][3] = 2;         array1[3][4] = 2;          for(int[] row : array1){             for(int temp: row){                 System.out.printf("%d\t",temp);             }             System.out.println();         }          /*            将二维数组转化为稀稀数组          */         int sum=0;          //计数器，用于计算二维数组中有效值的个数         for(int i=0;i<array1.length;i  )             for(int j=0;j<array1[i].length;j  ){                 if(array1[i][j] != 0){                     sum  ;                 }             }         //System.out.println(sum);           int[][] sparseArray = new int[sum 1][3];         sparseArray[0][0] = array1.length;         sparseArray[0][1] = array1[0].length;         sparseArray[0][2] = sum;          int count = 0;      //计数器，稀疏数组的行数         for (int i=0;i<array1.length;i  )             for(int j=0;j<array1[i].length;j  ){                 if(array1[i][j] != 0){                     count  ;                     sparseArray[count][0] = i;                     sparseArray[count][1] = j;                     sparseArray[count][2] = array1[i][j];                 }             }          System.out.println();         System.out.println("稀疏数组为：");         for (int i=0;i<sparseArray.length;i  ){             System.out.printf("%d\t%d\t%d\t\n",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);         }          /*            将稀疏数组保存在文件中          */         File file = new File("E:/sparseArray.txt");         FileWriter out = new FileWriter(file);         for (int i=0;i<sparseArray.length;i  ){             for (int j=0;j<sparseArray[i].length;j  ){                 out.write(sparseArray[i][j] "\t");             }             out.write("\r\n");         }         out.close();          /*            稀疏数组从文件中读取          */         int sparseArray2[][]  = new int[sum 1][3];         BufferedReader in = new BufferedReader(new FileReader(file));         String line;         int r = 0;         while ((line = in.readLine())!= null){             String[] temp = line.split("\t");       ///每读一行保存在数组中             for (int j=0;j<temp.length;j  ){                 sparseArray2[r][j] = Integer.parseInt(temp[j]);     从文件中读取的数据是字符串类型，要转为int类型             }             r  ;         }         in.close();         System.out.println("从文件中读取的稀疏数组：");         for (int i=0;i<sparseArray2.length;i  ){             System.out.printf("%d\t%d\t%d\t\n",sparseArray2[i][0],sparseArray2[i][1],sparseArray2[i][2]);         }          /*            稀疏数组转为二维数组          */         int[][] array2= new int[sparseArray[0][0]][sparseArray[0][1]；      ///根据稀疏数组的第一行确定二维数组的行列数          ///将稀疏数组的值赋予相应的二维数组         for (int i=1;i<sparseArray.length;i  ){             array2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];         }          System.out.println();         System.out.println("恢复的二维数组为：");         for(int[] row : array2){             for(int temp: row){                 System.out.printf("%d\t",temp);             }             System.out.println();         }     }   } 

二.实现数组队列

package com.bzw.array.arrayQueue;  import java.util.Scanner;  public class ArrayQueue {      public static void main(String[] args) {          Queue queue = new Queue(3);         Scanner scanner = new Scanner(System.in);         char key = ' ';         Boolean loop = true;         while (loop){             System.out.println("s(show)显示队列：");             System.out.println("a(add)添加数据：");             System.out.println("g(get)获取数据：");             System.out.println("h(head)查看队首数据：");             System.out.println("e(exit)退出程序：");              key = scanner.next().charAt(0);             switch (key){                 case 's':                     queue.show();                 break;                  case 'a':                     System.out.println("请输入数据：");                     int n = scanner.nextInt();                     try {                         queue.add(n);                     } catch (Exception e) {                         e.printStackTrace();                     }                     break;                  case 'g':                     try {                         System.out.println("取得数据：" queue.get());                     } catch (Exception e) {                         e.printStackTrace();                     }                     break;                  case 'h':                     System.ut.println("队首数据："+queue.headQueue());
                    break;

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

                default:break;
            }
        }
    }
}

class Queue{

    private int maxSize;
    private int front ;     //队列首，指向第一数据的前一个位置
    private int rear ;      //队列尾，指向最后一个数据
    private int[] queue ;

    public Queue(int maxSize){
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
    }

    public boolean isFull(){
        return rear == maxSize - 1;
    }

    public  boolean isEmpty(){
        return rear == front;
    }
    public void add(int n){
        if(isFull()){
            throw new RuntimeException("队列已满，无法添加！");
        }
        rear++;
        queue[rear] = n;
    }


    public int get(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取！");
        }
        front++;
        return queue[front];
    }

    public void show(){
        for ( int i=front+1;i<queue.length;i++)
                System.out.printf("array[%d]:%d\n",i,queue[i]);

    }
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取！");
        }
        return queue[front+1];
    }
}

三.数组实现循环队列

package com.bzw.array.circleQueue;

import java.util.Scanner;

/*
    循环队列
    判断循环队列为空的条件：front == rear
    判断循环队列满的条件： (rear + 1) % maxSize = front
    判断循环队列有多少个元素条件： (rear - front +maxSize)% maxSize
 */
public class CircleQueue {
    public static void main(String[] args) {

        Queue queue = new Queue(4);     //此算法预留了一个位置，长度为4的数组，只能存3个数据
        Scanner scanner = new Scanner(System.in);
        char key = ' ';
        Boolean loop = true;
        while (loop) {
            System.out.println("s(show)显示队列：");
            System.out.println("a(add)添加数据：");
            System.out.println("g(get)获取数据：");
            System.out.println("h(head)查看队首数据：");
            System.out.println("e(exit)退出程序：");

            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.show();
                    break;

                case 'a':
                    System.out.println("请输入数据：");
                    int n = scanner.nextInt();
                    try {
                        queue.add(n);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;

                case 'g':
                    try {
                        System.out.println("取得数据：" + queue.get());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;

                case 'h':
                    System.out.println("队首数据：" + queue.headQueue());
                    break;

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

                default:
                    break;
            }
        }
    }
}

class Queue {

    private int maxSize;
    private int front;     //队列首，指向第一个数据
    private int rear;      //队列尾，指向最后一个数据的后一个位置
    private int[] queue;

    public Queue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = 0;
        rear = 0;
    }

    public boolean isFull() {
        return (rear + 1) % maxSize == front;       //循环队列满时的条件
    }

    public boolean isEmpty() {
        return rear == front;       //循环队列空时的条件
    }

    public void add(int n) {
        if (isFull()) {
            throw new RuntimeException("队列已满，无法添加！");
        }
        queue[rear] = n;
        rear = (rear + 1) % maxSize;
    }


    public int get() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法获取！");
        }
        int value = queue[front];
        front = (front+1) % maxSize;
        return  value;
    }

    public void show() {
        for (int i = front; i < front+size(); i++)
            System.out.printf("array[%d]:%d\n", i%maxSize, queue[i%maxSize]);

    }

    //循环队列元素个数
    public int size(){
        return (rear - front + maxSize) % maxSize;
    }


    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法获取！");
        }
        return queue[front];
    }
}