current position:Home>Java implementation sequence table
Java implementation sequence table
2022-05-15 05:09:22【banbanbanni】
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
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 .
There are two situations about this article
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;
}
public void add(int pos,int date){
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
We have to make two judgments about this :
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 !
copyright notice
author[banbanbanni],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/135/202205142226455522.html
The sidebar is recommended
- Language model what is language model?
- What platforms have the Dharma Institute language laboratory built?
- How to develop UI component library (heavy UI) based on Vue
- My colleague told me that the reason why his code is silky is that he uses mybatis plus?
- Artificial intelligence is undoubtedly a very hot research direction at present. According to the development level of artificial intelligence, which stages will researcher Shiluo divide it into?
- What are the problems and challenges of rate adaptive technology?
- How to make the video clearer?
- What is neurolinguistic model and representation learning?
- What are the two kinds of traditional language model construction?
- The best configuration for IntelliJ idea development
guess what you like
How to count the number of words in English text through C language?
On the problem of C language: the division of students' grades
The interactive search system adopts the modular design idea. According to the hierarchical logical structure, which levels are divided into?
Common problems and solutions of get technology message middleware application
How to deal with facial beauty when achieving facial beauty effect?
In order to achieve the effect of facial beauty, what are we mainly through in technology?
How to watch hot dramas on vertical screen?
Three party application login access GitHub scheme
Online FAQ positioning FAQ what does high CPU utilization mean?
Online FAQ positioning FAQ what is the cause of the high load problem?
Random recommended
- Why do we do quality evaluation?
- What is the function of getstatic, a common tool for online FAQs?
- Android 11 new soft keyboard occlusion / animation solution
- Common tools for online FAQs include?
- How does SAP commerce cloud configure new applications for storefront
- In the CMS GC process, what is the reason why the business thread puts objects into the old generation (the characteristics of concurrent collection)?
- How good and accurate is the recommendation?
- Online FAQ positioning FAQs what are the causes of continuous GC problems?
- Does the data reflect the real viewing experience?
- What are the reasons for fullgc (throw oom if FGC recovery is invalid)?
- Algorithm improvement - basic algorithm (turtle speed multiplication)
- [C + +] sword finger offer 10 - I. Fibonacci sequence
- Online FAQ positioning FAQ nosuchmethodexception what is the cause of the problem?
- IOS enables native im development
- What is the common function of SM?
- "Automated testing" a new generation of Web front-end automated testing framework - playwright, get started quickly!
- Online FAQ positioning FAQ what is the cause of the high load problem?
- What is the function of watch, a common tool for online FAQs?
- Timeliness in recommender systems, Zhang Fuguo et al. ESWA 2017
- Alibaba's open source Java diagnostic tool uses what methods to diagnose.
- What is the function of dashboard, a common tool for online FAQs?
- What is the role of JAD, a common tool for online FAQs?
- Online FAQ positioning FAQ what are the causes of high CPU utilization?
- 07 - explore the underlying principles of IOS | several OC objects [instance object, class object, metaclass], ISA pointer of object, superclass, method call of object and the underlying essence of class
- Extreme fox gitlab settled in Alibaba cloud computing nest to jointly improve the development experience on the cloud
- How does artificial intelligence help natural science
- Elementui upload file
- Modern CSS solution: CSS mathematical functions
- Create a general efficiency improvement solution for front desk + middle desk based on vue3 (network disk link)
- Brush 100 front-end high-quality interview real questions in 2 weeks, and the source code is complete
- Vue has reduced its workload by half since using components
- I built a front-end mock tool
- About uboot -- Ping virtual machine Ubuntu operation
- Video transcoder editready for Mac
- [taro] taro gets the detailed attributes of the element (solved)
- Picture and text difference comparison tool: kaleidoscope for Mac
- Background of spatiotemporal artificial intelligence
- The top 10 of oceanbase database competition was born, and the integration of industry and education accelerated the training of database talents
- China brand Day | Youxuan software: strengthen its own brand and fight for China's database industry
- New feature release of gaussdb (for redis): enhanced prefix scanning and multi rent isolation