Array definition and basic operations of data structures
The most basic structure in the data structure is the linear structure, and the linear structure is divided into continuous storage structure and discrete storage structure. The so-called continuous storage structure is actually an array.
Arrays are essentially also a way to store data. Since there is data storage, it involves the issue of how to address data. First, let’s talk about how data is stored in an array. In memory, the data in the array exists in memory as a continuous set of data. When we access an array that exists in memory, we should find its address in memory. When we find the address of the data, we can find the corresponding data. After understanding the above knowledge, we can design the array (we can design our own array for others to use, haha).
After understanding the above knowledge, the first question arises. How can we find the address of the data in memory? This problem is actually very simple, because an array is a continuous set of data in memory, so we only need to know the first address of the array, and then add or subtract the corresponding byte length to find the data of the number of bytes. With these, we can define our array. However, as a reasonable array, we should also have the flag len of the array length and the flag cnt of the valid elements of the array. This gives the definition of the array (in this example, the structure is used. Friends who don’t know about the structure can check it out)
struct Arr
{
int *pBase; //Storing the address of the first element of the array int len; //The maximum number of elements that the array can hold int cnt; //The number of valid elements of the array
};
The above code defines a struct Arr structure, which is an array, which contains members that store the first address of the array element, and members that store the length of the array and the number of valid elements of the array.
After defining the structure, it should involve basic operations on the array, including initialization of the array, determining whether the array is empty, displaying the array, determining whether the array is full, appending an element to the last array, and inserting the array elements. Among them, the main algorithm is to insert array elements. The core of the insertion algorithm is to first move the elements after the inserted and inserted positions back, and then insert the empty position into the element we want to insert. Here is the implementation of C language:
/*
Array initialization function
Initialization is just to give an array of a certain length, but there is no valid value in the array
*/
void init_arr(struct Arr * pArr,int len)
{
pArr->pBase=(int *)malloc(sizeof(int)*len);
if(NULL==pArr->pBase){
printf("Dynamic memory allocation failed");
exit(-1); //Terminate the entire program }
else{
pArr->len=len;
pArr->cnt=0;
}
}
/*
Functions that determine whether an array is empty
*/
int is_empty(struct Arr * pArr){
if(pArr->cnt==0){
return 0; //0 means true }
else{
return 1; //1 represents false }
}
/*
Array output display function
When performing array output, you should first determine whether the array is empty
*/
void show_arr(struct Arr * pArr){
if(is_empty(pArr)==0){
printf("The current array is empty!");
}
else{
int i;
for(i=0; i<pArr->cnt; ++i){
printf("%d ",pArr->pBase[i]);
}
printf("\n");
}
}
/*
Function that determines whether the array is full
*/
int is_full(struct Arr * pArr){
if(pArr->cnt==pArr->len){
return 0; //0 means true, indicating full }
else{
return 1; //1 represents false, indicating that it is not full }
}
/*
Append an element to the end of the array
Before appending an array element, you must determine whether the current array is full. If it is full, you are not allowed to add new elements.
*/
int append_arr(struct Arr *pArr,int val){
if(is_full(pArr)==0){
return 0;
}
else{
pArr->pBase[pArr->cnt]=val;
pArr->cnt++;
return 1;
}
}
/*
Insert elements at the specified location of the array
Insert algorithm: First move all the elements in the inserted position backwards, and then insert the empty position.
According to the principle of the algorithm, therefore, when inserting, you should check whether the array is full.
When both of the above situations are reasonable, data is inserted. When inserting, if the third position is inserted, the data is actually assigned to arr[pos-1]
Note: When moving the element after the insertion position backward, it should move from back to forward. Otherwise, the value of the position "moved to" will be overwritten.
*/
int insert_arr(struct Arr *pArr,int pos,int val){
if(is_full(pArr)==0){
return 0; //0 means that the current array is full and no longer inserted }
//When the array is inserted, the pos position value entered by the user should be checked to see if the user has reasonable pos position value entered if(pos<0||pos>(pArr->len)){
return 1; //1 means that the current user insertion position is illegal }
//Move position int i;
for(i=pArr->cnt -1;i>=pos-1;--i){
pArr->pBase[i+1]=pArr->pBase[i];
}
//Insert element at the vacant position pArr->pBase[pos-1]=val;
return 2; //2 means that the current insertion is successful}
Thank you for reading, I hope it can help you. Thank you for your support for this site!