数据结构学习笔记（一）

灰太狼 2023-09-30 11:56 6阅读 0赞

## 一：数据结构 ##

**1.1 数据结构的概述：**

数据结构包括：**线性结构**和**非线性结构**

**1. 线性结构：**

> 1.  线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
> 2.  线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中存储元素是连续的。
> 3.  链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
> 4.  线性结构常见的有：数组、队列、链表和栈。

**2. 非线性结构：**

> 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构。

## 二：稀疏sparsearray数组 ##

**2.1 稀疏数组的基本介绍：**

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

稀疏数组的处理方法是：

>  *  记录数组一共有几行几列，有多少个不同的值。
>  *  把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

--------------------

![28599e6011114ab28773e3a1840532b0.png][]

**2.2 二维数组与稀疏数组的相互转换**

1.二维数组转换稀疏数组的思路：

> 遍历原始的二维数组，得到有效数据的个数sum
> 
> 根据sum就可以创建稀疏数组sparseArr int【sum+1】【3】

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

> 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr2=int【11】【11】
> 
> 在读取稀疏数组后几行的数据，并赋给原始的二维数组即可。

--------------------

package package01;
    
    import java.io.*;
    
    public class sparseArray {
        public static void main(String[] args) throws IOException, ClassNotFoundException {
            //创建一个原始的二维数组11*11
            //0：表示没有棋子，1：表示黑子 2：表示来自蓝子
            int chessArr1[][] = new int[11][11];
            chessArr1[1][2] = 1;
            chessArr1[2][3] = 2;
            chessArr1[4][5] = 2;
            //输出原始的二维数组
            for (int[] low : chessArr1) {
                for (int date : low) {
                    System.out.printf("%d\t", date);
                }
                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 = 1;//count 用于记录是第几个非0数据
            for (int i = 0; i < 11; i++) {
                for (int j = 0; j < 11; j++) {
                    if (chessArr1[i][j] != 0) {
                        sparseArr[count][0] = i;
                        sparseArr[count][1] = j;
                        sparseArr[count][2] = chessArr1[i][j];
                        count++;
                    }
                }
            }
    
           /* //将稀疏数组保存到磁盘（map.date）上
            BufferedWriter bw = new BufferedWriter(new FileWriter("mokuai-02\\mapDate.txt"));
            //读写数据
            String line;
            for (int[] row : sparseArr) {
                line = row.toString();
                bw.write(line);
                bw.flush();
                bw.newLine();
            }
            //释放资源
            bw.close();*/
    
            //采用序列化将数组储存到mapDate中
            ObjectOutputStream oos=new ObjectOutputStream(new FileOutputStream("mokuai-02\\mapDate.txt"));
            //存储数据
            oos.writeObject(sparseArr);
            //释放资源
            oos.close();
    
    
            //输出稀疏数组的形式
            System.out.println();
            System.out.println("稀疏数组为：");
            for (int[] row : sparseArr) {
                for (int item : row) {
                    System.out.printf("%d\t", item);
                }
                System.out.println();
            }
    
            //将稀疏数组恢复成原始的二维数组
            int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
    
    
            /*for(int[] row:sparseArr){
                chessArr2[row[0]][row[1]]=row[2];
            }*/          //要从第二行开始遍历
    
            //恢复原来的数组，读取mapDate进行恢复
            System.out.println("用IO流恢复后的数组为：");
            /*BufferedReader br = new BufferedReader(new FileReader("mokuai-02\\mapDate.txt"));
            //读取数据,一次读取一个字符串
            //char[] bytes=new char[1024];
           String line1;
           int count1=0;//
            while ((line1=br.readLine())!=null) {
                if(count1>=1){
                    for(int i=0;i<line1.length();i++){
                        chessArr2[line1.charAt(0)-'0'][line1.charAt(1)-'0']=(line1.charAt(2)-'0');
                    }
                }
                count1++;
            }*/
    
            //采用反序列化方式读取稀释数组，并恢复成原来的数组
            ObjectInputStream ois=new ObjectInputStream(new FileInputStream("mokuai-02\\mapDate.txt"));
            //读写数据
            Object obj1=ois.readObject();
            int[][] sparseArr1=(int[][]) obj1;
            for (int i = 1; i < sparseArr1.length; i++) {
                chessArr2[sparseArr1[i][0]][sparseArr1[i][1]] = sparseArr1[i][2];
            }
    
            //输出二维数组
            for (int[] rows : chessArr2) {
                for (int ans : rows) {
                    System.out.printf("%d\t", ans);
                }
                System.out.println();
            }
    
    
           /* for (int i = 1; i < sparseArr.length; i++) {
                chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
    
            }*/
    
            //输出二维数组
            // *System.out.println("恢复后的二维数组为：");
            /*for (int[] rows : chessArr2) {
                for (int ans : rows) {
                    System.out.printf("%d\t", ans);
                }
                System.out.println();
            }*/
        }
    }

--------------------

## 三：队列 ##

**3.1 队列的介绍**

> 队列是一个有序列表，可以用数组或是链表来实现。
> 
> 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

**3.2 数组模拟队列**

队列本身是有序列表，因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。

--------------------

import java.util.Scanner;
    
    /*
     * 测试类
     * */
    public class ArrayQueueDemo {
        public static void main(String[] args) {
            //创建一个队列
            ArrayQueue arrayQueue=new ArrayQueue(3);//初始化容量为3
            char key=' ';//接收用户输入
            Scanner sc=new Scanner(System.in);
            //输出一个菜单
            while(true){
                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=sc.next().charAt(0);//接收一个字符
                switch(key){
                    case 's'://显示队列
                        arrayQueue.showQueue();
                        break;
                    case 'a'://添加数据
                        System.out.println("输入一个数");
                        int value=sc.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g'://取出数据
                        try {
                            int res=arrayQueue.getQueue();
                            System.out.printf("取出的数据%d\n",res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h'://显示队列的头数据
                        try{
                            int ans=arrayQueue.headQueue();
                            System.out.printf("队列的头数据为%d\n",ans);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e'://退出程序
                        System.out.println("程序退出");
                        sc.close();
                        return;
                    default:
                        System.out.println("你输入的字符有误，请重新输入");
                }
                }
            }
        }
    
    
    
    
    //使用数组模拟队列-缩写一个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;//指向队列头部，分析出front是指向队列头的前一个位置
            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++;
            arr[rear] = n;
        }
    
        //获取队列的数据，出队列
        public int getQueue() {
            //先判断队列是否空
            if (isEmpty()) {
                //通过抛出异常
                throw new RuntimeException("队列空，不能取数据");
            }
            front++;//front后移
            return arr[front];
        }
    
        //显示队列的所有数据
        public void showQueue() {
            //先判断队列是否空
            if (isEmpty()) {
                System.out.println("队列为空,没有数据");
                return;
            } else {
                //遍历集合
                for(int i=0;i<arr.length;i++){
                    System.out.printf("arr[%d]=%d\t",i,arr[i]);
                    System.out.println();
                }
            }
        }
    
        //显示队列的头数据，并不是取出来
        public int headQueue() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空,没有数据");
            }
            return arr[front + 1];
        }
    
    }

**（PS：该队列是一次性的，没有达到复用的效果）**

--------------------

**3.3 数组模拟环形队列**

环形队列的思路：

> 1.  front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr\[front\]就是队列的第一个元素，front的初始值=0
> 2.  rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值=0
> 3.  当队列满时，条件是（rear+1）%maxSize=front【满】
> 4.  对队列为空的条件，rear==front【空】
> 5.  当我们这样分心，队列中有效的数据的个数（rear+maxSize-front）%maxSize
> 6.  我们就可以在原来的队列上修改得到，一个环形队列

--------------------

package package03;
    
    import java.util.Scanner;
    
    public class CircleArrayQueueDemo {
        public static void main(String[] args) {
            /*
            * 测试类：测试数组模拟环形队列
            */
            //创建一个队列
            CircleArray arrayQueue=new CircleArray(3);//初始化容量为3，但是只能存储2个数据，因为要预留一个位置
            char key=' ';//接收用户输入
            Scanner sc=new Scanner(System.in);
            //输出一个菜单
            while(true){
                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=sc.next().charAt(0);//接收一个字符
                switch(key){
                    case 's'://显示队列
                        arrayQueue.showQueue();
                        break;
                    case 'a'://添加数据
                        System.out.println("输入一个数");
                        int value=sc.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g'://取出数据
                        try {
                            int res=arrayQueue.getQueue();
                            System.out.printf("取出的数据%d\n",res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h'://显示队列的头数据
                        try{
                            int ans=arrayQueue.headQueue();
                            System.out.printf("队列的头数据为%d\n",ans);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e'://退出程序
                        System.out.println("程序退出");
                        sc.close();
                        return;
                    default:
                        System.out.println("你输入的字符有误，请重新输入");
                }
            }
    
    
        }
    }
    
    class CircleArray {
        private int maxSize;//表示数组的最大容量
        private int front;//队列头
        //1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0
    
        private int rear;//队列尾
        //2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值=0
    
        private int[] arr;//该数组用于存放数据
    
        //构造器
        public CircleArray(int maxSize) {
            this.maxSize = maxSize;
            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 headQueue() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空,没有数据");
            }
            return arr[front];
        }
    
        //获取队列的数据，出队列
        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("队列为空，没有数据");
            }
            //思路：从front开始遍历，遍历多少个元素
            for(int i=front;i<front+size();i++){
                System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
            }
        }
    
        //求出当前队列有效数据的个数
        public int size(){
            return (rear+maxSize-front)%maxSize;
        }
    
    }

[28599e6011114ab28773e3a1840532b0.png]: https://img-blog.csdnimg.cn/28599e6011114ab28773e3a1840532b0.png