Hello ~ I'm bay_Tong tongxiaobai
The content of this article is Tong Xiaobai's personal summary and sharing of the knowledge learned. The knowledge points will be edited, updated and improved from time to time. For the latest updated content, please refer to the update log. You are welcome to leave messages and suggestions

[update log]

Recent updates:

• There is no editing content, and it is constantly updating

Requirements for 408 syllabus of computer unified examination

2021 computer unified examination 408 outline data structure discipline investigation objectives

• Master the basic concepts, principles and methods of data structure
• Master the logical structure, storage structure and implementation of basic operations of data structure, and be able to analyze the basic time complexity and space complexity of the algorithm
• Be able to use the basic principles and methods of data structure to analyze and solve problems, and have the ability to design and implement algorithms in C or C + + language

Changes in data structure syllabus of 408 computer unified examination in 2021

overview

Data structure: the way in which a computer stores and organizes data

Different data structures have their corresponding application scenarios, which aims to reduce the time and space complexity of various algorithms and achieve the best task execution efficiency

Basic classification:

Linear data structure: non empty set; There is only one start and one terminal; All nodes have at most one direct precursor and one direct successor. [in short, one-to-one in logical relationship]

Nonlinear data structure: non empty set; Each node may have multiple direct precursors or multiple direct successors. [in short, i.e. one to many or many to many in logical relationship]

Common linear data structures

array

Array: a data structure in which elements of the same type are stored in continuous memory space, which can be accessed randomly through array subscripts, and the array size is fixed

Variable array: Based on array and capacity expansion mechanism, it is more flexible than ordinary array. Common operations include: accessing elements, adding elements and deleting elements

//C
int array[1] = {0};
//Add elements and expand array size
array = (int*)realloc(array,sizof(int)*5);
array[1] = 10;
/* realloc()Function syntax:
Pointer name = (data type *) realloc (pointer name to change memory size, new size)
For the newly applied array size, if the new one is larger than the original memory size, the newly allocated part will not be initialized; If the new size is smaller than the original memory size, data loss may occur
 Header file: #include < stdlib h> Some compilers require #include < malloc h>
*/

//C++
vector<int> array;
//Add element to tail
array.push_back(10);

Linked list

Linked list: in the unit of nodes, each data element needs to store its direct predecessor or direct successor address information in addition to its own information

//C
struct ListNode {
    int data;        // Node data
    ListNode* next; // Successor node address
};

struct ListNode* n1 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
n1->data = 1;	n1->next = n2;
n2->data = 10;	n2->next = n3;
n3->data = 100;	n3->next = NULL;

//C++
struct ListNode {
    int data;        // Node data
    ListNode* next; // Successor node address
    ListNode(int x) : data(x) , next(NULL) {} //Constructor
};

ListNode* n1 = new ListNode(1);
ListNode* n2 = new ListNode(10);
ListNode* n3 = new ListNode(100);
n1->next = n2;	n2->next = n3;

[see the article in this column for the detailed knowledge of arrays and linked lists Summary of linear table - Summary of key points of basic knowledge]

Stack

Stack: a data structure that performs insert and delete operations (called stack in and stack out) only at one end (stack top). It has the characteristics of first in first out [FILO] and last in first out [LIFO]. It can be implemented by array or linked list

//C++
stack<char> s;
s.push('A');	s.push('B');	s.push('C');
s.pop();

queue

Queue: a data structure that is inserted only at one end (tail of the queue) and deleted (called queue in and queue out) at the other end (head of the queue). It has the characteristics of first in first out [FIFO], then in and then out [LILO]. It can be implemented by array or linked list

//C++
queue<int> q;
q.push(0);	q.push(1);	q.push(2);	q.push(3);	q.push(4);	q.push(5);
q.pop();

[see the article in this column for details of stack and queue Stack and queue Summary - Summary of basic knowledge points]

Common nonlinear data structures

tree

The commonly used tree structure is binary tree. Each node contains node value, left child node address and right child node address

//C
struct TreeNode {
    char data;         // Node value
    TreeNode* left;  // Left child node
    TreeNode* right; // Right child node
};

struct TreeNode* n1 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n2 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n3 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n4 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n5 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
n1->data = 'A';	n1->left = n2;	n1->right = n3;
n2->data = 'B';	n2->left = n4;  n2->right = n5;
n3->data = 'C';	n3->left = NULL; n3->right = NULL;
n4->data = 'D';	n4->left = NULL; n4->right = NULL;
n5->data = 'E';	n5->left = NULL; n5->right = NULL;

//C++
struct TreeNode {
    char data;         // Node value
    TreeNode* left;  // Left child node
    TreeNode* right; // Right child node
    TreeNode(int x) : data(x), left(NULL), right(NULL) {}//Constructor
};

TreeNode* n1 = new TreeNode('A');
TreeNode* n2 = new TreeNode('B');
TreeNode* n3 = new TreeNode('C');
TreeNode* n4 = new TreeNode('D');
TreeNode* n5 = new TreeNode('E');
n1->left = n2;  n1->right = n3;
n2->left = n4;  n2->right = n5;

[detailed knowledge of tree structure can be found in this column Tree and binary tree Summary - Summary of basic knowledge points]

heap

Heap: a data structure based on complete binary tree, which can be realized by array. Heap is divided into large top heap and small top heap. Large (small) top heap: the value of any node is not greater than (less than) the value of its parent node

Take the example in leetcode graphical algorithm data structure as an example:

As shown in the following figure, it is a small top heap containing elements 1, 4, 2, 6 and 8. By numbering the nodes in the heap (complete binary tree) by layer, you can map them to the array storage form on the right

//C++
// Initialize small top heap
priority_queue<int, vector<int>, greater<int>> heap;

// Element heap
heap.push(1);
heap.push(4);
heap.push(2);
heap.push(6);
heap.push(8);

// Element out of heap (from small to large)
heap.pop(); // -> 1
heap.pop(); // -> 2
heap.pop(); // -> 4
heap.pop(); // -> 6
heap.pop(); // -> 8

Author: kretas
Link: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
Source: LeetCode

Hash table

Hash table: the hash function is used to map the specified key to the corresponding value to achieve efficient element lookup

Take the example in leetcode graphical algorithm data structure as an example:

Imagine a simple scenario: the student numbers of Xiaoli, xiaote and Xiaokou are 10001, 10002 and 10003 respectively; Now you need to find "student number" from "name"
This requirement can be achieved by creating a hash table with the name of key and the student number of value

Author: kretas
Link: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
Source: LeetCode

chart

Figure: it is composed of nodes (vertices) and edges, and each edge connects a pair of vertices

Adjacency matrix representation: it is represented by a two-dimensional array. For example, G [i] [j] represents an edge from I to j. if there is an edge in the weighted graph, the value of G [i] [j] is 1, otherwise it is 0. If there is an edge in the weighted graph, the value can be the weight of the edge, and if there is no edge, it is infinite, which is represented by a large number

//C++
int vertices[5] = { 0, 1, 2, 3, 4 };
int edges[5][5] = { {0, 1, 0, 1, 0},
                    {1, 0, 1, 0, 1},
                    {0, 1, 0, 1, 1},
                    {1, 0, 1, 0, 0},
                    {0, 1, 1, 0, 0} };

Adjacency table representation: use an array to store all vertices in the graph. Each vertex (array cell) has a single linked list to store all its associated edges

[see the article in this column for the detailed knowledge of figure structure Summary of drawings - Summary of key points of basic knowledge]

Continuously updating
I'm Tong Xiaobai, a computer Xiaobai