The course “Data Structures” is mostly equivalent to “Data Structures and Algorithms”, so when we say data structures, we usually involve algorithms. “Data Structure” this course requires students to be able to complete complex programming according to the data structure theory they have learned. And the improvement of program design ability, must have the process of study, observation, reference and practice.

By the time you read this article, you should have some basic C/C++ programming knowledge and an understanding of Pointers and structs.

Overview of data structure

1. Concepts of data structure and algorithm

We store real complex problems in computer memory as specific data types (real individuals) and specific storage structures (relationships between real individuals). We call these “specific storage structures” data structures. The operations performed on the basis of this data structure for some function (such as find, delete, sort) are called algorithms.

We can simply understand as: data structure = individual + individual relationship, algorithm = operations on stored data.

2. Criteria for measuring algorithms

By 1, we call the methods and steps used to process data algorithms. The criteria to measure the algorithm include the following aspects:

  • Time complexity: The approximate number of times the program should be executed, not the time of execution
  • Space complexity: The maximum amount of memory used during the execution of an algorithm
  • How easy is it
  • Robustness,

The core content of algorithm is to study the time complexity and space complexity of algorithm.

3. The role of data structures in program development

Data structure is the core of software engineering. In the actual program development, we will use various programming languages to carry out corresponding functional operations on various data, such as storage, query, deletion, or more complex operations. Therefore, to a certain extent, the data structure foundation determines the individual’s comprehensive ability in program development.

We can think of it as: program = data storage + data operations (i.e., algorithms) + language that can be executed by a computer.

4. Basic module of data structure

In order to facilitate our future study, this paper lists the basic knowledge modules of data structure as follows

(1) Linear structure (we can call it a linear table)

  • Sequential storage [array]
  • Discrete storage [linked list]
  • One of the two common applications of linear structures is —— stack
  • Two common applications of linear structures are —— queues

(2) Nonlinear structure

  • The tree
  • figure

Second, continuous storage data structure and basic algorithms

In data structure, the object of our study is data, followed by the methods and steps of data manipulation. Today, we’re going to start with continuous storage in linear structures, rethinking data structures from a code point of view.

Continuous storage is actually a continuous storage structure, and we can understand that arrays are the implementation of continuous storage. Next, we define the continuous storage of this data structure through the STRUCt keyword of C language, which is called array here, and study its basic algorithm.

The continuous storage structure is easy to realize the operation of chasing the element and reading the ith element in the linear table. However, when implementing insert and delete operations, a large number of elements need to be moved. Therefore, it is suitable for storing relatively stable linear tables, such as employee salary table, student status table.

1. Define arrays

First we define a 01-arr. CPP file, need to introduce the basic C language header file, the following code

# include <stdio.h> // The standard IO header contains the printf function
# include <malloc.h> // contains the malloc function. On Macs, change to sys/malloc.h
# include <stdlib.h> // contains the exit function
Copy the code

Next we define the structure of the array. This data type contains three members, pBase, len, and CNT, as shown in the following code

struct Arr
{
    int *pBase; // Store the address of the first element of the array
    int len;    // The maximum number of elements an array can hold
    int cnt;    // The number of valid elements in the current array
};
Copy the code

2. Initialize the array

Next, we define a function that initializes the array and dynamically allocates memory based on the size of the array to store the corresponding array elements

void init_arr(struct Arr *pArr, int length)
{
    // Allocate memory pBase according to the length of the array
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase)
    {
        printf("Dynamic memory allocation failed");
        exit(- 1);
    }
    // Memory allocation succeeded
    pArr->len = length;
    pArr->cnt = 0;
    return;
}
Copy the code

3. Check whether the array is empty or full

We can determine whether an array is empty or full based on its valid elements and total elements. We define the following two functions

// Check whether the array is empty
bool is_empty(struct Arr *pArr)
{
    // The valid number of arrays is 0, that is, the array is empty
    if (0 == pArr->cnt)
    {
        return true;
    }
    // Otherwise, the array is not empty
    else
    {
        return false; }}// Check whether the array is full
bool is_full(struct Arr *pArr)
{
    // The valid number of arrays is the length of the array, i.e. the array is full
    if (pArr->cnt == pArr->len)
    {
        return true;
    }
    // Otherwise, the array is not full
    else
    {
        return false; }}Copy the code

4. Iterate over the array elements

The purpose of traversing an array is to print every valid array element to the terminal. To iterate over and print each element based on the current number of valid elements in the array, we define the following code

// go through the number group
void traverse_arr(struct Arr *pArr)
{
    for (int i = 0; i < pArr->cnt; i++)
    {
        printf("%d\t", pArr->pBase[i]);
    }
    printf("\n");
}
Copy the code

5. Append array elements

Append is to add elements to the end of an unfilled array, as shown in the following code

bool append_arr(struct Arr *pArr, int val)
{
    // If the array is full, return false
    if (is_full(pArr))
    {
        return false;
    }
    // Append if the array is not sufficient
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true;
}
Copy the code

6. Insert elements

In addition to append arrays, there are also array insert operations, which add data at a specific location, as shown in the following code

bool insert_arr(struct Arr *pArr, int pos, int val)
{
    // If the array element is full, return false
    if (is_full(pArr))
    {
        return false;
    }
    // If you want to insert in the wrong position, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // Start at the last element position and move the array elements one by one to the position to be inserted
    for (int i = pArr->cnt - 1; i >= pos; --i)
    {
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    // Assign the inserted value to the specified position
    pArr->pBase[pos] = val;
    // The field that marks the valid element of the array is incremented by 1
    (pArr->cnt)++;
    return true;
}
Copy the code

7. Delete elements

The deletion operation is similar to the insert operation, but the difference is that: When inserting data, it starts from the insert position, moves the following data backward, and adds elements at the insert position. When deleting data, we need to start at the last bit of the deleted position, and the data after the deleted position will be overwritten, as shown in the following code

bool delete_arr(struct Arr *pArr, int pos, int *pVal)
{
    // If the array element is full, return false
    if (is_full(pArr))
    {
        return false;
    }
    // If you want to insert in the wrong position, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // Assign the value of the deleted element to the pointer variable passed in
    *pVal = pArr->pBase[pos];
    // Move the array elements forward one by one, starting at the location to be deleted and continuing to the last location
    for (int i = pos; i < pArr->cnt; ++i)
    {
        pArr->pBase[i] = pArr->pBase[i + 1];
    }
    pArr->cnt--;
    return true;
}
Copy the code

8. Array inversion

The inversion of an array involves substituting the first and last bits of the array, the second and second-to-last bits, and so on. Finally complete the inversion, the following code

void inverse_arr(struct Arr *pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int t;
    while (i < j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }
    return;
}
Copy the code

9. Array sort

This is followed by a simple sorting process with two layers of loops in the function. The first layer circulation, select the current position of the element (starting from the position of the index of 0, namely before cycle, the current position is the first element), in the second cycle, from the current position of the elements of the next element, until the last element, each size compared with the current position of the element, with each comparison to replace the small elements into the current position.

At the end of the first cycle, position 0 will be the smallest element, at the end of the second cycle, position 1 will be the next smallest element, and so on. Finally, the elements of the array are sorted from smallest to largest, as shown in the following code

void sort_arr(struct Arr *pArr)
{
    int i, j, t;
    for (i = 0; i < pArr->cnt; i++)
    {
        for (j = i + 1; j < pArr->cnt; j++)
        {
            if(pArr->pBase[i] > pArr->pBase[j]) { t = pArr->pBase[i]; pArr->pBase[i] = pArr->pBase[j]; pArr->pBase[j] = t; }}}}Copy the code

Iii. Test and verification

The final test code is as follows

#include <stdio.h>
#include <sys/malloc.h> #include 
       
#include <stdlib.h>

// Define an array structure
struct Arr
{
    int *pBase; // Store the address of the first element of the array
    int len;    // The maximum number of elements an array can hold
    int cnt;    // The number of valid elements in the current array
};

// Initialize the array
void init_arr(struct Arr *pArr, int length)
{
    // Assign allocated memory to pBase
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase)
    {
        printf("Dynamic memory allocation failed");
        exit(- 1);
    }
    // Memory allocation succeeded
    pArr->len = length;
    pArr->cnt = 0;
    return;
}

// Check whether the array is empty
bool is_empty(struct Arr *pArr)
{
    // The valid number of arrays is 0, that is, the array is empty
    if (0 == pArr->cnt)
    {
        return true;
    }
    // Otherwise, the array is not empty
    else
    {
        return false; }}// Check whether the array elements are full
bool is_full(struct Arr *pArr)
{
    // The valid number of arrays is the length of the array, i.e. the array is full
    if (pArr->cnt == pArr->len)
    {
        return true;
    }
    // Otherwise, the array is not full
    else
    {
        return false; }}// go through the number group
void traverse_arr(struct Arr *pArr)
{
    for (int i = 0; i < pArr->cnt; i++)
    {
        printf("%d\t", pArr->pBase[i]);
    }
    printf("\n");
}

// Append an array (element)
bool append_arr(struct Arr *pArr, int val)
{
    // Array full returns false
    if (is_full(pArr))
    {
        return false;
    }
    // Append when the array is insufficient
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true;
}

// Insert array (element)
bool insert_arr(struct Arr *pArr, int pos, int val)
{
    // If the array element is full, return false
    if (is_full(pArr))
    {
        return false;
    }
    // If you want to insert in the wrong position, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // Start at the last element position and move the array elements one by one to the position to be inserted
    for (int i = pArr->cnt - 1; i >= pos; --i)
    {
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    // Assign the inserted value to the specified position
    pArr->pBase[pos] = val;
    // The field that marks the valid element of the array is incremented by 1
    (pArr->cnt)++;
    return true;
}

// Delete array (element)
bool delete_arr(struct Arr *pArr, int pos, int *pVal)
{
    // If the array element is full, return false
    if (is_full(pArr))
    {
        return false;
    }
    // If you want to insert in the wrong position, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // Assign the value of the deleted element to the pointer variable passed in
    *pVal = pArr->pBase[pos];
    // Move the array elements forward one by one, starting at the location to be deleted and continuing to the last location
    for (int i = pos; i < pArr->cnt; ++i)
    {
        pArr->pBase[i] = pArr->pBase[i + 1];
    }
    pArr->cnt--;
    return true;
}

// Invert array (element)
void inverse_arr(struct Arr *pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int t;
    while (i < j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }
    return;
}

// Array sort
void sort_arr(struct Arr *pArr)
{
    int i, j, t;
    for (i = 0; i < pArr->cnt; i++)
    {
        for (j = i + 1; j < pArr->cnt; j++)
        {
            if(pArr->pBase[i] > pArr->pBase[j]) { t = pArr->pBase[i]; pArr->pBase[i] = pArr->pBase[j]; pArr->pBase[j] = t; }}}}// Main function test
int main(a)
{
    struct Arr arr;
    // Initialize an array of length 6
    init_arr(&arr, 6);

    // Appends elements
    append_arr(&arr, 1);
    append_arr(&arr, 2);
    append_arr(&arr, 3);
    append_arr(&arr, 4);

    traverse_arr(&arr); // The output is 1, 2, 3, 4

    // Insert 6 at index 0
    insert_arr(&arr, 0.5);
    traverse_arr(&arr); // The output is 5, 1, 2, 3, 4

    // Delete the element at index 0
    int delval; // Used to receive deleted elements
    delete_arr(&arr, 0, &delval);
    traverse_arr(&arr); // The output is 1, 2, 3, 4

    // Array inverted
    inverse_arr(&arr);
    traverse_arr(&arr); // The output is 4, 3, 2, 1

    // Array sort
    sort_arr(&arr);
    traverse_arr(&arr); // The output is 1, 2, 3, 4

    return 0;
}
Copy the code

This article originally appeared on WX Subscription number: Geek Development up