C언어 집합 구현

1 개요[ | ]

C언어 집합 구현

2 예시 1[ | ]

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;
Node *root = NULL;

Node *newNode(int item) {
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

Node *_addRec(Node *node, int key) {
    if (node == NULL) return newNode(key);
    if (key < node->key) {
        node->left = _addRec(node->left, key);
    } else if (key > node->key) {
        node->right = _addRec(node->right, key);
    }
    return node;
}

void add(int key) {
    root = _addRec(root, key);
}

bool _findRec(Node *node, int key) {
    if (node == NULL) return false;
    if (key == node->key) return true;
    if (key < node->key) return _findRec(node->left, key);
    return _findRec(node->right, key);
}

bool contains(int key) {
    return _findRec(root, key);
}

void _printAllRec(Node *node) {
    if (node == NULL) return;
    _printAllRec(node->left);
    printf("%d ", node->key);
    _printAllRec(node->right);
}

void printAll() {
    _printAllRec(root);
    printf("\n");
}

Node *minValueNode(Node *node) {
    Node *current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

Node *_delRec(Node *node, int key) {
    if (node == NULL) return node;
    if (key < node->key) {
        node->left = _delRec(node->left, key);
    } else if (key > node->key) {
        node->right = _delRec(node->right, key);
    } else {
        if (node->left == NULL) {
            Node *temp = node->right;
            free(node);
            return temp;
        }
        if (node->right == NULL) {
            Node *temp = node->left;
            free(node);
            return temp;
        }
        Node *temp = minValueNode(node->right);
        node->key = temp->key;
        node->right = _delRec(node->right, temp->key);
    }
    return node;
}

void del(int key) {
    root = _delRec(root, key);
}

int main() {
    add(10);
    add(20);
    add(30);
    add(40);
    printAll(); // 10 20 30 40 
    add(40);
    add(50);
    del(30);
    printAll(); // 10 20 40 50 
    printf("50: %s\n", contains(50) ? "yes" : "no"); // 50: yes
    printf("60: %s\n", contains(60) ? "yes" : "no"); // 60: no
}

3 예시 2[ | ]

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int elements[MAX_SIZE];
    int size;
} Set;

void initializeSet(Set *set) {
    set->size = 0;
}

bool addElement(Set *set, int element) {
    if (set->size >= MAX_SIZE) return false;
    for (int i = 0; i < set->size; i++) {
        if (set->elements[i] == element) return false;
    }
    set->elements[set->size++] = element;
    return true;
}

bool removeElement(Set *set, int element) {
    for (int i = 0; i < set->size; i++) {
        if (set->elements[i] == element) {
            set->elements[i] = set->elements[--set->size];
            return true;
        }
    }
    return false;
}

void printSet(Set *set) {
    printf("{ ");
    for (int i = 0; i < set->size; i++) {
        printf("%d ", set->elements[i]);
    }
    printf("}\n");
}

void unionSet(Set *set1, Set *set2, Set *resultSet) {
    initializeSet(resultSet);
    for (int i = 0; i < set1->size; i++) {
        addElement(resultSet, set1->elements[i]);
    }
    for (int i = 0; i < set2->size; i++) {
        addElement(resultSet, set2->elements[i]);
    }
}

void intersectSet(Set *set1, Set *set2, Set *resultSet) {
    initializeSet(resultSet);
    for (int i = 0; i < set1->size; i++) {
        for (int j = 0; j < set2->size; j++) {
            if (set1->elements[i] == set2->elements[j]) {
                addElement(resultSet, set1->elements[i]);
                break;
            }
        }
    }
}

void differenceSet(Set *set1, Set *set2, Set *resultSet) {
    initializeSet(resultSet);
    for (int i = 0; i < set1->size; i++) {
        bool found = false;
        for (int j = 0; j < set2->size; j++) {
            if (set1->elements[i] == set2->elements[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            addElement(resultSet, set1->elements[i]);
        }
    }
}

int main() {
    Set setA, setB, resultSet;
    initializeSet(&setA);
    initializeSet(&setB);

    // 집합 A에 원소 추가
    addElement(&setA, 1);
    addElement(&setA, 2);
    addElement(&setA, 3);

    // 집합 B에 원소 추가
    addElement(&setB, 3);
    addElement(&setB, 4);
    addElement(&setB, 5);

    // 집합 A와 B의 합집합
    unionSet(&setA, &setB, &resultSet);
    printf("Union: ");
    printSet(&resultSet);

    // 집합 A와 B의 교집합
    intersectSet(&setA, &setB, &resultSet);
    printf("Intersection: ");
    printSet(&resultSet);

    // 집합 A와 B의 차집합
    differenceSet(&setA, &setB, &resultSet);
    printf("Difference (A - B): ");
    printSet(&resultSet);
}

4 같이 보기[ | ]