Wondershare EdrawMind
MindMap Gallery data structure
- 25
- 1
data structure
Data structure mind map: basic concepts of data structure, algorithms and algorithm evaluation, linear tables, trees and binary trees. The definition of tree is recursive and is a recursive data structure. etc.
Edited at 2022-03-31 15:00:22
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
data structure
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
- Recommended to you
- Outline
data structure
introduction
Basic concepts of data structures
Basic concepts and terminology
Three elements of data structure
Algorithms and Algorithm Evaluation
Basic concepts of algorithms
A measure of algorithm efficiency
linear table
Definition and basic operations of linear tables
Definition of linear table
Is a finite sequence of n (n>=0) data elements with n identical data types.
Features
The number of elements in the table is limited
The elements in the table have a logical sequence. The elements in the table have their order.
The elements in the table are all data elements, and each element is a single element.
The data types of the elements in the table are all the same, which means that each element occupies the same size of storage space.
The elements in the table are abstract, that is, only the logical relationship between the elements is discussed, without considering what the elements actually represent.
⚠️
A linear list is a logical structure that represents a one-to-one adjacent relationship between elements.
Sequence lists and linked lists refer to storage structures.
Basic operations of linear tables
Add, delete, modify and check
Sequential representation of linear tables
Definition of sequence table
Sequential storage of linear tables is also called sequential tables
Features: The logical order of elements in the table is the same as their physical order.
Any data element in the linear table can be accessed randomly, so the sequential storage structure of the linear table is a random access storage structure.
⚠️ The bit order of elements in a linear list starts from 1, while the subscripts of elements in an array start from 0.
Linear table sequential storage
#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList;
dynamic
#defineInitSize 100 typedef struct{ ElemType *data; int MaxSize,length; }SeqList; //Type definition of dynamically allocated array sequence table
C language dynamic allocation statement
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
The initial dynamic allocation statement for C is
L.data=new ElemType[InitSize];
Dynamic allocation is not chain storage. It also belongs to a sequential storage structure. The physical structure does not change and it is still a random access method. However, the allocated space size can be dynamically determined at runtime.
The main features of linear tables:
Random access O(1)
High storage density, each node only stores data elements
Elements that are logically adjacent in a sequence table are also physically adjacent, so insertion and deletion operations require moving a large number of elements.
Expanding capacity is inconvenient.
Implementation of basic operations on sequence tables
1⃣️ Insert operation
bool ListInsert(SqList &L,int i,ElemType e){ if(i<1 || i > L.length 1) return false; if( L.length >= MaxSize) return false; for(int j=L.length;j>=i;j- -) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length; return true; }
The average time complexity of insertion is O(1).
2⃣️ Delete operation
bool ListDelete(SqList &L,int i, ElemType &e){ if(i < 1 || i > L.length) return false; e=L.data[i - 1]; for(int j = i;j < L.length;j ) L.data[j-1] = L.data[j]; L.length- -; return true; }
Removal average time complexity O(n)
3⃣️ Search by value
int LocateElem(SqList L,ElemType e){ int i; for(i =0;i < L.length;i ) if(L.data[i]==e) return i 1; return 0; }
Find average case O(n).
Linked representation of linear list
Insertion and deletion operations do not require moving elements, but only need to modify pointers, but they will also lose the advantage of random access in the sequential list.
Definition of singly linked list
subtopic
Implementation of basic operations on singly linked list
Create a singly linked list using head insertion method
Create a singly linked list using tail insertion method
Find node value by serial number
Find table nodes by value
Insert node operation
Delete node operation
Find table length operation
Double linked list
subtopic
circular linked list
static linked list
Trees and Binary Trees
Basic concepts of trees
tree definition
A tree is a finite set of n (n>=0) nodes.
When n=0, it is called an empty tree
A non-empty tree should satisfy
1⃣️ There is and is only one specific node called the root
2⃣️ When n>1, the remaining nodes can be divided into m (m>0) disjoint finite sets T1, T2, •••Tm. Each of the remaining sets is itself a tree and is called the root. subtree.
The definition of tree is recursive and is a recursive data structure.
As a logical structure, a tree is also a hierarchical structure and has the following characteristics:
1⃣️ The root node of the tree has no predecessor, and all nodes except the root node have one and only one predecessor.
2⃣️ All nodes in the tree can have zero or more successors.
Trees are suitable for representing data with a hierarchical structure.
There are n-1 edges in a tree with n nodes.
Each node in the tree is directly related to zero or more nodes in the next level.
basic terminology
1⃣️ Consider nodes (ancestors, parents, brothers, descendants)
The root is the only node in the tree that does not have a parent.
2⃣️ The number of children of a node in the tree is called the degree of the node, and the maximum degree of the node in the tree is called the degree of the tree.
3⃣️ Nodes with degree greater than 0 are called branch nodes (also called non-terminal nodes) and nodes with degree 0 are called leaf nodes (terminal nodes).
In a branch node, the branch tree of each node is the degree of the node.
4⃣️ Depth, height and level of nodes.
The hierarchy of nodes is defined starting from the root node. The root node is the first level, its child nodes are the second level, and so on.
Nodes whose parent nodes are on the same level are cousins of each other.
The depth of a node is accumulated layer by layer starting from the root node and going from top to bottom.
The height of the node is accumulated layer by layer starting from the leaf node and going from bottom to top.
The height (depth) of a tree is the largest level of nodes in the tree.
5⃣️Ordered trees and unordered numbers
The subtrees in the tree are ordered from left to right and cannot be interchanged. It is called an ordered tree. Otherwise, it is an unordered tree.
An ordered tree becomes a different tree if the positions of its child nodes are swapped.
6⃣️ Path and path length
The path between two nodes in the tree is composed of the sequence of nodes passed between the two nodes, and the path length is the number of edges passed on the path.
Since the branches in the tree are directed, that is, from the parents to the children, the path of the tree is from top to bottom, and there is no path between two children of the same parent.
7⃣️ Forest
A forest is a collection of m (m>=0) disjoint trees.
As long as the root node of the tree is deleted, it becomes a forest. On the contrary, as long as m independent trees are added to a node, and these m trees are used as subtrees of the node, the forest becomes a tree.
tree nature
The number of nodes in the tree is equal to the sum of the degrees of all nodes ➕1
There are at most m^(i-1) nodes in the i-th level of the tree of degree m (i>=1)
An m-ary tree with height h has at most (m^h-1)/(m-1) nodes.
The minimum height of an m-ary tree with n nodes is
Binary tree concept
The concept of binary tree and its main characteristics
Binary tree definition
Features: Each node has at most two subtrees, and they can be divided into left and right subtrees and cannot be reversed.
A binary tree is a finite set of nodes with n greater than or equal to zero:
Or an empty binary tree, that is, n=0
Or it consists of a root node and two disjoint left subtrees and right subtrees called roots. The left subtree and the right subtree are each a binary tree.
The difference between a binary tree and an ordered tree of degree 2:
1⃣️ A tree with degree 2 has at least 3 nodes, while a binary tree can be empty
The left and right order of the children of an ordered tree with degree 2 is relative to another child, while the node order of a binary tree is not relative to another node, but is determined.
Several special binary trees
1⃣️ Full binary tree
A binary tree with height h and 2^h-1 nodes is called a full binary tree.
The degree of every node except leaf nodes is 2
Numbering starts from the root node
For the node number i, if there are parents, the parents are i/2 (rounded down
If there is a left child, the left child is 2i
If there is a right child, the right child is 2i 1
2⃣️ Complete binary tree
A full binary tree is a special complete binary tree
If i<=[n/2] is rounded down, node i is a branch node, otherwise it is a leaf node.
Leaf nodes can only appear on the two levels with the largest number of levels. The leaf nodes in the largest level are arranged in sequence at the leftmost position of the level.
There can be at most one node with degree one, and this node has only left children but no right children.
3⃣️ Binary sorting tree
The keys of all nodes in the left subtree are smaller than the keys of the root node
The keys of all nodes on the right subtree are greater than the keys of the root node
The left subtree and the right subtree are another binary sorting tree.
Facilitates element search
4⃣️ Balanced Binary Tree
🤡👹2009 The depth difference between the left subtree and the right subtree of any node in the tree does not exceed 1
Properties of binary trees
🤡🐉2011 The number of leaf nodes on a non-empty binary tree is equal to the number of nodes with degree 2 ➕1
n=n0 n1 n2
n=B 1
B=n1 2n2
n0=n2 1
There are at most 2^(k-1) nodes (k>=1) on the k-th level of a non-empty binary tree (a geometric sequence with a common ratio of 2)
A binary tree with height h has at most 2^h-1 nodes h greater than or equal to 1
complete binary tree sorting
The height of a complete binary tree with n (n>0) nodes is
Binary tree storage structure
sequential storage structure
The sequence number of the nodes in the tree can uniquely reflect the logical relationship between the nodes.
Save storage space
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.
🚬The following table of array starts from 1⃣️
Low space utilization
chain storage structure
Contains data field data, left pointer field lchild and right pointer field rchild
Binary tree chain structure description
typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
A binary linked list containing n nodes contains n 1 empty link fields‼ ️
Binary tree traversal and clue binary trees
Binary tree traversal
Binary tree traversal refers to visiting each node in the tree according to a certain search path, so that each node is visited once and only once.
Preorder traversal (NLR)
If the binary tree is empty, do nothing
If not empty
access root node
Preorder traversal of left subtree
recursive algorithm
void PreOrder(BiTree T){ if(T!Null){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
Preorder traverse the right subtree
inorder traversal
If empty, do nothing
If not empty then
In-order traversal of left subtree
access root node
recursive algorithm
void InOrder(BiTree T){ if(T!=Null){ InOrder->lchild; visit(T); InOrder->rchild; } }
In-order traversal of right subtree
Postorder traversal
Same as above
total
The left and right order of traversal is fixed, but the order of accessing the root node is different. Each node is visited only once, and the time complexity is O(n).
In the recursive workstation, the depth of the recursive workstation is exactly the depth of the tree. In the worst case, the binary tree is a single-branch tree with n nodes and depth n, and the space complexity of the traversal algorithm is O (n).
Conversion between recursive and non-recursive algorithms
clue binary tree
🤡🐉2011 Count the number of non-leaf nodes in a binary tree
int NoLeafCount(BiTNode *pHead){ if(pHead=NULL) return 0; else if(NULL=pHead->lchild&&NULL=pHead->rchild) return 0; else return(1 NoLeafCount(pHead->lchild) NoLeafCounf(pHead->rchild)); }
tree, forest 🌳
tree storage structure
parent representation
A set of continuous spaces is used to store each node, and a pseudo pointer is added to each node to indicate the position of its parent node in the array.
Storage structure of parent representation
#define MAX_TREE_SIZE 100 typedef struct { ElemType data; int parent; //Parent location field }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; //Parent representation int n; //Number of nodes }PTree;
Except for the root node, there is only one parent. You can quickly get the parent node of each node, but you need to traverse the entire structure to find the child nodes of its node.
The difference between the sequential storage of trees and the sequential storage of binary trees
In the sequential storage of the tree, the array subscript represents the number of the node, and the content stored in the subscript indicates the relationship between the nodes.
The binary tree is stored sequentially. The array subscript not only represents the number of the node, but also indicates the relationship between the nodes in the binary tree.
Binary trees can be stored using the tree storage structure, but trees cannot be stored using the binary tree storage structure.
child representation
Link the child nodes of each node with a singly linked list to form a linear structure. At this time, n nodes have n child linked lists (the child linked lists of leaf nodes are empty).
The operation of finding children is very straightforward, while the operation of finding parents requires traversing the n child linked lists pointed to by the child linked list pointer fields in n nodes.
Child brother representation (binary tree representation)
A binary linked list is used as the storage structure of the tree.
Each pointer contains: the node value, a pointer to the node's first child node, and a pointer to the node's next sibling node (all siblings of the node can be found along this field).
Storage structure of child sibling representation
typedef struct CSNode{ ElemType data; //data field struct CSNode *firstchild,*nextsibling;//first child and right sibling pointers }CSNode,*CSTree;
Advantages: The operation of converting a tree into a binary tree can be easily realized, and it is easy to find the children's nodes, etc.
Disadvantage: It is troublesome to find its parent node from the current node.
If a parent field is added for each node to point to its parent node, it is also convenient to find the parent node of the node.
Conversion of trees, forests and binary trees
Tree and forest traversal
Application of trees - union search
Applications of trees and binary trees
sort
Basic concepts of sorting
Just rearrange the elements in the list
According to whether the data is in memory, it is divided into
Internal sorting
All in memory sorting
external sort
Sorting that is constantly moved between internal and external memory as required.
The number of comparisons for sorting n keywords is at least 2^t >= n! 🤡
insertion sort
direct insertion method
O(n) at best, O(^2) at worst
Maximum number of comparisons [n (n-1)]/2
Time complexity O(n^2)
Average O(n^2)
Stablize
Before the last pass begins, it may happen that all elements are not in their final positions.
half insertion sort
Time complexity O(n^2)
Hill sort
The Hill sorting group uses direct insertion sorting.
swap sort
swap sort
selection sort
Merge sort and radix sort
Comparison and application of various internal sorting algorithms
external sort
stacks and queues
Stack
Basic concepts of stack
stack definition
A stack is a linear list that only allows insertion or deletion operations at one end.
The top of the stack (Top) is the end of the linear table that allows insertion and deletion.
The bottom of the stack is fixed and does not allow insertion or deletion.
Empty stack An empty list containing no elements
Operating characteristics: last in, first out. (Last In First Out, LIFO)
The mathematical properties of the stack: n different elements are pushed into the stack, and the number of different arrangements of the elements that are popped out of the stack is [1 / (n 1)] C^n 2n (n up and 2n down) is called a Cattleya tree.
Basic operations of stack
InitStack (& S): Initialize an empty stack S.
StackEmpty(S): Determines whether a stack is empty.
Returns true if the stack is empty
Otherwise false
Push ( & S , x): push onto the stack
If stack S is not full, add x to make it the top of the new stack.
Pop (& S, & x): Pop off the stack
If the stack S is not empty, pop the top element of the stack and return it with x.
GetTop (S, & x): Read the top element of the stack
If the stack is not empty, use x to return the top element of the stack.
DestroyStack ( & S ): Destroy the stack
And release the storage space occupied by stack S ("&" indicates a reference call).
Stack sequential storage
The stack is a linear list with limited operations, similar to a linear list, and has two corresponding storage methods.
Implementation of sequential stack
A stack that uses sequential storage is called a sequential stack. It uses a set of storage units with consecutive addresses to store data elements from the bottom of the stack to the top of the stack. It also has a pointer (top) attached to indicate the location of the current top element of the stack.
The sequential storage type of the stack can be described as
#define Maxsize 50 //Define the maximum number of elements in the stack typedef struct { ElemType data [Maxsize]; //Storage elements in the stack int top; //Stack top pointer } SqStack;
Stack top pointer: S.top
Initially set S.top=-1;
Top element of stack: S.data[S.top].
Push operation: When the stack is not full, the top pointer of the stack first ➕1, and then the value is sent to the top element of the stack.
Pop operation: When the stack is not empty, first take the value of the top element of the stack, and then - 1 the top pointer of the stack.
Stack empty condition: S.top==-1; Stack full condition: S.top==MaxSize - 1; Stack length: S.top 1.
Since the push operation of the sequential stack is subject to the upper bound of the array, when the maximum usage space of the stack is insufficiently estimated, overflow may occur. At this time, the message should be reported to the user in a timely manner so that it can be processed in a timely manner and avoid errors.
🤡When a function is called, the stack must be used to save necessary information.
Basic operations of sequential stack
1⃣️Initialization
viod InitStack ( SqStack &S){ S.top = - 1; //Initialize the stack top pointer }
2⃣️ The stack is empty
viodStackEmpty(SqStackS){ if (S.top == - 1) //Stack is empty return true; else //not empty return false; }
3⃣️ Push into the stack
bool Push ( SqStack &S , ElemType x ){ if (S.top == MaxSize - 1) //The stack is full and an error will be reported return false; S.data[ S.top]=x; //The pointer first➕1, then pushed onto the stack return true; }
4⃣️ Pop out
bool push ( SqStack &S , ElemType &x ){ if (S.top == - 1) //The stack is empty and an error is reported return false; x=S.data[S.top- -]; //Pull the stack first, then -1 the pointer return true; }
5⃣️ Read the top element of the stack
bool GetTop ( SqStack &S , ElemType &x ){ if (S.top == - 1) //The stack is empty and an error is reported return false; x=S.data[S.top]; //x records the top element of the stack return true; }
It only reads the top element of the stack, and there is no pop operation, so the original top element of the stack is still saved in the stack.
shared stack
Taking advantage of the relatively unchanged position of the bottom of the stack, two sequential stacks can share a one-dimensional array space. The bottoms of the two stacks are set at both ends of the shared space, and the tops of the two stacks face the middle edge of the shared space. stretch.
🤡The shared stack is to utilize the storage space more effectively. The spaces of the two stacks are adjusted to each other, and overflow will only occur when the entire storage space is full.
The event complexity of accessing data is O(1)
stack chain structure
A stack that uses chained storage is called a chain stack.
🤡The advantage of the chain stack is that it facilitates multiple stacks to share storage space and improves its efficiency, and there is no stack overflow.
The chain storage type of the stack can be described as
typedef struct Linknode{ ElemType data; //data field struct Linknode *next; //Pointer field } *LiStack; //Stack type definition
Chain storage is used to facilitate the insertion and deletion of nodes.
The operation of the linked stack is similar to that of the linked list. The push and pop operations are performed at the head of the linked list.
⚠️The specific implementation will be different for the chain stack of the leading node and the non-leading node.
To insert a node x into a chain stack (without the head node) with the top pointer of the stack as top, execute:
x -> next = top;
top = x;
Insert a node x into a chain stack (head node) with the top pointer of the stack as top, then execute:
x -> next = top -> next;
top -> next = x;
The chain stack (without the head node) performs the Pop operation and stores the popped elements in x. It should be executed:
x = top -> data;
top = top -> next;
The chain stack (lead node) performs the Pop operation and stores the popped elements in x. It should execute:
x = top -> next - data;
top -> next = top -> next -> next;
The relationship between stack and queue
🤡The logical structures of stacks and queues are the same, both are linear structures, but they operate on data differently.
🤡Stacks and queues are linear structures that limit access points.
queue
Basic concepts of queues
queue definition
Queue, referred to as queue, is also a linear table with limited operations. It only allows insertion at one end of the table and deletion at the other end of the table.
Inserting elements into the queue is called enqueuing and enqueuing; deleting elements is called dequeuing and leaving the queue.
Operating characteristics: First In First Out (FIFO)
🤡Front. The end that is allowed to be deleted is also called the head of the team.
🤡Rear. The end that allows insertion.
⚠🤡🤡🤡️ Cyclic, non-cyclic, and singly linked lists are most suitable for use as chain teams. The main consideration is the rear pointer at the end of the team (insert one end)
Empty queue. An empty list containing no elements.
Common basic operations of queues
InitQueue(&Q): Initialize the queue to construct an empty queue Q
QueueEmply(Q): Determine if the queue is empty
Returns true if the queue is empty
Otherwise return false
EnQueue(&Q,x):Enqueue
If queue Q is not full, add x to make it the new tail of the queue.
DeQueue(Q, &x): Dequeue
If queue Q is not empty, delete the opposite element and return it with x.
GetHead(Q, &x): Read the head element
If the queue Q is not empty, assign the head element to x.
The sequential storage structure of the queue
Queue sequential storage
The sequential implementation of the queue refers to allocating a continuous storage unit to store the elements of the queue, and attaching two pointers:
The head pointer front points to the head element
The tail pointer rear points to the next position of the tail element of the queue.
The sequential storage type of the queue
#define Maxsize 50 //Define the maximum number of elements in the queue typedef struct { ElemType data [Maxsize]; //Storage elements in the queue int front, rear; // Head pointer and tail pointer } SqQueue;
Initial state (condition of empty team)
Q.front == Q.rear == 0.
Joining the team:
When the team is not satisfied, first send the value to the tail element of the team, and then set the tail pointer to ➕1
Dequeue operation:
When the queue is not empty, first get the value of the opponent element, and then add the opponent pointer ➕1
Q.rear == MaxSize cannot be used to determine when the team is full
This condition is also met when there is only one element in the queue
This is an "overflow" when entering the queue, but this overflow is not a real overflow but a false overflow.
circular queue
concept
The circular queue is imagined as a ring-shaped space, that is, the table storing queue elements is logically regarded as a ring.
When Q.front = MaxSize - 1, moving forward one position will automatically reach 0⃣️. This can be achieved by using the remainder operation (%) of division.
Initially:
Q.front = Q.rear = 0.
The head pointer advances by 1:
Q.front = (Q.front 1)%MaxSize.
Advance the tail pointer by 1:
Q.rear = (Q.rear 1)%MaxSize.
queue length
(Q.rear MaxSize - Q.front) % MaxSize.
🤡When leaving the queue and entering the queue, the pointer advances by 1 clockwise.
Distinguish whether the queue is empty or full
1⃣️ It is a common practice to sacrifice one unit to distinguish between empty and full queues, and to use one less queue unit when joining the queue.
It is agreed that a head pointer is located at the next position of the queue tail pointer as a sign that the queue is full.
Team full conditions:
(Q.rear 1)%MaxSize = = Q.front.
Team empty conditions:
Q.front == Q.rear.
The number of elements in the queue:
(Q.rear-Q.front MaxSize)%Maxsize.
2⃣️ Add a data member indicating the number of elements to the type.
The empty team condition is:
Q. size == 0.
Team full conditions:
Q.size == MaxSize.
3⃣️ Add tag members to the type to distinguish whether the team is full or empty
tag equals 0
If Q.front == Q.rear is caused by deletion, it will be empty.
tag equals 1
If Q.front == Q.rear due to insertion, the queue is full.
Circular queue operations
1⃣️Initialization
void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; //Initialize the head and tail pointers of the team ｝
2⃣️ The team is empty
bool isEmpty(SqQueue Q){ if(Q.rear==Q.front) //Team empty condition return true; else return false; }
3⃣️ Join the team
bool EnQueue(SqQueue &Q,ElemType x){ if ((Q.rear 1)%MaxSize==Q.front) //Error when the team is full return false; Q.data[Q.rear]=x; Q.rear=(Q.rear 1)%MaxSize; //Add 1 to the tail pointer modulo return true; }
4⃣️Leave the team
bool DeQueue(SqQueue &Q,ElemType &x) if(Q.rear==Q.front){ return false; x=Q.data[Q.front]; Q.front=(Q.front 1)%MaxSize; return true; }
Queue chain storage structure
Queue chain storage
The chained representation of a queue is called a chained queue, which is actually a singly linked list with both a queue pointer and a queue tail pointer.
The head pointer points to the head node of the queue.
The tail pointer points to the tail node of the queue, which is the last node of the singly linked list.
⚠️Different from sequential storage.
Chained storage type of queue:
typedef struct{ //chained queue node ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //chained queue LinkNode *front,*rear; //queue head and tail pointers }LinkQueue;
When Q.rear==NULL and Q.front==NULL, the chained queue is empty.
Dequeue and enter queue operations
Dequeue
First, determine whether the queue is empty. If not, take out the opposite element, delete it from the linked list, and let Q.front point to the next node.
If the queue is the last node, set both Q.front and Q.rear to NULL.
Join the team
Create a new node, insert the new node into the end of the linked list, and change Q.rear to point to the newly inserted node.
If the original queue is empty, make Q.front also point to the node.
Chain storage without a head node is more troublesome. A chain queue with a head node is usually used to unify the insertion and deletion operations.
The queue represented by a singly linked list is suitable for situations where data elements change significantly, and there is no problem of the queue being full and overflowing.
If you want to use multiple queues and multiple stacks, it is best to use chained queues, so that there will be no unreasonable storage allocation and overflow problems.
Basic operations of chained queues
1⃣️Initialization
void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//Initially empty }
2⃣️ The team is empty
bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }
3⃣️ Join the team
bool EnQueue(LinkQueue &Q,ElemType x){ LinkNode *S=(LinkNode*)malloc(sizeof(LinkNode)); s->next=x; //Create a new node and insert it at the end of the queue s->next=NULL; Q.rear->next=s; }
4⃣️Leave the team
bool DeQueue(LinkQueue &Q,Elempty &x){ if(Q.front==Q.rear){ return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; //If the original queue has only one node, it will become empty after deletion. free(p); return true; }
deque
It is a queue that can perform enqueue and dequeue operations at both ends.
The logical structure of its elements is still a linear structure.
The two ends of the queue are called the front end and the back end respectively, and both ends can enter and exit the queue.
When entering the team
The elements entered from the front end are arranged in front of the elements entered from the rear end in the queue.
The elements entered from the back end are arranged behind the elements entered from the front end in the queue.
When leaving the team
Regardless of whether it is dequeued by the front end or the back end, the elements that come out first are arranged in front of the elements that come out later.
Output and input restricted deque
Output-restricted deque: A deque that allows insertions and deletions at one end but only insertions at the other end is called an output-restricted deque.
Input-restricted deque: A deque that allows insertions and deletions at one end but only deletions at the other end is called an input-restricted deque.
If the element inserted from a certain endpoint of the double-ended queue is restricted to be deleted from that endpoint, then the double-ended queue will transform into two stacks with adjacent bottoms (last in, first out).
Applications of stacks and queues
Application of stack in bracket matching
Algorithmic thinking
1⃣️Initially set an empty stack and read the brackets sequentially
2⃣️ If it is a right parenthesis, it will either eliminate the most urgent expectation placed on the top of the stack, or it will be an illegal situation (if the bracket sequence does not match, exit the program.
3⃣️ If it is a left parenthesis, it will be pushed onto the stack as a new more urgent expectation, which will naturally reduce the urgency of all the original unresolved expectations in the stack by one level.
At the end of the algorithm, the stack is empty, otherwise there is no match.
Application of stack in expression evaluation
infix expression
postfix expression
Application of stack in recursion
concept
If the definition of a function, procedure, or data structure applies to itself, the function, procedure, or data structure is said to be defined recursively, or recursively for short.
Recursion reduces the amount of code but it is inefficient.
Contains a lot of calculations
During the recursive call process, the system opens up a recursive work stack for data storage for each layer's return points, local variables, incoming actual parameters, etc.
Too many recursions can easily cause stack overflow, etc.
Advantages: The code is simple and easy to understand.
Fibonacci Sequence
Conditions that need to be met for the recursive model
Recursive expression (recursive body)
Boundary conditions (recursive exit)
The key to recursion is the ability to transform the original problem into a smaller problem with the same properties.
A recursive algorithm can be converted into a non-recursive algorithm using a stack.
🤡For solving a problem, non-recursive algorithms are usually higher than recursive algorithms
Recursive algorithms contain many repeated calculations
🤡A stack storage is required when the function is called
local variables
call return value
Arguments
🤡🐉2013 Utilization of queues in hierarchical traversal
Tree level traversal
Breadth-first traversal of the graph
Application of queues in computer systems
data buffer
CPU processing request
Compressed storage of special matrices
string
Definition and implementation of string
string matching pattern
picture
Basic concepts of graphs
Storage and basic operations of graphs
Graph traversal
Application of diagrams
Find
Basic concepts of search
Sequential search and binary search
B-tree and B-tree
hash table