I’ve been studying C recently, trying to implement a dynamic array. There are six basic functions of arrays:

  • Initialize the
  • insert
  • increase
  • Modify the
  • The query
  • Remove elements

Before initialization, we first need to define an array structure called dynamic_array

The three most basic elements of an array

  1. Int m_capacity,
  2. The actual length int m_size,
  3. Content (Since arrays can be filled with any type of element, the basic element is void *, and our array contains multiple elements, which we put into one address)
void * void * void * void * void *

Let’s say we have five elements, and we have one address to hold the addresses of those five elements, so we also need a void **pAddr element

struct dynamic_array{

    void** pAddr;

    int m_capacity;

    int m_size;

};
Copy the code

1. Initialization

When we initialize the array, we need to give a default maximum capacity, which is m_capacity. Our return value is our array structure, so our method is defined as:

struct dynamic_array * init_array(int capacity){

    if(capacity <= 0) {return NULL;
    }

    return NULL;

};
Copy the code

Then we need to open up the required memory and set the default values

struct dynamic_array * init_array(int capacity){

    if(capacity <= 0) {return NULL;

    }

    struct dynamic_array *array = malloc(sizeof(struct dynamic_array));

    if(array= =NULL) {return NULL;
    }
    
    void **pAddr = malloc(sizeof(void *) * capacity);

    if(pAddr == NULL) {return NULL;
    }

    array->pAddr = pAddr;

    array->m_capacity = capacity;

    array->m_size = 0;

    return array;

};
Copy the code

2. Insert

We need to make a simple judgment before we insert the data at the specified location based on the given array

void insert_array(struct dynamic_array *array.int pos){

    if(array= =NULL) {return;
    }

    if(pos < 0 || pos > array->m_size){
        return; }}Copy the code

If the current m_size is as large as the maximum size, you need to consider expanding it

if(array->m_size == array->m_capacity){

        int new_capacity = array->m_capacity * 2;

        // Open up new space
        void **new_pAddr = malloc(sizeof(void *) * new_capacity);
        // Copy the original data to the new address
        memcpy(new_pAddr, array->pAddr, sizeof(void *) * array->m_capacity);
        // Release the original address
        free(array->pAddr);
        // Change the capacity and the new array address
        array->m_capacity = new_capacity;

        array->pAddr = new_pAddr;

}
    
array->m_size += 1;
Copy the code

When new data is inserted into the array with or without expansion, the value of the data after the inserted position is moved one bit further back, and the inserted data is placed directly at the specified position

for(int i = array->m_size - 1; i > pos; i--){array->pAddr[i+1] = array->pAddr[i];

}

array->pAddr[pos] = data;
Copy the code

The complete insert code is as follows:

void insert_array(struct dynamic_array *array.int pos, void *data){

    if(array= =NULL) {return;
    }

    if(data == NULL) {return;
    }

    if(pos < 0 || pos > array->m_size){
        return;
    }

    if(array->m_size == array->m_capacity){

        int new_capacity = array->m_capacity * 2;

        void **new_pAddr = malloc(sizeof(void *) * new_capacity);

        memcpy(new_pAddr, array->pAddr, sizeof(void *) * array->m_capacity);

        free(array->pAddr);

        array->m_capacity = new_capacity;

        array->pAddr = new_pAddr;

    }

    array->m_size += 1;

    for(int i = array->m_size - 1; i > pos; i--){array->pAddr[i+1] = array->pAddr[i];

    }

    array->pAddr[pos] = data;

}
Copy the code

3. Add elements

This one is easier, just insert it at the end of the data

void add_array(struct dynamic_array *array.void *data){

    if(array= =NULL) {return;
    }

    if(data == NULL) {return;
    }

    insert_array(array.array->m_size, data);

}
Copy the code

4. Modify elements

You can just replace it at the specified location

void update_array(struct dynamic_array *array.int pos, void *data){

    if(array= =NULL) {return;
    }

    if(data == NULL) {return;
    }

    if(pos < 0 || pos >= array->m_size){
        return;
    }

    array->pAddr[pos] = data;

}
Copy the code

5. Delete elements

Delete element is special, if the specified position is deleted, the following element needs to be added, also need -1 m_size. The code is as follows:

void delete_array(struct dynamic_array *array.int pos){

    if(array= =NULL) {return;
    }

    if(pos < 0 || pos >= array->m_size){
        return;
    }

    if(pos == array->m_size - 1) {// If the last element is deleted, you need to avoid overstepping the bounds
        array->pAddr[pos] = NULL;
    }else{
        for(inti=pos; i<array->m_size - 1; i++){// Put the value of the element to the previous position
            array->pAddr[i] = array->pAddr[i+1]; }}// Update the array length
    array->m_size -= 1;

}
Copy the code

6. Query elements

We can query the specific value according to the specified position, and the code is as follows:

void * search_array(struct dynamic_array *array.int pos){

    if(array= =NULL) {return NULL;
    }

    if(pos < 0 || pos >= array->m_size){
        return NULL;
    }
    
    return array->pAddr[pos];

}
Copy the code

Now that we’ve implemented the basic add, delete, change, and query functionality for an array, let’s test it out

// Initialize the array

    struct dynamic_array *array = init_array(2);

    // Add a new element
    add_array(array, (void *)1);
    add_array(array, (void *)10);
    add_array(array, (void *)100);
    
   // we can see that the array has three elements: 1,10,100
   // Let's modify the element with subscript 1
   update_array(array.1, (void *)200);
   // By printing we can see that the array has three elements, 1,200,100
   
   // We delete the last two elements, leaving only the first element
   delete_array(array.1);
   delete_array(array.1);
   
   // This is not recommended
   int num = (int)array->pAddr[0];
   
Copy the code

Through detection, it is found that the basic functions are normal, and the overall idea is no problem.