遞增的有序順序表，插入元素并保持遞增有序。
內存分配按照 2 被原則進行分配。
1 #include <iostream>
2 using namespace std;
3
4 // 遞增有序的順序表
5 template <typename Type>
6 class IncTable
7 {
8 public:
9 typedef Type value_type;
10 typedef Type* p_type;
11 typedef unsigned int size_type;
12 typedef p_type iterator;
13 typedef const p_type const_iterator;
14 private:
15 p_type table;
16 size_type size_;
17 size_type capacity_;
18 public:
19 IncTable(int s = 1)
20 {
21 size_ = 0;
22 capacity_ = s * 2;
23 table = new value_type[capacity_];
24 if (table == 0)
25 {
26 exit(0);
27 }
28 }
29 ~IncTable()
30 {
31 delete [] table;
32 }
33 void insert(value_type item)
34 {
35 if (size_ >= capacity_)
36 {
37 reallocate(size_ * 2);
38 }
39 size_type ix = size_;
40 while (ix > 0 && table[ix - 1] > item)
41 {
42 table[ix] = table[ix - 1];
43 --ix;
44 }
45 table[ix] = item;
46 ++size_;
47 }
48 void reallocate(size_type size)
49 {
50 p_type p = new value_type[size];
51 if (p == 0)
52 {
53 exit(1);
54 }
55 memcpy(p, table, sizeof (value_type) * size_);
56 delete table;
57 table = p;
58 capacity_ = size;
59 }
60 size_type size()
61 {
62 return size_;
63 }
64 size_type capacity()
65 {
66 return capacity_;
67 }
68 iterator begin()
69 {
70 return table;
71 }
72 iterator end()
73 {
74 return table + size_;
75 }
76 const_iterator begin() const
77 {
78 return table;
79 }
80 const_iterator end() const
81 {
82 return table + size_;
83 }
84 };
85
86 int main()
87 {
88 IncTable<int> t;
89 for (int i = 10; i > 0; --i)
90 {
91 t.insert(i);
92 }
93 for (int i = 0; i < 10; ++i)
94 {
95 t.insert(i);
96 }
97 for (IncTable<int>::iterator iter = t.begin(); iter != t.end(); ++iter)
98 {
99 cout << *iter << ' ';
100 }
101 cout << endl;
102 }
posted @
2011-04-24 01:39 unixfy 閱讀(573) |
評論 (0) |
編輯 收藏
摘要: 標準庫里的 list 實現是通過雙向鏈表實現的。這里沒有使用雙向鏈表，自然功能也就不能像標準庫里的 list 那樣完備。不支持逆向。
這里在單向鏈表的基礎上，加入了泛型，迭代器，盡可能多地添加一些接口，已盡量像標準庫里的 list 那樣操作。另外，這里沒有過多里涉及內存分配的問題。每次插入的時候是直接分配一個元素的空間，而不是采用 2 倍法則。
總體上，還沒有看過 STL 里 list 具體是...
閱讀全文
posted @
2011-04-24 01:04 unixfy 閱讀(338) |
評論 (0) |
編輯 收藏
輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
這個問題在多處曾出現過。大體思路是兩次翻轉，即先翻轉各個單詞，然后將整個句子翻轉。也可將兩個翻轉順序顛倒過來，先翻轉句子，在翻轉單詞。
一種無意義的做法是，先把句子中的每個單詞存放在一個 vector<string> 中，然后反向遍歷輸出。
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 void reverseStr(string& s, string::size_type left, string::size_type right)
6 {
7 while (left < right)
8 {
9 swap(s[left++], s[right--]);
10 }
11 }
12
13 string getReverse(const string& s)
14 {
15 if (s.empty())
16 {
17 return string("");
18 }
19 string ret = s;
20 string::size_type left, right;
21 left = s.find_first_not_of(' ', 0);
22 right = s.find_first_of(' ', left);
23 while (right != string::npos)
24 {
25 reverseStr(ret, left, right - 1);
26 left = s.find_first_not_of(' ', right);
27 right = s.find_first_of(' ', left);
28 }
29 if (left != string::npos)
30 {
31 reverseStr(ret, left, ret.size() - 1);
32 }
33 reverseStr(ret, 0, ret.size() - 1);
34 return ret;
35 }
36
37 int main()
38 {
39 string s;
40 while (getline(cin, s))
41 {
42 cout << getReverse(s) << endl;
43 }
44 return 0;
45 }
posted @
2011-04-23 19:26 unixfy 閱讀(1280) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
代理模式（Proxy）：為其他對象提供一種代理以控制對這個對象的訪問。
代理模式的應用：
·遠程代理
·虛擬代理
·安全代理
·智能指針
UML 圖：
代碼實現 C++：
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 class SchoolGirl
6 {
7 private:
8 string name;
9 public:
10 SchoolGirl(string n) : name(n) {}
11 string GetName()
12 {
13 return name;
14 }
15 };
16
17 class IGiveGift
18 {
19 public:
20 virtual void GiveDolls() = 0;
21 virtual void GiveFlowers() = 0;
22 virtual void GiveChocolate() = 0;
23 };
24
25 class Pursuit : public IGiveGift
26 {
27 private:
28 SchoolGirl mm;
29 public:
30 Pursuit(SchoolGirl sg) : mm(sg) {}
31 virtual void GiveDolls()
32 {
33 cout << mm.GetName() << " 送你洋娃娃" << endl;
34 }
35 virtual void GiveFlowers()
36 {
37 cout << mm.GetName() << " 送你鮮花" << endl;
38 }
39 virtual void GiveChocolate()
40 {
41 cout << mm.GetName() << " 送你巧克力" << endl;
42 }
43 };
44
45 class Proxy : public IGiveGift
46 {
47 private:
48 Pursuit* gg;
49 public:
50 Proxy(SchoolGirl sg)
51 {
52 gg = new Pursuit(sg);
53 }
54 ~Proxy()
55 {
56 delete gg;
57 }
58 virtual void GiveDolls()
59 {
60 gg->GiveDolls();
61 }
62 virtual void GiveFlowers()
63 {
64 gg->GiveFlowers();
65 }
66 virtual void GiveChocolate()
67 {
68 gg->GiveChocolate();
69 }
70 };
71
72 int main()
73 {
74 SchoolGirl mm("Lili");
75
76 Proxy* pp = new Proxy(mm);
77 pp->GiveDolls();
78 pp->GiveFlowers();
79 pp->GiveChocolate();
80
81 delete pp;
82 return 0;
83 }
posted @
2011-04-23 18:44 unixfy 閱讀(256) |
評論 (0) |
編輯 收藏來自于《大話設計模式》
裝飾模式（Decorator）：動態地給一個對象添加額外的職責，就增加的功能來說，裝飾模式比生成子類更為靈活。
UML 圖：
代碼實現 C++：
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 class Person
6 {
7 private:
8 string name;
9 public:
10 Person() {}
11 Person(string n): name(n) {}
12 virtual void Show()
13 {
14 cout << "裝飾的 " << name << endl;
15 }
16 };
17
18 class Finery: public Person
19 {
20 protected:
21 Person* component;
22 public:
23 void Decorate(Person* p)
24 {
25 component = p;
26 }
27 virtual void Show()
28 {
29 if (component != 0)
30 {
31 component->Show();
32 }
33 }
34 };
35
36 class TShirts: public Finery
37 {
38 public:
39 virtual void Show()
40 {
41 cout << "大 T 恤 ";
42 Finery::Show();
43 }
44 };
45
46 class BigTrouser: public Finery
47 {
48 public:
49 virtual void Show()
50 {
51 cout << "垮褲 ";
52 Finery::Show();
53 }
54 };
55
56 int main()
57 {
58 Person* p = new Person("Mark");
59 p->Show();
60
61 TShirts* t = new TShirts;
62 t->Decorate(p);
63 t->Show();
64
65 BigTrouser* b = new BigTrouser;
66 b->Decorate(t);
67 b->Show();
68
69 delete p;
70 delete t;
71 delete b;
72 }
posted @
2011-04-23 18:09 unixfy 閱讀(127) |
評論 (0) |
編輯 收藏
來自于《大話設計模式》
策略模式（Strategy）：它定義了算法家族，分別封裝起來，讓它們之間可以相互替換，此模式讓算法的變化不會影響到使用算法的客戶。
所謂的算法即使 acceptCash 虛函數，由 CashSuper 的派生類實現各個 acceptCash。客戶端代碼根據使用不同的參數生成不同的 CashContext 對象，來使用不同的策略（acceptCash 虛函數）
UML 圖：
代碼實現 C++：
1 #include <iostream>
2 using namespace std;
3
4 class CashSuper
5 {
6 public:
7 virtual double acceptCash(double money) = 0;
8 };
9
10 class CashNormal : public CashSuper
11 {
12 public:
13 virtual double acceptCash(double money)
14 {
15 return money;
16 }
17 };
18
19 class CashRebate : public CashSuper
20 {
21 private:
22 double moneyRebate;
23 public:
24 CashRebate(double mr = 1.0) : moneyRebate(mr) {}
25 virtual double acceptCash(double money)
26 {
27 return money * moneyRebate;
28 }
29 };
30
31 class CashReturn : public CashSuper
32 {
33 private:
34 double moneyCondition;
35 double moneyReturn;
36 public:
37 CashReturn(double c = 1.0, double r = 1.0) : moneyCondition(c), moneyReturn(r) {}
38 virtual double acceptCash(double money)
39 {
40 return money - money / moneyCondition * moneyReturn;
41 }
42 };
43
44 class CashContext
45 {
46 private:
47 CashSuper* cs;
48 public:
49 CashContext()
50 {
51 cs = new CashNormal;
52 // cs = new CashNormal();
53 }
54 CashContext(double r)
55 {
56 cs = new CashRebate(r);
57 }
58 CashContext(double c, double r)
59 {
60 cs = new CashReturn(c, r);
61 }
62 ~CashContext()
63 {
64 delete cs;
65 }
66 double GetResult(double money)
67 {
68 return cs->acceptCash(money);
69 }
70 };
71
72 int main()
73 {
74 CashContext* cc = new CashContext;
75 cout << cc->GetResult(300) << endl;
76 delete cc;
77
78 cc = new CashContext(0.8);
79 cout << cc->GetResult(300) << endl;
80 delete cc;
81
82 cc = new CashContext(100, 50);
83 cout << cc->GetResult(300) << endl;
84 delete cc;
85
86 return 0;
87 }
posted @
2011-04-23 16:27 unixfy 閱讀(167) |
評論 (0) |
編輯 收藏
設計一個保護 min 函數的棧，min 函數返回棧的最小元素。并且 min、push、pop 函數的時間復雜度都為 O(1)。
主要思想是定義一個輔助棧記錄最小元素在原棧中的索引。
實現中參考：
http://hi.baidu.com/xiangzifengshi/blog/item/2f9e833aef17d6f7828b131e.htmlhttp://zhedahht.blog.163.com/blog/static/25411174200712895228171/代碼實現：
1 #include <iostream>
2 #include <ctime>
3 #include <cassert>
4 using namespace std;
5
6 class MinStack
7 {
8 private:
9 int stack[100];
10 int p;
11 int minstack[100];
12 int q;
13
14 bool minEmpty()
15 {
16 return q == 0;
17 }
18 void minPop()
19 {
20 assert(!minEmpty());
21 --q;
22 }
23 int minTop()
24 {
25 assert(!minEmpty());
26 return minstack[q - 1];
27 }
28 public:
29 MinStack() : p(0), q(0) {}
30 bool empty()
31 {
32 return p == 0;
33 }
34 void push(int i)
35 {
36 stack[p++] = i;
37 if (minEmpty())
38 {
39 minstack[q++] = p - 1;
40 }
41 else
42 {
43 if (i <= stack[minTop()])
44 {
45 minstack[q++] = p - 1;
46 }
47 }
48 }
49 void pop()
50 {
51 assert(!empty());
52 if (top() == stack[minTop()])
53 {
54 minPop();
55 }
56 --p;
57 }
58 int min()
59 {
60 assert(!empty());
61 return stack[minTop()];
62 }
63 int top()
64 {
65 assert(!empty());
66 return stack[p - 1];
67 }
68 };
69
70 int main()
71 {
72 MinStack ms;
73 srand(time(0));
74 for (int i = 0; i < 10; ++i)
75 {
76 int n = rand() % 100;
77 ms.push(n);
78 }
79 while (!ms.empty())
80 {
81 cout << ms.top() << '\t' << ms.min() << endl;
82 ms.pop();
83 }
84 return 0;
85 }
posted @
2011-04-23 01:28 unixfy 閱讀(170) |
評論 (0) |
編輯 收藏
設計一個字符串類 String，實現
·+= 連接兩個字符串
·+ 連接兩個字符串
·== 判斷兩個字符串是否相等
·< 判斷兩個字符串大小關系
類的聲明：
class String
{
private:
char* mychar;
int len;
public:
};
代碼：
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 class String
6 {
7 private:
8 char* mychar;
9 int len;
10 private:
11 void clear()
12 {
13 delete[] mychar;
14 mychar = 0;
15 len = 0;
16 }
17 public:
18 String(char* s = "")
19 {
20 int l = strlen(s);
21 mychar = new char[l + 1];
22 if (mychar != 0)
23 {
24 strcpy(mychar, s);
25 len = l;
26 }
27 }
28 String(const String& s)
29 {
30 mychar = new char[s.len + 1];
31 if (mychar != 0)
32 {
33 strcpy(mychar, s.mychar);
34 len = s.len;
35 }
36 }
37 String& operator=(const String& s)
38 {
39 if (this != &s)
40 {
41 clear();
42 mychar = new char[s.len + 1];
43 if (mychar != 0)
44 {
45 strcpy(mychar, s.mychar);
46 len = s.len;
47 }
48 }
49 return *this;
50 }
51 ~String()
52 {
53 clear();
54 }
55 String& operator +=(const String& s)
56 {
57 int l = len + s.len + 1;
58 char* t = new char[l];
59 if (t != 0)
60 {
61 // 初始化內存
62 memset(t, 0, sizeof (char) * l);
63 strcat(t, mychar);
64 strcat(t, s.mychar);
65 }
66 delete [] mychar;
67 mychar = t;
68 len = l;
69 return *this;
70 }
71
72 friend String operator +(const String& lhs, const String& rhs);
73 friend bool operator ==(const String& lhs, const String& rhs);
74 friend bool operator < (const String& lhs, const String& rhs);
75 friend istream& operator >>(istream& in, String& s);
76 friend ostream& operator <<(ostream& out, const String& s);
77 };
78
79 String operator +(const String& lhs, const String& rhs)
80 {
81 String t(lhs);
82 return t += rhs;
83 }
84
85 bool operator==(const String& lhs, const String& rhs)
86 {
87 return strcmp(lhs.mychar, rhs.mychar) == 0;
88 }
89
90 bool operator<(const String& lhs, const String& rhs)
91 {
92 return strcmp(lhs.mychar, rhs.mychar) < 0;
93 }
94
95 bool operator >(const String& lhs, const String& rhs)
96 {
97 return !(lhs < rhs) && !(lhs == rhs);
98 }
99
100 bool operator <=(const String& lhs, const String& rhs)
101 {
102 return lhs < rhs || lhs == rhs;
103 }
104
105 bool operator >=(const String& lhs, const String& rhs)
106 {
107 return !(lhs < rhs);
108 }
109
110 istream& operator >>(istream& in, String& s)
111 {
112 s.clear();
113 char t[100];
114 in >> t;
115 if (!in)
116 {
117 cerr << "Input error!" << endl;
118 exit(1);
119 }
120 int l = strlen(t);
121 s.mychar = new char[l + 1];
122 if (s.mychar != 0)
123 {
124 strcpy(s.mychar, t);
125 s.len = l;
126 }
127 return in;
128 }
129
130 ostream& operator <<(ostream& out, const String& s)
131 {
132 out << s.mychar;
133 return out;
134 }
135
136 int main()
137 {
138 String s1, s2;
139 while (cin >> s1 >> s2)
140 {
141 cout << s1 << endl;
142 cout << s2 << endl;
143 cout << (s1 == s2) << endl;
144 cout << (s1 < s2) << endl;
145 cout << (s1 > s2) << endl;
146 cout << (s1 <= s2) << endl;
147 cout << (s1 >= s2) << endl;
148
149 cout << s1 + s2 << endl;
150 s1 += s2;
151 cout << s1 << endl;
152 cout << s2 << endl;
153 s2 += s1;
154 cout << s1 << endl;
155 cout << s2 << endl;
156 }
157 return 0;
158 }
posted @
2011-04-22 13:12 unixfy 閱讀(180) |
評論 (0) |
編輯 收藏
摘要: 設計一個日期類 Date，包括 年月日 三個私有數據成員。設計運算符重載，實現：·兩個日期對象之間的“-”，求得兩個日期的相差天數。注意兩個日期不能相加。·實現日期對象“+”“-”“+=”“-=”一個整型數，求得運算后的日期。
1&n...
閱讀全文
posted @
2011-04-22 11:13 unixfy 閱讀(286) |
評論 (0) |
編輯 收藏
閏年判斷就是 能被 400 整除的，后者能被 4 整除且不能被 100 整除的年份。
即
1 int isLeapYear(int y)
2 {
3 if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
4 {
5 return 1;
6 }
7 else
8 {
9 return 0;
10 }
11 }
但是這里有個細節需要注意就是，(y % 4 == 0 && y % 100 != 0) || y % 400 == 0 這個表達式中的三個子表達式的順序怎樣調整。
y % 4 == 0
y % 100 != 0
y % 400 == 0
這里有 4 中組合：
·(y % 4 == 0 && y % 100 != 0) || y % 400 == 0
·(y % 100 != 0 && y % 4 == 0) || y % 400 == 0
·y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)
·y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)
我們首先確定 y % 400 是不是應該在最前，對于一般的年份很少有能被 400 整除的年份，其概率為 1 / 400，所以 y % 400 == 0 基本都為假，這樣就必須還要判斷后面的表達式，所以應該將 y % 400 放在后面。
然后，判斷 y % 100 != 0 是否應該在 y % 4 == 0 之前，y % 100 != 0 為真的概率很大及為 99 / 100，而 y % 4 == 0 為真的概率為 1 / 4，也就是說 y % 4 為假的概率更大。根據 && 操作符的性質，當前面一個為假時其就不用判斷后面的表達式是否為真假了。所以應該把 y % 4 == 0 放在 y % 100 != 0 前面效率更好。
即判斷閏年的表達式順序應該為這樣是，效率最高：
(y % 4 == 0 && y % 100 != 0) || y % 400 == 0
posted @
2011-04-22 00:17 unixfy 閱讀(135) |
評論 (0) |
編輯 收藏