Java implementation sequence table

2022-05-15 05:09:22

Catalog

One 、 Simple understanding of sequence table

1、 Why should we build a sequential table based on an array ？

2、 What functions does the sequence table have

Two 、 Code implementation of sequence table

1、 Build and initialize the sequence table

2、 Add elements to the sequence table

1、 Judge whether the subscript of the element to be added is within the range of the sequence table

2、 If the subscript of the added element is legal , Add elements .

3、 If the sequence table is full, we need to expand the capacity

4、 The implementation code is as follows ：

3、 Print the elements in the sequence table

4、 Determine whether the sequence table contains an element

5、 Look up the subscript of the element in the order table

6、 Update the element value of the subscript corresponding to the sequence table

7、 Look up the element value corresponding to the subscript in the sequence table

8、 Delete the elements in the order table

9、 Get the length of the sequence table

10、 Clear the sequence table

3、 ... and 、 Summary of disadvantages and advantages of sequence table

1、 The advantages of a sequence table

2、 The disadvantages of the sequence table

One 、 Simple understanding of sequence table

The order is represented by a paragraph A storage unit with continuous physical addresses A linear structure that stores data elements in turn , Generally, it is stored on the basis of array .

1、 Why should we build a sequential table based on an array ？

First , Our array is in memory Sequential storage , Therefore, it can better logically implement the sequence table .

also , The elements stored in the array are like a team , Everyone is closely connected , We can't disrupt the order of the team , You can't skip an empty seat , Go to the next position , And everyone has their own code , That's their subscript .

This is an array , Therefore, due to the above advantages , He is fully qualified for the foundation of the sequence table .

2、 What functions does the sequence table have

First of all, the sequence table will be added , Delete , check , Find these four functions , Next we will use java In the form of code to realize these functions and build a sequence table .

Two 、 Code implementation of sequence table

1、 Build and initialize the sequence table

First, we need to build a sequence table , The previous article pointed out that the base of the sequence table is an array , So we need an array , But just having an array is not enough , Because we only know the length of the array , I don't know how many elements are stored in the array , So we also need something to record how many elements are stored in our sequence table .

``````public class myArraysList {

public int[]arrary;
public int usedSize ;
//  Get the valid data length of the sequence table

public myArraysList(){
this.arrary = new int[10];// Initialize array
}
}``````

Here I define a construction method , The purpose is to define the array size inside the method , Open up space .

2、 Add elements to the sequence table

When adding elements , We need to consider two issues

1、 Judge whether the subscript of the element to be added is within the range of the sequence table

Judge whether the subscript of the added element is greater than zero , And whether it is within the number of elements stored in the sequence table

2、 If the subscript of the added element is legal , Add elements .

1、 Tail insertion

This insertion is the simplest , Just insert it directly at the end of the sequence table

2、 Intermediate insertion

This is a little complicated , First, we have to empty the position where the array insert elements , Therefore, we need to move the position of the inserted element and the following elements back by one bit , This makes room for , Then insert the element

3、 If the sequence table is full, we need to expand the capacity

For judging whether the sequence table is full , I built a Boolean return method , Therefore, it can be better used in judgment statements . For capacity expansion, we can use copyOf This method is used to expand the capacity of the array

4、 The implementation code is as follows ：

`````` public boolean isFull() {
return this.arrary.length == this.usedSize;
}
if(pos <0||pos >this.usedSize){// Determine whether it is within the scope of the sequence table
System.out.println("pos illegal ");
return;
}
if(isFull()){
// Judge whether it is full , If it's full, expand the capacity
this.arrary = Arrays.copyOf(this.arrary,this.usedSize*2);
}
for(int i = this.usedSize - 1; i > pos; i--){
this.arrary[i+1] = this.arrary[i];// Fall from back to front
}
this.arrary[pos] = date;
this.usedSize++;
}``````

3、 Print the elements in the sequence table

The elements in the print sequence table are relatively simple , Because we already know the number of elements stored in the sequence table , therefore for If the loop is normal, print the array

``````  public void display(){
for (int i = 0; i < this.usedSize; i++){
System.out.print(this.arrary[i]+" ");
}
System.out.println();
}``````

4、 Determine whether the sequence table contains an element

This directly traverses the entire sequence table to find elements , The return type is Boolean

``````    Determine whether to include an element
public boolean contains(int toFind) {
for(int i = 0; i < this.usedSize ; i++){
if(toFind == this.arrary[i]){
return true;
}
}
return false;
}``````

5、 Look up the subscript of the element in the order table

This directly traverses the entire sequence table to find elements , And return the subscript value , When we can't find it, we return -1

`````` //  Find the corresponding position of an element , No return found -1
public int search(int toFind){
for (int i = 0; i < this.usedSize; i++){
if(toFind == this.arrary[i]){
return i;
}
}
return -1;
}``````

6、 Update the element value of the subscript corresponding to the sequence table

1、 Judge whether the corresponding subscript is out of bounds or does not exist

2、 Judge whether the sequence table is empty

To determine whether the sequence table is empty, I built a method with a return value of boolean type

``````  //  to  pos  The element of the position is set to / to update  value
public void setPos(int pos, int value){
if(pos < 0||pos > this.usedSize){
System.out.println("pos The subscript crossing the line ");
return;
}
if(ifEmp()){
System.out.println(" Sequence table is empty ");
return;
}
this.arrary[pos] = value;
}``````

7、 Look up the element value corresponding to the subscript in the sequence table

This is the same as before , First judge whether the subscript is out of bounds or does not exist , Then traverse the return value

``````//  obtain  pos  The element of location
// Judge whether you crossed the line
// Judge whether the sequence table is empty
// Directly return the subscript element
public int getPos(int pos){
if(pos < 0||pos > this.usedSize){
System.out.println("pos The subscript crossing the line ");
return -1;
}
if(ifEmp()){
System.out.println(" Sequence table is empty ");
return -1;
}
return this.arrary[pos];

}``````

8、 Delete the elements in the order table

Deleting elements is actually the opposite of adding elements , If you delete an element at the end , You can delete it directly, but if the deleted element is in the middle , The elements behind it have to move forward by one

The code is as follows ：

``````   // Delete the first keyword key
public void remove(int toRemove){
if(ifEmp()){
System.out.println(" Sequence table is empty ");
return;
}
if(-1 == search(toRemove)){
System.out.println(" non-existent ");
return;
}
for(int i = search(toRemove); i < this.usedSize - 1; i++){
this.arrary[i] = this.arrary[i+1];// Move left
}
this.usedSize--;
}``````

9、 Get the length of the sequence table

`````` public int size() {
return this.usedSize;
}``````

Return represents the effective length Value usedSize .

10、 Clear the sequence table

``````
public void clear(){
this.usedSize = 0;
}``````

By way of The effective length is set to 0 To clear the array .

3、 ... and 、 Summary of disadvantages and advantages of sequence table

1、 The advantages of a sequence table

The advantage of sequential table is reflected in the search , Just give the corresponding subscript , Then you can quickly find the time complexity is O(1).

2、 The disadvantages of the sequence table

The disadvantages of the sequence table are also obvious , His weakness lies mainly in deleting and adding , Because each element is closely connected , So we have to move the whole array when deleting and adding , So the time complexity is zero O(n).

This is the simple implementation of our sequence table , I'm Xiao Xia , I'll see you next time ！