[Data structure]: 21- Union search (array) (C language implementation)

Table of contents

foreword

Completed content

And check the implementation

01-Development environment

02-File layout

03-code

01-main function

02-header file

03-UFFunction.cpp

epilogue

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

[Data structure]: 05-circular queue (linked list) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 06-queue (linked list leading node) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 07-Binary tree (headless node) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 08-Sequential search (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 09-Binary search (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 10-Binary sorting tree (headless node) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 11- Bubble sort (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 12-Quick sort (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 13- Insertion sorting (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 14-selection sorting (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 15-Heap sorting (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 16-merge sort (sequence table pointer implementation form) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 17-Double linked list (lead node) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 18-chain stack (without head node) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 19-string KMP pattern matching (array) (C language implementation)_Chandni.'s Blog-CSDN Blog

[Data structure]: 20-thread binary tree (headless node) (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.

Tags: C C++ data structure Union Find

Posted by chadowch on Sat, 01 Apr 2023 03:32:21 +0530