catalogue
Importance of data structures and algorithms
Relationship between data structure and algorithm
Linear structure and nonlinear structure
Importance of data structures and algorithms
-
Algorithms are the soul of programs. Excellent programs can still maintain high-speed computing when computing massive data
-
Generally speaking, the program will use memory computing framework (such as Spark) and cache technology (such as Redis) to optimize the program. After further thinking, what are the core functions of these computing frameworks and cache technology?
-
Take the actual work experience as an example. The function of developing server programs under Unix is to support tens of millions of people online at the same time. Before going online, do an internal test and everything is OK. After going online, the server can't support it. The CTO of the company optimizes the code and goes online again, which is as solid as a rock. You can feel that the program has a soul, which is the algorithm.
-
At present, the threshold of programmer interview is getting higher and higher. Many front-line IT companies (large factories) will have data structure and algorithm interview questions (I'm responsible to tell you, there must be)
-
If you don't want to be a coder forever, take the time to study data structures and algorithms
-
Explain according to the application scenario - > data structure or algorithm - > analysis principle - > analysis and implementation steps (illustration) - > code implementation steps [such as eight queens problem and dynamic programming algorithm]
-
Course objective: to master the essence and achieve the purpose of flexibly using to solve practical problems and optimize procedures in work
Relationship between data structure and algorithm
-
data structure is a research organization data With programming language, there will be data structure Learning data structure well can write more beautiful and efficient code.
-
To learn data structure well, we should consider how to solve the problems encountered in life with programs
-
Procedure= data structure +Algorithm
-
Data structure is the basis of algorithm. In other words, if you want to learn algorithm well, you need to learn data structure in place.
Linear structure and nonlinear structure
The data structure includes linear structure and nonlinear structure.
-
linear structure
-
As the most commonly used data structure, linear structure is characterized by * * * one-to-one * * * linear relationship between data elements
-
Linear structure has two different storage structures, namely sequential storage structure (array) and linked storage structure (linked list). A linear table with sequential storage is called a sequential table. The storage elements in the sequential table are continuous,
-
A linear list with linked storage is called a linked list. The storage elements in the linked list are not necessarily continuous. The address information of data elements and adjacent elements are stored in the element node
-
Common linear structures are array, queue, linked list and stack, which will be explained in detail later
-
-
Nonlinear structure
-
Nonlinear structures include: two-dimensional array, multi-dimensional array, generalized table, tree structure and graph structure
-
Sparse arrays and queues
Sparse array
When most elements in an array are 0 or an array with the same value, you can use a sparse array to save the array.
The processing method of sparse array is:
-
How many rows and columns are there in the record array? How many different values are there
-
The rows, columns and values of elements with different values are recorded in a small-scale array, so as to reduce the size of the program
Examples of sparse arrays:
Application example:
1) Use a sparse array to preserve a two-dimensional array similar to the previous one (chessboard, map, etc.)
2) Save the sparse array, and you can restore the original number of two-dimensional arrays
3) Overall thinking analysis
The idea of transforming two-dimensional array into sparse array
-
Traverse the original two-dimensional array to get the number of valid data sum
-
Based on sum, you can create a sparse array sparseArr int[sum+1]-[3]
-
The valid data of the two-dimensional array is stored in the sparse array
Code implementation:
public class SparseArray {
public static void main(String[] args) {
//Create an original two-dimensional array 11 * 11
//0: create a piece without chess pieces. 1 means sunspot and 2 means blue
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//Output the original two-dimensional array
System.out.println("Original two-dimensional array:");
// Java 5 introduces an enhanced for loop that is primarily used for arrays or collections
//
// Format:
//
// for (declaration statement: expression){
// / / loop body
//
// }
for(int[] row : chessArr1) {
//Traverse each element of the chessArr1 array and assign it to the one-dimensional array row
for(int data : row) {
//Traverse each element of the array one-dimensional array row and assign it to the variable data
System.out.printf("%d\t",data);
}
System.out.println();
}
//The idea of converting two-dimensional array to sparse array
//1. First traverse the original two-dimensional array to get the number of valid data sum
int sum =0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++){
if(chessArr1[i][j] != 0) {
sum++;
}
continue;
}
}
System.out.println("sum ="+sum);
//2. According to sum, you can create a sparse array sparsearr int [sum + 1] - [3]
int[][] sparseArr = new int[sum+1][3];
//sparseArr [row] [column]
//3. The valid data of the two-dimensional array is stored in the sparse array
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//Traverse the two-dimensional array and store non-0 values in sparseArr
int count = 0;//How many non-zero data are used to record, because the first non-zero data is in the second row and the second non-zero data is in the third row,
//count can be used as the number of rows of non-0 data
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++){
if(chessArr1[i][j] != 0) {
count ++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr1[i][j];
}
continue;
}
}
//Output sparse array form
System.out.println();
System.out.println("The resulting sparse array is:");
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]);
}
}
}The idea of transforming sparse array into original two-dimensional array
-
First read the first row of the sparse array and create the original two-dimensional array according to the data of the first row, such as chessArr2=int[11]-[11] above
-
Then read the data of the last few rows of the sparse array and assign it to the original two-dimensional array.
Code implementation:
public class SparseArray {
public static void main(String[] args) {
//Create an original two-dimensional array 11 * 11
//0: create a piece without chess pieces. 1 means sunspot and 2 means blue
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//Output the original two-dimensional array
System.out.println("Original two-dimensional array:");
// Java 5 introduces an enhanced for loop that is primarily used for arrays or collections
//
// Format:
//
// for (declaration statement: expression){
// / / loop body
//
// }
for(int[] row : chessArr1) {
//Traverse each element of the chessArr1 array and assign it to the one-dimensional array row
for(int data : row) {
//Traverse each element of the array one-dimensional array row and assign it to the variable data
System.out.printf("%d\t",data);
}
System.out.println();
}
//The idea of converting two-dimensional array to sparse array
//1. First traverse the original two-dimensional array to get the number of valid data sum
int sum =0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++){
if(chessArr1[i][j] != 0) {
sum++;
}
continue;
}
}
System.out.println("sum ="+sum);
//2. According to sum, you can create a sparse array sparsearr int [sum + 1] - [3]
int[][] sparseArr = new int[sum+1][3];
//sparseArr [row] [column]
//3. The valid data of the two-dimensional array is stored in the sparse array
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//Traverse the two-dimensional array and store non-0 values in sparseArr
int count = 0;//How many non-zero data are used to record, because the first non-zero data is in the second row and the second non-zero data is in the third row,
//count can be used as the number of rows of non-0 data
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++){
if(chessArr1[i][j] != 0) {
count ++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr1[i][j];
}
continue;
}
}
//Output sparse array form
System.out.println();
System.out.println("The resulting sparse array is:");
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]);
}
System.out.println("****************************");
// 1. First read the first row of the sparse array and create the original two-dimensional array according to the data of the first row
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2. Read the data of the last few rows of the sparse array and assign it to the original two-dimensional array
for(int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
// Output recovered 2D array
System.out.println();
System.out.println("Restored 2D array");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}queue
-
Queue is a sequential list, which can be implemented by array or linked list.
-
Follow the principle of first in, first out. That is, the data stored in the queue should be taken out first. After the deposit, it shall be taken out
Array emulation queue
-
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 maximum capacity of the queue.
-
Because the output and input of the queue are processed from the front and rear ends respectively, two variables front and rear are required to record the subscripts at the front and rear ends of the queue respectively. The front will change with the data output, while the rear will change with the data input, as shown in the figure:
Note:
-
rear is the last [including] in the queue
-
Front is the front element of the queue [excluding]
-
Queue operation (addQueue):
1) Move the tail pointer back: rear+1, when front== rear [empty]
2) If the tail pointer rear is less than the maximum subscript maxSize-1 of the queue, the data will be stored in the array element referred to by rear, otherwise the data cannot be stored. rear == maxSize - 1 [queue full]
Code implementation:
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//Test one
//Create a queue
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //Receive user input
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//Output a menu
while(loop) {
System.out.println("s(show): Show queue");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Fetch data from queue");
System.out.println("h(head): View data of 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': //Fetch data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //View data of queue header
try {
int res = queue.headQueue();
System.out.printf("The data in the queue header is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
// Use arrays to simulate queues - write an ArrayQueue class
class ArrayQueue {
private int maxSize; // Represents the maximum capacity of the array
private int front; // Queue header
private int rear; // Queue tail
private int[] arr; // This data is used to store data and simulate the queue
// Constructor to create a queue
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; // Point to the queue header and analyze that front is the previous position pointing to the queue header There is no data at the point
rear = -1; // Data pointing to the end of the queue (that is, the last data of the queue)
}
// Determine whether the queue is full
public boolean isFull() {
return rear == maxSize - 1;
}
// Determine whether the queue is empty
public boolean isEmpty() {
return rear == front;
}
// Add data to queue
public void addQueue(int n) {
// Determine whether the queue is full
if (isFull()) {
System.out.println("The queue is full and data cannot be added~");
return;
}
rear++; // Move rear
arr[rear] = n;
}
// Get the data of the queue and get out of the queue
public int getQueue() {
// Judge whether the queue is empty
if (isEmpty()) {
// By throwing an exception
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
front++; // front backward
return arr[front];
}
// Displays all data for the queue
public void showQueue() {
// ergodic
if (isEmpty()) {
System.out.println("The queue is empty and there is no data~~");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// The header data of the queue is displayed. Note that it is not taken out
public int headQueue() {
// judge
if (isEmpty()) {
throw new RuntimeException("The queue is empty and there is no data~~");
}
return arr[front + 1];
}
}Array simulation ring queue
-
The previous array simulation queue optimization, make full use of the array So think of the array as a ring. (it can be realized by taking mold)
-
Analysis description:
When the next index in the tail index is the header index, it indicates that the queue is full, that is, one queue capacity is vacated as a convention. This should be noted when judging that the queue is full
-
(rear + 1)% maxsize = = front [Full]
-
rear== front [empty]
-
Code implementation:
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//Test one
System.out.println("Test array simulation ring queue case~~~");
// Create a ring queue
CircleArray queue = new CircleArray(4); //Description set 4, and the maximum valid data of its queue is 3
char key = ' '; // Receive user input
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// Output a menu
while (loop) {
System.out.println("s(show): Show queue");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Fetch data from queue");
System.out.println("h(head): View data of 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': // Fetch data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // View data of queue header
try {
int res = queue.headQueue();
System.out.printf("The data in the queue header is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
class CircleArray {
private int maxSize; // Represents the maximum capacity of the array
//Adjust the meaning of the front variable: front points to the first element of the queue, that is, arr[front] is the first element of the queue
//Initial value of front = 0
private int front;
//Adjust the meaning of the rear variable: rear points to the next position of the last element of the queue Because I want to make a space as an agreement
//Initial value of rear = 0
private int rear; // Queue tail
private int[] arr; // This data is used to store data and simulate the queue
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// Determine whether the queue is full
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// Determine whether the queue is empty
public boolean isEmpty() {
return rear == front;
}
// Add data to queue
public void addQueue(int n) {
// Determine whether the queue is full
if (isFull()) {
System.out.println("The queue is full and data cannot be added~");
return;
}
//Add data directly
arr[rear] = n;
//Move the rear, and here you must consider taking the mold
rear = (rear + 1) % maxSize;
}
// Get the data of the queue and get out of the queue
public int getQueue() {
// Judge whether the queue is empty
if (isEmpty()) {
// By throwing an exception
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
// Here, we need to analyze that front is the first element pointing to the queue
// 1. First keep the value corresponding to front to a temporary variable
// 2. Move the front backward and consider taking the mold
// 3. Return temporarily saved variables
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// Displays all data for the queue
public void showQueue() {
// ergodic
if (isEmpty()) {
System.out.println("The queue is empty and there is no data~~");
return;
}
// Idea: start traversing from front, and how many elements are traversed
// Use your head
for (int i = front; i < front + size() ; i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// Find the number of valid data in the current queue
public int size() {
// rear = 2
// front = 1
// maxSize = 3
return (rear + maxSize - front) % maxSize;
}
// The header data of the queue is displayed. Note that it is not taken out
public int headQueue() {
// judge
if (isEmpty()) {
throw new RuntimeException("The queue is empty and there is no data~~");
}
return arr[front];
}
}