"Data structure" course is equivalent to "data structure and algorithm" most of the time, so we generally say that data structure will involve algorithm< Data structure requires students to complete complex programming according to the data structure theory. To improve the ability of program design, we must learn, observe, draw lessons from and practice.

When reading this article, you should have a certain C/C + + programming foundation, and be able to understand pointers and structs.

1, Overview of data structure

1. The concept of data structure and algorithm

We store complex problems in the computer memory with specific data types (real individuals) and specific storage structures (relationships between real individuals). We call this "specific storage structure" data structure. On the basis of this data structure, the corresponding operation for a certain function (such as search, delete, sort) is called algorithm.

We can simply understand it as: data structure = individual + individual relationship, algorithm = operation of stored data.

2. The standard to measure the algorithm

Through 1, we call the method and step of data processing algorithm. The standard of algorithm includes the following aspects

• Time complexity: the approximate number of times a program will be executed, not the execution time
• Space complexity: the maximum memory occupied during the execution of the algorithm
• Degree of difficulty
• Robustness

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

3. The position of data structure in program development

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

We can understand it as: program = data storage + data operation (algorithm) + language that can be executed by 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 linear table)

• Continuous storage
• Discrete storage [linked list]
• One of the two common applications of linear structure stack
• Two common applications of linear structure -- queue

(2) Nonlinear structure

• tree
• chart

2, Data structure and basic algorithm of continuous storage

In data structure, the object of our research is data, followed by the method and step of operating data. Today, we start from the continuous storage in linear structure, and re recognize the data structure from the perspective of code.

Continuous storage is actually a continuous storage structure. We can understand that array is the implementation of continuous storage. Next, we define the data structure of continuous storage through the struct keyword of C language, here we call it array, and study its basic algorithm.

Continuous storage structure is easy to realize the operation of element tracing and reading the i-th element in linear table; However, in the implementation of 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 and student status table.

1. Define array

First of all, we define a 01-Arr.cpp file. We need to introduce the basic c language header file, as follows

# Include < stdio. H > / / standard io header, including printf function
# Include < malloc. H > / / include malloc function. On mac, change to sys/malloc.h
# Include < stdlib. H > / / include exit function

Next, we define the structure of the array. The data type contains three members, pBase, len and cnt. The code is as follows

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

2. Initialize array

Next, we define the function to initialize the array, and dynamically allocate memory according to the length of the array to store the corresponding array elements. The code is as follows

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

3. Determine whether the array is empty or full

We can determine whether the array is empty or full according to the effective elements and total elements of the current array, and define the following two functions

// Determine whether the array is empty
bool is_empty(struct Arr *pArr)
{
    // The valid number of the array is 0, that is, the array is empty
    if (0 == pArr->cnt)
    {
        return true;
    }
    // Otherwise, the array is not empty
    else
    {
        return false;
    }
}
// Determine whether the array is full
bool is_full(struct Arr *pArr)
{
    // The effective number of an array is the length of the array, that is, the array is full
    if (pArr->cnt == pArr->len)
    {
        return true;
    }
    // Otherwise, the array is not full
    else
    {
        return false;
    }
}

4. Traverse array elements

The purpose of traversing the array is to print every valid array element to the terminal. According to the current valid number of array, traverse and print each element, we define the following code

// Traversing arrays
void traverse_arr(struct Arr *pArr)
{
    for (int i = 0; i < pArr->cnt; i++)
    {
        printf("%d\t", pArr->pBase[i]);
    }
    printf("\n");
}

5. Add array elements

Appending is to add elements at the end of an array that is not full, as shown in the following code

bool append_arr(struct Arr *pArr, int val)
{
    // Returns false if the array is full
    if (is_full(pArr))
    {
        return false;
    }
    // The array is appended when it is not full
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true;
}

6. Insert element

In addition to appending an array, there is also an array insert operation. Insert means to add data at a specific location. The code is as follows

bool insert_arr(struct Arr *pArr, int pos, int val)
{
    // Returns false if the array element is full
    if (is_full(pArr))
    {
        return false;
    }
    // If the position to be inserted is not correct, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // From the position of the last element to the position to be inserted, move the array elements back one bit one by one
    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;
    // Mark the fields of the valid elements of the array plus 1
    (pArr->cnt)++;
    return true;
}

7. Delete element

Delete operation is similar to insert operation, the difference is: when inserting data, start from the insert position, move the following data back, and add elements at the insert position; When deleting data, we need to start at the last bit of the deletion position, and all the subsequent data will move forward, and the data at the deletion position will be covered, as shown in the following code

bool delete_arr(struct Arr *pArr, int pos, int *pVal)
{
    // Returns false if the array element is full
    if (is_full(pArr))
    {
        return false;
    }
    // If the position to be inserted is not correct, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // Assign the value of the deleted element to the passed in pointer variable
    *pVal = pArr->pBase[pos];
    // Move the array elements forward one by one from the position to be deleted to the last position
    for (int i = pos; i < pArr->cnt; ++i)
    {
        pArr->pBase[i] = pArr->pBase[i + 1];
    }
    pArr->cnt--;
    return true;
}

8. Array inversion

The operation of array inversion is to replace the first and last element of the array, the second and last element, 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;
}

9. Array sorting

Next is a simple sorting process, with two loops in the function. In the first layer of loop, select the element at the current position (starting from the position with index 0, that is, before the loop, the current position is the first element). In the second layer of loop, start from the next element of the element at the current position until the last element, compare the size with the element at the current position one by one, and replace the small element to the current position each time.

At the end of the first cycle, the position with index 0 will be the smallest element, at the end of the second cycle, the position with index 1 will be the second smallest element, and so on. Finally, the array elements will be arranged from small to large, as follows

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;
            }
        }
    }
}

3, Testing and verification

Finally, all the test codes are as follows

#include <stdio.h>
#include <sys/malloc.h> // Using # include < malloc. H > in windows
#include <stdlib.h>

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

// Initialize 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 failure");
        exit(-1);
    }
    // Memory allocation successful
    pArr->len = length;
    pArr->cnt = 0;
    return;
}

// Determine whether the array is empty
bool is_empty(struct Arr *pArr)
{
    // The valid number of the array is 0, that is, the array is empty
    if (0 == pArr->cnt)
    {
        return true;
    }
    // Otherwise, the array is not empty
    else
    {
        return false;
    }
}

// Determine whether the array element is full
bool is_full(struct Arr *pArr)
{
    // The effective number of an array is the length of the array, that is, the array is full
    if (pArr->cnt == pArr->len)
    {
        return true;
    }
    // Otherwise, the array is not full
    else
    {
        return false;
    }
}

// Traversing arrays
void traverse_arr(struct Arr *pArr)
{
    for (int i = 0; i < pArr->cnt; i++)
    {
        printf("%d\t", pArr->pBase[i]);
    }
    printf("\n");
}

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

// Insert array (element)
bool insert_arr(struct Arr *pArr, int pos, int val)
{
    // Returns false if the array element is full
    if (is_full(pArr))
    {
        return false;
    }
    // If the position to be inserted is not correct, return false
    if (pos < 0 || pos > pArr->cnt)
    {
        return false;
    }
    // From the position of the last element to the position to be inserted, move the array elements back one bit one by one
    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;
    // Mark the fields of the valid elements of the array plus 1
    (pArr->cnt)++;
    return true;
}

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

// Inverted 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 sorting
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()
{
    struct Arr arr;
    // Initializes an array of length 6
    init_arr(&arr, 6);

    // Additional 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 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 inversion
    inverse_arr(&arr);
    traverse_arr(&arr); // The output is 4 3 2 1

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

    return 0;
}

This article originally started from wx subscription number: geek development up, prohibit reprint