定義:
class Shape
{
public:
//...
void moveTo(Point newLocation);
bool validate()const;
vritual bool draw() const=0;
//...
}:
class Circle: public Shape
{
//...
bool draw() const;
//...
};
void (Shape::*mf1)(Point ) = &Shape::moveTo;//指向類的成員函數的指針。
ReturnType (ClassName::*pFuncName)(paramList);
pFuncName定義了指向ClassName中的一組函數。這組函數的形式是返回值為ReturnType，函數列表為paramList.
ClassName的限定使得只有ClassName或派生自它的類的對象才能解引用這個函數指針。
1 #include"stdafx.h"
2 #include<stdio.h>
3 #include<stdlib.h>
4
5 class Base;
6 class Derived;
7 typedef long (Base::*PFunc)(long,long);
8
9 enum FuncType
10 {
11 ADD=1,
12 SUB,
13 DIV,
14 MUL,
15 };
16
17 typedef struct tagCallBackFunc
18 {
19 long funcType;
20 PFunc proc;
21 }COMMAND,*PCOMMAND;
22
23 class Base
24 {
25 public:
26
27 virtual PCOMMAND GetCommands(void);
28 static COMMAND command[];
29
30 long base_add(long a,long b){printf("in base_add()\n");return a+b;}
31 long base_sub(long a,long b){printf("in base_sub()\n");return a-b;}
32 long base_div(long a,long b){printf("in base_div()\n");return a/b;}
33 long base_mul(long a,long b){printf("in base_mul()\n");return a*b;}
34 };
35
36 COMMAND Base::command[]={
37 {ADD,(PFunc)&Base::base_add},
38 {SUB,(PFunc)&Base::base_sub},
39 {MUL,(PFunc)&Base::base_mul},
40 {DIV,(PFunc)&Base::base_div},
41 };
42 PCOMMAND Base::GetCommands()
43 {
44 return command;
45 }
46
47 class Derived:public Base
48 {
49 public:
50 Derived(void){}
51 ~Derived(void){}
52 virtual PCOMMAND GetCommands(void){return command;}
53
54 long add(long a,long b){printf("in add()\n");return a+b;}
55 long sub(long a,long b){printf("in sub()\n");return a-b;}
56 long div(long a,long b){printf("in div()\n");return a/b;}
57 long mul(long a,long b){printf("in mul()\n");return a*b;}
58
59 static COMMAND command[];
60 };
61
62 COMMAND Derived::command[]=
63 {
64 {ADD,(PFunc)&Derived::add},
65 {SUB,(PFunc)&Derived::sub},
66 {MUL,(PFunc)&Derived::mul},
67 {DIV,(PFunc)&Derived::div},
68 {0}
69 };
70
71
72
73 void test(Base *control,FuncType funcType,long operand1,long operand2)
74 {
75 PCOMMAND pCommand = control->GetCommands();
76 PCOMMAND pNowCommand=NULL;
77
78 for(long i=0;pCommand[i].funcType;++i)
79 {
80 if(funcType == pCommand[i].funcType)
81 {
82 pNowCommand = &pCommand[i];
83 break;
84 }
85 }
86
87 if(pNowCommand)
88 {
89 long res = (control->*pNowCommand->proc)(operand1,operand2);
90 printf("res=%d\n",res);
91 }
92 }
93
94 int main()
95 {
96 Derived *d =new Derived();
97 Base *b = (Base*)d;
98 test(b,ADD,1,2);
99
100 Base *bb = new Base;
101 test(bb,MUL,1,2);
102 delete bb;
103 delete d;
104 return 0;
105 }
第89行是對指向類成員函數的指針的解析。
首先說一下數組指針和函數指針的定義問題。
一條重要的規(guī)則：函數和數組修飾符的優(yōu)先級比指針修飾符的優(yōu)先級高。函數的修飾符為()、數組的修飾符為[]、指針的修飾符為*。
eg:
int *A[N]: 等價于(int*)(A[N])：A[N]表示有N個元素的數組。元素類型為int*
int (*A)[N]：因為有括號提高了*的優(yōu)先級。所以等價于int ((*A)[N])。表示A是一個指針。A指向的是含有N個元素的數組。數組中存放的元素為int型。
對于指向函數的指針。
int (*afp2[N])(); afp2[N]表示afp2是個含有N個元素的數組。數組中的元素為指向返回值為int、無參數的函數指針。
因為函數的聲明較為復雜。可以用typedef來使代碼更加明確。
我們用typedef來改寫上面的聲明。
typedef int (*FP)();//定義FP為返回值為int、參數列表為空的函數的類型。
FP afp2[N];//含有N個元素的數組，返回值為FP。
將一個函數的地址初始化或賦值給一個指向函數的指針時，無需顯示的取其地址。編譯器知道隱式的取其地址。
void*可以指向任意類型的數據。
不存在可以指向任意類型函數的通用指針。
下面的代碼片段中紅色標出的部分等價于綠色標出的部分：
紅色的部分更簡潔明了。很適合鏈表操作中的添加操作。
zwl_srv_control *__list__,*__end__;
void add_job(zwl_srv_control*pcontrol)
{
pcontrol->_pnext = NULL;
EnterCriticalSection(&__cs__);
(__end__?__end__->_pnext:__list__) = pcontrol;
/*
if(!__end__)
__list__ = pcontrol;
else
__end__->next = pcontrol;
*/
__end__ = pcontrol;
LeaveCriticalSection(&__cs__);
Sleep(0);
}
對于任意含有n個節(jié)點的有根樹僅用O(n)的空間。
是一種左孩子、有兄弟的表示。
每一個節(jié)點包含下列屬性：
1.指向父節(jié)點的指針
2.left-child[x]指向節(jié)點x的最左孩子
3.right-sibling[x]指向節(jié)點x緊右邊的兄弟。
在O(3n/2)比較后求出最大值和最小值
思想:成對的處理元素，兩者較大的和max比較，兩者較小的和min比較。
GetMaxAndMin(A,n)
if n為奇數
max = min = A[0];
i = 1;
else
if A[0]>A[1] then max = A[0]; min = A[1]
else max = A[1]; min = A[0];
i =2;
for i to n-1
if(A[i]>A[i+1])
{
max = max>A[i] ? max: A[i];
min = A[i+1]<min ? A[i+1]:min;
}
else
{
max = A[i+1]>max ? A[i+1]:max;
min = A[i]<min ? A[i] : min;
}
i+=2;
下面介紹一種在O(n)的時間內找出第k個最大值(最小值)的方法
該方法和快速排序相似。不同在于每次只出理一邊。
偽代碼如下：
Random-select(A,p,r,i)//找到A中的第i個最小值
if p==r
then return a[p]
q = random-partition(A,p,r)
k = p-q+1
if(i==k)
then return A[q]
else if i<k
then return random-select(A,p,q-1,i)
else return random-select(A,q+1,r,i-k)
這個算法很不錯。
最近在看《算法導論》，首先在這推薦一下這本書，寫的確實很精彩
。
《算法導論》的第二部分分析了多種排序算法。包括插入排序、歸并排序、堆排序、快速排序以及線性排序的幾個算法。
下面簡要總結一下。
對于輸入規(guī)模為n的數組。插入排序的復雜度為O(n^2)。
歸并排序、堆排序、快速排序的復雜度為O(n㏒n);
線性排序的復雜度為O(n)
1.插入排序的性能和輸入元素的的序列有很大的關系，如果輸入已排序的序列，則復雜度是線性的，若輸入是逆序的則是O(n^2)的。
2.堆排序用到了優(yōu)先隊列（優(yōu)先隊列是一種用來維護由一組元素構成的集合S的數據結構）。
3.快速排序的關鍵是主元的選取(pivot)。在排序過程中元素被分成四部分：小于等于主元的序列、大于主元的序列、未比較的序列、主元。
當未比較的序列未空時，再分別對小于等于主元的序列進行排序、對大于主元的序列進行排序。
以上三種排序都是原地排序。所謂的原地排序(in-place)是指這些元素是在原數組中重排序的，在任何時刻，至多其中的常數個數字是存儲在數組之外的。
4.歸并排序是將原數組劃分成子序列，對子序列進行排序，然后將排序好的子序列合并到一起從而使得原序列重排。
歸并排序不是原地排序，它需要額外的內存資源。
以上四種是比較常用的排序，對于輸入序列沒有特殊的要求，并且都是比較排序，也就是說通過比較各個元素而進行的排序。它們的時間復雜度最好為O(n㏒n);
下面介紹能在時間內完成的排序。
1.計數排序
適用條件：輸入序列中的元素取值在一個范圍之內0-k
基本思想:對于每一個元素確定比它小的的元素的個數。
排序A序列，將結果放入B中，元素的取值范圍為0-k
偽代碼如下：
Count-sort(A,B,k)
for i=0 to k
do C[i]=0
for j=1 to length(A)
do C[A[j]] = C[A[j]]+1;計算A[j]的個數。
for i=1 to k
do C[i] = C[i-1]+C[i];計算小于和等于i的元素個數
for j=length(A) downto 1
do B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]]-1;
我們可以明顯看到計數排序不是原地排序。同時計數排序是穩(wěn)定的（即相同的元素輸入和輸出的相對位置不變。）
| c語言之typedef 的用法 |
用途一：
定義一種類型的別名，而不只是簡單的宏替換。可以用作同時聲明指針型的多個對象。比如：
char* pa, pb; // 這多數不符合我們的意圖，它只聲明了一個指向字符變量的指針，
// 和一個字符變量；
以下則可行：
typedef char* PCHAR; // 一般用大寫
PCHAR pa, pb; // 可行，同時聲明了兩個指向字符變量的指針
雖然：
char *pa, *pb;
也可行，但相對來說沒有用typedef的形式直觀，尤其在需要大量指針的地方，typedef的方式更省事。
用途二：
用在舊的C代碼中（具體多舊沒有查），幫助struct。以前的代碼中，聲明struct新對象時，必須要帶上struct，即形式為： struct 結構名 對象名，如：
struct tagPOINT1
{
int x;
int y;
};
struct tagPOINT1 p1;
而在C++中，則可以直接寫：結構名 對象名，即：
tagPOINT1 p1;
估計某人覺得經常多寫一個struct太麻煩了，于是就發(fā)明了：
typedef struct tagPOINT
{
int x;
int y;
}POINT;
POINT p1; // 這樣就比原來的方式少寫了一個struct，比較省事，尤其在大量使用的時候
或許，在C++中，typedef的這種用途二不是很大，但是理解了它，對掌握以前的舊代碼還是有幫助的，畢竟我們在項目中有可能會遇到較早些年代遺留下來的代碼。
用途三：
用typedef來定義與平臺無關的類型。
比如定義一個叫 REAL 的浮點類型，在目標平臺一上，讓它表示最高精度的類型為：
typedef long double REAL;
在不支持 long double 的平臺二上，改為：
typedef double REAL;
在連 double 都不支持的平臺三上，改為：
typedef float REAL;
也就是說，當跨平臺時，只要改下 typedef 本身就行，不用對其他源碼做任何修改。
標準庫就廣泛使用了這個技巧，比如size_t。
另外，因為typedef是定義了一種類型的新別名，不是簡單的字符串替換，所以它比宏來得穩(wěn)健（雖然用宏有時也可以完成以上的用途）。
用途四：
為復雜的聲明定義一個新的簡單的別名。方法是：在原來的聲明里逐步用別名替換一部分復雜聲明，如此循環(huán)，把帶變量名的部分留到最后替換，得到的就是原聲明的最簡化版。舉例：
1. 原聲明：int *(*a[5])(int, char*);
變量名為a，直接用一個新別名pFun替換a就可以了：
typedef int *(*pFun)(int, char*);
原聲明的最簡化版：
pFun a[5];
2. 原聲明：void (*b[10]) (void (*)());
變量名為b，先替換右邊部分括號里的，pFunParam為別名一：
typedef void (*pFunParam)();
再替換左邊的變量b，pFunx為別名二：
typedef void (*pFunx)(pFunParam);
原聲明的最簡化版：
pFunx b[10];
3. 原聲明：doube(*)() (*e)[9];
變量名為e，先替換左邊部分，pFuny為別名一：
typedef double(*pFuny)();
再替換右邊的變量e，pFunParamy為別名二
typedef pFuny (*pFunParamy)[9];
原聲明的最簡化版：
pFunParamy e;
理解復雜聲明可用的“右左法則”：從變量名看起，先往右，再往左，碰到一個圓括號就調轉閱讀的方向；括號內分析完就跳出括號，還是按先右后左的順序，如此循環(huán)，直到整個聲明分析完。舉例：
int (*func)(int *p);
首先找到變量名func，外面有一對圓括號，而且左邊是一個*號，這說明func是一個指針；然后跳出這個圓括號，先看右邊，又遇到圓括號，這說明(*func)是一個函數，所以func是一個指向這類函數的指針，即函數指針，這類函數具有int*類型的形參，返回值類型是int。
int (*func[5])(int *);
func右邊是一個[]運算符，說明func是具有5個元素的數組；func的左邊有一個*，說明func的元素是指針（注意這里的*不是修飾func，而是修飾func[5]的，原因是[]運算符優(yōu)先級比*高，func先跟[]結合）。跳出這個括號，看右邊，又遇到圓括號，說明func數組的元素是函數類型的指針，它指向的函數具有int*類型的形參，返回值類型為int。
也可以記住2個模式：
type (*)(....)函數指針
type (*)[]數組指針
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
陷阱一：
記住，typedef是定義了一種類型的新別名，不同于宏，它不是簡單的字符串替換。比如：
先定義：
typedef char* PSTR;
然后：
int mystrcmp(const PSTR, const PSTR);
const PSTR實際上相當于const char*嗎？不是的，它實際上相當于char* const。
原因在于const給予了整個指針本身以常量性，也就是形成了常量指針char* const。
簡單來說，記住當const和typedef一起出現時，typedef不會是簡單的字符串替換就行。
陷阱二：
typedef在語法上是一個存儲類的關鍵字（如auto、extern、mutable、static、register等一樣），雖然它并不真正影響對象的存儲特性，如：
typedef static int INT2; //不可行
編譯將失敗，會提示“指定了一個以上的存儲類”。
|
|
|
|
在C++中，有三種類型的循環(huán)語句：for, while, 和do...while， 但是在一般應用中作循環(huán)時，我們可能用for和while要多一些，do...while相對不受重視。
但是，最近在讀我們項目的代碼時，卻發(fā)現了do...while的一些十分聰明的用法，不是用來做循環(huán)，而是用作其他來提高代碼的健壯性。
1. do...while(0)消除goto語句。
通常，如果在一個函數中開始要分配一些資源，然后在中途執(zhí)行過程中如果遇到錯誤則退出函數，當然，退出前先釋放資源，我們的代碼可能是這樣：
version 1
bool Execute()
{
// 分配資源
int *p = new int;
bool bOk(true);
// 執(zhí)行并進行錯誤處理
bOk = func1();
if(!bOk)
{
delete p;
p = NULL;
return false;
}
bOk = func2();
if(!bOk)
{
delete p;
p = NULL;
return false;
}
bOk = func3();
if(!bOk)
{
delete p;
p = NULL;
return false;
}
// ..........
// 執(zhí)行成功，釋放資源并返回
delete p;
p = NULL;
return true;
}
這里一個最大的問題就是代碼的冗余，而且我每增加一個操作，就需要做相應的錯誤處理，非常不靈活。于是我們想到了goto:
version 2
bool Execute()
{
// 分配資源
int *p = new int;
bool bOk(true);
// 執(zhí)行并進行錯誤處理
bOk = func1();
if(!bOk) goto errorhandle;
bOk = func2();
if(!bOk) goto errorhandle;
bOk = func3();
if(!bOk) goto errorhandle;
// ..........
// 執(zhí)行成功，釋放資源并返回
delete p;
p = NULL;
return true;
errorhandle:
delete p;
p = NULL;
return false;
}
代碼冗余是消除了，但是我們引入了C++中身份比較微妙的goto語句，雖然正確的使用goto可以大大提高程序的靈活性與簡潔性，但太靈活的東西往往是很危險的，它會讓我們的程序捉摸不定，那么怎么才能避免使用goto語句，又能消除代碼冗余呢，請看do...while(0)循環(huán)：
version3
bool Execute()
{
// 分配資源
int *p = new int;
bool bOk(true);
do
{
// 執(zhí)行并進行錯誤處理
bOk = func1();
if(!bOk) break;
bOk = func2();
if(!bOk) break;
bOk = func3();
if(!bOk) break;
// ..........
}while(0);
// 釋放資源
delete p;
p = NULL;
return bOk;
}
“漂亮！”， 看代碼就行了，啥都不用說了...
2 宏定義中的do...while(0)
如果你是C++程序員，我有理由相信你用過，或者接觸過，至少聽說過MFC, 在MFC的afx.h文件里面，你會發(fā)現很多宏定義都是用了do...while(0)或do...while(false)， 比如說：
#define AFXASSUME(cond) do { bool __afx_condVal=!!(cond); ASSERT(__afx_condVal); __analysis_assume(__afx_condVal); } while(0)
粗看我們就會覺得很奇怪，既然循環(huán)里面只執(zhí)行了一次，我要這個看似多余的do...while(0)有什么意義呢？
當然有！
為了看起來更清晰，這里用一個簡單點的宏來演示：
#define SAFE_DELETE(p) do{ delete p; p = NULL} while(0)
假設這里去掉do...while(0),
#define SAFE_DELETE(p) delete p; p = NULL;
那么以下代碼：
if(NULL != p) SAFE_DELETE(p)
else ...do sth...
就有兩個問題，
1) 因為if分支后有兩個語句，else分支沒有對應的if，編譯失敗
2) 假設沒有else, SAFE_DELETE中的第二個語句無論if測試是否通過，會永遠執(zhí)行。
你可能發(fā)現，為了避免這兩個問題，我不一定要用這個令人費解的do...while, 我直接用{}括起來就可以了
#define SAFE_DELETE(p) { delete p; p = NULL;}
的確，這樣的話上面的問題是不存在了，但是我想對于C++程序員來講，在每個語句后面加分號是一種約定俗成的習慣，這樣的話，以下代碼:
if(NULL != p) SAFE_DELETE(p);
else ...do sth...
其else分支就無法通過編譯了（原因同上），所以采用do...while(0)是做好的選擇了。
也許你會說，我們代碼的習慣是在每個判斷后面加上{}, 就不會有這種問題了，也就不需要do...while了，如：
if(...)
{
}
else
{
}
誠然，這是一個好的，應該提倡的編程習慣，但一般這樣的宏都是作為library的一部分出現的，而對于一個library的作者，他所要做的就是讓其庫具有通用性，強壯性，因此他不能有任何對庫的使用者的假設，如其編碼規(guī)范，技術水平等。
