Изучаем язык программирования C с C Set

C set - это коллекция уникальных элементов в языке программирования C. Она обеспечивает быстрое добавление и удаление элементов из коллекции, а также быстрый доступ к элементам.

Для работы с множествами в C используются структуры данных, которые реализуют множества. Наиболее популярным способом создания множества является использование «битового поля», которое представляет собой булевский массив, каждый элемент которого представляет элемент множества.

Вместо использования битового поля можно использовать структуру данных "указатель на указатель", чтобы создать массив указателей, каждый из которых указывал бы на элементы множества. Такой подход не только повышает быстродействие, но и обеспечивает возможность упорядочивания элементов в множестве.

Рассмотрим примеры кода на C, демонстрирующие использование множеств.

Пример №1. Создание множества с помощью структуры данных "битовое поле".

c
#include 
#define SIZE 10
struct set {
    unsigned int member[SIZE];
};
void add_element(struct set *s, int element) {
    s->member[element / 32] |= (1 << (element % 32));
}
void remove_element(struct set *s, int element) {
    s->member[element / 32] &= ~(1 << (element % 32));
}
int is_member(struct set *s, int element) {
    return s->member[element / 32] & (1 << (element % 32));
}
int main()
{
    struct set s = {{0}};
    int i;
    for (i = 0; i < 10; ++i)
        add_element(&s, i);
    printf("Set: { ");
    for (i = 0; i < 10; ++i)
        if (is_member(&s, i))
            printf("%d ", i);
    printf("}\n");
    remove_element(&s, 5);
    printf("Set after removing element 5: { ");
    for (i = 0; i < 10; ++i)
        if (is_member(&s, i))
            printf("%d ", i);
    printf("}\n");
    return 0;
}

В этом примере мы создали структуру данных "set" и определили три функции: add_element, remove_element и is_member. Функция add_element добавляет элемент в множество, remove_element удаляет элемент из множества, а is_member проверяет, есть ли элемент в множестве. Мы также создали пример заполнения множества и удаления элемента из множества.

Пример №2. Создание множества с помощью структуры данных "указатель на указатель".

c
#include 
#include 
typedef struct {
    int value;
    struct node *next;
} node;
typedef struct {
    node *head;
    node *tail;
} list;
list *create_list()
{
    list *l = malloc(sizeof(list));
    l->head = NULL;
    l->tail = NULL;
}
void add_element(list *l, int value)
{
    node *n = malloc(sizeof(node));
    n->value = value;
    n->next = NULL;
    if (l->head == NULL) {
        l->head = n;
        l->tail = n;
    } else {
        l->tail->next = n;
        l->tail = n;
    }
}
void remove_element(list *l, int value)
{
    node *n = l->head;
    node *prev = NULL;
    while (n != NULL && n->value != value) {
        prev = n;
        n = n->next;
    }
    if (n == NULL)
        return;
    if (prev == NULL)
        l->head = n->next;
    else
        prev->next = n->next;
    free(n);
}
int is_member(list *l, int value)
{
    node *n = l->head;
    while (n != NULL) {
        if (n->value == value)
            return 1;
        n = n->next;
    }
    return 0;
}
void print_list(list *l)
{
    node *n = l->head;
    printf("Set: { ");
    while (n != NULL) {
        printf("%d ", n->value);
        n = n->next;
    }
    printf("}\n");
}
int main()
{
    list *l = create_list();
    int i;
    for (i = 0; i < 10; ++i)
        add_element(l, i);
    print_list(l);
    remove_element(l, 5);
    printf("Set after removing element 5: ");
    print_list(l);
    return 0;
}

В этом примере мы создали структуру данных "list", которая представляет собой связанный список. Мы создали три функции: add_element, remove_element и is_member, которые используются для добавления, удаления и проверки элементов в множестве. Также мы создали функцию print_list, которая печатает элементы множества. В этом примере мы создали связанный список, заполнили его элементами и удалили один элемент из него.