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.