离散数学-0x00

妈耶厥了

本系列博客作为我学习的一个笔记,注重于代码实现,本人非数学专业,证明能力非常弱,本文掺杂着大量我自己的理解,如有数学大佬光顾,请尽情指正,谢谢
本系列默认大家都学会了C/C++基本语法

集合

书上的定义

集合是指具有某种特定性质的不同对象无序聚集成的一个整体。
集合中的每一个对象称为集合的元素；
通常用大写字母表示集合；
用小写字母表示集合中的元素。

也就是说把一些东西放到一起叫做集合(个人理解)

代码实现

#include <string>
#include <vector>
#include <stdint.h>
#include <iostream>

// 抽象基类，定义集合元素的基本接口
class elmBase
{
public:
    // 将元素转换为字节数组的纯虚函数（序列化基础）
    virtual std::vector<uint8_t> getUint8Array() const = 0;

    // 默认比较运算符，通过字节数组逐字节比较
    virtual int operator==(const elmBase &other)
    {
        std::vector<uint8_t> thisDate = getUint8Array();
        std::vector<uint8_t> otherDate = other.getUint8Array();
        if (thisDate.size() != otherDate.size())
            return 0;
        for (int i = 0; i < thisDate.size(); i++)
        {
            if (thisDate[i] != otherDate[i])
                return 0;
        }
        return 1;
    }

    // 转换为字符串表示的纯虚函数
    virtual std::string toString() = 0;

    // 虚析构函数确保正确释放派生类对象
    virtual ~elmBase()
    {
    }
};

// 特殊元素类型，始终返回比较不成立
class alwaysFalse : public elmBase
{
public:
    std::vector<uint8_t> getUint8Array() const override
    {
        return std::vector<uint8_t>(); // 返回空数组
    }

    std::string toString() override
    {
        return {}; // 返回空字符串
    }

    // 重载运算符始终返回false，用于占位符场景
    virtual int operator==(const elmBase &other) override
    {
        return 0;
    }
    ~alwaysFalse()
    {
    }
};

// 哈希表节点结构，使用链表法解决冲突
using elmNode = struct elmNode
{
    elmBase *elm;  // 元素指针
    elmNode *next; // 下一个节点指针
};

// 节点工厂函数，创建新节点并初始化元素
elmNode *elmNodeFactory(elmBase *elm)
{
    elmNode *newNode = new elmNode();
    newNode->elm = elm;
    newNode->next = nullptr;
    return newNode;
}

// 自定义集合类，基于哈希表实现
class set
{
private:
    uint32_t prime;   // 哈希表大小（通常选择质数）
    elmNode **setMap; // 哈希桶数组

    // 初始化哈希表结构
    void inline _init_(uint32_t prime)
    {
        this->prime = prime;
        this->setMap = new elmNode *[prime];
        // 初始化每个桶为alwaysFalse哨兵节点
        for (uint32_t i = 0; i < prime; ++i)
        {
            this->setMap[i] = elmNodeFactory(new alwaysFalse());
        }
    }

protected:
    // 查找元素对应的哈希桶
    elmNode **__find__(elmBase *elm)
    {
        uint32_t hash = rotatingHash(elm->getUint8Array(), this->prime);
        return &(this->setMap[hash]); // 返回桶的指针
    }

    /**
     * 通用链表操作函数
     * @param link 链表头指针的指针
     * @param elm 目标元素
     * @param cmp 自定义比较函数，返回true时停止遍历
     * @param finally 遍历结束后的处理函数（插入等操作）
     * @return 找到的节点或操作结果节点
     */
    elmNode *__link__(elmNode **link, elmBase *elm,
                      bool (*cmp)(elmNode *, elmBase *),
                      elmNode *(*finally)(elmNode **, elmNode *, elmBase *) = nullptr)
    {
        elmNode *linkPriv = *link;
        elmNode *linkCurrent = linkPriv;

        // 遍历链表查找元素
        while (linkCurrent != nullptr)
        {
            if (cmp(linkCurrent, elm))
            {
                return linkCurrent;
            }
            linkPriv = linkCurrent;
            linkCurrent = linkCurrent->next;
        }

        // 执行最终处理函数（如插入新节点）
        if (finally != nullptr)
        {
            return finally(link, linkPriv, elm);
        }
        return nullptr;
    }

public:
    // 构造函数初始化哈希表
    set(uint32_t prime) { _init_(prime); }
    ~set()
    {
        for (uint32_t i = 0; i < this->prime; ++i)
        {
            elmNode *link = this->setMap[i];
            while (link != nullptr)
            {
                elmNode *tmp = link;
                link = link->next;
                if (tmp != nullptr)
                {
                    if (tmp->elm != nullptr)
                    {
                        std::cout << "delete " << tmp->elm->toString() << std::endl;
                        delete tmp->elm;
                    }
                    delete tmp;
                }
            }
        }
    }
    // 旋转哈希算法实现
    static uint32_t rotatingHash(std::vector<uint8_t> key, uint32_t prime)
    {
        uint32_t hash = key.size();
        for (uint32_t i = 0; i < key.size(); ++i)
            hash = (hash << 4) ^ (hash >> 28) ^ (uint32_t)(key[i]);
        return (hash % prime);
    }

    // 添加元素到集合
    bool add(elmBase *elm, bool force = false)
    {
        elmNode **node = __find__(elm);
        auto finally = [](elmNode **node, elmNode *linkPriv, elmBase *elm) -> elmNode *
        {
            // 插入新节点到链表末尾
            if (linkPriv->next == nullptr)
            {
                linkPriv->next = elmNodeFactory(elm);
            }
            return nullptr;
        };

        // 使用lambda作为比较函数
        elmNode *targetNode = this->__link__(node, elm, [](elmNode *node, elmBase *tag) -> bool
                                             { return *(node->elm) == *tag; }, finally);

        return targetNode == nullptr; // 返回是否插入成功
    }

    // 检查元素是否存在
    bool get(elmBase *elm)
    {
        elmNode **node = __find__(elm);
        elmNode *targetNode = this->__link__(node, elm,
                                             [](elmNode *node, elmBase *tag) -> bool
                                             {
                                                 return *(node->elm) == *tag;
                                             });
        return targetNode != nullptr;
    }

    // 移除集合中的元素
    bool remove(elmBase *elm)
    {
        elmNode **node = __find__(elm);
        elmNode *ret = this->__link__(node, elm,
                                      [](elmNode *current, elmBase *tag) -> bool
                                      {
                                          // 查找前驱节点执行删除
                                          if (current->next != nullptr && *(current->next->elm) == *tag)
                                          {
                                              elmNode *tmp = current->next;
                                              current->next = current->next->next;
                                              delete tmp->elm; // 释放元素内存
                                              delete tmp;      // 释放节点内存
                                              return true;
                                          }
                                          return false;
                                      });
        return ret != nullptr;
    }

    // 调试用打印函数，显示哈希表结构
    void print()
    {
        std::cout << "[HashTable Structure]" << std::endl;
        for (int i = 0; i < this->prime; i++)
        {
            std::cout << "Bucket " << i << ": ";
            elmNode *node = this->setMap[i];
            while (node != nullptr)
            {
                std::cout << node->elm->toString() << " -> ";
                node = node->next;
            }
            std::cout << "NULL" << std::endl;
        }
    }
};

// 数值类型元素实现
class number : public elmBase
{
    int data;

public:
    number(int data) : data(data) {}

    std::vector<uint8_t> getUint8Array() const override
    {
        // 将整型转换为字节数组
        return std::vector<uint8_t>(
            reinterpret_cast<const uint8_t *>(&data),
            reinterpret_cast<const uint8_t *>(&data) + sizeof(data));
    }

    std::string toString() override
    {
        return std::to_string(data);
    }
    ~number()
    {
    }
};

// 字符串类型元素实现
class string : public elmBase
{
    std::string data;

public:
    string(std::string data) : data(data) {}

    std::vector<uint8_t> getUint8Array() const override
    {
        // 将字符串内容转换为字节数组
        return std::vector<uint8_t>(data.begin(), data.end());
    }

    std::string toString() override
    {
        return data;
    }
    ~string()
    {
    }
};

集合与元素的关系

若A表示一个集合，a是集合A中的元素，记作aA，读作a属于A；
若a不是集合A中的元素，则记作aA，读作a不属于A。

未完待续

D2Learn Forums

离散数学-0x00

集合

书上的定义

代码实现

集合与元素的关系