Table of contents
foreword
This column contains all the content of the 408 postgraduate entrance examination data structure, except for the C++ references used in it, all of which are C language codes. The main purpose of using C++ references is to simplify the use of pointers and avoid the appearance of double pointers.
Completed content
[Data structure]: 01-sequence table (C language implementation)_Chandni.'s Blog-CSDN Blog
[Data structure]: 02-singly linked list (C language implementation)_Chandni.'s Blog-CSDN Blog
[Data structure]: 03-stack (C language implementation)_Chandni.'s Blog-CSDN Blog
[Data structure]: 04-circular queue (array) (C language implementation)_Chandni.'s Blog-CSDN Blog
And check the implementation
01-Development environment
Language: C/C++14
Compiler: MinGW64
Integrated development environment: CLion2022.1.3
02-File layout
Please create a C++ executable program in the CLion integrated development environment, otherwise it cannot run, the reason has been explained above.
03-code
01-main function
for testing.
#include "./Head/UFData.h" #include "./Source/UFFunction.cpp" int main() { Initial(UFSets); // merge UnionRandomNode(UFSets, 0, 3); UnionRandomNode(UFSets, 5, 2); UnionRandomNode(UFSets, 1, 4); UnionRandomNode(UFSets, 4, 2); UnionRandomNode(UFSets, 0, 4); PrintSets(UFSets); printf("---------------------------\n"); // look up int pos; pos = FindOptimize(UFSets, 2); PrintSets(UFSets); printf("---------------------------\n"); return 0; }
02-header file
It is used to store structures and constants, etc.
// // Created by 24955 on 2023-03-31. // #ifndef INC_07_DISJOINTSETS_UFDATA_H #define INC_07_DISJOINTSETS_UFDATA_H // head File #include <stdio.h> // constant #define MAXSIZE 6 typedef int ElemType; // Structure - Union Check ElemType UFSets[MAXSIZE]; #endif //INC_07_DISJOINTSETS_UFDATA_H
03-UFFunction.cpp
It is used for operations such as storing and searching.
// // Created by 24955 on 2023-03-31. // // Initialize and check void Initial(ElemType UFS[]) { for (int i = 0; i < MAXSIZE; i++) { UFS[i] = -1; } } // check int Find(ElemType UFS[], int x) { /* * 1. The value stored in the array is the subscript of the root node of the current element * 2. When it is a negative number, it is represented as the root node*/ while (UFS[x] >= 0) { x = UFS[x]; } // Return the subscript of the root node return x; } // Check Optimization - Compression Path int FindOptimize(ElemType UFS[], int x) { int root = x; // find parent node while (UFS[root] >= 0) { root = UFS[root]; } // compressed path while (x != root) { // Record the parent node of x int parent = UFS[x]; UFS[x] = root; x = parent; } return root; } // merge void Union(ElemType UFS[], int Root1, int Root2) { /* * 1. If there is an intersection between the two sets, return directly * 2. Otherwise merge root2 into root1*/ if (Root1 == Root2) { return; } // Merge root2 into root1 UFS[Root2] = Root1; } // Union optimization - small trees are merged into big trees void UnionOptimize(ElemType UFS[], int Root1, int Root2) { /* * 1. Use an array value to represent the number of current tree nodes * 2. merge small tree into big tree*/ if (Root1 == Root2) { return; } // root2 is a small tree if (UFS[Root2] >= UFS[Root1]) { UFS[Root1] += UFS[Root2]; UFS[Root2] = Root1; } else { // root1 is a small tree UFS[Root2] += UFS[Root1]; UFS[Root1] = Root2; } } // Merge any two nodes void UnionRandomNode(ElemType UFS[], int Node1, int Node2) { /* * 1. find the root node * 2. merge*/ int Root1, Root2; Root1 = Find(UFS, Node1); Root2 = Find(UFS, Node2); UnionOptimize(UFS, Root1, Root2); } // Print out the collection value void PrintSets(ElemType UFS[]) { for (int i = 0; i < MAXSIZE; i++) { printf("%5d", UFS[i]); } printf("\n"); }
epilogue
This blog is mainly used to record the C language implementation of the 408 postgraduate entrance examination data structure. If there are any deficiencies, you can leave a message and discuss it.