本系列博客作为我学习的一个笔记,注重于代码实现,本人非数学专业,证明能力非常弱,本文掺杂着大量我自己的理解,如有数学大佬光顾,请尽情指正,谢谢
本系列默认大家都学会了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中的元素，记作aA，读作a属于A；
若a不是集合A中的元素，则记作aA，读作a不属于A。
未完待续
