示例一
1 2 3 4 5 6
^Z
1 * x ^ 2 + 3 * x ^ 4 + 5 * x ^ 6
1 2 3 4 5 6
^Z
1 * x ^ 2 + 3 * x ^ 4 + 5 * x ^ 6
2 * x ^ 2 + 6 * x ^ 4 + 10 * x ^ 6
示例二
1 2 100 10000
^Z
1 * x ^ 2 + 100 * x ^ 10000
1 3 1000 1000
^Z
1 * x ^ 3 + 1000 * x ^ 1000
1 * x ^ 2 + 1 * x ^ 3 + 1000 * x ^ 1000 + 100 * x ^ 10000
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 using namespace std;
5
6 struct node
7 {
8 double coe;
9 double exp;
10 node* next;
11 node(double c = 0.0, double e = 0.0, node* n = 0)
12 : coe(c), exp(e), next(n) {}
13 };
14
15 void init(node*& poly)
16 {
17 poly = new node;
18 }
19
20 void create(node* poly, const vector<int>& v)
21 {
22 node* p = poly;
23 for (vector<int>::size_type i = 0; i != v.size(); i += 2)
24 {
25 node* temp = new node(v[i], v[i + 1]);
26 p->next = temp;
27 p = temp;
28 }
29 }
30
31 void display(node* poly)
32 {
33 poly = poly->next;
34 while (poly != 0)
35 {
36 cout << poly->coe << " * x ^ " << poly->exp;
37 if (poly->next != 0)
38 {
39 if (poly->coe > 0)
40 {
41 cout << " + ";
42 }
43 else
44 {
45 cout << " ";
46 }
47 }
48 poly = poly->next;
49 }
50 cout << endl;
51 }
52
53 node* add(node* ret, node* poly1, node* poly2)
54 {
55 node* p1 = poly1->next;
56 node* p2 = poly2->next;
57 node* r = ret;
58 while (p1 != 0 && p2 != 0)
59 {
60 if (p1->exp == p2->exp)
61 {
62 double c = p1->coe + p2->coe;
63 if (abs(c) > 1e-6)
64 {
65 node* t = new node(c, p1->exp);
66 r->next = t;
67 r = t;
68 }
69 p1 = p1->next;
70 p2 = p2->next;
71 }
72 else if (p1->exp < p2->exp)
73 {
74 node* t = new node(p1->coe, p1->exp, 0);
75 r->next = t;
76 r = t;
77 p1 = p1->next;
78 }
79 else
80 {
81 node* t = new node(p2->coe, p2->exp, 0);
82 r->next = t;
83 r = t;
84 p2 = p2->next;
85 }
86 }
87 while (p1 != 0)
88 {
89 node* t = new node(p1->coe, p1->exp, 0);
90 r->next = t;
91 r = t;
92 p1 = p1->next;
93 }
94 while (p2 != 0)
95 {
96 node* t = new node(p2->coe, p2->exp, 0);
97 r->next = t;
98 r = t;
99 p2 = p2->next;
100 }
101 return ret;
102 }
103
104 void clear(node* poly)
105 {
106 node* p = poly->next, *q;
107 while (p != 0)
108 {
109 q = p->next;
110 delete p;
111 p = q;
112 }
113 }
114
115 void destroy(node*& poly)
116 {
117 clear(poly);
118 delete poly;
119 poly = 0;
120 }
121
122 int main()
123 {
124 vector<int> v;
125 int n;
126 while (cin >> n)
127 {
128 v.push_back(n);
129 }
130 node* p1;
131 init(p1);
132 create(p1, v);
133 display(p1);
134
135 v.clear();
136 cin.clear();
137 while (cin >> n)
138 {
139 v.push_back(n);
140 }
141 node* p2;
142 init(p2);
143 create(p2, v);
144 display(p2);
145 cin.clear();
146
147 node* p3;
148 init(p3);
149 add(p3, p1, p2);
150 display(p3);
151
152 destroy(p1);
153 destroy(p2);
154 destroy(p3);
155 }
posted @
2011-09-11 09:43 unixfy 閱讀(127) |
評論 (0) |
編輯 收藏有代碼有真相
操作計數，一個遞歸函數時，
void foo(int m)
{
++m;
foo(m);
}
調用 foo(0);
void foo(int m)
{
foo(++m);
}
調用 foo(0);
但是當存在兩個遞歸函數時
void foo(int m)
{
++m;
foo(m)
// ...
++m;
foo(m);
}
調用 foo(0);
這種方式不能正常工作，因為 m 是 int 型的，第一個 foo 改變對第二個 foo 不起作用。
應該是
void foo(int& m)
{
++m;
foo(m)
// ...
++m;
foo(m);
}
調用：
int m = 0;
void foo(m);
以下方式
void foo(int& m)
{
foo(++m);
// ...
foo(++m);
}
會造成混亂，不能正常工作。
m++, 編譯失敗，因為 m++ 的結果是 const 的。
也不能是 m + 1, 因為 m + 1 的結果也是 const 的。
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 void tower(int n, const string& a, const string& b, const string& c, int& m)
6 {
7 if (n == 1)
8 {
9 ++m;
10 cout << m << "\t";
11 cout << n << ": " << a << " -> " << b << endl;
12 return;
13 }
14 tower(n - 1, a, c, b, m);
15 ++m;
16 cout << m << "\t";
17 cout << n << ": " << a << " -> " << b << endl;
18 tower(n - 1, c, b, a, m);
19 }
20
21 int main()
22 {
23 int n;
24 while (cin >> n)
25 {
26 int m = 0;
27 tower(n, "towerA", "towerB", "towerC", m);
28 }
29 return 0;
30 }
posted @
2011-09-10 16:53 unixfy 閱讀(148) |
評論 (0) |
編輯 收藏聯合容器的第三個參數
map 容器的第三個參數，即函數對象類型。
對第一個參數進行比較，重載 operator ()。這是第一種方案。
第二種方案，對第一個參數類型進行包裝，然后針對這個類型重載 operator < 。
總結：
·第一個參數原裝類型，添加第三個類型，函數對象，重載 operator () 。
·第一個參數對原類型進行包裝，重載 operator < 。
參考：
為什么數據結構很重要
http://download.csdn.net/detail/yun_2106118/1768192
1 #include <iostream>
2 #include <map>
3 using namespace std;
4
5 struct ltstr
6 {
7 bool operator () (const char* s1, const char* s2) const
8 {
9 return strcmp(s1, s2) < 0;
10 }
11 };
12
13 int main()
14 {
15 map<const char*, const char*, ltstr> phones;
16 phones["Gao Jun"] = "23423423";
17 phones["Gao Jie"] = "89878979";
18
19 for (map<const char*, const char*, ltstr>::const_iterator cit = phones.begin(); cit != phones.end(); ++cit)
20 {
21 cout << cit->first << '\t' << cit->second << endl;
22 }
23
24 return 0;
25 }
posted @
2011-09-10 12:51 unixfy 閱讀(254) |
評論 (0) |
編輯 收藏霍夫曼編碼
英文名 Huffman Coding
中文名：霍夫曼、赫夫曼、哈夫曼
具體原理不重述，見百科
維基百科：http://zh.wikipedia.org/zh/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
百度百科：http://baike.baidu.com/view/189694.htm
幾個點：
樹節點的表示
霍夫曼樹的建立
得到編碼映射
編碼
解碼，根據霍夫曼樹解碼
演示 I
A 1 B 2 C 3 D 4 E 5
^Z
A 010
B 011
C 00
D 10
E 11
Encoding:
A
B
C
D
E
^Z
010011001011
Decoding:
010011001011
ABCDE
演示 II
asdf 23 asdfwoeri 232 ljljkl 2398 agslk;jfqwoeijasldfjals 988
^Z
agslk;jfqwoeijasldfjals 01
asdf 000
asdfwoeri 001
ljljkl 1
Encoding:
asdf
^Z
000
Decoding:
010000011111111
agslk;jfqwoeijasldfjalsasdfasdfwoeriljljklljljklljljklljljklljljklljljklljljkl
實現：
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 #include <vector>
5 #include <map>
6 using namespace std;
7
8 struct node
9 {
10 string trueform;
11 double probability;
12 string encoding;
13 node* left;
14 node* right;
15 node(string tt = "", double tp = 0.0, string te = "", node* tl = 0, node* tr = 0)
16 : trueform(tt), probability(tp), encoding(te), left(tl), right(tr) {}
17 friend bool operator < (const node& lhs, const node& rhs);
18 friend bool operator == (const node& lhs, const node& rhs);
19 };
20
21 bool operator < (const node& lhs, const node& rhs)
22 {
23 return lhs.probability < rhs.probability;
24 }
25
26 bool operator == (const node& lhs, const node& rhs)
27 {
28 return lhs.probability == rhs.probability;
29 }
30
31 void init(vector<node>& treenodes)
32 {
33 treenodes.clear();
34 string tt;
35 double tp;
36 while (cin >> tt >> tp)
37 {
38 treenodes.push_back(node(tt, tp));
39 }
40 sort(treenodes.begin(), treenodes.end());
41 }
42
43 void generateTree(node*& htree, vector<node>& treenodes)
44 {
45 while (treenodes.size() >= 2)
46 {
47 node* left = new node(treenodes[0]);
48 node* right = new node(treenodes[1]);
49 treenodes.erase(treenodes.begin(), treenodes.begin() + 2);
50 node temp("", left->probability + right->probability, "", left, right);
51 treenodes.push_back(temp);
52 sort(treenodes.begin(), treenodes.end());
53 }
54 htree = new node(treenodes[0]);
55 }
56
57 void generateCoding(map<string, string>& encodingmap, node* htree, string coding = "")
58 {
59 if (htree != 0)
60 {
61 if (htree->left != 0)
62 {
63 generateCoding(encodingmap, htree->left, coding + '0');
64 }
65 if (htree->right != 0)
66 {
67 generateCoding(encodingmap, htree->right, coding + '1');
68 }
69 if (htree->left == 0 && htree->right == 0)
70 {
71 encodingmap[htree->trueform] = coding;
72 htree->encoding = coding;
73 // codingnodes.push_back(node(htree->trueform, htree->probability, coding, htree->left, htree->right));
74 }
75 }
76 }
77
78 void inputCiphertext(string& ciphertext)
79 {
80 cin.clear();
81 cin >> ciphertext;
82 //for (string::size_type i = 0; i != ciphertext.size(); ++i)
83 //{
84 // if (ciphertext[i] != '0' && ciphertext[i] != '1')
85 // {
86 // cerr << "Ciphertext error!" << endl;
87 // exit(1);
88 // }
89 //}
90 }
91
92 string decodeCiphertext(string& result, const string& ciphertext, node* htree)
93 {
94 result.clear();
95 node* temp;
96 for (string::size_type i = 0; i != ciphertext.size();)
97 {
98 temp = htree;
99 while (temp->left != 0 && i != ciphertext.size())
100 {
101 if (ciphertext[i] == '0')
102 {
103 temp = temp->left;
104 }
105 else if (ciphertext[i] == '1')
106 {
107 temp = temp->right;
108 }
109 else
110 {
111 cerr << "Illegal character!" << endl;
112 exit(1);
113 }
114 ++i;
115 }
116 result += temp->trueform;
117 }
118
119 if (temp->left != 0)
120 {
121 cerr << "Ciphertext cannot be decoded!" << endl;
122 }
123 return result;
124 }
125
126 void inputPlaintext(vector<string>& plaintext)
127 {
128 cin.clear();
129 string temp;
130 while (cin >> temp)
131 {
132 plaintext.push_back(temp);
133 }
134 }
135
136 string encodePlaintext(string& result, const vector<string>& plaintext, map<string, string>& encodingmap)
137 {
138 result.clear();
139 for (vector<string>::const_iterator cit = plaintext.begin(); cit != plaintext.end(); ++cit)
140 {
141 if (encodingmap.find(*cit) != encodingmap.end())
142 {
143 // const map<string, string>& encodingmap
144 //result += encodingmap[*cit];
145 result += encodingmap[*cit];
146 }
147 else
148 {
149 cerr << "Cannot encode!" << endl;
150 }
151 }
152 return result;
153 }
154
155 int main()
156 {
157 vector<node> treenodes;
158 init(treenodes);
159 node* htree = 0;
160 generateTree(htree, treenodes);
161 //for (vector<node>::size_type i = 0; i != treenodes.size(); ++i)
162 //{
163 // cout << treenodes[i].trueform << '\t' << treenodes[i].probability << endl;
164 //}
165 map<string, string> encodingmap;
166 generateCoding(encodingmap, htree);
167 for (map<string, string>::const_iterator cit = encodingmap.begin(); cit != encodingmap.end(); ++cit)
168 {
169 cout << cit->first << '\t' << cit->second << endl;
170 }
171 cout << "Encoding:" << endl;
172 vector<string> plaintext;
173 inputPlaintext(plaintext);
174 string encoderesult;
175 encodePlaintext(encoderesult, plaintext, encodingmap);
176 cout << encoderesult << endl;
177
178 cout << "Decoding:" << endl;
179 string ciphertext;
180 inputCiphertext(ciphertext);
181 string result;
182 decodeCiphertext(result, ciphertext, htree);
183 cout << result << endl;
184 }
posted @
2011-09-09 20:39 unixfy 閱讀(577) |
評論 (0) |
編輯 收藏求兩個數之和等于某個數
例如 {2, 3, 1, 6, 5, 4, 9, 8}, 10
1.
直接兩次循環掃描，時間 O(N ^ 2)
2.
先排序，從兩端掃描
時間復雜度是 O(N ^ logN)
3.
從同學那里學到的
首先對和這個數 M ，分配 M + 1 個空間
掃描集合，記錄每個數出現的情況
然后掃描 M + 1 的空間，檢測出
但是這種方法，在集合中的元素大于 M 時就失效了
另外記錄每個數出現的情況，其實也就是對集合進行了排序，
然后對這個輔助空間進行掃描
本質上講，這種方法和第二種方法是一樣的，也是先排序，然后再從兩端掃描
只不過這種方法利用了限制信息，也就是說排序算法是基數排序。
時間復雜度是 O(N + M)
空間復雜度是 O(M)
當存在大量集合元素，元素的范圍為 0 - 2^(sizeof (int) * 8)-1, M 為任意的，我們可以設定輔助數組的大小為
2^(sizeof (int) * 8)
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 void foo(int a[], int n, int m)
6 {
7 int* p = new int[m + 1];
8 memset(p, 0, sizeof (*p) * (m + 1));
9 for (int i = 0; i != n; ++i)
10 {
11 ++p[a[i]];
12 }
13 int i = 0, j = m;
14 while (i < j)
15 {
16 if (p[i] != 0 && p[j] != 0)
17 {
18 for (int k = 0; k != p[i] * p[j]; ++k)
19 {
20 cout << i << ' ' << j << endl;
21 }
22 }
23 ++i;
24 --j;
25 }
26 if (i == j && p[i] >= 2)
27 {
28 for (int k = 0; k != p[i] * (p[i] - 1) / 2; ++k)
29 {
30 cout << i << ' ' << i << endl;
31 }
32 }
33 }
34
35 int main()
36 {
37 int a[] = {2, 2, 2, 3, 1, 6, 5, 5, 5, 4, 9, 8};
38 int m = 10;
39 foo(a, sizeof (a) / sizeof (*a), m);
40 return 0;
41 }
posted @
2011-08-03 21:33 unixfy 閱讀(326) |
評論 (0) |
編輯 收藏電梯調度算法
http://www.shnenglu.com/jake1036/archive/2011/06/29/149720.html
n1
n2
n3
自下向上
自上向下
n1 + n2 n3
n2 + n3 n1
1 #include <iostream>
2 using namespace std;
3
4 int whichFloorDownToUp(int ps[], int n)
5 {
6 if (n <= 1)
7 {
8 return 0;
9 }
10 else if (n == 2)
11 {
12 return 1;
13 }
14 int all = 0;
15 int n1 = ps[0];
16 int n2 = ps[1];
17 int n3 = 0;
18 int retf = 1;
19
20 for (int i = 2; i != n; ++i)
21 {
22 all += ps[i] * (i - 1);
23 n3 += ps[i];
24 }
25
26 for (int i = 2; i != n; ++i)
27 {
28 if (n1 + n2 <= n3)
29 {
30 all += (n1 + n2 - n3);
31 n1 += n2;
32 n2 = ps[i];
33 n3 -= ps[i];
34 // cout << i << endl;
35 retf = i;
36 }
37 }
38 return retf;
39 }
40
41 int whichFloorUpToDown(int ps[], int n)
42 {
43 if (n <= 1)
44 {
45 return 0;
46 }
47 else if (n == 2)
48 {
49 return 1;
50 }
51 int all = 0;
52 int n3 = 0;
53 int n2 = ps[n - 1];
54 int n1 = 0;
55 int retf = n - 1;
56 for (int i = n - 2; i >= 0; --i)
57 {
58 all += ps[i] * (n - 1 - i);
59 n1 += ps[i];
60 }
61
62 for (int i = n - 2; i >= 0; --i)
63 {
64 if (n2 + n3 <= n1)
65 {
66 all += (n2 + n3 - n1);
67 n3 += n2;
68 n2 = ps[i];
69 n1 -= ps[i];
70 // cout << i << endl;
71 retf = i;
72 }
73 }
74 return retf;
75 }
76
77 int main()
78 {
79 int ps[] = {0, 5, 3, 2, 8, 9, 1, 8, 9, 2, 5, 8};
80 cout << whichFloorDownToUp(ps, sizeof (ps) / sizeof (*ps)) << endl;
81 cout << whichFloorUpToDown(ps, sizeof (ps) / sizeof (*ps)) << endl;
82 return 0;
83 }
posted @
2011-08-03 18:01 unixfy 閱讀(338) |
評論 (0) |
編輯 收藏合并兩個有序的單鏈表
http://www.shnenglu.com/jake1036/archive/2011/06/15/148692.html
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int data;
7 node* next;
8 };
9
10 void clear(node* head)
11 {
12 node* t = head->next, * p;
13 while (t != 0)
14 {
15 p = t;
16 t = t->next;
17 delete p;
18 }
19 delete head;
20 }
21
22 void print(node* head)
23 {
24 while (head->next != 0)
25 {
26 cout << head->next->data << ' ';
27 head = head->next;
28 }
29 cout << endl;
30 }
31
32 node* init()
33 {
34 node* ret = new node;
35 ret->next = 0;
36 return ret;
37 }
38
39 node* build(node* head, int item)
40 {
41 node* t = new node;
42 t->next = 0;
43 t->data = item;
44 head->next = t;
45 return t;
46 }
47
48 node* merge(node* h, node* h1, node* h2)
49 {
50 h1 = h1->next;
51 h2 = h2->next;
52 node* t;
53 while (h1 != 0 && h1 != 0)
54 {
55 if (h1->data < h2->data)
56 {
57 t = new node;
58 t->data = h1->data;
59 t->next = 0;
60 h->next = t;
61 h = h->next;
62
63 h1 = h1->next;
64 }
65 else if (h1->data > h2->data)
66 {
67 t = new node;
68 t->data = h2->data;
69 t->next = 0;
70 h->next = t;
71 h = h->next;
72
73 h2 = h2->next;
74 }
75 else
76 {
77 t = new node;
78 t->data = h1->data;
79 t->next = 0;
80 h->next = t;
81 h = h->next;
82 t = new node;
83 t->data = h2->data;
84 t->next = 0;
85 h->next = t;
86 h = h->next;
87
88 h1 = h1->next;
89 h2 = h2->next;
90 }
91 }
92 while (h1 != 0)
93 {
94 t = new node;
95 t->data = h1->data;
96 t->next = 0;
97 h->next = t;
98 h = h->next;
99
100 h1 = h1->next;
101 }
102 while (h2 != 0)
103 {
104 t = new node;
105 t->data = h2->data;
106 t->next = 0;
107 h->next = t;
108 h = h->next;
109
110 h2 = h2->next;
111 }
112
113 return h;
114 }
115
116 int main()
117 {
118 node* h1 = init(), * h2 = init();
119 node* t = h1;
120 for (int i = 1; i <= 10; i += 2)
121 {
122 t = build(t, i);
123 }
124 t = h2;
125 for (int i = 0; i <= 10; i += 2)
126 {
127 t = build(t, i);
128 }
129 print(h1);
130 print(h2);
131
132 node* h = init();
133
134 merge(h, h1, h2);
135
136 print(h);
137
138 clear(h1);
139 clear(h2);
140 clear(h);
141 }
posted @
2011-07-31 18:25 unixfy 閱讀(579) |
評論 (0) |
編輯 收藏淘汰數組中的重復的數
淘汰數組中的重復的數，有多種方式
1.
有序的
重復的只保留一個
2.
有序的
重復的全部淘汰
3.
無序的
連續重復的保留一個，后面如果再次出現，但是不連續，還是保留
4.
無序的
連續重復的都淘汰，后面如果在重復出現多次，也是全部淘汰，如果只出現一次，則保留
5.
無序的
考慮整個數組中，對重復的，只保留第一個，不管連續還是不連續
6.
無序的
考慮整個數組，對多次出現的，不考慮連續不連續，都淘汰
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <map>
5 using namespace std;
6
7 void foo_0(int* a, int n, int& alen)
8 {
9 sort(a, a + n);
10 // foo_2(a, n, alen);
11 alen = 1;
12 for (int i = 1; i <= n - 1; ++i)
13 {
14 if (a[i] != a[i - 1])
15 {
16 a[alen++] = a[i];
17 }
18 }
19 }
20
21 void foo_1(int* a, int n, int& alen)
22 {
23 sort(a, a + n);
24 // foo_3(a, n, alen);
25 alen = 0;
26 int i = 0;
27 while (i <= n - 1)
28 {
29 if (i <= n - 2)
30 {
31 if (a[i] == a[i + 1])
32 {
33 i += 2;
34 while (i <= n - 1 && a[i] == a[i - 1])
35 {
36 ++i;
37 }
38 }
39 else
40 {
41 a[alen++] = a[i++];
42 }
43 }
44 else
45 {
46 a[alen++] = a[i++];
47 }
48 }
49 }
50
51 void foo_2(int* a, int n, int& alen)
52 {
53 alen = 1;
54 for (int i = 1; i <= n - 1; ++i)
55 {
56 if (a[i] != a[i - 1])
57 {
58 a[alen++] = a[i];
59 }
60 }
61 }
62
63 void foo_3(int* a, int n, int& alen)
64 {
65 alen = 0;
66 int i = 0;
67 while (i <= n - 1)
68 {
69 if (i <= n - 2)
70 {
71 if (a[i] == a[i + 1])
72 {
73 i += 2;
74 while (i <= n - 1 && a[i] == a[i - 1])
75 {
76 ++i;
77 }
78 }
79 else
80 {
81 a[alen++] = a[i++];
82 }
83 }
84 else
85 {
86 a[alen++] = a[i++];
87 }
88 }
89 }
90
91 void foo_4(int* a, int n, int& alen)
92 {
93 alen = 0;
94 map<int, int> m;
95 for (int i = 0; i <= n - 1; ++i)
96 {
97 ++m[a[i]];
98 }
99 for (int i = 0; i <= n - 1; ++i)
100 {
101 if (m[a[i]] == 1)
102 {
103 a[alen++] = a[i];
104 }
105 else if (m[a[i]] >= 2)
106 {
107 a[alen++] = a[i];
108 m[a[i]] = -1;
109 }
110 }
111 }
112
113 void foo_5(int* a, int n, int& alen)
114 {
115 alen = 0;
116 map<int, int> m;
117 for (int i = 0; i <= n - 1; ++i)
118 {
119 ++m[a[i]];
120 }
121 for (int i = 0; i <= n - 1; ++i)
122 {
123 if (m[a[i]] == 1)
124 {
125 a[alen++] = a[i];
126 }
127 }
128 }
129
130 void init(int*& a, int& len)
131 {
132 int t[] = {2, 2, 3, 4, 5, 2, 2, 6, 7, 8, 9, 9, 9};
133 // int t[] = {1, 1, 1, 1};
134 len = sizeof (t) / sizeof (*t);
135 delete [] a;
136 a = new int[len];
137 memcpy(a, t, sizeof (*a) * len);
138 }
139
140 void print(int a[], int n)
141 {
142 for (int i = 0; i != n; ++i)
143 {
144 cout << a[i] << ' ';
145 }
146 cout << endl;
147 }
148
149 int main()
150 {
151 int* a = 0;
152 int len = 0;
153
154 init(a, len);
155 foo_0(a, len, len);
156 print(a, len);
157
158 init(a, len);
159 print(a, len);
160
161 foo_1(a, len, len);
162 print(a, len);
163
164 init(a, len);
165 print(a, len);
166
167 foo_2(a, len, len);
168 print(a, len);
169
170 init(a, len);
171 foo_3(a, len, len);
172 print(a, len);
173
174 init(a, len);
175 print(a, len);
176 foo_4(a, len, len);
177 print(a, len);
178
179 init(a, len);
180 print(a, len);
181 foo_5(a, len, len);
182 print(a, len);
183 }
posted @
2011-07-29 00:27 unixfy 閱讀(153) |
評論 (0) |
編輯 收藏刪除兩個數組中的共同元素
http://www.shnenglu.com/jake1036/archive/2011/07/01/149882.html
兩個數組是有序的，也就是說給了一定的初始信息
在 O(N) 下刪除各自共同的元素
思路
因為是有序的
對這兩個數組從高到低遍歷
檢測兩個當前元素
如果相等，則是要刪除的對象，并且要向后查找后面相等的情況
如果不相等，提取小的那個，因為大的有可能在后面相等
這種方法不能刪除自身重復的元素
可以寫個過濾函數過濾掉重復的元素
過濾有兩個策略，一是只留一個重復的元素
二是全部刪除重復的元素
1 #include <iostream>
2 using namespace std;
3
4 void foo(int a[], int b[], int an, int bn, int& alen, int& blen)
5 {
6 int i = 0, j = 0;
7 int u = 0, v = 0;
8 while (i != an && j != bn)
9 {
10 if (a[i] == b[j])
11 {
12 ++i;
13 ++j;
14 while (i != an && a[i] == a[i - 1])
15 {
16 ++i;
17 }
18 while (j != bn && b[j] == b[j - 1])
19 {
20 ++j;
21 }
22 }
23 else if (a[i] < b[j])
24 {
25 a[u++] = a[i++];
26 }
27 else
28 {
29 b[v++] = b[j++];
30 }
31 }
32 while (i != an)
33 {
34 a[u++] = a[i++];
35 }
36 while (j != bn)
37 {
38 b[v++] = b[j++];
39 }
40 alen = u;
41 blen = v;
42 }
43
44 void filter(int a[], int n, int& t)
45 {
46 t = 0;
47 bool f = false;
48 for (int i = 0; i != n - 1; ++i)
49 {
50 if (a[i] == a[i + 1])
51 {
52 }
53 else
54 {
55 a[t++] = a[i];
56 }
57 }
58 }
59
60 int main()
61 {
62 int a[] = {1, 3, 6, 6, 6, 7, 7, 8, 9, 14, 15, 20, 22};
63 int b[] = {2, 3, 3, 7, 15, 15, 17, 19, 20, 20};
64 int alen, blen;
65 foo(a, b, sizeof (a) / sizeof (*a), sizeof (b) / sizeof (*b), alen, blen);
66
67 filter(a, alen, alen);
68 filter(b, blen, blen);
69
70 for (int i = 0; i != alen; ++i)
71 {
72 cout << a[i] << ' ';
73 }
74 cout << endl;
75 for (int i = 0; i != blen; ++i)
76 {
77 cout << b[i] << ' ';
78 }
79 cout << endl;
80 }
81
posted @
2011-07-28 17:51 unixfy 閱讀(482) |
評論 (0) |
編輯 收藏二叉樹的遍歷
·先根 中根 后根
·遞歸 非遞歸
·層序
1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 using namespace std;
5
6 struct node
7 {
8 int item;
9 node* left;
10 node* right;
11 };
12
13 void visit(node* p)
14 {
15 if (p != 0)
16 {
17 cout << p->item << ' ';
18 }
19 }
20
21 node* insert(node*& p, int i)
22 {
23 if (p == 0)
24 {
25 p = new node;
26 p->item = i;
27 p->left = 0;
28 p->right = 0;
29 }
30 else
31 {
32 if (i < p->item)
33 {
34 insert(p->left, i);
35 }
36 else
37 {
38 insert(p->right, i);
39 }
40 }
41 return p;
42 }
43
44 void preOrder(node* root)
45 {
46 if (root != 0)
47 {
48 visit(root);
49 preOrder(root->left);
50 preOrder(root->right);
51 }
52 }
53
54 void preOrderNonrecursive(node* root)
55 {
56 //
57 }
58
59 void inOrder(node* root)
60 {
61 if (root != 0)
62 {
63 inOrder(root->left);
64 visit(root);
65 inOrder(root->right);
66 }
67 }
68
69 void inOrderNonrecursive(node* root)
70 {
71 //
72 }
73
74 void postOrder(node* root)
75 {
76 if (root != 0)
77 {
78 postOrder(root->left);
79 postOrder(root->right);
80 visit(root);
81 }
82 }
83
84 void postOrderNonrecursive(node* root)
85 {
86 //
87 }
88
89 void levelOrder(node* root)
90 {
91 if (root != 0)
92 {
93 queue<node*> q;
94 node* t;
95 q.push(root);
96 while (!q.empty())
97 {
98 t = q.front();
99 cout << t->item << ' ';
100 q.pop();
101 if (t->left != 0)
102 {
103 q.push(t->left);
104 }
105 if (t->right != 0)
106 {
107 q.push(t->right);
108 }
109 }
110 }
111 }
112
113 int main()
114 {
115 int a[] = {3, 4, 2, 1, 5, 6};
116 node* bt = 0;
117 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
118 {
119 cout << i << endl;
120 insert(bt, a[i]);
121 }
122 preOrder(bt);
123 cout << endl;
124 inOrder(bt);
125 cout << endl;
126 postOrder(bt);
127 cout << endl;
128 levelOrder(bt);
129 cout << endl;
130 return 0;
131 }
posted @
2011-07-27 10:59 unixfy 閱讀(118) |
評論 (0) |
編輯 收藏