递归生成某集合的所有序列:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| template <class T>
void Swap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
template <class T>
void Permulation(T list[], int k, int m)
{
if (k == m)
{
for (int i = 0; i <= m; i++)
cout << list[i];
cout << endl;
}
else
{
for (int i = k; i <= m; i++)
{
Swap(list[k], list[i]);
Permulation(list, k+1, m);
Swap(list[k], list[i]);
}
}
} |
递归生成某集合的所有子集：
思想：
设集合X (A1, A2, A3,…, An)的所有子集为S[X(n)]，从集合X中移走A1的子集X(n-1)的所有子集集合记为S[X(n-1)]
S[X(n)] = S[X(n-1)] ∪ {S[X(n-1)]每个子集加上A1}
例如 集合{A, B, C}
{A}:
{} {A}
{A B}:
{} {A} ∪ {B} {A B}
{A B C}:
{} {A} {B} {A B} ∪ {C} {A C} {B C} {A B C}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| template <class T>
void FindSubSets(T list[], int lowIndex, int highIndex, vector< set<T> > &results)
{
if (lowIndex == highIndex)
{
set<T> empty;
set<T> oneElem;
oneElem.insert(list[lowIndex]);
results.push_back(empty);
results.push_back(oneElem);
}
else
{
FindSubSets(list, lowIndex+1, highIndex, results);
int existedSetSize = results.size();
for (int jj = 0; jj < existedSetSize; jj++)
{
set<T> newSet(results[jj]);
newSet.insert(list[lowIndex]);
results.push_back(newSet);
}
}
} |
斐波那契数列计算：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 递归：
int r_Fibonacci(int n)
{
if ( n < 2)
return n;
return r_Fibonacci(n-1) + r_Fibonacci(n-2);
}
非递归：
int fibonacci(int n)
{
if ( n < 2)
return n;
int f0 = 0;
int f1 = 1;
for (int ii = 1; ii < n; ii++)
{
f1 = f1 + f0;
f0 = f1 - f0;
}
return f1;
} |
递归查找：
1
2
3
4
5
6
7
8
| template <class InputIter, class T>
InputIter find(InputIter begin, InputIter end, const T& val)
{
if (begin != end && *begin != val)
return find(begin+1, end, val);
else
return begin;
} |
指针和引用都是用来间接访问对象的，他们之间有什么区别呢？何时用指针？何时用引用？为什么？
1. 首先认识到指针可以初始化为NULL而引用则不可以。 一个引用变量必须引用到某个对象上， 而且一旦初始化一个引用后，这个引用只能访问这个对象，而不能重新给该引用赋值到其他对象，即关系一旦建立，就不能解除。 因此当你需要一个变量可以间接访问其他对象时， 你需要使用指针。
因为一个引用必须关联到某个对象， 因为在定义引用时必须初始化：
string &rs; // 错误： 引用变量必须初始化
string s(“xyzzy”);
string &rs = s; // okay, rs引用s
指针没有这个限制：
string *ps; // 未初始化的指向string的指针
2. 指针可以重新指向其他的对象， 引用只能指向他初始化的对象，可以说引用像一个指针常量。
Watch out for bugs introduced in the constructor of base and other parent classes. Make sue an object is fully constructed before calling any virtual function.
在基类的构造函数中调用虚函数很容易引起bug，因为在构造派生类对象的时候先调用基类的的构造函数，因为此时派生类对象还没有构造完全，如果基类中的虚函数在派生类中重写了，那么基类不会调用这些虚函数，而是调用中的虚函数实现， 很容易引起bug。
Ａ 声明从它的名字开始读取，然后按照优先级顺序依次读取
Ｂ 优先级从高到底依次是
- 声明中被括号括起来的那一部分
- 后缀操作符： 括号（）表示这是一个函数，而方括号［］表示这是一个数组
- 前缀操作符： 星号 * 表示“指向．．．的指针”
Ｃ 如果const和(或) volatile关键字后面紧跟类型说明符（如int，long等）， 那么它作用于类型说明符，在其他情况下，const和（或）volatile关键字作用于它左边紧邻的指针星号。
例如， 声明 char * const *(*next)();
A 首先变量名为“next”， 并注意到它直接被括号括住
B.1 把括号里作为一个整体，得出“next是指向…的指针”
B 考虑括号外面的东西， 在星号*前缀和()后缀间作选择，根据优先级规则，（）优先级较高，所以next是一个函数指针，指向一个返回…的函数
B.3 处理前缀“*”， 得出指针所指的内容
C 最后把char * const解释为指向字符的常量指针
根据分析可以概括出： next是一个指针，它指向一个函数，该函数的参数列表为空，并返回一个指针，返回的指针指向一个类型为指向char的常量指针。
通过地下的例子可以证明，引用不是一个别名，他拥有自己独立的内存空间。 检验一个只含有引用数据成员的类的大小，就可以证明。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
using namespace std;
class Test
{
int &i; // int *const i;
int &j; // int *const j;
int &k; // int *const k;
};
int main()
{
// This will print 12 i.e. size of 3 pointers
cout<< “size of class Test = ” << sizeof(class Test) << endl;
return 0;
} |
原则：从中间开始到两边结束
中间开始指的是从中间定义的变量开始，
到两边结束：指的是从中间变量开始先右后左的原则依次解读
sample： void （*pFuncPtr)()
中间开始：定义一个pFuncPtr，
先右后左，右边是个右括号，忽略之， 左边是个*说明pFuncPtr是个指针，然后右边是个（）， 说明指针指向一个没有参数的函数，然后在左边是void说明指向
的函数的返回类型是void
“从中间开始” （pFuncPtr是一个…), 到右边（无意义的右括号）， 左边“*”（指针，指向。。。）， 右边-空的参数列表（“ 一个没有参数的函数），
左边void（pFuncPtr是一个指针， 指向带无参的返回类型为void函数)
void *pFuncPtr()
pFuncPtr是一个没有参数的函数，返回类型为void*
复杂的声明和定义
1。 void * (*(*fp1)(int))[10]
fp1是一个函数指针， 指向点一个int参数的函数，该函数返回一个指针，该指针指向一个有10个void*指针元素的数组
2. float (*(*fp2)(int, int, float))(int);
fp2是一个函数指针，指向一个参数列表为(int, int, float)的函数，该函数返回一个函数指针，指向一个参数为（int）返回类型为float的指针
3. typedef double (*(*(*fp3)())[10])();
fp3 a;
fp3是一个函数指针指向一个无参的函数， 返回类型是一个指针，指向一个有十个数组的元素，其中每个元素是一个函数指针指向一个没有参数的返回类型
为double的函数
4 int (*(*f4())[10])();
f4是一个函数返回一个指针，指向一个有十个元素的数组，每个数组元素为一个函数指针，指向一个带无参返回类型为int的函数
近期评论