栈是 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 阅读(917) |
评论 (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 阅读(185) |
评论 (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 阅读(417) |
评论 (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 阅读(362) |
评论 (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 阅读(120) |
评论 (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 阅读(673) |
评论 (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.cppblog.com/dawnbreak/archive/2009/08/11/92854.html
posted @
2011-05-15 23:19 unixfy 阅读(244) |
评论 (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 阅读(377) |
评论 (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 阅读(282) |
评论 (0) |
编辑 收藏
摘要: 来自于《冒号课堂》顺序表实现：
1 #include <iostream> 2 using namespace std; 3 4 typedef char ItemType; 5&n...
阅读全文
posted @
2011-05-14 18:37 unixfy 阅读(262) |
评论 (0) |
编辑 收藏