- Characteristics of queues
- One-way queue
- The circular queue
- Singly linked list
- Two-way linked list
- Circular linked list
The following ideas and key methods are only given. The source code of the algorithm is put in Git, and you need to take it yourself
Gitee.com/leidl97/alg…
Characteristics of queues
First in, first out (FIFO)
Can be interpreted as queuing, first in line first in. As is shown in
It’s from the Fourth Edition of Algorithms, page 78
One-way queue
Ideas (how to define data)
It is implemented as an array. The first position of the head pointer to the beginning is -1, and the default position is 0
The position where the tail pointer points to the last element is also -1. (In the initial case, there are no elements, so it points to -1. When the element is added, the tail pointer +1 adds the value to the last element.)
Check that the queue is full
The tail pointer points to the last position of the element
Determine that the queue is empty
Head pointer = tail pointer
In the data
First move, then take. Let the tail pointer +1 first, before assigning the value to the position of the tail pointer
Take out the data
First move, then take. To fetch the tail data, first set the head pointer to +1 to fetch the position to which the head pointer points
Java implementation
Write the queue entry and exit methods, usually in an array
Attribute definitions
// The maximum size of the array
private int maxSize;
/ / queue head
private int begin;
/ / queue tail
private int end;
// An array of queues
private int[] arr;
public ArrayQueue(int maxSize){
// This can be omitted, but it is clearer to write
this.maxSize = maxSize;
this.arr = new int[maxSize];
// The queue header points to the position before the start
this.begin = -1;
// The end of the queue points to the last position. They're both -1 but they don't mean the same thing
this.end = -1;
}
Copy the codeJudge team full
// If the queue is not full, the end of the queue is the last element of the array
public boolean isFull(a){
return this.end == this.maxSize - 1;
}
Copy the codeJudge team empty
// Check whether the queue is empty
public boolean isEmpty(a){
return this.begin == this.end;
}
Copy the codeAdd data to the queue
// Add data to the queue
public void addQueue(int data){
// Check to see if it is full
if (isFull()) {
throw new RuntimeException("Queue full, cannot add data");
}
this.arr[++this.end] = data;
}
Copy the codeGet queue data
// Get the data from the queue
public int getQueue(a){
if (isEmpty()) {
// Throw an exception without writing return
throw new RuntimeException("Queue empty, no data can be fetched.");
}
return this.arr[++this.begin];
}
Copy the codeDisplay queue data
// Get the data from the queue
public int getQueue(a){
if (isEmpty()) {
// Throw an exception without writing return
throw new RuntimeException("Queue empty, no data can be fetched.");
}
return this.arr[++this.begin];
}
Copy the codeDisplay queue header data
// Display the queue header data
public int getBegin(a){
if (isEmpty()) {
throw new RuntimeException("This team is listed as empty.");
}
return this.arr[begin+1];
}
Copy the codedefects
Can not reuse, use once obsolete, can not frequently add and delete elements, the solution is to use a ring queue
The circular queue
thought
Can you think about what you need to do to reuse, yes, take modules
So when you define an array, you sacrifice a space for judgment
The difference is, we define a header pointer to the first element, which is 0
The tail pointer to the next position at the end of the array is also 0
Determine that the queue is empty
Head pointer = tail pointer. Like in the beginning
Check that the queue is full
(tail pointer +1) % array size is 0 when the queue is full
In the data
Unlike unidirectional, this time there is a shift. Saves the region pointed to by the tail pointer to the specified data, and then moves to the next location
Take out the data
Take first and then move. Retrieves the element to which the current head pointer points, and then moves to the next position
Get all elements
You have to figure it out, right? How should I fill in the position of
for(int i = ? ; i < ? ; i++)Copy the codeThe first one? Should be the subscript of the element to which the current header pointer points
The second one? The current header pointer should be subscript + the number of valid elements
If not, then you need to determine which of the two Pointers is in front and which is behind
Get a significant number
(tail pointer – head pointer + array size)% Array size
That’s the absolute value of the tail pointer – the head pointer
Java implementation
Attribute definitions
// The maximum size of the array
private int maxSize;
/ / queue head
private int begin;
/ / queue tail
private int end;
// An array of queues
private int[] arr;
// If the header points to the first element and the tail points to the last element, the initial state cannot be determined as empty or full
// Add the data tail pointer to move, fetch the data header pointer to move, this design sacrifice a space, that is, by default, the last location does not store data
public CircleArrayQueue(int maxSize){
// This can be omitted, but it is clearer to write
this.maxSize = maxSize;
this.arr = new int[maxSize];
// The queue header points to the first position of the element
this.begin = 0;
// The end of the queue points to the last position of the element
this.end = 0;
}
Copy the codeJudge team full
Maxsize = tail: the head is always pointing to the first element. The tail is full (the last element +1).
public boolean isFull(a){
return (this.end + 1)%maxSize == this.begin;
}
Copy the codeJudge team empty
// Check whether the queue is empty
public boolean isEmpty(a){
return this.begin == this.end;
}
Copy the codeAdd data
// Add data to queue, tail pointer +1
public void addQueue(int data){
// Check to see if it is full
if (isFull()) {
throw new RuntimeException("Queue full, cannot add data");
}
arr[end] = data;
end = (end + 1) % maxSize;
System.out.println("Save data:"+data);
}
Copy the codeGet queue header data
// Get queue data, header pointer +1
public int getQueue(a){
if (isEmpty()) {
// Throw an exception without writing return
throw new RuntimeException("Queue empty, no data can be fetched.");
}
int data = arr[begin];
begin = (begin + 1) % maxSize;
System.out.println("Fetch data :"+data);
return data;
}
Copy the codeDisplays all data in the queue
// Display all data in the queue.
public void getAllQueue(a){
StringBuffer sb = new StringBuffer();
if (isEmpty()) {
throw new RuntimeException("This team is listed as empty.");
}
for (int i = begin; i< begin+getActive(); i++) {
System.out.println("arr["+i%maxSize+"] ="+arr[i%maxSize]); }}Copy the codeDisplays valid data for the queue
// Displays valid data for the queue
public int getActive(a){
return (end + maxSize - begin) % maxSize;
}
Copy the codeThe list
Linked list is an ordered list with an address, a data field for storing data, and a next field for pointing to the next address
Linked lists are stored as nodes
Each node contains the data field, and the next field
It doesn’t have to be continuous storage
Images from the Internet
Singly linked list
Train of thought
Start by defining a Node class Node
There are ID, data, and at least three attributes of the next node
Define a node class that initializes the head node, and since the head node cannot move, define secondary nodes for addition and traversal
Add: The end interpolation method, determine whether the next element of the current element is empty, if so, insert the next node in the current node, if not in order to find the next empty node and then insert
Traversal: first determine whether the next element of the head node is empty, otherwise look down, and then output the node once
Disadvantages: Cannot be added in serial order
Java implementation
The test part
MangerNode mangerNode = new MangerNode();
Node node1 = new Node(1."Wife Number one");
Node node2 = new Node(2."Wife Number two");
Node node3 = new Node(3."Wife Number three");
Node node4 = new Node(4."Wife Number four.");
mangerNode.add(node1);
mangerNode.add(node2);
mangerNode.add(node3);
mangerNode.add(node4);
mangerNode.show();
Copy the codeDefine the nodes
// Marks the current node number
public int no;
/ / data domain
public String data;
// Next node
public Node next;
public Node(int no, String data){
this.no = no;
this.data = data;
}
Copy the codeAdd a node
// Add a node
public void add(Node node){
temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = node;
}
Copy the codeTraversing the list
// Iterate over the list
public void show(a){
temp = head.next;
// Check whether it is null
if(temp == null) {
System.out.println("Linked list is empty");
} else {
while (true) {
System.out.println(temp);
if (temp.next == null) {break; } temp = temp.next; }}}Copy the codeIf you want to add them in order of number
You have to go through and judge. Start from the head node, use temp as an auxiliary variable to point to the head node, determine whether the serial number of the next element no is greater than the inserted node, if so, find the current element. If equal, the node is repeated, otherwise the loop continues until the next element is empty
Add the following code
// Add a node (advanced version)
public void addPro(Node node){
temp = head;
// There are no repeating elements by default
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > node.no) {
break;
} else if (temp.next.no == node.no) {
flag = true;
break;
}
temp = temp.next;
}
// Add elements
if (flag) {
System.out.println("There is no for"+node.no+"Duplicate elements may not be added");
} else{ node.next = temp.next; temp.next = node; }}Copy the codeModify: directly modify after finding
// Find the modification
public void update(Node node){
if (head.next == null) {
System.out.println("The list is empty!");
} else {
temp = head.next;
while (true) {
if (temp.next == null) {break;
}
if (temp.no == node.no) {
temp.data = node.data;
break; } temp = temp.next; }}}Copy the codeDelete: in addition to finding the node B to be deleted, we also need to find the previous node A, which used to point to B, now A points to C, and finally delete B (directly assigning is equivalent to deleting).
// find A pointing to B instead of pointing to C and delete B
public void delete(Node node){
if (head.next == null) {
System.out.println("The list is empty!");
} else {
temp = head;
while (true) {
if (temp.next == null) {break;
}
if (temp.next.no == node.no) {
temp.next = temp.next.next;
break; } temp = temp.next; }}}Copy the codeList inversion
Train of thought
It’s the old linked list and the current linked list
The important core steps are
1. The current node (cur) points to the next node of the new head node (new.next).
2. The next header of the new node (new.next) points to the current node (cur).
Draw a diagram
First move
Second movement
Code implementation
public void reverse(Node headNode){
// Returns the result when there is no node or only one node
if (headNode.next == null || headNode.next.next == null) {
System.out.println("The list is empty!");
}
// Define an auxiliary variable, cur, to iterate over the original list
Node cur = headNode.next;
// Define the next node for cur, next, to record
Node next = null;
// Define the head node of the new node
Node newHead = new Node(0."");
while(cur ! =null) {
// Next points to the next node for cur
next = cur.next;
// The next node of cur points to the next node of the new head node
cur.next = newHead.next;
// The next node of the new head node points to the cur node
newHead.next = cur;
/ / a cur
cur = next;
}
// At this point, cur is already a list of linked nodes reversed after head. The new node is transferred to the original node to reverse the original node
headNode.next = newHead.next;
}
Copy the codeEffect of screenshots
Two-way linked list
Train of thought
Unlike a one-way linked list, attributes add a Pre that points to the previous node
Add, delete, change and check to make some changes, but also easy to implement
Added: In addition to needing to point to the next, you now need to point to the previous one
Delete: After finding the node to be deleted, use the previous node to point to the next node, and the same last node also points to the previous node.
Modify: This does not change, after the node finds the specific element, modify the data
Query: Next traversal, pre traversal can be done
Note: Implementing the toString method with next and pre will overflow the stack and cause a pit
Java implementation
The test part
DoubleNode node1 = new DoubleNode(1."Wife Number one");
DoubleNode node2 = new DoubleNode(2."Wife Number two");
DoubleNode node3 = new DoubleNode(3."Wife Number three");
// Update the node
DoubleNode node4 = new DoubleNode(1."Wife Number four");
ManagerDoubleNode.add(node1);
ManagerDoubleNode.add(node2);
ManagerDoubleNode.add(node3);
// ManagerDoubleNode.delete(node3.getNo());
ManagerDoubleNode.update(node4);
ManagerDoubleNode.show();
Copy the codeNode definition
// Define the node number
private int no;
// Define the previous node
public DoubleNode pre;
// Define data
public String data;
// Define the latter node
public DoubleNode next;
DoubleNode(int no, String data) {
this.no = no;
this.data = data;
}
Copy the codeAdd node
// Add a node
public static void add(DoubleNode node) {
DoubleNode temp = ManagerDoubleNode.head;
while(temp.next ! =null) {
temp = temp.next;
}
temp.next = node;
node.pre = temp;
}
Copy the codeDelete nodes
// Delete a node
public static void delete(int no) {
DoubleNode temp = ManagerDoubleNode.head.next;
boolean flag = false;
while(temp ! =null) {
if (temp.getNo() == no) {
// Find the node and delete it
flag = true;
temp.pre.next = temp.next;
if(temp.next ! =null) {
// If the node is not the last, its next node points to the previous node of temp
temp.next.pre = temp.pre;
}
break;
}
// If you cannot find it, move to the next position
temp = temp.next;
}
if (flag) {
System.out.println("This node has been deleted!");
} else {
System.out.println("This node does not exist and cannot be deleted!"); }}Copy the codeUpdate the node
public static void update(DoubleNode node) {
DoubleNode temp = ManagerDoubleNode.head.next;
boolean flag = false;
while(temp ! =null) {
if (temp.getNo() == node.getNo()) {
// Find the node and update it
flag = true;
temp.data = node.data;
break;
}
// If you cannot find it, move to the next position
temp = temp.next;
}
if (flag) {
System.out.println("This node is updated!");
} else {
System.out.println("This node does not exist and cannot be updated!"); }}Copy the codeShow nodes
public static void show(a) {
DoubleNode temp = ManagerDoubleNode.head.next;
while(temp ! =null) { System.out.println(temp); temp = temp.next; }}Copy the codeCircular linked list
One way circular linked list
Implementation ideas and code
Same node definition as before, number, data field, next point to
Add, delete, alter, and check are slightly different. Next does not now point to null, even if only one element points to itself
To determine the end condition change, you need to determine whether the next node of the current node is the head node
Walk through the code implementation
public CircleNode show(a) {
cur = first;
while (true) {
System.out.println(cur);
if (cur.next == first) {
break;
}
cur = cur.next;
}
return cur;
}
Copy the codeIncrease constant, find the last position and increase
public void add(CircleNode circleNode) {
cur = first;
while (true) {
if (cur.next == first) {
break;
}
cur = cur.next;
}
cur.next = circleNode;
circleNode.next = first;
}
Copy the codeChange it. Find the corresponding no and change it
It should be noted that there is no end judgment condition, so no judgment should be made first and then traversal judgment should be made once
Otherwise, if there are no elements that need to be modified, just keep looking for them and delete them
public void update(int no, String data) {
cur = first;
while (true) {
if (cur.no == no) {
cur.data = data;
System.out.println("Data modified successfully!");
break;
}
if (cur.next == first) {
System.out.println("No data to modify found!");
break; } cur = cur.next; }}Copy the codeNote that: if the head node is to be deleted, the head node needs to be transformed. Here, I extend the head node, and then make the previous one of the node to be deleted point to the modified head node. Because it is a single linked list, the next one of the current node needs to be traversed
public void delete(CircleNode circleNode) {
cur = first;
while (true) {
if (cur.next.no == circleNode.no) {
if (cur.next == first) {
first = cur.next.next;
cur.next = first;
System.out.println("Deleted data is the head node, the current head node continues as"+first);
break;
}
cur.next = cur.next.next;
System.out.println("Data deleted successfully!");
break;
}
if (cur.next == first) {
System.out.println("No data found to delete!");
break; } cur = cur.next; }}Copy the codeIf you specify the size of a circular list, it is important to initialize it in the method, not at object creation time, at I =1, and then add nodes
public MangerCircleNode addByNum(int num) {
if (num < 1) {
System.out.println("Size can't be less than 1!");
return null;
}
MangerCircleNode mangerCircleNode = new MangerCircleNode();
CircleNode newNode = null;
for (int i = 1; i<=num; i++) {
if (i == 1) {/ / initialization
mangerCircleNode.first = new CircleNode(i,"Wife"+i+"No.");
mangerCircleNode.first.next = mangerCircleNode.first;
cur =mangerCircleNode.first;
} else {
// Add a ring node
newNode = new CircleNode(i,"Wife"+i+"No.");
cur.next = newNode;
newNode.next = mangerCircleNode.first;
}
//cur points to the next node
cur = cur.next;
}
return mangerCircleNode;
}
Copy the codePractical classic problem: Joseph problem
Numbers for 1, 2,… ,n of n people sitting in a clockwise circle, each with a number (positive integer). From the NTH number, counting clockwise from the first person starting at 1, stop counting when reporting m. The person calling m goes out, and the next person counts, and so on, until everyone is out. Try to design a program to figure out the column order. The basic requirement is to use the storage structure of one-way circular linked list to simulate this process, and print out the number of each person in the order of the column. After the implementation of the prompt program, the user is required to specify the initial upper limit value, and then read each password. Can set n 30 or less. There is no need for “headers” in the circular linked list used in this question. Note the distinction between empty and non-empty tables.
Images from the Internet
Images from the Internet
And so on
Images from the Internet
Simulation: pass in a m, which means traversal once every m times, and output the result after traversal finally
public void yusefu(int m){
int count = getCount();
if (m > count) {
System.out.println("The number entered cannot be larger than the list size");
} else {
/ / reset
cur = first;
while (true) {
if (count == 0) {
break;
}
for (int j = 0; j<m-1; j++){
cur = cur.next;
}
System.out.println(cur);
first = cur.next;
this.delete(cur); cur = first; count--; }}}// Get the number of lists
public int getCount(a) {
cur = first;
int count = 0;
while (true) {
count++;
if(cur.next == first){
break;
}
cur = cur.next;
}
return count;
}
Copy the codeEnhanced version, input three numbers, output traversal results
From the number, how many times, how big a list to create
Simulate a real problem
Count from the number of children, count how many times, how many children there are
Note the scope of variables
/ * * * *@paramStartNo From what number *@paramCountNo how many times *@paramHow many people are there in total
public void yusefu(int startNo, int countNo, int size){
if (startNo < 1 || countNo < 1 || size < 1 || startNo > size) {
System.out.println("The numbers don't add up!");
return;
}
MangerCircleNode mangerCircleNode = new MangerCircleNode(size);
// Check which node is first. This node is already a loop
for (int i = 0; i<startNo-1; i++) {
mangerCircleNode.first = mangerCircleNode.first.next;
}
/ / reset
mangerCircleNode.cur = mangerCircleNode.first;
while (true) {
if (size == 0) {
System.out.println("The final number of the circle is:"+mangerCircleNode.cur.no);
break;
}
for (int j = 0; j<countNo-1; j++){ mangerCircleNode.cur = mangerCircleNode.cur.next; } System.out.println(mangerCircleNode.cur); mangerCircleNode.first = mangerCircleNode.cur.next; mangerCircleNode.delete(mangerCircleNode.cur); mangerCircleNode.cur = mangerCircleNode.first; size--; }}Copy the codeAdded: Sparse array
What is a sparse array?
Change a two-dimensional array into a 3xn array to save space and improve storage efficiency
thought
When most elements of an array are zero, or a fixed value, sparse arrays can be used
Converts a 2×2 two-dimensional array into a 3xn array, as shown in the following table
The application requirements
gobang
Two-dimensional –> sparse
1. Iterate through the original two-dimensional array to get the number of valid data sum
SparseArr int[sum+1][3]
3. Store valid data of two-dimensional array into sparse array
Sparse –> two dimensions
ChessArr = int[row][col] chessArr = int[col]
2. Read the data in the last few lines of the sparse array and assign it to the original two-dimensional array
Java implementation
public static void main(String[] args) {
// Create a checkerboard with 0 for unplayed, 1 for black, and 2 for white
int chessArr[][] = new int[11] [10];
chessArr[1] [2] = 1;
chessArr[2] [3] = 2;
chessArr[3] [4] = 1;
int k = 0;
// Outputs the original two-dimensional array
for (int[] row : chessArr){
for (int data : row){
// Output + TAB in decimal notation
System.out.printf("%d\t",data);
if(data ! =0){
k++;
}
}
System.out.println();
}
// select row from col
int row = chessArr[0].length;
int col = chessArr.length;
System.out.println("row="+row+"col="+col);
int a = 1,b = 0;
// Create a sparse array
int sparseArr[][] = new int[k+1] [3];
sparseArr[0] [0] = col;
sparseArr[0] [1] = row;
sparseArr[0] [2] = k;
for (int i = 0; i<chessArr.length; i++){
for (int j = 0; j<chessArr[i].length; j++){
if(chessArr[i][j] ! =0){
sparseArr[a][0] = i;
sparseArr[a][1] = j;
sparseArr[a][2] = chessArr[i][j]; a++; }}}for (int[] row1 : sparseArr){
for (int data : row1){
// Output + TAB in decimal notation
System.out.printf("%d\t",data);
}
System.out.println();
}
// How to count rows and columns in a group
}
Copy the codeThe output
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 row=10col=11 11 10 3 1 2 1 2 3 2 3 4 1 Process finished with exit code 0Copy the code