之前有借助于 STL 中的 multimap 實(shí)現(xiàn)查找最小的 k 個(gè)元素。
這里繼續(xù)解決 查找最小的 k 個(gè)元素，采用 最大根堆。
1 #include <iostream>
2 #include <ctime>
3 #include <vector>
4 using namespace std;
5
6 class Heap
7 {
8 private:
9 int* data;
10 int _size;
11 int _capacity;
12 public:
13 Heap()
14 {
15 _size = 0;
16 _capacity = 2 * _size;
17 data = new int[_capacity];
18 if (data == 0)
19 {
20 exit(1);
21 }
22 }
23 Heap(const Heap& h)
24 {
25 _size = h._size;
26 _capacity = h._capacity;
27 data = new int[_capacity];
28 if (data == 0)
29 {
30 exit(1);
31 }
32 memcpy(data, h.data, sizeof (int) * h._size);
33 }
34 Heap& operator =(const Heap& h)
35 {
36 delete [] data;
37 _size = h._size;
38 _capacity = h._capacity;
39 data = new int[_capacity];
40 if (data == 0)
41 {
42 exit(1);
43 }
44 memcpy(data, h.data, sizeof (int) * h._size);
45 }
46 ~Heap()
47 {
48 delete [] data;
49 }
50 void insert(int item)
51 {
52 if (_size >= _capacity - 1)
53 {
54 _capacity = (_capacity + 1) * 2;
55 int * tmp = new int[_capacity];
56 if (tmp == 0)
57 {
58 exit(1);
59 }
60 // 1
61 memcpy(tmp, data, sizeof (int) * _capacity / 2 - 1);
62 delete [] data;
63 data = tmp;
64 }
65 data[++_size] = item;
66 int pos1 = _size;
67 int pos2 = pos1 / 2;
68 while (pos2 >= 1 && data[pos1] > data[pos2])
69 {
70 data[pos1] ^= data[pos2];
71 data[pos2] ^= data[pos1];
72 data[pos1] ^= data[pos2];
73 pos1 = pos2;
74 pos2 = pos1 / 2;
75 }
76 }
77 int max()
78 {
79 return data[1];
80 }
81 int erase()
82 {
83 int tmp = data[1];
84 data[1] = data[_size];
85 --_size;
86 int pos1 = 1, pos2;
87 pos2 = pos1 * 2;
88
89 while (pos2 <= _size)
90 {
91 if (pos2 < _size && data[pos2 + 1] > data[pos2])
92 {
93 ++pos2;
94 }
95 if (data[pos1] < data[pos2])
96 {
97 data[pos1] ^= data[pos2];
98 data[pos2] ^= data[pos1];
99 data[pos1] ^= data[pos2];
100 }
101 pos1 = pos2;
102 pos2 = pos1 * 2;
103 }
104 return tmp;
105 }
106 int size()
107 {
108 return _size;
109 }
110 int capacity()
111 {
112 return _capacity;
113 }
114 void test()
115 {
116 for (int i = 1; i <= _size; ++i)
117 {
118 cout << data[i] << ' ';
119 }
120 cout << endl;
121 }
122 };
123
124 void findMinK(Heap& h, int k, const vector<int>& data)
125 {
126 int m = 0;
127 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
128 {
129 if (m < k)
130 {
131 h.insert(*cit);
132 ++m;
133 }
134 else
135 {
136 if (*cit < h.max())
137 {
138 h.erase();
139 h.insert(*cit);
140 }
141 }
142 }
143 }
144
145 int main()
146 {
147 int n = 100;
148 Heap h;
149 vector<int> data;
150 srand(time(0));
151 while (n--)
152 {
153 data.push_back(rand());
154 }
155 findMinK(h, 10, data);
156 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
157 {
158 cout << *cit << ' ';
159 }
160 cout << endl;
161 for (int i = 0; i < 10; ++i)
162 {
163 cout << h.erase() << endl;
164 }
165 cout << endl;
166 return 0;
167 }
一個(gè)簡單的堆的實(shí)現(xiàn)，大根堆。
1 #include <iostream>
2 #include <ctime>
3 using namespace std;
4
5 class Heap
6 {
7 private:
8 int* data;
9 int _size;
10 int _capacity;
11 public:
12 Heap()
13 {
14 _size = 0;
15 _capacity = 2 * _size;
16 data = new int[_capacity];
17 if (data == 0)
18 {
19 exit(1);
20 }
21 }
22 Heap(const Heap& h)
23 {
24 _size = h._size;
25 _capacity = h._capacity;
26 data = new int[_capacity];
27 if (data == 0)
28 {
29 exit(1);
30 }
31 memcpy(data, h.data, sizeof (int) * h._size);
32 }
33 Heap& operator =(const Heap& h)
34 {
35 delete [] data;
36 _size = h._size;
37 _capacity = h._capacity;
38 data = new int[_capacity];
39 if (data == 0)
40 {
41 exit(1);
42 }
43 memcpy(data, h.data, sizeof (int) * h._size);
44 }
45 ~Heap()
46 {
47 delete [] data;
48 }
49 void insert(int item)
50 {
51 if (_size >= _capacity - 1)
52 {
53 _capacity = (_capacity + 1) * 2;
54 int * tmp = new int[_capacity];
55 if (tmp == 0)
56 {
57 exit(1);
58 }
59 // 1
60 memcpy(tmp, data, sizeof (int) * _capacity / 2 - 1);
61 delete [] data;
62 data = tmp;
63 }
64 data[++_size] = item;
65 int pos1 = _size;
66 int pos2 = pos1 / 2;
67 while (pos2 >= 1 && data[pos1] > data[pos2])
68 {
69 data[pos1] ^= data[pos2];
70 data[pos2] ^= data[pos1];
71 data[pos1] ^= data[pos2];
72 pos1 = pos2;
73 pos2 = pos1 / 2;
74 }
75 }
76 int max()
77 {
78 return data[1];
79 }
80 int erase()
81 {
82 int tmp = data[1];
83 data[1] = data[_size];
84 --_size;
85 int pos1 = 1, pos2;
86 pos2 = pos1 * 2;
87
88 while (pos2 <= _size)
89 {
90 if (pos2 < _size && data[pos2 + 1] > data[pos2])
91 {
92 ++pos2;
93 }
94 if (data[pos1] < data[pos2])
95 {
96 data[pos1] ^= data[pos2];
97 data[pos2] ^= data[pos1];
98 data[pos1] ^= data[pos2];
99 }
100 pos1 = pos2;
101 pos2 = pos1 * 2;
102 }
103 return tmp;
104 }
105 int size()
106 {
107 return _size;
108 }
109 int capacity()
110 {
111 return _capacity;
112 }
113 void test()
114 {
115 for (int i = 1; i <= _size; ++i)
116 {
117 cout << data[i] << ' ';
118 }
119 cout << endl;
120 }
121 };
122
123 int main()
124 {
125 int n = 10;
126 Heap h;
127 srand(time(0));
128 while (n--)
129 // for (int i = 0; i < 10; ++i)
130 {
131 h.insert(rand());
132 // h.insert(i);
133 // cout << h.size() << ' ' << h.capacity() << endl;
134 }
135 h.test();
136 for (int i = 0; i < 10; ++i)
137 {
138 cout << h.erase() << endl;
139 }
140 h.test();
141 return 0;
142 }
直觀的解法是對(duì)所有的 N 個(gè)數(shù)進(jìn)行排序，再取最前或最后的 k 個(gè)元素。
這種做法的時(shí)間復(fù)雜度為 O(NlogN) 。
一種較好的解法是：維持一個(gè) k 個(gè)元素的集合 S，遍歷 N 個(gè)數(shù)，對(duì)每個(gè)元素，首先檢查 S 中的元素個(gè)數(shù)是否小于 k，如果小于直接加入到 S 中。如果 S 中已有 k 個(gè)元素，則比較待處理元素與 S 中最大的元素的大小關(guān)系，若小于 S 中最大的元素，則刪除 S 中最大的元素，并將該元素加入到 S 中。
怎樣才能快速地從 S 中尋找到我們想要的最大的元素，使用堆是個(gè)好方法，最大堆。每次直接去堆的第一個(gè)元素即是 S 中最大的元素。如果將 S 中的最大元素刪除，然后將 最后的一個(gè)元素放在堆頂，下滑，已調(diào)整堆。在講新的元素加入到堆中，上滑，以調(diào)整堆?？梢詫⑦@兩個(gè)過程合并，即將 S 中最大的元素替換為 待處理的元素。對(duì)這個(gè)堆頂上的元素下滑，以調(diào)整堆。這里的復(fù)雜度為 O(Nlogk)。
STL 中的 multimap 不是堆，但是其可以以 O(logn) 維護(hù)其有序性，所以可以直接用 multimap 代替堆來實(shí)現(xiàn)。
http://zhedahht.blog.163.com/blog/static/2541117420072432136859/
1 #include <iostream>
2 #include <vector>
3 #include <set>
4 #include <ctime>
5 using namespace std;
6
7 void findMinK(multiset<int, greater<int> >& Kdata, int k, const vector<int>& data)
8 {
9 Kdata.clear();
10 int m = 0;
11 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
12 {
13 if (m < k)
14 {
15 Kdata.insert(*cit);
16 ++m;
17 }
18 else
19 {
20 if (*cit < *(Kdata.begin()))
21 {
22 Kdata.erase(Kdata.begin());
23 Kdata.insert(*cit);
24 }
25 }
26 }
27 }
28
29 int main()
30 {
31 vector<int> data;
32 srand(time(0));
33 int n = 100;
34 while (n--)
35 {
36 data.push_back(rand());
37 }
38 multiset<int, greater<int> > Kdata;
39 findMinK(Kdata, 10, data);
40 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
41 {
42 cout << *cit << ' ';
43 }
44 cout << endl;
45 for (multiset<int, greater<int> >::const_iterator cit = Kdata.begin(); cit != Kdata.end(); ++cit)
46 {
47 cout << *cit << ' ';
48 }
49 cout << endl;
50 return 0;
51 }
posted @
2011-04-26 22:59 unixfy 閱讀(1200) |
評(píng)論 (3) |
編輯 收藏
來自于《大話設(shè)計(jì)模式》
觀察者模式：定義了一種一對(duì)多的依賴關(guān)系，讓多個(gè)觀察者對(duì)象同時(shí)監(jiān)聽某一個(gè)主題對(duì)象。這個(gè)主題對(duì)象在狀態(tài)發(fā)生時(shí)，會(huì)通知所有觀察者對(duì)象，使他們自動(dòng)更新自己。
行為型模式。
UML 類圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 #include <string>
3 #include <list>
4 #include <algorithm>
5 using namespace std;
6
7 class Subject;
8
9 class Observer
10 {
11 protected:
12 string name;
13 Subject* sub;
14 public:
15 Observer(const string& n, Subject* s) : name(n), sub(s) {}
16 virtual void Update() = 0;
17 };
18
19 class Subject
20 {
21 protected:
22 list<Observer*> observers;
23 string action;
24 public:
25 virtual void Attach(Observer* ob) = 0;
26 virtual void Detach(Observer* ob) = 0;
27 virtual void Notify() = 0;
28 virtual void setAction(const string& s) = 0;
29 virtual string getAction() = 0;
30 };
31
32 class StockObserver : public Observer
33 {
34 public:
35 StockObserver(const string& name, Subject* s) : Observer(name, s) {}
36 virtual void Update()
37 {
38 cout << sub->getAction() << '\t' << name << " 關(guān)閉股票行情，繼續(xù)工作！" << endl;
39 }
40 };
41
42 class NBAObserver : public Observer
43 {
44 public:
45 NBAObserver(const string& name, Subject* s) : Observer(name, s) {}
46 virtual void Update()
47 {
48 cout << sub->getAction() << '\t' << name << " 關(guān)閉 NBA，繼續(xù)工作！" << endl;
49 }
50 };
51
52 class Boss : public Subject
53 {
54 //private:
55 // list<Observer*> observers;
56 // string action;
57 public:
58 virtual void Attach(Observer* ob)
59 {
60 observers.push_back(ob);
61 }
62 virtual void Detach(Observer* ob)
63 {
64 list<Observer*>::iterator iter= find(observers.begin(), observers.end(), ob);
65 if (iter != observers.end())
66 {
67 observers.erase(iter);
68 }
69 }
70 virtual void Notify()
71 {
72 for (list<Observer*>::iterator iter = observers.begin(); iter != observers.end(); ++iter)
73 {
74 (*iter)->Update();
75 }
76 }
77 virtual void setAction(const string& s)
78 {
79 action = s;
80 }
81 virtual string getAction()
82 {
83 return action;
84 }
85 };
86
87 class Secretary : public Subject
88 {
89 //private:
90 // list<Observer*> observers;
91 // string action;
92 public:
93 virtual void Attach(Observer* ob)
94 {
95 observers.push_back(ob);
96 }
97 virtual void Detach(Observer* ob)
98 {
99 list<Observer*>::iterator iter = find(observers.begin(), observers.end(), ob);
100 if (iter != observers.end())
101 {
102 observers.erase(iter);
103 }
104 }
105 virtual void Notify()
106 {
107 for (list<Observer*>::iterator iter = observers.begin(); iter != observers.end(); ++iter)
108 {
109 (*iter)->Update();
110 }
111 }
112 virtual void setAction(const string& s)
113 {
114 action = s;
115 }
116 virtual string getAction()
117 {
118 return action;
119 }
120 };
121
122
123
124 int main()
125 {
126 Boss* huhansan = new Boss;
127 StockObserver* so = new StockObserver("abc", huhansan);
128 NBAObserver* no = new NBAObserver("xyz", huhansan);
129
130 huhansan->Attach(so);
131 huhansan->Attach(no);
132 huhansan->setAction("我胡漢三又回來了！");
133 huhansan->Notify();
134
135 huhansan->Detach(no);
136 huhansan->setAction("開會(huì)！");
137 huhansan->Notify();
138
139 delete huhansan;
140
141 Secretary* s = new Secretary;
142 s->Attach(no);
143 s->Attach(so);
144 s->setAction("老板來了！");
145 cout << s->getAction() << endl;
146 s->Notify();
147
148 delete so;
149 delete no;
150 delete s;
151
152 return 0;
153 }
來自于《大話設(shè)計(jì)模式》
建造者模式（Builder）：將一個(gè)復(fù)雜對(duì)象的構(gòu)建與它的表示分離，使得同樣的構(gòu)建過程可以創(chuàng)建不同的表示。
UML 類圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 #include <string>
3 #include <list>
4 using namespace std;
5
6 class Product
7 {
8 private:
9 list<string> parts;
10 public:
11 void Add(string s)
12 {
13 parts.push_back(s);
14 }
15 void Show()
16 {
17 for (list<string>::const_iterator cit = parts.begin(); cit != parts.end(); ++cit)
18 {
19 cout << *cit << endl;
20 }
21 }
22 };
23
24 class Builder
25 {
26 public:
27 Builder() {}
28 virtual ~Builder() {}
29 virtual void BuildPartA() = 0;
30 virtual void BuildPartB() = 0;
31 virtual Product* GetResult() = 0;
32 };
33
34 class ConcreteBuilder1 : public Builder
35 {
36 private:
37 Product* p;
38 public:
39 ConcreteBuilder1() : p(new Product) {}
40 virtual ~ConcreteBuilder1()
41 {
42 delete p;
43 }
44 virtual void BuildPartA()
45 {
46 p->Add("部件 A - 1");
47 }
48 virtual void BuildPartB()
49 {
50 p->Add("部件 B - 1");
51 }
52 virtual Product* GetResult()
53 {
54 return p;
55 }
56 };
57
58 class ConcreteBuilder2 : public Builder
59 {
60 private:
61 Product* p;
62 public:
63 ConcreteBuilder2() : p(new Product) {}
64 virtual ~ConcreteBuilder2()
65 {
66 delete p;
67 }
68 virtual void BuildPartA()
69 {
70 p->Add("部件 A - 2");
71 }
72 virtual void BuildPartB()
73 {
74 p->Add("部件 B - 2");
75 }
76 virtual Product* GetResult()
77 {
78 return p;
79 }
80 };
81
82 class Director
83 {
84 public:
85 void Construct(Builder& b)
86 {
87 b.BuildPartA();
88 b.BuildPartB();
89 }
90 };
91
92 int main()
93 {
94 Director d;
95 ConcreteBuilder1 b1;
96 ConcreteBuilder2 b2;
97
98 d.Construct(b1);
99 Product* p1 = b1.GetResult();
100 p1->Show();
101
102 d.Construct(b2);
103 Product* p2 = b2.GetResult();
104 p2->Show();
105
106 return 0;
107 }
來自于《大話設(shè)計(jì)模式》
外觀模式（Facade）：為子系統(tǒng)的一組接口提供一個(gè)一致的界面，此模式定義了一個(gè)高層接口，這個(gè)接口使得這一子系統(tǒng)更加容易使用。
UML 類圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 using namespace std;
3
4 class Stock1
5 {
6 public:
7 void Sell()
8 {
9 cout << "股票 1 賣出" << endl;
10 }
11 void Buy()
12 {
13 cout << "股票 1 買入" << endl;
14 }
15 };
16
17 class Stock2
18 {
19 public:
20 void Sell()
21 {
22 cout << "股票 2 賣出" << endl;
23 }
24 void Buy()
25 {
26 cout << "股票 2 買入" << endl;
27 }
28 };
29
30 class Stock3
31 {
32 public:
33 void Sell()
34 {
35 cout << "股票 3 賣出" << endl;
36 }
37 void Buy()
38 {
39 cout << "股票 3 買入" << endl;
40 }
41 };
42
43 class Stock4
44 {
45 public:
46 void Sell()
47 {
48 cout << "股票 4 賣出" << endl;
49 }
50 void Buy()
51 {
52 cout << "股票 4 買入" << endl;
53 }
54 };
55
56 class Fund
57 {
58 private:
59 Stock1* s1;
60 Stock2* s2;
61 Stock3* s3;
62 Stock4* s4;
63 public:
64 Fund() : s1(new Stock1), s2(new Stock2), s3(new Stock3), s4(new Stock4) {}
65 ~Fund()
66 {
67 delete s1;
68 delete s2;
69 delete s3;
70 delete s4;
71 }
72 void Sell()
73 {
74 s1->Sell();
75 s2->Sell();
76 s3->Sell();
77 s4->Sell();
78 }
79 void Buy()
80 {
81 s1->Buy();
82 s2->Buy();
83 s3->Buy();
84 s4->Buy();
85 }
86 };
87
88 int main()
89 {
90 Fund f;
91 f.Buy();
92 f.Sell();
93 return 0;
94 }
函數(shù)實(shí)現(xiàn)將網(wǎng)址進(jìn)行如下操作
www.google.com 轉(zhuǎn)成 com.google.www 及 mail.netease.com 轉(zhuǎn)成 com.netease.mail
不允許用STL,空間為 O(1)
http://topic.csdn.net/u/20110425/12/8b5e155c-73d1-40af-84b8-6b6493f638e2.html一開始把 O(1) 看做時(shí)間復(fù)雜度了，如果是空間復(fù)雜度，直接在原地兩次翻轉(zhuǎn)即可。整體翻轉(zhuǎn)，部分翻轉(zhuǎn)順序可以任意。
1 #include <iostream>
2 using namespace std;
3
4 void reverse_(char* s, int left, int right)
5 {
6 while (left < right)
7 {
8 s[left] ^= s[right];
9 s[right] ^= s[left];
10 s[left] ^= s[right];
11 ++left;
12 --right;
13 }
14 }
15
16 int findch(char* s, char c, int n)
17 {
18 int ret, len = strlen(s);
19 for (ret = n; ret < len; ++ret)
20 {
21 if (s[ret] == c)
22 {
23 return ret;
24 }
25 }
26 return -1;
27 }
28
29 char* reverse(char* s)
30 {
31 reverse_(s, 0, strlen(s) - 1);
32 int left = 0, right = findch(s, '.', left);
33 while (right != -1)
34 {
35 reverse_(s, left, right - 1);
36 left = right + 1;
37 right = findch(s, '.', left);
38 }
39 reverse_(s, left, strlen(s) - 1);
40 return s;
41 }
42
43 int main()
44 {
45 char s[100];
46 while (cin >> s)
47 {
48 cout << reverse(s) << endl;
49 }
50 return 0;
51 }
如果是時(shí)間復(fù)雜度呢？
這里由個(gè)限制，就是只有兩個(gè) . 符號(hào)時(shí)才成立。使用字符串?dāng)?shù)組存儲(chǔ)字符串，將首尾字符串指針交換即可。
例如 mail.netease.com
存在于字符串指針數(shù)組中：
mail
.
netease
.
com
將指向 mail 和 指向 com 的兩個(gè)字符串指針交換即可。
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 char* s[100];
7 int i;
8 for (i = 0; i < 100; ++i)
9 {
10 s[i] = new char[100];
11 }
12 char c;
13 i = 0;
14 int j = 0;
15 // while (cin >> c)
16 // while (scanf("%c", &c))
17 while (c = getchar())
18 {
19 if (c == '\n')
20 {
21 break;
22 }
23 if (c != '.')
24 {
25 s[i][j] = c;
26 ++j;
27 s[i][j] = '\0';
28 }
29 else
30 {
31 // s[i][j] = '\0';
32 ++i;
33 s[i][0] = c;
34 s[i][1] = '\0';
35 j = 0;
36 ++i;
37 }
38 }
39 char* t = s[0];
40 s[0] = s[i];
41 s[i] = t;
42 for (j = 0; j <= i; ++j)
43 {
44 cout << s[j];
45 }
46 cout << endl;
47 return 0;
48 }
來自于《大話設(shè)計(jì)模式》
模板方法模式：定義一個(gè)操作中的算法的骨架，而將一些步驟延遲到子類中。模板方法使得子類可以不改變一個(gè)算法的結(jié)構(gòu)即可重定義該算法的某些特定步驟。
盡量將公共操作上移到基類中，這樣便于修改，代碼復(fù)用性更強(qiáng)。
UML 類圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 class TestPaper
6 {
7 public:
8 virtual void TestQuestion1()
9 {
10 cout << "TestQuestion1" << endl;
11 cout << "Answer: " << Answer1() << endl;
12 }
13 virtual void TestQuestion2()
14 {
15 cout << "TestQuestion2" << endl;
16 cout << "Answer: " << Answer2() << endl;
17 }
18 virtual void TestQuestion3()
19 {
20 cout << "TestQuestion3" << endl;
21 cout << "answer: " << Answer3() << endl;
22 }
23 virtual const string Answer1() = 0
24 {
25 return "";
26 }
27 virtual const string Answer2() = 0
28 {
29 return "";
30 }
31 virtual const string Answer3() = 0
32 {
33 return "";
34 }
35 };
36
37 class TestPaperA : public TestPaper
38 {
39 public:
40 virtual const string Answer1()
41 {
42 return "a";
43 }
44 virtual const string Answer2()
45 {
46 return "b";
47 }
48 virtual const string Answer3()
49 {
50 return "c";
51 }
52 };
53
54 class TestPaperB : public TestPaper
55 {
56 public:
57 virtual const string Answer1()
58 {
59 return "c";
60 }
61 virtual const string Answer2()
62 {
63 return "b";
64 }
65 virtual const string Answer3()
66 {
67 return "a";
68 }
69 };
70
71 int main()
72 {
73 TestPaperA a;
74 a.TestQuestion1();
75 a.TestQuestion2();
76 a.TestQuestion3();
77
78 TestPaperB b;
79 b.TestQuestion1();
80 b.TestQuestion2();
81 b.TestQuestion3();
82
83 TestPaper* p;
84 p = new TestPaperA;
85 p->TestQuestion1();
86 p->TestQuestion2();
87 p->TestQuestion3();
88 delete p;
89
90 p = new TestPaperB;
91 p->TestQuestion1();
92 p->TestQuestion2();
93 p->TestQuestion3();
94 delete p;
95
96 return 0;
97 }
來自于《大話設(shè)計(jì)模式》
原型模式（Prototype）：用原型實(shí)例指定創(chuàng)建對(duì)象的種類，并且通過拷貝這些原型創(chuàng)建新的對(duì)象。
這個(gè)設(shè)計(jì)模式在 C++ 中如何實(shí)現(xiàn)？
UML 圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 using namespace std;
3
4 class Prototype
5 {
6 public:
7 virtual Prototype& Clone() = 0;
8 };
9
10 class ConcretePrototype
11 {
12 private:
13 int m;
14 char* str;
15 public:
16 ConcretePrototype(int n = 0, const char* s = "") : m(n)
17 {
18 str = new char[strlen(s) + 1];
19 if (str == 0)
20 {
21 exit(1);
22 }
23 strcpy(str, s);
24 }
25 ConcretePrototype(const ConcretePrototype& p)
26 {
27 str = new char[strlen(p.str) + 1];
28 if (str == 0)
29 {
30 exit(1);
31 }
32 strcpy(str, p.str);
33 m = p.m;
34 }
35 ConcretePrototype& operator =(const ConcretePrototype& p)
36 {
37 if (this == &p)
38 {
39 delete [] str;
40 str = new char[strlen(p.str) + 1];
41 if (str == 0)
42 {
43 exit(1);
44 }
45 strcpy(str, p.str);
46 m = p.m;
47 }
48 return *this;
49 }
50 ~ConcretePrototype()
51 {
52 delete [] str;
53 }
54 ConcretePrototype& Clone()
55 {
56 return *this;
57 }
58 void SetStr(const char* s = "")
59 {
60 delete [] str;
61 str = new char[strlen(s) + 1];
62 if (str == 0)
63 {
64 exit(1);
65 }
66 strcpy(str, s);
67 }
68 void SetM(int n)
69 {
70 m = n;
71 }
72 void SetStrAndM(const char* s, int n)
73 {
74 delete [] str;
75 str = new char[strlen(s) + 1];
76 if (str == 0)
77 {
78 exit(1);
79 }
80 strcpy(str, s);
81 m = n;
82 }
83 void test()
84 {
85 cout << m << endl;
86 cout << str << endl;
87 }
88 };
89
90 int main()
91 {
92 ConcretePrototype c(5, "abc");
93 c.test();
94
95 ConcretePrototype c2 = static_cast<ConcretePrototype>(c.Clone());
96 c2.test();
97
98 c2.SetStrAndM("xyz", 7);
99 c2.test();
100
101 return 0;
102
103 }
來自于《大話設(shè)計(jì)模式》
工廠方法模式（Factory Method）：定義一個(gè)用于創(chuàng)建對(duì)象的接口，讓子類決定實(shí)例化哪一個(gè)類。工廠方法使一個(gè)類的實(shí)例化延遲到其子類。
有一個(gè)操作類 Operation，繼承其而派生出具體各個(gè)操作的操作派生類。
產(chǎn)生操作類的工廠基類 IFactory，繼承其而派生出產(chǎn)生具體操作類的工廠派生類。
UML 類圖：
代碼實(shí)現(xiàn) C++：
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5 class Operation
6 {
7 protected:
8 double NumberA;
9 double NumberB;
10 public:
11 virtual void SetNumberA(double a)
12 {
13 NumberA = a;
14 }
15 virtual void SetNumberB(double b)
16 {
17 NumberB = b;
18 }
19 virtual double GetResult() = 0;
20 };
21
22 class OperationAdd : public Operation
23 {
24 public:
25 virtual double GetResult()
26 {
27 return NumberA + NumberB;
28 }
29 };
30
31 class OperationSub : public Operation
32 {
33 public:
34 virtual double GetResult()
35 {
36 return NumberA - NumberB;
37 }
38 };
39
40 class OperationMul : public Operation
41 {
42 public:
43 virtual double GetResult()
44 {
45 return NumberA * NumberB;
46 }
47 };
48
49 class OperationDiv : public Operation
50 {
51 public:
52 virtual double GetResult()
53 {
54 if (NumberB == 0)
55 {
56 throw runtime_error("NumberB = 0!");
57 }
58 return NumberA / NumberB;
59 }
60 };
61
62 class OperationPow : public Operation
63 {
64 public:
65 virtual double GetResult()
66 {
67 if (NumberA == 0 && NumberB <= 0)
68 {
69 throw runtime_error("NumberA = 0, NumberB <= 0!");
70 }
71 return pow(NumberA, NumberB);
72 }
73 };
74
75 class IFactory
76 {
77 public:
78 virtual Operation* CreateOperation() = 0;
79 };
80
81 class AddFactory : public IFactory
82 {
83 public:
84 virtual Operation* CreateOperation()
85 {
86 return new OperationAdd;
87 }
88 };
89
90 class SubFactory : public IFactory
91 {
92 public:
93 virtual Operation* CreateOperation()
94 {
95 return new OperationSub;
96 }
97 };
98
99 class MulFactory : public IFactory
100 {
101 public:
102 virtual Operation* CreateOperation()
103 {
104 return new OperationMul;
105 }
106 };
107
108 class DivFactory : public IFactory
109 {
110 public:
111 virtual Operation* CreateOperation()
112 {
113 return new OperationDiv;
114 }
115 };
116
117 class PowFactory : public IFactory
118 {
119 public:
120 virtual Operation* CreateOperation()
121 {
122 return new OperationPow;
123 }
124 };
125
126 int main()
127 {
128 double a, b;
129 while (cin >> a >> b)
130 {
131 IFactory* pfactory = new AddFactory;
132 Operation* poperation = pfactory->CreateOperation();
133 poperation->SetNumberA(a);
134 poperation->SetNumberB(b);
135 cout << poperation->GetResult() << endl;
136 delete pfactory;
137 delete poperation;
138
139 pfactory = new SubFactory;
140 poperation = pfactory->CreateOperation();
141 poperation->SetNumberA(a);
142 poperation->SetNumberB(b);
143 cout << poperation->GetResult() << endl;
144 delete pfactory;
145 delete poperation;
146
147 pfactory = new MulFactory;
148 poperation = pfactory->CreateOperation();
149 poperation->SetNumberA(a);
150 poperation->SetNumberB(b);
151 cout << poperation->GetResult() << endl;
152 delete pfactory;
153 delete poperation;
154
155 pfactory = new DivFactory;
156 poperation = pfactory->CreateOperation();
157 poperation->SetNumberA(a);
158 poperation->SetNumberB(b);
159 try
160 {
161 cout << poperation->GetResult() << endl;
162 }
163 catch (const runtime_error& e)
164 {
165 cerr << e.what() << endl;
166 }
167 delete pfactory;
168 delete poperation;
169
170 pfactory = new PowFactory;
171 poperation = pfactory->CreateOperation();
172 poperation->SetNumberA(a);
173 poperation->SetNumberB(b);
174 cout << poperation->GetResult() << endl;
175 delete pfactory;
176 delete poperation;
177 }
178 }