0

C++ アプリでDisjoint セットを処理するクラスのセットがあります。これらのクラスのデストラクタを実装するのに苦労しています。誰でもそれについて私を助けることができますか?

これらが基本的に行うことは次nodeのNodeAddress[]とおりnodeですval。すべてのノードには、互いに素なセットの先頭と末尾のItemプレースホルダーであるへのポインターがあります。hdtl

変数の可視性 (パブリック アクセス)、定数サイズのバッファーなど、いくつかの問題があることを認識していることを述べたいと思います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?
}
4

1 に答える 1

1

あなたのコードは非常に複雑です。これが、素集合の森に対する私の見解です。すべてのメモリ管理は、セットを に配置することで外部から処理できますvector。size_tセットはフォレストへの 型付きインデックスによって一意に識別できるため、ポインター操作は必要ないことに注意してください。

于 2012-02-27T20:13:46.553 に答える