What is the data structure in c language? What are the common data structures?

In the C language, a data structure refers to a collection of data elements that have one or more specific relationships with each other. It is a way for computers to store and organize data; common data structures include: linear data structures ( Array, linked list, stack, queue and linear list), tree structure (binary tree, complete binary tree, binary search tree, heap), graph structure (directed graph and undirected graph).

The operating environment of this tutorial: windows7 system, c99 version, Dell G3 computer.

What is a data structure?

Data structure is the way computers store and organize data. A data structure refers to a collection of data elements that have one or more specific relationships with each other

The implementation of most data structures requires the help of pointers and structure types in the C language

Next, let’s get to today’s focus. O(∩_∩)O Several common data structures

(1) Linear data structure: There is generally a one-to-one relationship between elements, which is the most commonly used A type of data structure, typically: arrays, stacks, queues and linear tables

(2) Tree structure: There is a hierarchical relationship between nodes, and a node in each layer can and can only be combined with A node on the upper layer is related, but it can be related to multiple nodes on the next layer at the same time, which is called a "one-to-many" relationship. Common types are: tree, heap

(3) Graphic structure : In the graph structure, multiple nodes are allowed to be related, which is called a "many-to-many" relationship

The following is a brief introduction to each of these data structures:

1. Linear data structures: Typical ones are: arrays, stacks, queues and linear tables

(1) Arrays and linked lists

a. Array: stores a group of data of the same type. The length of the array needs to be specified in advance, such as one-dimensional array, two-dimensional array, multi-dimensional array, etc.

b. Linked list: Linked list is a type of C language A widely used structure, it is implemented in the form of dynamically allocated memory, using a set of arbitrary storage units to store a linked list of data elements. Generally, a pointer field is added for each element to point to subsequent elements

c, arrays The difference from a linked list:

From a logical structure perspective: arrays must have a fixed length defined in advance and cannot adapt to the dynamic increase or decrease of data; linked lists dynamically allocate storage and can adapt to the dynamic increase or decrease of data. situation, and can easily insert and delete data items (when inserting or deleting data items in the array, other data items need to be moved)

From the memory storage point of view: (static) the array allocates space from the stack (using NEW is created in the heap), which is convenient and fast for programmers, but has a small degree of freedom; linked lists allocate space from the heap, which has a large degree of freedom but is troublesome to apply for and manage.

From the perspective of access methods: the array is in memory It is stored continuously, so you can use subscript indexes for random access; the linked list is a linked storage structure, and elements can only be accessed sequentially from front to back in a linear manner, so the access efficiency is lower than that of arrays

(2) Stack, queue and linear table: sequential storage and chain storage methods can be used for storage

Sequential storage: with the help of the relative position of data elements in the storage space Position to represent the logical relationship between elements

Chain storage: Use pointers representing the storage addresses of data elements to represent the logical relationship between elements

a. Stack: only allowed at the end of the sequence Operations, stack operations can only be performed on the top of the stack. Generally, the stack is also called a last-in-first-out or first-in-last-out linear structure

Sequential stack: A stack using a sequential storage structure is called a sequential stack, that is, it needs A space with consecutive addresses is used to store the elements of the stack. The type of the sequential stack is defined as follows:

Chain stack: A stack using a chain storage structure is called a chain stack:

b. Queue: Only operations are allowed at both ends of the sequence. Generally, the queue is also called a first-in, first-out linear structure.
Circular queue: A sequential storage structure is used. Queue needs to allocate storage space according to the maximum possible length of the queue. Its type is defined as follows:

Chain queue: A queue using a chain storage structure is called a chain queue. Generally, it needs Setting the head and tail pointers is just the head and tail nodes of the linked list:

c. Linear table: allows operations at any position in the sequence. The operation position of the linear table is not restricted. Table operations are very flexible. Common operations include inserting and deleting at any location, and querying and modifying elements at any location

Sequential table: A linear table represented by a sequential storage structure is called a sequential table. A set of storage units with consecutive addresses is used to store the data elements of the linear table at one time, that is, the adjacent storage locations represent the sequence between two elements. In order to avoid moving elements, in order to avoid moving elements, generally only inserting and deleting elements at the end of the table is considered in the interface definition of the sequence table. The sequence table implemented in this way can also be called a stack table:

Linear lists: generally include singly linked lists, doubly linked lists, circular linked lists and two-way circular linked lists

Singly linked lists:

Double linked lists :

Comparison of two storage structures of linear tables:

Sequential tables:

Advantages: In sequential tables, logic is relatively Two adjacent elements are also physically adjacent, making it easier to search. The time complexity of accessing any element is O(1)

. Disadvantages: Not suitable for inserting or deleting elements at any position. Because elements need to be moved, the average time complexity is O(n)

Linked list:

Advantages: To insert or delete an element at any position of the link, you only need to modify the corresponding pointer, and there is no need to move the element; Dynamic allocation on demand, no need to pre-allocate a continuous empty space according to the maximum demand

Disadvantages: It is inconvenient to search. To find an element, you need to start from the head pointer and search along the pointer field, so the average time complexity is O(n)

2. Tree structure: There is a hierarchical relationship between nodes. A node in each layer can and can only be related to one node in the previous layer, but it can also be related to multiple nodes in the next layer. Nodes are related, which is called a "one-to-many" relationship. Common types are: tree, heap

(1) Binary tree: A binary tree is a recursive data structure that contains n (n>=0) nodes. A finite set of points. A binary tree has the following characteristics:

A binary tree can be an empty tree; each node of a binary tree has exactly two subtrees, one or two of which may be empty; each node in a binary tree The positions of the left and right subtrees cannot be reversed. If the positions of the two are changed, it will become another binary tree

(2) Complete binary tree: starting from the root, top to bottom, left to right, Each node of a full binary tree is numbered consecutively from 1 to n. If each node corresponds one-to-one with the nodes numbered from 1 to n in the full binary tree of depth k, it is called a complete binary tree

a. Use a sequential storage structure: use a one-dimensional array to store a complete binary tree. The number of the node is related to the subscript of the node (for example, the root is 1, then the left child of the root is 2i=21=2, and the right child is 2i 1=21 1=2)

##b. Adopt chain storage structure:

Binary linked list:

Trident linked list: Its node has one more pointer field parent than a binary linked list, which is used to execute the node's parents and facilitate the search for parent nodes

Comparison of two storage structures: For a complete binary tree, the sequential storage structure can not only save space, but also use the subscript value of the array element to determine the position of the node in the binary tree and the relationship between the nodes, but the sequential storage structure is used to store Generally, binary trees tend to waste space. The chain structure can overcome this shortcoming.

(3) Binary search tree: Binary search tree is also called binary sorting tree, or it is an empty binary tree, or it has the following characteristics: Characteristic binary tree:

a. If its left subtree is not empty, then the values ​​of all nodes on the left subtree are less than the value of the root node.

b. If its right If the subtree is not empty, then the values ​​of all nodes on the right subtree are greater than the value of the root node

c, and its left and right subtrees are also binary search trees

(4) Balanced binary tree: A balanced binary search tree is referred to as a balanced binary tree. A balanced binary tree is either an empty tree or a binary search tree with the following properties: its left subtree and right subtree are both balanced binary trees, and the left The absolute value of the difference between the heights of the subtree and the right subtree does not exceed 1

The imbalance and adjustment of the balanced binary tree can be summarized into the following four situations: LL type, RR Type, LR type, RL type

(5) Tree: A tree is a finite set containing n (n>=0) nodes. In any non-empty tree type: a. There is and is only one A specific node called the root

b. When n>1, the remaining nodes can be divided into m (m>0) mutually disjoint finite sets T1, T2,...,Tm, where Each set itself is a tree, and T1, T2,...,Tm are called subtrees of the root

(6) Heap: A heap is a complete binary tree with the following characteristics: all non-leaf nodes are no larger than (or no smaller than) its left and right child nodes. If all non-leaf nodes in the heap are not larger than their left and right child nodes, it is called a small top heap (small root heap). If all non-leaf nodes in the heap are not smaller than their left and right child nodes, it is called a large heap. Top heap (big root heap)

(7) Union-find: Union-find refers to a set composed of a set of disjoint subsets, denoted as: S= {S1,S2,S3,…,Sn}

(8) B-tree

3. Graph structure: In the graph structure, correlation between multiple nodes is allowed. It is called a "many-to-many" relationship and can be divided into directed graphs and undirected graphs

Tutorial recommendation: "c language tutorial video"

The above is the detailed content of What is the data structure in c language? What are the common data structures?. For more information, please follow other related articles on the PHP Chinese website!