之前有借助于 STL 中的 multimap 實現查找最小的 k 個元素。
這里繼續解決 查找最小的 k 個元素，采用 最大根堆。
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 }
posted @
2011-04-27 00:03 unixfy 閱讀(244) |
評論 (0) |
編輯 收藏
一個簡單的堆的實現，大根堆。
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 }
posted @
2011-04-26 23:54 unixfy 閱讀(165) |
評論 (0) |
編輯 收藏直觀的解法是對所有的 N 個數進行排序，再取最前或最后的 k 個元素。
這種做法的時間復雜度為 O(NlogN) 。
一種較好的解法是：維持一個 k 個元素的集合 S，遍歷 N 個數，對每個元素，首先檢查 S 中的元素個數是否小于 k，如果小于直接加入到 S 中。如果 S 中已有 k 個元素，則比較待處理元素與 S 中最大的元素的大小關系，若小于 S 中最大的元素，則刪除 S 中最大的元素，并將該元素加入到 S 中。
怎樣才能快速地從 S 中尋找到我們想要的最大的元素，使用堆是個好方法，最大堆。每次直接去堆的第一個元素即是 S 中最大的元素。如果將 S 中的最大元素刪除，然后將 最后的一個元素放在堆頂，下滑，已調整堆。在講新的元素加入到堆中，上滑，以調整堆。可以將這兩個過程合并，即將 S 中最大的元素替換為 待處理的元素。對這個堆頂上的元素下滑，以調整堆。這里的復雜度為 O(Nlogk)。
STL 中的 multimap 不是堆，但是其可以以 O(logn) 維護其有序性，所以可以直接用 multimap 代替堆來實現。
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 閱讀(1188) |
評論 (3) |
編輯 收藏
來自于《大話設計模式》
觀察者模式：定義了一種一對多的依賴關系，讓多個觀察者對象同時監聽某一個主題對象。這個主題對象在狀態發生時，會通知所有觀察者對象，使他們自動更新自己。
行為型模式。
UML 類圖：
代碼實現 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 << " 關閉股票行情，繼續工作！" << 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 << " 關閉 NBA，繼續工作！" << 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("開會！");
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 }
posted @
2011-04-26 19:28 unixfy 閱讀(313) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
建造者模式（Builder）：將一個復雜對象的構建與它的表示分離，使得同樣的構建過程可以創建不同的表示。
UML 類圖：
代碼實現 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 }
posted @
2011-04-26 18:00 unixfy 閱讀(256) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
外觀模式（Facade）：為子系統的一組接口提供一個一致的界面，此模式定義了一個高層接口，這個接口使得這一子系統更加容易使用。
UML 類圖：
代碼實現 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 }
posted @
2011-04-26 15:49 unixfy 閱讀(241) |
評論 (0) |
編輯 收藏
函數實現將網址進行如下操作
www.google.com 轉成 com.google.www 及 mail.netease.com 轉成 com.netease.mail
不允許用STL,空間為 O(1)
http://topic.csdn.net/u/20110425/12/8b5e155c-73d1-40af-84b8-6b6493f638e2.html一開始把 O(1) 看做時間復雜度了，如果是空間復雜度，直接在原地兩次翻轉即可。整體翻轉，部分翻轉順序可以任意。
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 }
如果是時間復雜度呢？
這里由個限制，就是只有兩個 . 符號時才成立。使用字符串數組存儲字符串，將首尾字符串指針交換即可。
例如 mail.netease.com
存在于字符串指針數組中：
mail
.
netease
.
com
將指向 mail 和 指向 com 的兩個字符串指針交換即可。
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 }
posted @
2011-04-25 23:18 unixfy 閱讀(253) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
模板方法模式：定義一個操作中的算法的骨架，而將一些步驟延遲到子類中。模板方法使得子類可以不改變一個算法的結構即可重定義該算法的某些特定步驟。
盡量將公共操作上移到基類中，這樣便于修改，代碼復用性更強。
UML 類圖：
代碼實現 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 }
posted @
2011-04-25 16:41 unixfy 閱讀(176) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
原型模式（Prototype）：用原型實例指定創建對象的種類，并且通過拷貝這些原型創建新的對象。
這個設計模式在 C++ 中如何實現？
UML 圖：
代碼實現 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 }
posted @
2011-04-25 16:03 unixfy 閱讀(309) |
評論 (0) |
編輯 收藏來自于《大話設計模式》
工廠方法模式（Factory Method）：定義一個用于創建對象的接口，讓子類決定實例化哪一個類。工廠方法使一個類的實例化延遲到其子類。
有一個操作類 Operation，繼承其而派生出具體各個操作的操作派生類。
產生操作類的工廠基類 IFactory，繼承其而派生出產生具體操作類的工廠派生類。
UML 類圖：
代碼實現 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 }
posted @
2011-04-25 15:30 unixfy 閱讀(221) |
評論 (0) |
編輯 收藏