Question

如何用C++实现一个整数类的集合??

定义整数类，满足如下要求：
判断是否为空集合
判断某元素是否为集合中元素
向集合中添加新元素
从集合中删除指定元素
判断两集合是否相等
求两个集合的交集
求两个集合的并集
集合复制
输出集合元素
这个我想了很久,我打算用链表实现.但是有很多不会..希望帮我下..先谢谢了

如果程序不错还会再追加分数的
如果重复最好就不用添加了，因为如果重复就没满足集合的定义了,所以应该最好还要有一个函数判断是否重复,我之所以选择链表就是因为要集合中的整数个数没限制

Answer 1

这个东西还是用2叉树做吧，链表查找太慢，这是我今天写的，刚好昨天看完了2叉树，所以写了个，试试看，有问题请留言，如果你实在要用链表实现的话我也可以给你写个：

#include <iostream>
#include <cstddef>
#include <sstream>
using namespace std;

// pre declaration is needed for class BTFolk
template <class T>
class Set;

// binary tree common properties
template <class T>
class BTFolk {
protected:
    BTFolk(){}; // uncreatable
public:
    struct Node {
        T       data; // data
        Node*   lhs; // left child
        Node*   rhs; // right child
    };
    static void inorderWalk(const Node* node, std::ostream& os); // traverse the tree
    static void recursivelyDelete(Node* node); // clean up tree
    static void assign(Set<T>& lhs, const Set<T>& rhs); // assign to another tree
};

template <class T>
void BTFolk<T>::inorderWalk(const Node* node, std::ostream& os)
{
    if(node)
    {
        inorderWalk(node->lhs, os);
        os << node->data << ' ';
        inorderWalk(node->rhs, os);
    }
}

template <class T>
void BTFolk<T>::recursivelyDelete(Node* node)
{
    if(node)
    {
        recursivelyDelete(node->lhs);
        recursivelyDelete(node->rhs);
        delete node;
    }
}

template <class T>
void BTFolk<T>::assign(Set<T>& lhs, const Set<T>& rhs)
{
    T* a = rhs.toArray();
    lhs.clear();

    for(T* beg = a; beg != a + rhs.size(); ++beg)
        lhs.insert(*beg);
    delete [] a;
}

// class Set
template <class T>
class Set : private BTFolk<T> {
public:

    Set(); // default constructor
    Set(const T* beg, const T* end); // initialize from array
    Set(const Set<T>& rhs); // cc

    bool    search(const T& elem)const; // search a element
    bool    insert(const T& elem); // insert a element
    bool    remove(const T& elem); // delete a element
    bool    empty()const; // is set empty?
    void    clear(); // clean up, null set
    T*      toArray()const; // convert to a sorted array, remember to release memory

    std::size_t size()const; // return number of elements
    friend std::ostream& operator << <>(std::ostream& os, const Set<T>& theSet); // output set
    bool    operator == (const Set<T>& rhs)const; // test for equality

    Set<T>& operator = (const Set<T>& rhs)const; // assign 
    Set<T>  operator * (const Set<T>& rhs)const; // intersection 交集
    Set<T>  operator + (const Set<T>& rhs)const; // union 并集
    Set<T>  operator - (const Set<T>& rhs)const; // difference 差集

    ~Set();
private:
    typename Set<T>::Node*           root; // root node
    std::size_t     numElems;  // number of elements
    typename Set<T>::Node*   getParentNode(const T& elem); // get parent node
};

template <class T>
typename Set<T>::Node*   Set<T>::getParentNode(const T& elem)
{
    if(root->data == elem)
        return 0;

    typename Set<T>::Node* node = elem < root->data ? root->lhs : root->rhs;
    typename Set<T>::Node* preNode = root;

    while(node->data != elem)
    {
        preNode = node;
        if(elem < node->data)
            node = node->lhs;
        else
            node = node->rhs;
    }
    return preNode;
}

template <class T>
Set<T>::Set() : root(0), numElems(0)
{}

template <class T>
Set<T>::Set(const T* beg, const T* end) : root(0), numElems(0)
{
    while(beg != end)
        insert(*beg++);
}

template <class T>
Set<T>::Set(const Set<T>& rhs) : root(0), numElems(0)
{
    assign(*this, rhs);
}

template <class T>
bool    Set<T>::search(const T& elem)const
{
    typename Set<T>::Node* node = root;
    while(node && node->data != elem)
    {
        if(elem < node->data)
            node = node->lhs;
        else
            node = node->rhs;
    }
    return node ? true : false;
}

template <class T>
bool    Set<T>::insert(const T& elem)
{
    typename Set<T>::Node** pnode = &root;

    if(!search(elem))
    {
        while(*pnode)
        {
            if(elem < (*pnode)->data)
                pnode = &(*pnode)->lhs;
            else
                pnode = &(*pnode)->rhs;
        }
        *pnode = new typename Set<T>::Node;
        (*pnode)->data = elem;
        (*pnode)->lhs = (*pnode)->rhs = 0;
        ++numElems;
        return true;
    }
    return false;
}

template <class T>
bool    Set<T>::remove(const T& elem)
{
    if(!search(elem))
        return false;
    typename Set<T>::Node* parent = getParentNode(elem);
    
    typename Set<T>::Node* temp;
    typename Set<T>::Node** nodeToUpdate;
    typename Set<T>::Node* nodeToRemove;

    if(parent)
        nodeToUpdate = parent->lhs && parent->lhs->data == elem ? &parent->lhs : &parent->rhs;
    else
        nodeToUpdate = &root;

    nodeToRemove = *nodeToUpdate;

    if(!((*nodeToUpdate)->lhs || (*nodeToUpdate)->rhs))
        *nodeToUpdate = 0;
    else if(((*nodeToUpdate)->lhs ? 1 : 0) ^ ((*nodeToUpdate)->rhs ? 1 : 0))
        *nodeToUpdate = (*nodeToUpdate)->lhs ? (*nodeToUpdate)->lhs : (*nodeToUpdate)->rhs;
    else
    {
        temp = (*nodeToUpdate)->rhs;
        while(temp->lhs)
            temp = temp->lhs;
        temp->lhs = (*nodeToUpdate)->lhs;
        if(temp->rhs)
            getParentNode(temp->data)->lhs = temp->rhs;
        temp->rhs = (*nodeToUpdate)->rhs->rhs;
        *nodeToUpdate = temp;
    }
    delete nodeToRemove;
    --numElems;
    return true;
}

template <class T>
inline bool    Set<T>::empty()const
{
    return numElems == 0;
}

template <class T>
inline void    Set<T>::clear()
{
    recursivelyDelete(root);
    root = 0;
    numElems = 0;
}

template <class T>
T* Set<T>::toArray()const
{
    stringstream sstrm;
    inorderWalk(root, sstrm);
    T* a = new T[numElems];
    for(int* p = a; p != a + numElems; ++p)
        sstrm >> *p;
    return a;
}

template <class T>
inline std::size_t Set<T>::size()const
{
    return numElems;
}

template <class T>
std::ostream& operator << (std::ostream& os, const Set<T>& theSet)
{
    typename Set<T>::Node* node = theSet.root;
    Set<T>::inorderWalk(node, os);
    return os;
}

template <class T>
bool    Set<T>::operator == (const Set<T>& rhs)const
{
    typename Set<T>::Node* me = root;
    ostringstream oss1, oss2;

    inorderWalk(me, oss1);
    inorderWalk(rhs.root, oss2);

    return oss1.str() == oss2.str();
}

template <class T>
Set<T>& Set<T>::operator = (const Set<T>& rhs)const
{
    assign(*this, rhs);
    return *this;
}

template <class T>
Set<T>  Set<T>::operator * (const Set<T>& rhs)const
{
    T* a = toArray();
    T* bega = a;
    T* enda = a + numElems;

    Set<T> c;

    while(bega != enda)
    {
        if(rhs.search(*bega))
            c.insert(*bega);
        ++bega;
    }
    delete [] a;

    return c;
}

template <class T>
Set<T>  Set<T>::operator + (const Set<T>& rhs)const
{
    T* a = this->toArray();
    T* bega = a;
    T* enda = a + this->numElems;
    T* b = rhs.toArray();
    T* begb = b;
    T* endb = b + rhs.numElems;

    Set<T> c;
    while(bega != enda)
        c.insert(*bega++);
    while(begb != endb)
        c.insert(*begb++);

    delete [] a;
    delete [] b;

    return c;
}

template <class T>
Set<T>  Set<T>::operator - (const Set<T>& rhs)const
{
    T* a = toArray();
    T* bega = a;
    T* enda = a + numElems;

    Set<T> c;
    while(bega != enda)
    {
        if(!rhs.search(*bega))
            c.insert(*bega);
        ++bega;
    }

    delete [] a;

    return c;
}

template <class T>
Set<T>::~Set()
{
    recursivelyDelete(root);
}

int main()
{
    int foo[] = {2,6,4,3,4};
    Set<int> a, b(foo, foo + 5);
    
    a.insert(2);
    a.insert(5);
    a.insert(1);
    a.insert(9);
    a.insert(7);
    
    cout << "set a: " << a << "size: " << a.size() << '\n';
    cout << "set b: " << b << "size: " << b.size() << "\n\n";
    a.insert(6);
    b.insert(1);

    cout << "insert 6 to a: " << a << "size: " << a.size() << '\n';
    cout << "insert 1 to b: " << b << "size: " << b.size() << "\n\n";

    cout << "try to insert duplicate 9 to a: " << (a.insert(9) ? "success\n\n" : "failed\n\n");

    cout.setf(ios::boolalpha);
    cout << "a contains 3: " << a.search(3) << '\n';
    cout << "b contains 4: " << b.search(4) << "\n\n";

    cout << "delete 9 from a.\n";
    a.remove(9);

    int bar[] = {1,2,3,4,6};
    Set<int> c(bar, bar + 5);

    cout << "set a: " << a << "size: " << a.size() << '\n';
    cout << "set b: " << b << "size: " << b.size() << '\n';
    cout << "set c: " << c << "size: " << a.size() << "\n\n";

    cout << "intersection of a & b:\t" << a * b << '\n';
    cout << "union of a & b:\t\t" << a + b << '\n';
    cout << "difference of a & b:\t" << a - b << "\n\n";

    cout << "a == b: " << (a == b) << '\n';
    cout << "b == c: " << (b == c) << "\n\n";

    a.clear();
    cout << "a is empty: " << a.empty() << '\n';
    cout << "b is empty: " << b.empty() << endl;
    cout.unsetf(ios::boolalpha);
}

Answer 2

搞了n久，终于搞好了
#include<stdio.h>
#include<time.h>
#include <iostream.h>
class item
{
public:
item(int x){data=x;next=0;}
friend class aset;
friend int equ(aset &s,aset &a);
private:
int data;
item *next;
};
class aset
{
public:
aset(){st=0;end=0;}
aset(int x){st=new item(x);end=st;}
//复制函数
void cop(aset &a1){st=new item(a1.st->data);end=st;item *p=a1.st->next;while(p!=a1.end){append(p->data);p=p->next;}append(a1.end->data);}
//在最后插入
void append(int x){end->next=new item(x);end=end->next;}
//删除指定数据
int del(int x)
{int de=0;
item *sh=st,*now=st->next;
if (sh->data==x){st=st->next;delete sh;return 1;}
while(now!=0 )
{
if (x!=now->data){ sh=now;now=now->next;}
else {sh->next=now->next;de=1;break;}
}
if (de!=0)return 1;
else return 0;
}
//判断x是不是在集合中
int exitence(int x)
{
item *sh=st,*now=st->next;
if (sh->data==x){return 1;}
while(now!=0 )
{
if (x!=now->data){ sh=now;now=now->next;}
else {return 1;}
}
return 0;
}
//空集合判断
int impty()
{
if (st==0) return 1;
else return 0;
}
//判断集合是否相等
friend int equ(aset &s,aset &a);
//交集
void mix(aset a,aset &m)
{
item *now=st;
int x;
while(now!=0 )
{
x=now->data;
// cout<<x;
if (1==a.exitence(x)) {if (m.st==0) m=aset(x);else m.append(x);}
now=now->next;
}

}
//并集
void merge(aset a,aset &m)
{
m.cop(a);
item *now=st;
int x;
while(now!=0 )
{
x=now->data;
cout<<"xx:"<<x<<" ";
if (0==a.exitence(x)) {m.append(x);};
now=now->next;
}

}
//显示
void dis(){item *p=st;while(p!=0){cout<<p->data<<" ";p=p->next;} cout<<"\n";}
private:
item *st;
item *end;
};
int equ(aset &s,aset &a2)
{
aset a;
a.cop(a2);
item *p=s.st;
int da;
int eq(1);
while(p!=0)
{
da=p->data;
eq=a.del(da);
if (eq==0) return 1;
p=p->next;

}
if (a.st==0) return 0;
else return 1;
}

void main()
{
int i;
aset set1(5),set2(111);
for(i=1;i<10;i++)
{
if (i==1) set1=aset(i);
else set1.append(i);
}
cout<<"集合1:";
set1.dis();
for(i=1;i<20;i=i+2)
{
if (i==1) set2=aset(i);
else set2.append(i);
}
cout<<"集合2:";
set2.dis();
aset mset,mer;
cout<<"集合1 和集合2 的交集：";
set1.mix(set2,mset);
mset.dis();
cout<<"集合1 和集合2 的并集：";
set1.merge(set2,mset);
mset.dis();
}

Answer 3

类中的整数集合中的整数个数是有限的吗 如果是有限的那好办了，如果个数不一定是多少，那就先定义一个结构，里面存一个整数然后向堆内存申请空间
typedef struct aint
{
int a;
pint next=NULL;
}* pint;//C语言的语法
class gint
{
private:
gint();
pint head;
~gint;
public:
void add();
// del();
//isempty();
//delnum();
// cand();
// cor();
copaint();
}
gint::gint()
{
head=NULL;
}
gint::~gint()
{
delete head;
}
voie gint::add(int a)
{
pint nint=new aint();
nint->next=head;
head=nint;
}

大概就是这样了，在类里面定义一个指针，然后用指针指向一个链表
你表达的意思我不是十分看懂
如果向集合里面添加整数，重复了怎么办

Answer 4

错误太多了...我也不知道是哪都错了

Answer 5

LS的就这么简单？为何不给完全版？
偶晚上发完全版的。