1, Linear structure and nonlinear structure
(1) First look at a real demand
(2) , array simulation queue idea
(3) , array simulation of circular queue (implemented by modulus)
1, Linear structure and nonlinear structure
Data structure includes linear structure and nonlinear structure.
1. Linear structure
- As the most commonly used data structure, linear structure is characterized by one-to-one linear relationship between data elements;
- There are two different storage structures in linear structure: sequential storage structure (array) and chained storage structure (linked list). The linear table of sequential storage is called sequential table, and the total storage elements of the sequential table are continuous;
- The linear list of chain storage is called chain list. The storage elements in the chain list are not necessarily continuous. The address information of data elements and adjacent elements are stored in the element nodes;
- Linear structures are common: arrays, queues, linked lists, and stacks.
2. Nonlinear structure
Nonlinear structure includes two-dimensional array, multidimensional array, generalized table, tree structure and graph structure.
2, Sparse arrays and queues
1. Sparse array
(1) First look at a real demand
- In the program of Gobang, it has the function of saving, exiting and continuing the board
- Analysis problem: because many values of the 2D array are 0 by default, many meaningless data are recorded. - > sparse array.
(2) . basic introduction
When most of the elements in an array are 0, or an array with the same value, a sparse array can be used to hold the array.
The processing method of sparse array is as follows:
- The record array has several rows, columns and valid values;
- To reduce the size of the program, we record the columns and values of the elements of the effective value in a small array
An example of sparse array:
(3) . application examples
- Use sparse arrays to keep 2D arrays like the previous ones (checkerboard, map, etc.)
- Save the sparse array to disk, and restore the original two-dimensional array number
- Overall thinking analysis:
- code implementation
package com.narwal.sparsearray;
import java.io.*;
public class SparseArray {
public static void main(String[] args) throws IOException {
int[][] chessArr1 = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
System.out.println("Original array");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
/*
* Original array to sparse array
*/
// 1. Traversing the original two-dimensional array, the number of valid data sum is obtained;
int sum = 0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[0].length; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
// 2. Create sparse array
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
int count = 0;
// 3. Fill valid data into sparse array
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[0].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("Sparse array");
for (int[] row : sparseArr) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
File file = new File("/home/wise/Music/map.data"); //File for storing array data
// Save sparse array to file
writeArr(sparseArr, file);
// Read 2D array from file
readArr(file);
/*
* Sparse array to original array
*/
// 1. Read the first row to get the rows and columns of the original array
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2. Fill valid data into the original array
for (int i = 1; i <= sum; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("Two dimensional array after reversal");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
private static void readArr(File file) throws IOException {
int[][] sparseArr = new int[3][3];
BufferedReader in = new BufferedReader(new FileReader(file));
String line;
int row = 0;
while((line=in.readLine()) !=null){
String[] temp = line.split("\t");
for(int j=0;j<temp.length;j++){
sparseArr[row][j] = Integer.parseInt(temp[j]);
}
row ++;
}
in.close();
System.out.println("Sparse array read from file:");
for(int[] row1:sparseArr){
for(int data:row1){
System.out.printf("%d\t", data);
}
System.out.println();
}
}
private static void writeArr(int[][] sparseArr, File file) throws IOException {
FileWriter out = new FileWriter(file);
for (int[] row : sparseArr) {
for (int data : row) {
out.write(data + "\t");
}
out.write("\n");
}
out.close();
}
}
2. Queue (input element head pointer front unchanged, tail pointer rear+1; output element tail pointer rear unchanged, head pointer front+1)
(1) , queue introduction
- Queue is a list with sequence, which can be realized by array or linked list;
- Follow the principle of first in, first out;
- Diagram: (use array to simulate queue diagram)
(2) , array simulation queue idea
- The queue itself has a sequence table. If the array structure is used to store the data of the queue, the declaration of the queue array is shown in the figure below, where maxSize is the queue
The maximum capacity of the column. - Because the output and input of the queue are processed from the front and back ends respectively, two variables, front and rear, are required to record the subscripts of the front and back ends of the queue respectively,
The front will change with the data output, and the rear will change with the data input, as shown in the figure:
-
When we put the data into the queue, it is called "addQueue". The processing of addQueue needs two steps: train of thought analysis
1) Move the tail pointer back: rear+1, when front == rear, the queue is empty;
2) If the tail pointer rear is smaller than the maximum small scale maxSize-1 of the queue, it means that the queue is not full and data can be added, otherwise data cannot be added.
rear == maxSize-1 [queue full]
- code implementation
package com.narwal.queue;
// Add data is front invariant, get data is rear invariant
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(4);
char key; // Receive user input
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show): Show queues");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Get data from queue");
System.out.println("h(head): View the data of the queue header");
key = scanner.next().charAt(0);// Receive a character
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("Output a number");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': // Retrieve data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h': // View the data of the queue header
try {
int res = queue.headQueue();
System.out.printf("The data of the queue header is%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e': // sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
class ArrayQueue {
private int maxSize;
private int rear;
private int front;
private int[] arr;
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; // Point to the previous position of the queue header
rear = -1; // Point to the end of the queue, that is, arr[rear] is the data at the end of the queue
}
// Judge that the queue is full
public boolean isFull() {
return rear == maxSize - 1;
}
// Judge whether the queue is empty
public boolean isEmpty() {
return rear == front;
}
// Add data to the queue
public void addQueue(int n) {
if (isFull()) {
throw new RuntimeException("Queue full");
}
rear++;
arr[rear] = n;
}
// get data
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
front++;
return arr[front];
}
// Show all data for the queue
public void showQueue() {
// ergodic
if (isEmpty()) {
System.out.println("Queue empty,no data~~");
return;
}
for (int i = 0; i < rear-front; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// Show queue header data
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return arr[front + 1];
}
}(3) , array simulation of circular queue (implemented by modulus)
- Analysis description:
1) When the next index of the tail index is the header index, it means that the queue is full, that is to say, the queue capacity is empty as a contract, which is used to judge that the queue is full
Note (rear + 1)% maxsize = = front full]
2) rear == front [empty]
3) Analysis diagram:
4) Code implementation:
package com.narwal.queue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
CircleArrayQueue queue = new CircleArrayQueue(4);
char key; // Receive user input
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show): Show queues");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Get data from queue");
System.out.println("h(head): View the data of the queue header");
key = scanner.next().charAt(0);// Receive a character
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("Output a number");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': // Retrieve data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h': // View the data of the queue header
try {
int res = queue.headQueue();
System.out.printf("The data of the queue header is%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e': // sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
class CircleArrayQueue {
private int maxSize;
private int rear;
private int front;
private int[] arr;
public CircleArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = 0; // front points to the first element of the queue
rear = 0; // Point to the next location of the last element of the queue, because you want to make a space available as a convention
}
// Judge that the queue is full
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// Judge whether the queue is empty
public boolean isEmpty() {
return rear == front;
}
// Add data to the queue
public void addQueue(int n) {
if (isFull()) {
throw new RuntimeException("Queue full");
}
arr[rear] = n;
rear = (rear + 1) % maxSize;
}
// get data
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// Show all data for the queue
public void showQueue() {
// ergodic
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
for (int i = front; i < (rear + maxSize - front) % maxSize; i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// Show queue header data
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return arr[front];
}
}(4) . summary
- For the queue, first define the meaning of the head pointer and the tail pointer, such as:
1) One way queue:
front = -1; / / points to the previous position of the queue header
Rar = - 1; / / points to the end of the queue, that is, arr [rar] is the data at the end of the queue
2) Circular queue
front = 0; / / refers to the first element of the queue
Rar = - 1; / / points to the next position of the last element of the queue, because you want to make a space as a convention