檢查方法是一個集合b是另一個集合的一個子集a是循環遍歷b中的每個元素並驗證它存在於a中。如果兩個集合都被排序，這會更快（例如，這是std::set的情況）。
你的班級使用固定大小（5，無論出於何種原因）的int數組（而且最好使用std::vector）。我認爲這應該是一個使用動態分配的改進。
所以，檢查一組是一個子集，我會建議你是這樣的：
// a.isSubset(b) check if b is a subset of a
bool Sets::isSubset(const Sets &b) {
for (int i = 0; i < b.size; i++) {
bool is_present = false;
for (int j = 0; j < size; j++) {
// b is a subset if all of its element are in a
// so check if any element of b is in a
if (arr[j] == b.arr[i]) {
is_present = true;
break;
}
}
if (!is_present) return false;
}
return true;
}
// a.isProper(b) check if b is a proper subset of a
bool Sets::isProper(const Sets &b) {
int n_equals = 0;
for (int i = 0; i < b.size; i++) {
bool is_present = false;
for (int j = 0; j < size; j++) {
// b is a prpoper subset if all of its element are in a
// but there exists at least one element of a that is not in b
if (arr[j] == b.arr[i]) {
is_present = true;
++n_equals;
break;
}
}
if (!is_present) return false;
}
return n_equals < size;
}
你的類應該作相應的修改。
編輯
爲了獲得更好的性能，並簡化大部分最好使用一個排序容器的算法。例如，兩個函數belove可能會變成：
// a.isSubset(b) check if b is a subset of a. Requires that both are sorted
bool Sets::isSubset(const Sets &b) {
for (int i = 0, j = 0; i < b.size; i++) {
// scan a, which is sorted
while (j < size && arr[j] < b.arr[i]) ++j;
if (j == size || arr[j] > b.arr[i])
// There's at least one element of b which not belongs to a
return false;
// b.arr[i] == arr[j], move on
}
// all the element of b are in a too
return true;
}
// a.isProper(b) check if b is a proper subset of a.
// It requires that both are sorted
bool Sets::isProper(const Sets &b) {
int n_equals = 0;
for (int i = 0, j = 0; i < b.size; i++) {
while (j < size && arr[j] < b.arr[i]) ++j;
if (j == size || arr[j] > b.arr[i])
// b is a prpoper subset if all of its element are in a
// but there exists at least one element of a that is not in b
return false;
++n_equals;
}
return n_equals < size;
}
要強制排序，只需修改添加元素的函數。我加了一些輔助功能太：
#include <iostream>
using namespace std;
class Sets{
private:
int size;
int allocated;
int *arr;
// It's way better using a std::vector:
// vector<int> v;
// or you can cheat and use a std::set
public:
Sets();
~Sets();
void addElement(int);
void delElement(int);
int getLowerPos(int);
int getElement(int);
int getSize();
bool doesContain(int);
bool isSubset(const Sets &);
bool isProper(const Sets &);
void printSet();
void printOrderedPairs(const Sets &);
};
Sets::Sets() : size(0), allocated(0), arr(nullptr) { }
Sets::~Sets() {
delete[] arr;
}
int Sets::getSize(){
return size;
}
// Add an element if it isn't already present, keeping the array sorted
void Sets::addElement(int x) {
int pos = this->getLowerPos(x);
if (pos < size && arr[pos] == x) return;
if (size == allocated) {
// it's time to expand the array. If it's empty, start from 8
allocated = allocated > 0 ? allocated * 2 : 8;
int *new_arr = new int[allocated];
for (int i = 0; i < pos; i++) {
new_arr[i] = arr[i];
}
for (int i = size; i > pos; --i) {
new_arr[i] = arr[i - 1];
}
delete[] arr;
arr = new_arr;
}
else {
for (int i = size; i > pos; --i) {
arr[i] = arr[i - 1];
}
}
arr[pos] = x;
++size;
}
// Remove an element from the set if it is present, keeping the array sorted
void Sets::delElement(int x) {
int pos = this->getLowerPos(x);
if (pos == size || arr[pos] != x) return;
// I move the elements and update size only, without deallocation.
--size;
for (int i = pos; i < size; ++i) {
arr[i] = arr[i + 1];
}
}
// I guess you want to return the element j of the set or -1 if it's not present
int Sets::getElement(int j){
// consider using size_t instead of int for indeces or at least unsigned int
if (j < 0 || j >= size)
// I assume all the elements are positive integers
return -1;
else
// why the temp?
return arr[j];
}
// Find the position of the lowest element in the set such that x <= arr[pos]
// with a binary search. It requires that the array is sorted.
// Return the value size if all the elements are lower then x
int Sets::getLowerPos(int x) {
int first = 0, count = size - first, step, pos = 0;
while (count > 0) {
step = count/2;
pos = first + step;
if (arr[pos] < x) {
first = ++pos;
count -= step + 1;
}
else
count = step;
}
return first;
}
// Check if x is present in the set with a binary search.
// It requires that the array is sorted
bool Sets::doesContain(int x) {
int pos = this->getLowerPos(x);
return (pos != size && arr[pos] == x);
/*
// Or directly with a simple binary search:
int low = 0, high = size - 1, pos;
while (low <= high) {
pos = low + (high - low)/2;
if (x == arr[pos])
return true;
else if (x < arr[pos])
high = pos - 1;
else
low = pos + 1;
}
return false;
*/
}
// ... isSubset() and isProper() as above ...
void Sets::printOrderedPairs(const Sets &b){
cout << "A X B = {";
for (int i = 0; i < size; i++){
for (int j = 0; j < b.size; j++){
cout << '(' << arr[i] << ", " << b.arr[j] << "), ";
}
}
cout << "\b\b} ";
}
void Sets::printSet(){
cout << '{';
for (int i = 0; i < size; i++){
cout << arr[i] << ", ";
}
cout << "\b\b} ";
}
int main(void) {
try {
Sets a;
Sets b;
a.addElement(9);
a.addElement(3);
a.addElement(7);
a.addElement(5);
a.addElement(1);
b.addElement(3);
b.addElement(7);
b.addElement(1);
b.addElement(5);
cout << "Set A is ";
a.printSet();
cout << "\nSet B is ";
b.printSet();
cout << "\n\n";
a.printOrderedPairs(b);
cout << "\n\n";
if (a.isSubset(b)) {
cout << "Set B is a subset of set A\n";
}
else {
cout << "Set B is not a subset of set A\n";
}
if (a.isProper(b)){
cout << "Set B is a proper subset of set A\n";
}
else{
cout << "Set B is not a proper subset of set A\n";
}
system("PAUSE");
}
catch (const bad_alloc& e) {
cout << "Allocation failed: " << e.what() << '\n';
}
return 0;
}
現在輸出的是：
Set A is {1, 3, 5, 7, 9}
Set B is {1, 3, 5, 7}
A X B = {(1, 1), (1, 3), (1, 5), (1, 7), (3, 1), (3, 3), (3, 5), (3, 7), (5, 1), (5, 3), (5, 5), (5, 7), (7, 1), (7, 3), (7, 5), (7, 7), (9, 1), (9, 3), (9, 5), (9, 7)}
Set B is subset of set A
Set B is proper subset of set A
這是一個很好的起點，學習如何使用調試器。 –
爲什麼你的老師在你實際上只代表一個'Set'時要求你命名類'Sets'？我的意思是，命名**是重要的，重要的是要習慣從一開始就選擇有意義的名稱。 （可能比製作UML圖更重要:)） –
Navta我不知道這意味着什麼。弗蘭克，告訴我關於它 – Radon5K