Data structure refers to the collection of data elements, as well as the relationship between elements and the construction method. The relationship between elements is the logical structure of data, and the storage form of data and the relationship between elements is called a storage structure.
- Logical structure: interrelationships between elements
- Storage structure: element storage and mutual relationship storage
Linear table
Logical structure: There is a linear relationship between data elements, that is, “arranged one after another” Storage structure: sequential storage and chain storage
Stack and Queue
Logical structure: The logical structure of stack and queue is the same as that of linear table
Stack
A stack is a linear data structure that allows data storage and retrieval only by accessing one end of it. Features: Last In First Out (LIFO)
Queue
A queue is a first-in, first-out linear list that only allows elements to be inserted at one end of the list and deleted from the other end of the list.
Tips: In a queue, the end that allows elements to be inserted is called the tail of the queue, and the end that allows elements to be deleted is called the head of the queue.
String
A string is a finite sequence consisting only of characters, a linear list with a limited range.
tips: Generally recorded as S=a1a2a3…an’
Array
An array is an expansion of a fixed-length linear list in dimensions, that is, the elements in a linear list are also a linear list. Features:
- Fixed data elements
- Data elements have the same data type
- The subscript relationship of data elements has upper and lower bound constraints and the subscripts are ordered.
tips: Based on the above characteristics, data is suitable for sequential storage
Generalized table
A generalized list is a generalization of a linear list and is a finite sequence composed of 0 or more single elements or sublists.
Tree
A tree is a finite set of n (n>=0) nodes. When n=0, it is called an empty tree. In any non-empty tree (n>0), there is only one node called the root. The definition of tree is recursive, which shows the inherent characteristics of the tree itself, that is, a tree is composed of several subtrees, and subtrees are composed of smaller subtrees.
Binary tree
The subtree of a node in a binary tree must distinguish between the left subtree and the right subtree, that is, the maximum degree of the binary tree is 2.
- Properties of binary trees
-Number of nodes
- full binary tree
- Storage structure
- Complete binary trees are stored sequentially
- You can also use chained storage (three-pronged linked list, two-pronged linked list)
Binary tree traversal
Binary tree traversal is a process of visiting each node in the tree according to a certain strategy and only visiting it once. According to the writing method of traversing the left subtree first and then traversing the right subtree, depending on the location of the root node visited, three traversal methods of binary trees can be obtained: preorder, midorder and postorder.
- Preorder traversal: root node->left child->right child
- In-order traversal: left child->root node->right child
- Post-order traversal: left child->right child->root node