Dynamic array implementation

1. Class structure

The construction of all classes needs to be considered from two aspects: properties and methods.

• attribute

  To construct a dynamic array, we first need an array with uncertain size, and then determine the size of the array when calling its constructor.

  Secondly, some parameters about the array: first, we need length to determine its size, and then we can use size to represent the space actually used by the array. These two data will also help us judge whether we need to expand the capacity when adding and deleting objects later.

  	//Container for storing data
  	int[] arr;
  	//Size of container
  	int length = 0;
  	//The size of the space used (must be used in order, and the corresponding size is the location where you can start saving
  	int size = 0;
  

• method

  We need to traverse the array and realize the basic function of adding value one by one, and then we need to change the size of the array and realize the function of adding value one by one.

  	//Add signal factor adds a single element
  	//add  a queue 		 Add an array
  	//delete all x in the Array 		 Delete all x elements in the dynamic array
  	//delete  the factor located in x 		 Delete the element at position X in the dynamic array
  	//change  change x to y 		 Change all x's in the dynamic array to y's
  	//change  change factor in x to y 		 Change the element in the x position to y
  	//seek seek x 		 Find the position of all x in the dynamic array
  	//seek seek the factor in x  	 Find element at x
  
  	//show factors in arr 		 Display the output of all elements in the array
  

2. Class constructor

Since we implement a dynamic array, we need to pass in a parameter to confirm how large the array we just started needs to be built

We first need to overload the constructor of the class

	//Constructor, pass in a value and create a queue of the corresponding size
	public AQueue(int length){
		this.length=length;
		arr = new int[length];
	}

• TIPS:

  (1) The difference between overloading and Rewriting:

  1. Overloading means that different functions use the same function name, but the number or type of parameters of the function are different. When calling, different functions are distinguished according to the parameters of the function.

  2. Overriding (also known as rewriting) refers to the re implementation of virtual functions (note virtual functions) in the base class in the derived class. That is, the function name and parameters are the same, but the implementation of the function is different.

  (2) Priority of attributes and parameters

  When the parameter we pass in conflicts with the attribute name in the class, such as length above, the parameter priority in the function is higher than length. In other words, if you write system out. print(length); Then the passed in parameter length will be output. To get the attribute length, add this before the length

3. Implementation of the method

• Output display of array

  Traversal array output

	//show factors in arr
	public void showArr(){
		System.out.println("The elements in the array are as follows:");
		for(int i=0;i<size;i++)
		{
			System.out.println(arr[i]);
		}
	}

• Add a single element

  	//add  signal factor
  	public void add(int x){
          //Judge whether the array still has space to add elements. If so, add them directly
  		if(size<length){
  			arr[size]=x;
  			size++;
  		}
          //If not, expand the capacity of the array
  		else{
  			length++;
  			int[] Newarr = new int[length];	
  			for(int i = 0;i < size; i++){
  				Newarr[i]=arr[i];
  			}
  			Newarr[size]=x;
  			arr=Newarr;
  			size++;
  		}
  	}
  

  Implementation of capacity expansion: once the array is determined, the size cannot be changed, so if you want to expand the array, you need to create a new array, first pass the values in the old array, and then add the elements to be added

  * array refers to the address data type. Array = array is to assign the address of the first position of the array to the past. If you want to give the value inside to the past, you need a for loop

• Add an array

	//add  a queue
	public void add_Arr(int[] array){
		//Add the length of the array
		int arr_length=array.length;
		//Determine whether the array size is exceeded after being added
		//No more than
		if(size+arr_length<=length){
//			System.out.println("can be inserted directly");
			for(int i = 0;i < arr_length;i++){
				arr[size+i]=array[i];
			}
			size+=arr_length;
		}
		//Out of bounds, array expansion
		else{
//			System.out.println("the array needs to be expanded");
			int[] Newarr=new int[size+arr_length];
			for(int i=0;i<size;i++)
			{
				Newarr[i]=arr[i];
			}
			for(int i=0;i<arr_length;i++){
				Newarr[size+i]=array[i];
			}
			size+=arr_length;
			length=size;
			arr=Newarr;
		}
	}

• Delete all x in dynamic array

	//delete all x in the Array
	public void delete(int x){
		//Traversal search x
		for(int i=0;i<size;i++){
			if(arr[i]==x){
				//If there is an x, move the following elements forward one, and size-1 to delete
				for(int y=i;y<size-1;y++){
					arr[y]=arr[y+1];
				}
				//Because the element moves forward one, i still need to check from the current position at this time. i can't++
				//Use i -- to offset the i set by the for loop++
				i--;
				size--;
			}
		}
	}

• Delete the element at position x in the array

	//delete  the factor located in x
	public void delete_lo(int x){
		for(int i=x;i<size-1;i++){
			arr[i]=arr[i+1];
		}
		size--;
	}

• Modify all x in the array to y

	//change  change x to y
	public void change(int x,int y){
		for(int i=0;i<size;i++){
			if(arr[i]==x){
				arr[i]=y;
			}
		}
	}

• Modify the element in the x position of the array to y

	//change  change factor in x to y
	public void change_lo(int x,int y){
		arr[x]=y;
	}

• Find the position of all x's in the array

• Finds the element in the x position in the array

	//seek seek the factor in x 
	public int see_lo(int x){
		//The element at position x is actually the x+1 element of the array
		System.out.println("In the array at"+x+"The elements of the location are:"+arr[x]);
		return (arr[x]);
	}

• Verify output

  This is to check the output every time you write a function. Here, in order to facilitate writing directly together, interested readers can add all methods after commenting them one by one to check the effect

  public class AQueueMain {
  	public static void main(String[] args){
  		int length = 4;
  		int[] array={1,2,3,4,5,6,7,8,9};
  		
  		AQueue arr = new AQueue(length);
  		arr.add(0);
  		arr.add_Arr(array);
  		arr.delete(5);
  		arr.delete_lo(0);
  		arr.change(8, 4);
  		arr.change(2, 0);
  		
  		//Array after adding, deleting and changing
  		arr.showArr();
  		
  		arr.seek(4);
  		arr.seek_lo(9);	
  	}	
  }
  

The difference between object-oriented and process oriented

Process oriented: analyze what steps are needed to solve the problem, and then implement these steps one by one, which can be called at one time. The specific problem here is to solve the function. Although the overhead is reduced because there is no need for instantiation, the unity of the whole development process is not high and the maintenance cost is high.

Object oriented: decompose the things that constitute the problem into objects. The purpose is to describe the behavior of this thing in the steps of solving the problem, which can ensure the unity of solving the problem to a greater extent. At the same time, it has the characteristics of inheritance and polymorphism, which can better realize the reuse of code. More flexible and easy to maintain. However, because class calls need to be instantiated, it costs a lot and consumes a lot of resources.

The implementation of this dynamic array is the implementation of a class. The idea of the whole process is clear, the calling function in the main function is clear and obvious, and the grasp of the class is also improved.

Develop the good habit of Typing Code:

• Generally, the class and main function are written into two classes separately
• debug idea: find process errors: output each step
  • In each output, add some Chinese identification sentences, which is more convenient to view when outputting