我有一组类来处理我的 C++ 应用程序中的不相交集。我很难为这些类实现析构函数。任何人都可以帮助我吗?
这些基本上做的是:将node
s' 指针放入NodeAddress[]
,每个node
都由它来区分val
。每个节点都有一个指向不相交集头部和尾部的Item
占位符的指针。hd
tl
我想提一下,我意识到存在一些问题,例如:变量可见性(公共访问)、恒定大小NodeAddress
的缓冲区,但我想在这里关注内存释放。
是的,我想(需要)在指针上做(没有 STL)。如果您有任何建议或问题,请随时发表评论。
这是代码:
标题
class ListSet {
public:
unsigned int size;
node* NodeAddress[MAX_NUMBER_OF_LABELS];
struct Item;
class node {
public:
unsigned int val;
node *next;
Item *itemPtr;
node () : val(0), next(0), itemPtr(0) {}
node (const int& a) : val(a), next(0), itemPtr(0) {}
};
struct Item {
public:
node *hd, *tl;
Item(node *shd) : hd(shd), tl(shd) {}
void ListSet::Item::append (const Item* other);
//removal
ListSet::node* remove(node* old);
};
ListSet()
{
this->size = 0;
memset(NodeAddress, 0, sizeof(NodeAddress));
}
void setNodeAddress(const int& a, node* shd)
{
NodeAddress[a] = shd;
}
node* getNodeAddress(const int& a)
{
return NodeAddress[a];
}
ListSet::Item* ListSet::makeSet (const int& a) ;
ListSet::Item* ListSet::find (const int& a);
ListSet::Item* ListSet::unionSets (Item* s1, Item* s2);
void ListSet::unionSets (const int& a1, const int& a2);
};
资源
void ListSet::Item::append (const Item* other) {
//join the tail of the set to head of the other set
tl->next = other->hd;
tl = other->tl;
for (node* cur = other->hd; cur; cur = cur->next) {
cur->itemPtr = this;
}
}
ListSet::Item* ListSet::makeSet (const int& a) {
if( a > this->size) {this->size = a;}
assert(!getNodeAddress(a));
node *shd = new node(a);
Item *newSet = new Item(shd);
setNodeAddress(a, shd);
shd->itemPtr = newSet;
return newSet;
}
ListSet::Item* ListSet::find (const int& a) {
node* ptr = getNodeAddress(a);
if (ptr)
return ptr->itemPtr;
return 0;
}
ListSet::Item* ListSet::unionSets (Item* s1, Item* s2) {
Item *set1 = s1;
Item *set2 = s2;
set2->append(set1);
delete set1;
return set2;
}
void ListSet::unionSets (const int& a1, const int& a2) {
Item* s1 = find(a1);
Item* s2 = find(a2);
if (s1 && s2) {
(void) unionSets(s1, s2);
}
}
*编辑:* 我有一些东西但不工作
ListSet::node* ListSet::Item::remove(node* old) {
if (old == hd) {
if (old == tl) {
assert(! old->next);
return 0;
}
assert(old->next);
hd = old->next;
} else {
node* prev;
for (prev = hd; prev->next != old; prev = prev->next) {
assert(prev->next);
;
}
if (old == tl) {
assert(! old->next);
//
tl = prev;
prev->next = 0;
} else {
assert(old->next);
prev->next = old->next;
}
}
return hd;
}
ListSet::node::~node() {
if (itemPtr) {
if (! itemPtr->remove(this)) {
// Don't leak an empty set.
delete itemPtr;
}
}
}
void ListSet::remove(const int& a) {
node* ptr = getNodeAddress(a);
if (ptr) {
setNodeAddress(a, 0);
delete ptr;
}
// else error?
}