#include <iostream>
#include <fstream>
#include <algorithm>
#include<cstring>
using namespace std;
class AbsCollection {
protected:
int *iPtr;
int last;
int maxSize;
public:
AbsCollection(int size = 100) {
if(size < 1) {
throw "InvalidArgument: size < 1";
}
maxSize = size;
iPtr = new int[maxSize];
last = -1;
}
virtual ~AbsCollection() {}
void OutputSet() {
for(int i = 0; i <= last; i++) {
cout << iPtr[i] << " ";
}
cout << endl;
}
};
class Set : public AbsCollection {
private:
char* fileName;
public:
Set(int size = 100, const char* szFileName = "m") : AbsCollection(size), fileName(new char[strlen(szFileName)+1]) {
strcpy(fileName, szFileName);
ifstream fin(fileName);
if(!fin) {
last = -1;
return;
}
int x;
while(fin >> x) {
if(isInSet(x)) {
continue;
}
input(x);
}
fin.close();
}
~Set() {
ofstream fout(fileName,ios::out);
sort();
for(int i = 0; i <= last; i++) {
fout << iPtr[i] << " ";
}
fout.close();
delete[] fileName;
}
void input(int x) {
if(last >= maxSize-1) {
return;
}
if(isInSet(x)) {
return;
}
last++;
iPtr[last] = x;
}
void erase(int x) {
for(int i = 0; i <= last; i++) {
if(iPtr[i] == x) {
iPtr[i] = iPtr[last];
last--;
return;
}
}
}
int isInSet(int x) {
for(int i = 0; i <= last; i++) {
if(iPtr[i] == x) {
return 1;
}
}
return 0;
}
friend ostream& operator<<(ostream& os, Set& s) {
for(int i = 0; i <= s.last; i++) {
os << s.iPtr[i] << " ";
}
return os;
}
void intersection(Set& s) {
int i = 0, j = 0, k = 0;
while(i <= last && j <= s.last) {
if(iPtr[i] == s.iPtr[j]) {
iPtr[k++] = iPtr[i];
i++;
j++;
}
else if(iPtr[i] < s.iPtr[j]) {
i++;
}
else {
j++;
}
}
last = k-1;
}
void operator+(Set& s) {
for(int i = 0; i <= s.last; i++) {
input(s.iPtr[i]);
}
}
void diff(Set& s) {
for(int i = 0; i <= s.last; i++) {
erase(s.iPtr[i]);
}
}
Set& operator=(Set& s) {
if(this == &s) {
return *this;
}
maxSize = s.maxSize;
last = s.last;
delete[] iPtr;
iPtr = new int[maxSize];
for(int i = 0; i <= last; i++) {
iPtr[i] = s.iPtr[i];
}
return *this;
}
void sort() {
std::sort(iPtr, iPtr+last+1, std::greater<int>());
}
bool operator<(Set& s) {
return last < s.last;
}
};
int main() {
try {
Set s1(50, "set1.txt");
Set s2(50, "set2.txt");
cout << "Set 1: " << s1 << endl;
cout << "Set 2: " << s2 << endl;
s1.input(3);
cout << "After insert 3 to set 1: " << s1 << endl;
cout << "Is 3 in set 1 " << s1.isInSet(3) << endl;
s1.erase(2);
cout << "After erase 2 from set 1: " << s1 << endl;
s1.intersection(s2);
cout << "Intersection of set 1 and set 2: " << s1 << endl;
s1 + s2;
cout << "Union of set 1 and set 2: " << s1 << endl;
s1.diff(s2);
cout << "Difference of set 1 and set 2: " << s1 << endl;
s1.sort();
cout << "Set 1 after sorting: " << s1 << endl;
if(s1 < s2) {
cout << "Set 1 is smaller than set 2" << endl;
}
else {
cout << "Set 1 is not smaller than set 2" << endl;
}
}
catch(const char* msg) {
cerr << msg << endl;
}
return 0;
}
代码功能归根结底不是别人帮自己看或讲解或注释出来的;而是被自己静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒:再牛×的老师也无法代替学生自己领悟和上厕所!
单步调试和设断点调试(VS IDE中编译连接通过以后,按F10或F11键单步执行,按Shift+F11退出当前函数;在某行按F9设断点后按F5执行停在该断点处。)是程序员必须掌握的技能之一。
堆其实就是用数组实现的二叉树,它是利用完全二叉树的结构来维护一组数据。这使得它每进行一组相关操作的时间复杂度为O(1)~O(logN)
之间,是相当的有优势哇。
那么什么是完全二叉树呢?我们来看这样一组图:
完全二叉树其实就是指高为h的二叉树中前h-1层是满的,最后一层的节点连续集中在最左边。如上图中,你能分辨出来吗?左图为一个完全二叉树,右图则只是一个普通的二叉树。