我认为我的析构函数现在很好......但仍然不确定如何从 operator() 重载中调用 print_set 。
它按应有的方式输出，但我觉得有一种简单的方法可以从函数调用重载中调用 print_set ......似乎无法得到我想要的东西......
头文件：
/**
* disjoint_sets class declaration
*
*/
#include<ostream>
#include<string>
#include<list>
class disjoint_sets
{
public:
disjoint_sets(int n); //n is the maximum int that can be in a set, so arrays need to be of size n+1
~disjoint_sets();
bool make_set(int n);
int find_set(int u);
bool union_set(int u, int v);
void print_set(std::ostream& out, int u); //e.g. { 1, 2, 4, 8, 10, }
operator std::string(); //e.g. "{ { 1, 2, 4, 8, 10, }, { 3, 6, }, { 5, }, { 7, }, { 9, }, }"
private:
typedef std::list<int>* listptr;
int* p; //parent array
int* rank; //rank array
listptr* set; //array of pointers. Each set[i] is a pointer is to a list<int> containing the integers in the i'th set
int size; //the size i.e. maximum int that can be in a set
};
执行：
/**
* disjoint_sets class implementation
*
*/
#include <iostream>
#include <istream>
#include <sstream>
#include <string>
#include <list>
#include "disjoint.hpp"
/*********************
* CONSTRUCTOR
*********************/
disjoint_sets::disjoint_sets(int n)
{
size = n;
// initialize all arrays to same size (n+1)
p = new int[n+1];
rank = new int[n+1];
set = new listptr[n+1];
// loop through set (array of pointers) and initialize
// each element to an empty list
for (int i(1); i <= n; i++)
{
set[i] = new std::list<int>;
}
}
/*********************
* DESTRUCTOR
*********************/
disjoint_sets::~disjoint_sets()
{
delete[] p;
delete[] rank;
// delete each element in the set first, then delete the set.
for(int i(1); i<size+1; i++)
{
set[i]->clear();
}
delete[] set;
}
/*********************
* MAKE_SET
*********************/
bool disjoint_sets::make_set(int n)
{
// if parent already exists
if (p[n] != 0)
{
return false;
}
// else we need to make a set
else
{
// make itself the parent
p[n] = n;
// use push_front to add the int to front of set
set[n]->push_front(n);
return true;
}
}
/*********************
* FIND_SET
***********************/
int disjoint_sets::find_set(int u)
{
while (u != p[u])
{
u = p[u];
}
// returns parent
return u;
}
/*********************
* UNION_SET
*********************/
bool disjoint_sets::union_set(int u, int v)
{
// assign parents to u, v
u = find_set(u);
v = find_set(v);
// return false if parent is 0, list is empty
if (u == 0 or v == 0)
{
return false;
}
// if u's height is less than v's (not in same set)
if (rank[u] < rank[v])
{
// point u's parent to v (merge them)
p[u] = v;
// splice u out
(*set[v]).splice((*set[v]).end(), (*set[u]));
return true;
}
// u's height is greater than or equal to v's height
else
{
// set v's parent to u
p[v] = u;
// splice v out
(*set[u]).splice((*set[u]).end(), (*set[v]));
return true;
}
// if ranks are equal
if (rank[u] == rank[v])
{
// increment rank of u
rank[u]++;
return true;
}
}
/*********************
* PRINT_SET
*********************/
void disjoint_sets::print_set(std::ostream& out, int u)
{
// begin brace for set
out << "{ ";
// loop through with iter, seperate with comma
for (std::list<int>::iterator iter((*set[u]).begin()); iter != (*set[u]).end(); iter++)
{
out << *iter << ", ";
}
// end brace for set
out << "}";
}
/*********************
* STRING CONVERSION
*********************/
disjoint_sets::operator std::string()
{
// sstream variable
std::stringstream text;
// pointer to int array
int *test;
test = new int[size+1];
// opening paren
text << "{ ";
// start main loop through the array
for (int i(1); i <= (size + 1); i++)
{
// if the root is empty
if (test[find_set(i)] == 0)
{
// set to anything != 0?
test[find_set(i)] = 10;
// check if list is empty
if (set[i]->empty())
{
text << "";
}
else
{
// individual set opening parenthesis
text << "{ ";
// use iterator to loop through and load up the stringstream, separate w/ comma
for (std::list<int>::iterator iter((*set[i]).begin()); iter != (*set[i]).end(); iter++)
{
text << *iter << ", ";
}
// individual set closing parenthesis w/ proper punctuation
text << "}, ";
}
}
}
// closing parenthesis
text << "}";
delete[] test;
return text.str();
}
司机：
#include<iostream>
#include "disjoint.hpp"
int main()
{
using namespace std;
disjoint_sets ds(12);
for( int i=1; i <= 10; ++i)
ds.make_set(i);
ds.union_set(1,2);
ds.union_set(2,4);
ds.union_set(1,8);
ds.union_set(3,6);
ds.union_set(2,10);
//{ { 1, 2, 4, 8, 10, }, { 3, 6, }, { 5, }, { 7, }, { 9, }, }
cout << string(ds) << endl;
}