线性结构与非线性结构

线性结构与非线性结构

  • 数据结构包括：线性结构和非线性结构。

线性结构

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

非线性结构

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

稀疏数组

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

稀疏数组的处理方法是:

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

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

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

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

  • 先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组，例chessArr2=int[11][11]
  • 再读取稀疏数组后几行的数据，并赋给原始的二维数组即可
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
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();
        }
        // 将二维数组转稀疏数组
        // 先遍历二维数组得到非零数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // 遍历二维数组，将非零值存入稀疏数组
        int count = 0;// 用于记录是第几个非零数据
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; 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("得到的稀疏数组为~~~");
        System.out.printf("%s\t%s\t%s\t", "row", "col", "val");
        System.out.println();
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }
        // 将稀疏数组恢复为原始的二维数组
        // 先读取稀疏数组的异地航，根据第一行的数据，创建原始的二维数组
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 再读取稀疏数组后几行数据，并赋给chessArr2即可
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        // 输出恢复后的二维数组
        System.out.println();
        System.out.println("恢复后的二维数组~~~");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class SparseArrayIO {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("D://xiaojia/SparseArr.data"));
        BufferedWriter bw = new BufferedWriter(new FileWriter("D://xiaojia/SparseArr.data"));
        BufferedReader br2 = new BufferedReader(new FileReader("D://xiaojia/SparseArr.data"));
        // 创建一个原始的二维数组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();
        }
        // 将二维数组转稀疏数组
        // 先遍历二维数组得到非零数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // 遍历二维数组，将非零值存入稀疏数组
        int count = 0;// 用于记录是第几个非零数据
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        for (int i = 0; i < sparseArr.length; i++) {
            bw.write(sparseArr[i][0] + "\t" + sparseArr[i][1] + "\t" + sparseArr[i][2]);
            bw.newLine();
            bw.flush();
        }
        bw.close();
        String str;
        int row = 0;
        while ((str = br.readLine()) != null) {
            row++;
        }
        String line;
        int count2 = 0;
        int[][] sparseArr2 = new int[row][3];
        while ((line = br2.readLine()) != null) {
            String[] str1 = line.split("\t");
            for (int i = 0; i < str1.length; i++) {
                sparseArr2[count2][i] = Integer.parseInt(str1[i]);
            }
            count2++;
        }
        // 将稀疏数组恢复为原始的二维数组
        // 先读取稀疏数组的第一行数据，根据第一行的数据，创建原始的二维数组
        int[][] chessArr2 = new int[sparseArr2[0][0]][sparseArr2[0][1]];
        // 再读取稀疏数组后几行数据，并赋给chessArr2即可
        for (int i = 1; i < sparseArr2.length; i++) {
            chessArr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2];
        }
        // 输出恢复后的二维数组
        System.out.println();
        System.out.println("恢复后的二维数组~~~");
        for (int[] r : chessArr2) {
            for (int data : r) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
    }
}

队列

  • 队列是一个有序列表，可以用数组或是链表来实现。
  • 遵循先入先出的原则

数组模拟队列

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        // 测试
        // 创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; // 接收用户输入
        Scanner sc = 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 = sc.next().charAt(0);// 接收一个字符
            switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'a':
                System.out.println("请输入一个数字：");
                int value = sc.nextInt();
                queue.addQueue(value);
                break;
            case 'g':
                try {
                    int res = queue.getQueue();
                    System.out.printf("取出的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h':
                try {
                    int res = queue.headQueue();
                    System.out.printf("队列头的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'e':
                sc.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        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 front == rear;
    }

    // 添加数据到队列
    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++;// front后移
        return arr[front];
    }

    // 显示队列所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空的，没有数据~~~");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

    // 显示队列的头数据，注意不是取数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空的，没有数据~~~");
        }
        return arr[front + 1];
    }
}

问题分析并优化:

  • 目前数组使用一次就不能用了，没有达到复用的效果
  • 将这个数组使用算法，改进成一个环形的队列 取模%方式

数组模拟环形队列

思路分析：

  • front变量的含义做一个调整：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front初始值为0
  • rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为一个约定，rear初始值为0
  • 当队列满的条件，(rear+1)%maxSize==front【满】
  • 当队列空的条件，rear==front【空】
  • 队列中有效的数据的个数(rear+maxSize-front)%maxSize
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import java.util.Scanner;

public class CircleQueueDemo {
    public static void main(String[] args) {
        // 测试
        // 创建一个队列
        CircleArray queue = new CircleArray(3);
        char key = ' '; // 接收用户输入
        Scanner sc = 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 = sc.next().charAt(0);// 接收一个字符
            switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'a':
                System.out.println("请输入一个数字：");
                int value = sc.nextInt();
                queue.addQueue(value);
                break;
            case 'g':
                try {
                    int res = queue.getQueue();
                    System.out.printf("取出的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h':
                try {
                    int res = queue.headQueue();
                    System.out.printf("队列头的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'e':
                sc.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出~~~");
    }
}

//使用数组模拟队列-编写一个ArrayQueue类
class CircleArray {
    private int maxSize;// 表示数组的最大容量
//    front变量的含义做一个调整：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front初始值为0
    private int front;
//    rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为一个约定，rear初始值为0
    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 front == rear;
    }

    // 添加数据到队列
    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 < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    // 求出当前队列有效数据的个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    // 显示队列的头数据，注意不是取数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空的，没有数据~~~");
        }
        return arr[front];
    }
}