抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

数据结构（一）基本概念、稀疏数组、队列

数据结构

发布于：2020年7月23日

次浏览

今日开始总结数据结构相关的知识，本章复习了数据结构的基本知识点、稀疏数组和队列相关的知识。

数据结构

一、数据结构与算法的关系

1、数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构；

2、程序 = 数据结构 + 算法；

3、数据结构是算法的基础。


二、线性结构与非线性结构

1、数据结构的结构

数据结构的存储结构分为线性结构和非线性结构。


2、线性结构

（1）线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系；

（2）线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的；

（3）链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素结点中存放数据元素以及相邻元素的地址信息；

（4）线性结构常见的有：数组、队列、链表和栈。


3、非线性结构

（1）包括：二维数组、多维数组、广义表、树结构、图结构。




稀疏数组

一、基本介绍

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

1、处理方法：

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

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

​

设有一个 6 x 7 的数组，其中记录了5个非原始数据

数组

上面的数组转换为稀疏数组之后

稀疏数组

稀疏数组的第1行（[0]号位置）记录的是原始数组的行数（6行）和列数（7列）和非零元素的个数（5个）

稀疏数组的第二行开始（[1]及以后的行），行列存放的是非零元素在原始数组中的行的位置，列列存放的是同一个非零元素的列的位置，值的位置存放的是非零元素的实际值。


二、实现思路

（1）二维数组转稀疏数组

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

（2）稀疏数组转原始数组

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

三、代码实现

  • 创建一个原始二维数组并赋值
1
2
3
4
5
6
7
8
9
10
//二维数组转稀疏数组
//定义一个二维数组
int arr[][] = new int[6][7];

//向二维数组赋值
arr[0][3] = 22;
arr[0][6] = 15;
arr[1][1] = 11;
arr[1][5] = 17;
arr[3][3] = 8;

(1) 二维数组转稀疏数组实现

  • 遍历原始二维数组，获取有效的数据个数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //        稀疏数组
    //        获取非初始化数据的个数
            int r = arr.length;//二维数组的行
            int l = arr[0].length;//二维数组的列
            int sum = 0;//非0元素的个数
            for (int[] row : arr) {
                for (int data : row) {
                    if (data != 0) {
                        sum++;
                    }
                }
            }

  • 根据二维数组的非零元素的个数sum创建稀疏数组

    1
    2
    3
    4
    5
    6
    //        创建稀疏数组
            int sparseArr[][] = new int[sum + 1][3];
    //        对稀疏数组的第一行进行赋值，二维数组的信息
            sparseArr[0][0] = arr.length;
            sparseArr[0][1] = arr[0].length;
            sparseArr[0][2] = sum;

  • 将二维数组的有效个数存入稀疏数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //        获取非0数据并赋值
            int count = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    if (arr[i][j] != 0) {
                        count++;
                        sparseArr[count][0] = i;
                        sparseArr[count][1] = j;
                        sparseArr[count][2] = arr[i][j];
                    }
                }
            }

  • 遍历稀疏数组查看结果

    二维数组转换为稀疏数组


（2）稀疏数组转二维数组实现

  • 先读取稀疏数组的第一行，根据第一行的数据，创建原始二位数组

    1
    2
    3
    //稀疏数组转二维数组
    //创建一个二维数组
    int arr1[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

  • 在读取稀疏数组的后几行数据，并赋值给二维数组

    1
    2
    3
    4
    5
    6
    7
    8
    //        将稀疏数组中的值赋值给二维数组
            for (int i = 1; i < sparseArr.length; i++) {
                int rows = sparseArr[i][0];
                int c = sparseArr[i][1];
                int data = sparseArr[i][2];

                arr1[rows][c] = data;
            }

  • 运行结果

    稀疏数组转二维数组




队列

一、基本介绍

1、队列是一个有序列表，可以使用链表和数组实现；

2、遵循先进先出的原则。即：先存入队列的数据先取出，后存入的数据后取出。

数组队列逻辑结构图

数组队列逻辑结构图


当插入一个数据后，逻辑结构图变为如下的样子。

![数组队列逻辑结构图 (一)](数据结构（一）/数组队列逻辑结构图 (一).JPG)


当数组队列已满时rear == maxSize - 1或 rear + 1 == maxSize

数组队列位满时


二、数组队列思路

1、队列本身是一个有序列表，若使用数组存储数据则需声明maxSize（数组的最大容量）；

2、因数组需要输出，所以需要两个变量分别指向队列的头元素和尾元素；

3、front为指向队列的头元素索引。默认值为-1；

4、rear为指向队列的尾元素索引。默认值为-1；

5、当需要向队列中添加数据时需判断队列是否已满，若满则将rear的值加一然后存入元素；

6、队列为空的判断方法：rear == front；

7、队列是否已满的判断方法为 rear == maxSize - 1或 rear + 1 == maxSize;

8、当取元素时将front加一，然后将 queue[front] 的值返回。


三、代码实现

1、创建一个队列类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ArraysQueue {
    private int maxSize;//数组（队列）的最大值
    private int front;//队列的头元素
    private int rear;//队列的尾元素
    private int[] queue;//定义一个数组（队列）
    private int size;//有效元素个数

    //创建数组（队列）初始化——构造方法
    public ArraysQueue(int arrmaxSize) {
        maxSize = arrmaxSize;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
        size = arrmaxSize;
    }

}

2、判断队列是否为空与是否已满

1
2
3
4
5
6
7
8
9
//判断队列是否为空——isEmpty
public boolean isEmpty() {
    return front == rear;
}

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

3、向队列中添加元素

判断非空后，先将指向队列尾部的索引后移一位指向一个空的位置，然后将数据存入数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    //添加元素——addQueue
    public void addQueue(int n) {
        //判断队列是否已满
        if (isFull()) {
            //自定义异常
//            throw new RuntimeException("队列已满，无法添加！");
            System.out.println("队列已满，无法添加！");
            return;
        } else {
            //队列没满可以添加
            rear++;
            queue[rear] = n;
            System.out.println("添加成功！");
            size--;
        }
    }

4、取队头元素

待判断结束之后，将队头索引先向后移动一位，只想队头元素，然后取出元素，此时取出的数据不需要再将其删除，因为下次会直接跳过该元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
    //取队头元素getQueue
    public int getQueue() {
        //判断是否非空
        if (isEmpty()) {
//            throw new RuntimeException("队列已空！");
            System.out.println("队列为空！");
            return 0;
        } else {
            front++;
            size++;
            return queue[front];
        }
    }

5、输出队列

使用for循环输出队列，使 i 的值等于(front + 1)，使队列从头元素开始遍历，当 i 的值等于队尾的索引值时停止循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    //输出队列show
    public void showQueue() {
        //判断队列是否为空
        if (isEmpty()) {
//            throw new RuntimeException("队列为空！");
            System.out.println("队列为空！");
            return;
        } else {
            System.out.print("数组内的内容为:");
            System.out.print("[");
            int count = front;
            for (int i = front + 1; i <= rear; i++) {
                count++;
                if (count != rear) {
                    System.out.print(queue[i] + ",");
                } else {
                    System.out.print(queue[i]);
                }

            }
            System.out.println("]");
        }

6、输出获取头元素

1
2
3
4
5
6
7
8
9
//输出获取头元素——headQueue
public int headQueue() {
    //判断是否非空
    if (isEmpty()) {
        throw new RuntimeException("队列为空！");
    } else {
        return queue[front + 1];
    }
}




环形数组队列

一、基本介绍

1、环形数组队列修复了数组队列不能一致存放数据的缺点，但还是和数组队列一样需要设置maxSize；

2、环形数组只是再逻辑上时环形的，但其实在物理存储结构上依然是和数组队列一样的。

环形数组队列的逻辑结构图

环形数组逻辑结构图


二、环形数组队列实现思路

1、front指向数组（队列）的第一个元素queue[0] ，front的初始值设为0；

2、rear指向数组（队列）的最后一个元素的后一个位置，因为空出来一个空间用来做约定，rear的初始值为0；

3、当队列满的判断条件为（rear + 1）% maxSize == front时；

4、当队列为空的判断条件为 rear == front;

5、队列中有效数据的个数为（ rear + maxSize - front）% maxSize。


环形数组队列为满的逻辑机构图如下

环形数组队列逻辑满


三、环形数组队列的代码实现

1、创建一个环形队列类

1
2
3
4
5
6
7
8
9
10
11
12
public class CircleArraryQueueDemo {
    private int maxSize;//数组（队列）的最大值
    private int front;//队列的头元素
    private int rear;//队列的尾元素
    private int[] queue;//定义一个数组（队列）

    //创建数组（队列）初始化——构造方法
    public CircleArraryQueueDemo(int arrmaxSize) {
        maxSize = arrmaxSize;
        queue = new int[maxSize];
    }
}

2、判断队列是否为空与已满

1
2
3
4
5
6
7
8
9
//判断队列是否为空——isEmpty
public boolean isEmpty() {
    return rear == front;
}

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

3、向队列添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    //添加元素——addQueue
    public void addQueue(int n) {
        //判断队列是否已满
        if (isFull()) {
            //自定义异常
//            throw new RuntimeException("队列已满，无法添加！");
            System.out.println("队列已满，无法添加！");
            return;
        } else {
            //队列没满可以添加
            queue[rear] = n;
            //对rear进行取模,防止数组索引越界异常
            rear = (rear + 1) % maxSize;
            System.out.println("添加成功！");
        }
    }

4、获取队列中有效元素的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    //获取队列中有效元素的个数
    public int getLength() {
        return (rear + maxSize - front) % maxSize;
    }

    //取队头元素getQueue
    public int getQueue() {
        //判断是否非空
        if (isEmpty()) {
//            throw new RuntimeException("队列已空！");
            System.out.println("队列为空！");
            return 0;
        } else {
            //front是指向队列的第一个元素
            //1.用临时变量存储头元素
            //2.将front后移
            //3.将临时变量用做返回值
            int value = queue[front];
            front = (front + 1) % maxSize;
            return value;
        }
    }

5、输出队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    //输出队列show
    public void showQueue() {
        //判断队列是否为空
        if (isEmpty()) {
//            throw new RuntimeException("队列为空！");
            System.out.println("队列为空！");
            return;
        } else {
            System.out.print("数组内的内容为:");
            System.out.print("[");
            int count = 0;
            for (int a : queue) {
                if (count == getLength()) {
                    continue;
                }
                count++;
                if (count != maxSize) {
                    System.out.print(a + ",");
                } else {
                    System.out.print(a);
                }
            }
            /*for (int i = front; i < front + getLength(); i++) {
                if (queue[i % maxSize] != maxSize) {
                    System.out.println(queue[i % maxSize] + ",");
                }else {
                    System.out.print(queue[i % maxSize]);
                }
            }*/
            System.out.println("]");
        }
    }

6、获取头元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    //取队头元素getQueue
    public int getQueue() {
        //判断是否非空
        if (isEmpty()) {
//            throw new RuntimeException("队列已空！");
            System.out.println("队列为空！");
            return 0;
        } else {
            //front是指向队列的第一个元素
            //1.用临时变量存储头元素
            //2.将front后移
            //3.将临时变量用做返回值
            int value = queue[front];
            front = (front + 1) % maxSize;
            return value;
        }
    }

7、输出头元素

1
2
3
4
5
6
7
8
9
//输出获取头元素——headQueue
public int headQueue() {
    //判断是否非空
    if (isEmpty()) {
        throw new RuntimeException("队列为空！");
    } else {
        return queue[front];
    }
}




参考资料：

[https://www.bilibili.com/video/BV1E4411H73v]:

更新于：2020年11月21日

评论