棧是 LIFO，將進出順序逆序。
隊列是 FIFO，保持進與出的順序一致。
所以隊列對順序不起作用，不能用兩個隊列模擬一個棧。
兩個棧模擬一個隊列
S1 S2 Q
S1 為插入棧，S2 為彈出棧。以實現隊列 Q。
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4
5 template <typename T>
6 class QueueByDoubleStack
7 {
8 private:
9 stack<T> s1;
10 stack<T> s2;
11 public:
12 size_t size()
13 {
14 return s1.size() + s2.size();
15 }
16 bool empty()
17 {
18 return s1.empty() && s2.empty();
19 }
20 void push(T t)
21 {
22 s1.push(t);
23 }
24 void pop()
25 {
26 if (s2.empty())
27 {
28 while (!s1.empty())
29 {
30 s2.push(s1.top());
31 s1.pop();
32 }
33 }
34 s2.pop();
35 }
36 T top()
37 {
38 if (s2.empty())
39 {
40 while (!s1.empty())
41 {
42 s2.push(s1.top());
43 s1.pop();
44 }
45 }
46 return s2.top();
47 }
48 };
49
50 int main()
51 {
52 QueueByDoubleStack<int> q;
53 for (int i = 0; i < 10; ++i)
54 {
55 q.push(i);
56 }
57 while (!q.empty())
58 {
59 cout << q.top() << ' ';
60 q.pop();
61 }
62 cout << endl;
63 return 0;
64 }
posted @
2011-05-18 19:58 unixfy 閱讀(940) |
評論 (0) |
編輯 收藏字符串用字符數組來保存。
這里對一個大數求其階乘，N!
N! 的結果很大，需要字符數組保持，但是我們認定 N 沒有大到需要字符數組存儲的地步。
由于這個原因，我們是對結果用字符數組存儲，而對 N 還是保持到 int 中。
首先對 N 從 0 到 N 遍歷，對保持結果的字符數組 ret 中的每位進行逐位相乘，還是 int 型乘法。從左到右，從低位到高位進行運算，注意進位。對小于 N 的每個數，對 ret 中的每個元素相乘，進位。記錄 ret 中的元素個數。
然后對 ret 進行逆轉，以使高位放在最左邊，并且將實際數字轉換成字符以輸出顯示。
1 #include <iostream>
2 using namespace std;
3
4 char* bigFactorial(char* ret, int n)
5 {
6 ret[0] = 1;
7 int len = 1, i, j, t, c = 0;
8 for (i = 2; i <= n; ++i)
9 {
10 for (j = 0; j < len; ++j)
11 {
12 t = ret[j] * i + c;
13 ret[j] = t % 10;
14 c = t / 10;
15 }
16 while (c != 0)
17 {
18 ret[len] = c % 10;
19 c /= 10;
20 ++len;
21 }
22 }
23 for (int i = 0; i < len / 2; ++i)
24 {
25 ret[i] ^= ret[len - i - 1];
26 ret[len - i - 1] ^= ret[i];
27 ret[i] ^= ret[len - i - 1];
28 }
29 ret[len] = '\0';
30 for (i = 0; i < len; ++i)
31 {
32 ret[i] += '0';
33 }
34 return ret;
35 }
36
37 int main()
38 {
39 int n;
40 char result[1000];
41 while (cin >> n)
42 {
43 cout << bigFactorial(result, n) << endl;
44 }
45 return 0;
46 }
posted @
2011-05-18 19:36 unixfy 閱讀(205) |
評論 (0) |
編輯 收藏單鏈表可以順序非遞歸的遍歷訪問。同時，單鏈表具有遞歸的性質，可以遞歸訪問。
遞歸訪問有兩種方式，一是首先訪問當前節點，再遞歸訪問剩下的節點。
二是首先遞歸訪問剩下的節點，在訪問當前節點。這種方式的遞歸訪問可以實現單鏈表的逆序訪問。
來自于《算法：C 語言實現》
（CPPBLOG 刪除后為什么不能再提交，錯誤：不能重復提交！可是已經刪除了啊）
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void insert(int i, node* h)
11 {
12 node* p = new node;
13 p->item = i;
14 p->next = h->next;
15 h->next = p;
16 }
17
18 void traverse(node* h)
19 {
20 h = h->next;
21 while (h != 0)
22 {
23 cout << h->item << ' ';
24 h = h->next;
25 }
26 cout << endl;
27 }
28
29 void traverseRecurse(node* h)
30 {
31 if (h->next == 0)
32 {
33 cout << endl;
34 return;
35 }
36 cout << h->next->item << ' ';
37 traverseRecurse(h->next);
38 }
39
40 void traverseRecurseIvertedSequence(node* h)
41 {
42 if (h->next == 0)
43 {
44 cout << endl;
45 return;
46 }
47 traverseRecurseIvertedSequence(h->next);
48 cout << h->next->item << ' ';
49 }
50
51 void clear(node* h)
52 {
53 node* p = h->next, *q;
54 while (p != 0)
55 {
56 q = p->next;
57 delete p;
58 p = q;
59 }
60 }
61
62 int main()
63 {
64 node* h = new node;
65 h->next = 0;
66 for (int i = 0; i < 10; ++i)
67 {
68 insert(i, h);
69 }
70 traverse(h);
71 traverseRecurse(h);
72 traverseRecurseIvertedSequence(h);
73 clear(h);
74 delete h;
75 return 0;
76 }
posted @
2011-05-18 19:13 unixfy 閱讀(445) |
評論 (0) |
編輯 收藏大數乘法，利用字符串數組保持被乘數、乘數和商。
從左到右依次運算，兩個循環即可。
在內循環內有
result[i + j + 1] += (lhs[i] - '0') * (rhs[i] - '0');
最高位空著，因為有可能從次高位進過來位。
然后從左往右依次進位。
之后再檢測左邊的最高位是否為 0，若為 0，右移。
將結果轉存。
注意，這里高位一直在最左邊，沒有逆轉。
如果先逆轉，還是從左開始計算，即從最低位開始計算，有 result[i + j] += (lhs[i] - '0') * (rhs[i] - '0');
1 #include <iostream>
2 using namespace std;
3
4 char* bigMultiply(char ret[], char lhs[], char rhs[])
5 {
6 int llen = strlen(lhs), rlen = strlen(rhs);
7 int* result = new int[llen + rlen];
8 int i, j;
9 memset(result, 0, sizeof (int) * (llen + rlen));
10 //for (i = 0; i < llen + rlen; ++i)
11 //{
12 // result[i] = 0;
13 //}
14 for (i = 0; i < llen; ++i)
15 {
16 for (j = 0; j < rlen; ++j)
17 {
18 result[i + j + 1] += (lhs[i] - '0') * (rhs[j] - '0');
19 cout << result[i + j + 1] << endl;
20 }
21 }
22 for (i = llen + rlen - 1; i > 0; --i)
23 {
24 if (result[i] >= 10)
25 {
26 result[i - 1] += result[i] / 10;
27 result[i] %= 10;
28 }
29 }
30 i = 0;
31 while (result[i] == 0)
32 {
33 ++i;
34 }
35 for (j = 0; i < llen + rlen; ++i, ++j)
36 {
37 cout << result[i];
38 ret[j] = result[i] + '0';
39 }
40 cout << endl;
41 ret[j] = '\0';
42 delete [] result;
43 return ret;
44 }
45
46 int main()
47 {
48 char a[1000], b[1000], c[2000];
49 while (cin >> a >> b)
50 {
51 cout << a << " * " << b << " = " << endl;
52 cout << bigMultiply(c, a, b) << endl;
53 }
54 }
http://hi.baidu.com/unixfy/blog/item/d52eb6f600e57a03b17ec513.htmlhttp://hi.baidu.com/unixfy/blog/item/97b2e4e8fc96883263d09f69.html
posted @
2011-05-16 20:47 unixfy 閱讀(383) |
評論 (0) |
編輯 收藏來自于《算法：C 語言實現》
在邊長為 1 的正方形中隨機產生 N 個點，計算有多少個點對之間的距離小于 d。
一種直觀的解法就是對每個點，檢查其余其他點的距離。
另一種改進的方法是，考慮到距離小于 d 才符合要求，對于許多一開始就能知道距離大于 d 的點對沒有必要檢查。這里借助一個二維的鏈表數組進行操作。
由 d 得到 G = 1 / d，把正方形劃分成一個 (G + 2) * (G + 2) 的格子。對于要檢查的點，只需要檢查其所在格子以及周圍的 8 個格子中的其他點與它的距離。這樣效率得到很大的提升。
解法一：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <math.h>
4 #include <time.h>
5
6 typedef struct
7 {
8 float x;
9 float y;
10 } point;
11
12 float distance(point a, point b)
13 {
14 float dx = a.x - b.x, dy = a.y - b.y;
15 return sqrt(dx * dx + dy * dy);
16 }
17
18 float randFloat()
19 {
20 return 1.0 * rand() / RAND_MAX;
21 }
22
23 int main()
24 {
25 float d = 0.1;
26 int i, j, cnt = 0, N = 100;
27
28 point* a = (point*)malloc(N * sizeof (*a));
29 srand(time(0));
30 for (i = 0; i < N; ++i)
31 {
32 a[i].x = randFloat();
33 a[i].y = randFloat();
34 }
35 for (i = 0; i < N; ++i)
36 {
37 for (j = i + 1; j < N; ++j)
38 {
39 if (distance(a[i], a[j]) < d)
40 {
41 ++cnt;
42 }
43 }
44 }
45 printf("%d edges shorter than %f\n", cnt, d);
46 }
改進的解法：
1 // 二維鏈表數組
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <math.h>
6 #include <time.h>
7
8 typedef struct
9 {
10 float x;
11 float y;
12 } point;
13
14 typedef struct node* link;
15 struct node
16 {
17 point p;
18 link next;
19 };
20
21 link** grid;
22 int G;
23 float d;
24 int cnt;
25
26 float distance(point a, point b)
27 {
28 float dx = a.x - b.x, dy = a.y - b.y;
29 return sqrt(dx * dx + dy * dy);
30 }
31
32 float randFloat()
33 {
34 return 1.0 * rand() / RAND_MAX;
35 }
36
37 void gridinsert(float x, float y)
38 {
39 int i, j;
40 link s;
41 int X = x * G + 1;
42 int Y = y * G + 1;
43 link t = (link)malloc(sizeof (*t));
44 t->p.x = x;
45 t->p.y = y;
46
47 for (i = X - 1; i <= X + 1; ++i)
48 {
49 for (j = Y - 1; j <= Y + 1; ++j)
50 {
51 for (s = grid[i][j]; s != 0; s = s->next)
52 {
53 if (distance(s->p, t->p) < d)
54 {
55 ++cnt;
56 }
57 }
58 }
59 }
60 t->next = grid[X][Y];
61 grid[X][Y] = t;
62 }
63
64 int** malloc2d(int r, int c)
65 {
66 int i;
67 int **t = (int**)malloc(r * sizeof (int*));
68 for (i = 0; i < r; ++i)
69 {
70 t[i] = (int*)malloc(c * sizeof (int));
71 }
72 return t;
73 }
74
75 int main()
76 {
77 int i, j, N = 100;
78 d = 0.1;
79 G = 1 / d;
80
81 grid = (link**)malloc2d(G + 2, G + 2);
82
83 for (i = 0; i < G + 2; ++i)
84 {
85 for (j = 0; j < G + 2; ++j)
86 {
87 grid[i][j] = 0;
88 }
89 }
90
91 srand(time(0));
92 for (i = 0; i < N; ++i)
93 {
94 gridinsert(randFloat(), randFloat());
95 }
96
97 printf("%d edges shorter than %f\n", cnt, d);
98 return 0;
99 }
posted @
2011-05-16 14:12 unixfy 閱讀(134) |
評論 (0) |
編輯 收藏
（字符串）：
在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff，則輸出b。
先遍歷一遍，統計各個字符的出現次數。在遍歷一遍，若當前字符的出現次數為 1，則返回。若不存在這樣的字符則返回 0。
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 char solve(const string& s)
6 {
7 static int times[26] = {0};
8 memset(times, 0, sizeof (times));
9 for (size_t i = 0; i < s.size(); ++i)
10 {
11 ++times[s[i] - 'a'];
12 }
13 for (size_t i = 0; i < s.size(); ++i)
14 {
15 if (times[s[i] - 'a'] == 1)
16 {
17 return s[i];
18 }
19 }
20 return 0;
21 }
22
23 int main()
24 {
25 string s = "abaccdeff";
26 cout << solve(s) << endl;
27 return 0;
28 }
posted @
2011-05-15 23:44 unixfy 閱讀(695) |
評論 (0) |
編輯 收藏
0-1 背包問題有這幾個元素：個數、重量、價值。
n 個東西，有各自的重量和價值。一個背包，其最大的可行裝載量為 m。
要求，在不超過 m 的情況下，裝得最大的價值，并求出具體裝了哪些東西。
實現：
1 #include <iostream>
2 using namespace std;
3
4 void solve(int n_weights_values[6][11], int weights[5], int values[5], int n, int m)
5 {
6 int i, j;
7 for (i = 1; i <= n; ++i)
8 {
9
10 for (j = 1; j <= m; ++j)
11 {
12 n_weights_values[i][j] = n_weights_values[i - 1][j];
13 if (weights[i - 1] <= j)
14 {
15 int temp = n_weights_values[i - 1][j - weights[i - 1]] + values[i - 1];
16 if (temp > n_weights_values[i][j])
17 {
18 n_weights_values[i][j] = temp;
19 }
20 }
21 }
22 }
23 }
24
25 void getPaths(int paths[5], int n_weights_values[6][11], int weights[5], int n, int m)
26 {
27 int i, j = m;
28 for (i = n; i > 0; --i)
29 {
30 if (n_weights_values[i][j] > n_weights_values[i - 1][j])
31 {
32 paths[i - 1] = 1;
33 j -= weights[i - 1];
34 }
35 }
36 }
37
38 int main()
39 {
40 int n = 5;
41 int m = 10;
42 int weights[5] = {1, 3, 8, 2, 7};
43 int values[5] = {2, 5, 3, 9, 4};
44 int n_weights_values[6][11];
45 int paths[5];
46 memset(n_weights_values, 0, sizeof (n_weights_values));
47 memset(paths, 0, sizeof (paths));
48
49 solve(n_weights_values, weights, values, n, m);
50 getPaths(paths, n_weights_values, weights, n, m);
51
52 cout << n_weights_values[n][m] << endl;
53 for (int i = 0; i < n; ++i)
54 {
55 if (paths[i] == 1)
56 {
57 cout << i + 1 << ' ' << weights[i] << ' ' << values[i] << endl;
58 }
59 }
60
61 return 0;
62 }
參考：
http://blog.csdn.net/livelylittlefish/archive/2008/03/16/2186206.aspxhttp://www.cnblogs.com/zyobi/archive/2009/06/22/1508730.htmlhttp://hi.bccn.net/space-339919-do-blog-id-14722.htmlhttp://dev.firnow.com/course/3_program/c++/cppsl/2008316/104782.htmlhttp://www.shnenglu.com/dawnbreak/archive/2009/08/11/92854.html
posted @
2011-05-15 23:19 unixfy 閱讀(265) |
評論 (0) |
編輯 收藏2010年中興面試題
編程求解
輸入兩個整數 n 和 m，從數列1，2，3.......n 中隨意取幾個數，
使其和等于 m，要求將其中所有的可能組合列出來。
用一個 n 位的數根據其每位是否為 1 來判斷是否選擇相應的數。
實現：
1 #include <iostream>
2 using namespace std;
3
4 void solve(int m, int a[], int n)
5 {
6 for (int i = 0; i < (1 << n); ++i)
7 {
8 int sum = 0;
9 int index = 0;
10 int t = i;
11 while (t != 0)
12 {
13 if (t % 2 == 1)
14 {
15 sum += a[index];
16 }
17 ++index;
18 t /= 2;
19 }
20 if (sum == m)
21 {
22 index = 0;
23 t = i;
24 while (t != 0)
25 {
26 if (t % 2 == 1)
27 {
28 cout << a[index] << ' ';
29 }
30 ++index;
31 t /= 2;
32 }
33 cout << endl;
34 }
35 }
36 }
37
38 int main()
39 {
40 int a[] = {1, 2, 3, 4, 5, 6, 7};
41 int n = 7;
42 int m = 10;
43 solve(m, a, n);
44
45 return 0;
46 }
posted @
2011-05-15 21:42 unixfy 閱讀(398) |
評論 (0) |
編輯 收藏單鏈表有兩種版本，分別是帶有頭結點和不帶有頭結點。
各自的翻轉如下。
不帶有頭結點的：
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void insert(int i, node*& p)
11 {
12 node* q = new node;
13 if (q == 0)
14 {
15 exit(1);
16 }
17 q->item = i;
18 q->next = p;
19 p = q;
20 }
21
22 void print(node* p)
23 {
24 while (p != 0)
25 {
26 cout << p->item << ' ';
27 p = p->next;
28 }
29 cout << endl;
30 }
31
32 void clear(node*& p)
33 {
34 node* q;
35 while (p != 0)
36 {
37 q = p->next;
38 delete p;
39 p = q;
40 }
41 p = 0;
42 }
43
44 void reverse(node*& p)
45 {
46 node* p1, *p2, *p3;
47 p2 = p;
48 p1 = 0;
49 p3 = 0;
50 while (p2 != 0)
51 {
52 p3 = p2->next;
53 p2->next = p1;
54 p1 = p2;
55 p2 = p3;
56 }
57 p = p1;
58 }
59
60 int main()
61 {
62 node* p = 0;
63 for (int i = 0; i < 10; ++i)
64 {
65 insert(i, p);
66 }
67 print(p);
68 reverse(p);
69 print(p);
70 clear(p);
71 print(p);
72 return 0;
73 }
帶有頭結點的：
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void init(node*& p)
11 {
12 p = new node;
13 p->next = 0;
14 }
15
16 void insert(int i, node* p)
17 {
18 node* q = new node;
19 q->item = i;
20 q->next = p->next;
21 p->next = q;
22 }
23
24 void print(node* p)
25 {
26 p = p->next;
27 while (p != 0)
28 {
29 cout << p->item << ' ';
30 p = p->next;
31 }
32 cout << endl;
33 }
34
35 void clear(node* p)
36 {
37 node* q = p->next;
38 p->next = 0;
39 while (q != 0)
40 {
41 p = q->next;
42 delete q;
43 q = p;
44 }
45 }
46
47 void destroy(node*& p)
48 {
49 clear(p);
50 delete p;
51 p = 0;
52 }
53
54 void reverse(node* p)
55 {
56 node* p1, *p2, *p3;
57 p2 = p->next;
58 p1 = 0;
59 p3 = 0;
60 while (p2 != 0)
61 {
62 p3 = p2->next;
63 p2->next = p1;
64 p1 = p2;
65 p2 = p3;
66 }
67 p->next = p1;
68 }
69
70 int main()
71 {
72 node* p;
73 init(p);
74 for (int i = 0; i < 10; ++i)
75 {
76 insert(i, p);
77 }
78 print(p);
79 reverse(p);
80 print(p);
81 clear(p);
82 print(p);
83 destroy(p);
84 return 0;
85 }
posted @
2011-05-15 19:31 unixfy 閱讀(297) |
評論 (0) |
編輯 收藏
摘要: 來自于《冒號課堂》順序表實現：
1 #include <iostream> 2 using namespace std; 3 4 typedef char ItemType; 5&n...
閱讀全文
posted @
2011-05-14 18:37 unixfy 閱讀(284) |
評論 (0) |
編輯 收藏