摘要: 哈希結(jié)構(gòu)

C++博客 Alex-Lee 2009-10-21

哈希結(jié)構(gòu)在處理大量數(shù)據(jù)時具有很好的優(yōu)勢，在插入，查詢，刪除等操作上具有常量的時間復(fù)雜度O(1)。使用范圍是數(shù)據(jù)集具有自然數(shù)上的關(guān)鍵字域（不是自然數(shù)也需要能夠轉(zhuǎn)為自然數(shù)域），通過哈希函數(shù)將關(guān)鍵字映射到尋址數(shù)組的槽。由于關(guān)鍵字域U[0...n]與尋址數(shù)組[0...m]中，總是n>m，也就是說，總有多個關(guān)鍵字對應(yīng)一個槽。這個碰撞就需要通過一些方法改變?？梢酝ㄟ^拉鏈法（鏈表法）和開放地址法。對于拉鏈法中，鏈表不能太長，否則影響速度，最好控制在10個元素之內(nèi)，這樣就要去尋址數(shù)組長度m>= n/10，這樣就會多消耗些空間。為了讓每個鏈表長度基本一致，就需要  閱讀全文      摘要: 快速排序算法、計數(shù)排序算法

C++博客 Alex-Lee 2009-10-20

快速排序是分治算法，將數(shù)組分為幾部分，在各部分內(nèi)完成排序，遞歸排序。算法時間復(fù)雜度O(nlgn)。這是比較排序算法中速度最快的一個算法了。計數(shù)排序、基數(shù)排序、桶排序算法是非比較排序算法，他們的算法復(fù)雜度是O(n)。快速排序算法在選取支點上要有技巧，最好能達(dá)到隨即要求。
  閱讀全文      摘要: 優(yōu)先級隊列

C++博客 Alex-Lee 2009-10-18

上篇隨筆談到了堆結(jié)構(gòu)的一個應(yīng)用就是堆排序算法，雖然堆排序算法性能不錯，但是比起快速排序算法還是有些差距。但是堆結(jié)構(gòu)的另外一個應(yīng)該就比較廣泛了，就是優(yōu)先級隊列。
優(yōu)先級隊列有3中操作：插入(O(lgn))，最大最小值(O(1)),刪去最大最小值(O(lgn))。其算法性能很好，在優(yōu)先級調(diào)度作業(yè)上應(yīng)用比較廣泛。基于優(yōu)先級的調(diào)度算法中，基于堆結(jié)構(gòu)的實現(xiàn)算法是一個比較好選擇。在事件驅(qū)動的仿真器中也有應(yīng)用。  閱讀全文      摘要: 堆排序算法

---------- C++博客 Alex-Lee 2009-10-15

（二叉）堆結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一顆完全二叉樹。算法時間復(fù)雜度O(nlgn)，具有插入排序和合并排序的優(yōu)點。堆結(jié)構(gòu)滿足堆性質(zhì)：對除根以外的每個節(jié)點i,滿足A[PARENT(i)] >= A[i]。

堆排序算法實現(xiàn)有三個部分完成：
1，保持堆性質(zhì)函數(shù)heap_ify;
2,構(gòu)建堆函數(shù)build_heap;
3,堆排序函數(shù) heap_sort;
另外，在優(yōu)先級隊列中有extract-max 過程和insert過程，在作業(yè)隊列中常用，比如消息隊列。這部分在優(yōu)先級排序中說明。
  閱讀全文      摘要: 證書的申請過程（usbkey）  閱讀全文      摘要: MFC下CSocket編程詳解轉(zhuǎn)自：http://blog.csdn.net/yejiansnake/archive/2008/03/13/2175778.aspx MFC下CSocket編程詳解:  1. 常用的函數(shù)和注意事項(詳細(xì)的函數(shù)接口說明請查看MSDN):     CSocket::Create 初始化(一般寫服務(wù)器程序都不要用為好,用下面的...  閱讀全文

                        SetWindowsHookEx函數(shù)詳解

         轉(zhuǎn)正自：http://blog.csdn.net/hejinjiang/archive/2008/03/19/2197066.aspx






SetWindowsHookEx-HOOK 鉤子詳細(xì)介紹
基本概念
鉤子(Hook)，是Windows消息處理機(jī)制的一個平臺,應(yīng)用程序可以在上面設(shè)置子程以監(jiān)視指定窗口的某種消息，而且所監(jiān)視的窗口可以是其他進(jìn)程所創(chuàng)建的。當(dāng)消息到達(dá)后，在目標(biāo)窗口處理函數(shù)之前處理它。鉤子機(jī)制允許應(yīng)用程序截獲處理window消息或特定事件。
鉤子實際上是一個處理消息的程序段，通過系統(tǒng)調(diào)用，把它掛入系統(tǒng)。每當(dāng)特定的消息發(fā)出，在沒有到達(dá)目的窗口前，鉤子程序就先捕獲該消息，亦即鉤子函數(shù)先得到控制權(quán)。這時鉤子函數(shù)即可以加工處理（改變）該消息，也可以不作處理而繼續(xù)傳遞該消息，還可以強(qiáng)制結(jié)束消息的傳遞。
--------------------------------------------------------------------------------

運行機(jī)制

1、鉤子鏈表和鉤子子程：

每一個Hook都有一個與之相關(guān)聯(lián)的指針列表，稱之為鉤子鏈表，由系統(tǒng)來維護(hù)。這個列表的指針指向指定的，應(yīng)用程 序定義的，被Hook子程調(diào)用的回調(diào)函數(shù)，也就是該鉤子的各個處理子程。當(dāng)與指定的Hook類型關(guān)聯(lián)的消息發(fā)生時，系統(tǒng)就把這個消息傳遞到Hook子程。 一些Hook子程可以只監(jiān)視消息，或者修改消息，或者停止消息的前進(jìn)，避免這些消息傳遞到下一個Hook子程或者目的窗口。最近安裝的鉤子放在鏈的開始， 而最早安裝的鉤子放在最后，也就是后加入的先獲得控制權(quán)。

Windows 并不要求鉤子子程的卸載順序一定得和安裝順序相反。每當(dāng)有一個鉤子被卸載，Windows 便釋放其占用的內(nèi)存，并更新整個Hook鏈表。如果程序安裝了鉤子，但是在尚未卸載鉤子之前就結(jié)束了，那么系統(tǒng)會自動為它做卸載鉤子的操作。

鉤子子程是一個應(yīng)用程序定義的回調(diào)函數(shù)(CALLBACK Function),不能定義成某個類的成員函數(shù)，只能定義為普通的C函數(shù)。用以監(jiān)視系統(tǒng)或某一特定類型的事件，這些事件可以是與某一特定線程關(guān)聯(lián)的，也可以是系統(tǒng)中所有線程的事件。

鉤子子程必須按照以下的語法：

LRESULT CALLBACK HookProc
(
int nCode,
      WPARAM wParam,
      LPARAM lParam
);

HookProc是應(yīng)用程序定義的名字。

nCode參數(shù)是Hook代碼，Hook子程使用這個參數(shù)來確定任務(wù)。這個參數(shù)的值依賴于Hook類型，每一種Hook都有自己的Hook代碼特征字符集。

wParam和lParam參數(shù)的值依賴于Hook代碼，但是它們的典型值是包含了關(guān)于發(fā)送或者接收消息的信息。

2、鉤子的安裝與釋放：

使用API函數(shù)SetWindowsHookEx()把一個應(yīng)用程序定義的鉤子子程安裝到鉤子鏈表中。 SetWindowsHookEx函數(shù)總是在Hook鏈的開頭安裝Hook子程。當(dāng)指定類型的Hook監(jiān)視的事件發(fā)生時，系統(tǒng)就調(diào)用與這個Hook關(guān)聯(lián)的 Hook鏈的開頭的Hook子程。每一個Hook鏈中的Hook子程都決定是否把這個事件傳遞到下一個Hook子程。Hook子程傳遞事件到下一個 Hook子程需要調(diào)用CallNextHookEx函數(shù)。

HHOOK SetWindowsHookEx(
int idHook,      // 鉤子的類型，即它處理的消息類型
HOOKPROC lpfn,   // 鉤子子程的地址指針。如果dwThreadId參數(shù)為0
      // 或是一個由別的進(jìn)程創(chuàng)建的線程的標(biāo)識，
      // lpfn必須指向DLL中的鉤子子程。
      // 除此以外，lpfn可以指向當(dāng)前進(jìn)程的一段鉤子子程代碼。
      // 鉤子函數(shù)的入口地址，當(dāng)鉤子鉤到任何消息后便調(diào)用這個函數(shù)。
HINSTANCE hMod, // 應(yīng)用程序?qū)嵗木浔?。?biāo)識包含lpfn所指的子程的
DLL。
      // 如果dwThreadId 標(biāo)識當(dāng)前進(jìn)程創(chuàng)建的一個線程，
      // 而且子程代碼位于當(dāng)前進(jìn)程，hMod必須為NULL。
      // 可以很簡單的設(shè)定其為本應(yīng)用程序的實例句柄。
DWORD dwThreadId // 與安裝的鉤子子程相關(guān)聯(lián)的線程的標(biāo)識符。
      // 如果為0，鉤子子程與所有的線程關(guān)聯(lián)，即為全局鉤子。
            );

　　函數(shù)成功則返回鉤子子程的句柄，失敗返回NULL。

　　以上所說的鉤子子程與線程相關(guān)聯(lián)是指在一鉤子鏈表中發(fā)給該線程的消息同時發(fā)送給鉤子子程，且被鉤子子程先處理。

在鉤子子程中調(diào)用得到控制權(quán)的鉤子函數(shù)在完成對消息的處理后，如果想要該消息繼續(xù)傳遞，那么它必須調(diào)用另外一個 SDK中的API函數(shù)CallNextHookEx來傳遞它，以執(zhí)行鉤子鏈表所指的下一個鉤子子程。這個函數(shù)成功時返回鉤子鏈中下一個鉤子過程的返回值， 返回值的類型依賴于鉤子的類型。這個函數(shù)的原型如下：

LRESULT CallNextHookEx
   (
    HHOOK hhk;
    int nCode;
    WPARAM wParam;
    LPARAM lParam;
    );

hhk為當(dāng)前鉤子的句柄，由SetWindowsHookEx()函數(shù)返回。

NCode為傳給鉤子過程的事件代碼。

wParam和lParam 分別是傳給鉤子子程的wParam值，其具體含義與鉤子類型有關(guān)。

鉤子函數(shù)也可以通過直接返回TRUE來丟棄該消息，并阻止該消息的傳遞。否則的話，其他安裝了鉤子的應(yīng)用程序?qū)⒉粫邮盏姐^子的通知而且還有可能產(chǎn)生不正確的結(jié)果。

鉤子在使用完之后需要用UnHookWindowsHookEx()卸載，否則會造成麻煩。釋放鉤子比較簡單，UnHookWindowsHookEx()只有一個參數(shù)。函數(shù)原型如下：

UnHookWindowsHookEx
(
HHOOK hhk;
);

函數(shù)成功返回TRUE，否則返回FALSE。

3、一些運行機(jī)制：

在Win16環(huán)境中，DLL的全局?jǐn)?shù)據(jù)對每個載入它的進(jìn)程來說都是相同的；而在Win32環(huán)境中，情況卻發(fā)生了變化，DLL函數(shù)中的代碼所創(chuàng)建的任何對象（包括變量）都?xì)w調(diào)用它的線程或進(jìn)程所有。當(dāng)進(jìn)程在載入DLL時，操作系統(tǒng)自動把DLL地址映射到該進(jìn)程的私有空間，也就是進(jìn)程的虛擬地址空間，而且也復(fù)制該DLL的全局?jǐn)?shù)據(jù)的一份拷貝到該進(jìn)程空間。也就是說每個進(jìn)程所擁有的相同的DLL的全局?jǐn)?shù)據(jù)，它們的名稱相同，但其值卻并不一定是相同的，而且是互不干涉的。

因此，在Win32環(huán)境下要想在多個進(jìn)程中共享數(shù)據(jù)，就必須進(jìn)行必要的設(shè)置。在訪問同一個Dll的各進(jìn)程 之間共享存儲器是通過存儲器映射文件技術(shù)實現(xiàn)的。也可以把這些需要共享的數(shù)據(jù)分離出來，放置在一個獨立的數(shù)據(jù)段里，并把該段的屬性設(shè)置為共享。必須給這些 變量賦初值，否則編譯器會把沒有賦初始值的變量放在一個叫未被初始化的數(shù)據(jù)段中。

#pragma data_seg預(yù)處理指令用于設(shè)置共享數(shù)據(jù)段。例如：

#pragma data_seg("SharedDataName")
HHOOK hHook=NULL;
#pragma data_seg()

在#pragma data_seg("SharedDataName")和#pragma data_seg()之間的所有變量將被訪問該Dll的所有進(jìn)程看到和共享。再加上一條指令#pragma comment(linker,"/section:.SharedDataName,rws"),那么這個數(shù)據(jù)節(jié)中的數(shù)據(jù)可以在所有DLL的實例之間共 享。所有對這些數(shù)據(jù)的操作都針對同一個實例的，而不是在每個進(jìn)程的地址空間中都有一份。

當(dāng)進(jìn)程隱式或顯式調(diào)用一個動態(tài)庫里的函數(shù)時，系統(tǒng)都要把這個動態(tài)庫映射到這個進(jìn)程的虛擬地址空間里(以下簡稱"地址空間")。這使得DLL成為進(jìn)程的一部分，以這個進(jìn)程的身份執(zhí)行，使用這個進(jìn)程的堆棧。

4、系統(tǒng)鉤子與線程鉤子：

SetWindowsHookEx()函數(shù)的最后一個參數(shù)決定了此鉤子是系統(tǒng)鉤子還是線程鉤子。

線程勾子用于監(jiān)視指定線程的事件消息。線程勾子一般在當(dāng)前線程或者當(dāng)前線程派生的線程內(nèi)。

系統(tǒng)勾子監(jiān)視系統(tǒng)中的所有線程的事件消息。因為系統(tǒng)勾子會影響系統(tǒng)中所有的應(yīng)用程序，所以勾子函數(shù)必須放在獨立的動態(tài)鏈接庫(DLL) 中。系統(tǒng)自動將包含"鉤子回調(diào)函數(shù)"的DLL映射到受鉤子函數(shù)影響的所有進(jìn)程的地址空間中，即將這個DLL注入了那些進(jìn)程。

幾點說明：

（1）如果對于同一事件（如鼠標(biāo)消息）既安裝了線程勾子又安裝了系統(tǒng)勾子，那么系統(tǒng)會自動先調(diào)用線程勾子，然后調(diào)用系統(tǒng)勾子。

（2）對同一事件消息可安裝多個勾子處理過程，這些勾子處理過程形成了勾子鏈。當(dāng)前勾子處理結(jié)束后應(yīng)把勾子信息傳遞給下一個勾子函數(shù)。

（3）勾子特別是系統(tǒng)勾子會消耗消息處理時間，降低系統(tǒng)性能。只有在必要的時候才安裝勾子，在使用完畢后要及時卸載。

--------------------------------------------------------------------------------

鉤子類型

每一種類型的Hook可以使應(yīng)用程序能夠監(jiān)視不同類型的系統(tǒng)消息處理機(jī)制。下面描述所有可以利用的Hook類型。

1、WH_CALLWNDPROC和WH_CALLWNDPROCRET Hooks

WH_CALLWNDPROC和WH_CALLWNDPROCRET Hooks使你可以監(jiān)視發(fā)送到窗口過程的消息。系統(tǒng)在消息發(fā)送到接收窗口過程之前調(diào)用WH_CALLWNDPROC Hook子程，并且在窗口過程處理完消息之后調(diào)用WH_CALLWNDPROCRET Hook子程。

WH_CALLWNDPROCRET Hook傳遞指針到CWPRETSTRUCT結(jié)構(gòu)，再傳遞到Hook子程。

CWPRETSTRUCT結(jié)構(gòu)包含了來自處理消息的窗口過程的返回值，同樣也包括了與這個消息關(guān)聯(lián)的消息參數(shù)。

2、WH_CBT Hook

在以下事件之前，系統(tǒng)都會調(diào)用WH_CBT Hook子程，這些事件包括：

1. 激活，建立，銷毀，最小化，最大化，移動，改變尺寸等窗口事件；

2. 完成系統(tǒng)指令；

3. 來自系統(tǒng)消息隊列中的移動鼠標(biāo)，鍵盤事件；

4. 設(shè)置輸入焦點事件；

5. 同步系統(tǒng)消息隊列事件。

Hook子程的返回值確定系統(tǒng)是否允許或者防止這些操作中的一個。

3、WH_DEBUG Hook

在系統(tǒng)調(diào)用系統(tǒng)中與其他Hook關(guān)聯(lián)的Hook子程之前，系統(tǒng)會調(diào)用WH_DEBUG Hook子程。你可以使用這個Hook來決定是否允許系統(tǒng)調(diào)用與其他Hook關(guān)聯(lián)的Hook子程。

4、WH_FOREGROUNDIDLE Hook

當(dāng)應(yīng)用程序的前臺線程處于空閑狀態(tài)時，可以使用WH_FOREGROUNDIDLE Hook執(zhí)行低優(yōu)先級的任務(wù)。當(dāng)應(yīng)用程序的前臺線程大概要變成空閑狀態(tài)時，系統(tǒng)就會調(diào)用WH_FOREGROUNDIDLE Hook子程。

5、WH_GETMESSAGE Hook

應(yīng)用程序使用WH_GETMESSAGE Hook來監(jiān)視從GetMessage or PeekMessage函數(shù)返回的消息。你可以使用WH_GETMESSAGE Hook去監(jiān)視鼠標(biāo)和鍵盤輸入，以及其他發(fā)送到消息隊列中的消息。

6、WH_JOURNALPLAYBACK Hook

WH_JOURNALPLAYBACK Hook使應(yīng)用程序可以插入消息到系統(tǒng)消息隊列?？梢允褂眠@個Hook回放通過使用WH_JOURNALRECORD Hook記錄下來的連續(xù)的鼠標(biāo)和鍵盤事件。只要WH_JOURNALPLAYBACK Hook已經(jīng)安裝，正常的鼠標(biāo)和鍵盤事件就是無效的。

WH_JOURNALPLAYBACK Hook是全局Hook，它不能象線程特定Hook一樣使用。

WH_JOURNALPLAYBACK Hook返回超時值，這個值告訴系統(tǒng)在處理來自回放Hook當(dāng)前消息之前需要等待多長時間（毫秒）。這就使Hook可以控制實時事件的回放。

WH_JOURNALPLAYBACK是system-wide local hooks，它們不會被注射到任何行程位址空間。

7、WH_JOURNALRECORD Hook

WH_JOURNALRECORD Hook用來監(jiān)視和記錄輸入事件。典型的，可以使用這個Hook記錄連續(xù)的鼠標(biāo)和鍵盤事件，然后通過使用WH_JOURNALPLAYBACK Hook來回放。

WH_JOURNALRECORD Hook是全局Hook，它不能象線程特定Hook一樣使用。

WH_JOURNALRECORD是system-wide local hooks，它們不會被注射到任何行程位址空間。

8、WH_KEYBOARD Hook

在應(yīng)用程序中，WH_KEYBOARD Hook用來監(jiān)視WM_KEYDOWN and WM_KEYUP消息，這些消息通過GetMessage or PeekMessage function返回?？梢允褂眠@個Hook來監(jiān)視輸入到消息隊列中的鍵盤消息。

9、WH_KEYBOARD_LL Hook

WH_KEYBOARD_LL Hook監(jiān)視輸入到線程消息隊列中的鍵盤消息。

10、WH_MOUSE Hook

WH_MOUSE Hook監(jiān)視從GetMessage 或者 PeekMessage 函數(shù)返回的鼠標(biāo)消息。使用這個Hook監(jiān)視輸入到消息隊列中的鼠標(biāo)消息。

11、WH_MOUSE_LL Hook

WH_MOUSE_LL Hook監(jiān)視輸入到線程消息隊列中的鼠標(biāo)消息。

12、WH_MSGFILTER 和 WH_SYSMSGFILTER Hooks

WH_MSGFILTER 和 WH_SYSMSGFILTER Hooks使我們可以監(jiān)視菜單，滾動條，消息框，對話框消息并且發(fā)現(xiàn)用戶使用ALT+TAB or ALT+ESC 組合鍵切換窗口。WH_MSGFILTER Hook只能監(jiān)視傳遞到菜單，滾動條，消息框的消息，以及傳遞到通過安裝了Hook子程的應(yīng)用程序建立的對話框的消息。WH_SYSMSGFILTER Hook監(jiān)視所有應(yīng)用程序消息。

WH_MSGFILTER 和 WH_SYSMSGFILTER Hooks使我們可以在模式循環(huán)期間過濾消息，這等價于在主消息循環(huán)中過濾消息。

通過調(diào)用CallMsgFilter function可以直接的調(diào)用WH_MSGFILTER Hook。通過使用這個函數(shù)，應(yīng)用程序能夠在模式循環(huán)期間使用相同的代碼去過濾消息，如同在主消息循環(huán)里一樣。

13、WH_SHELL Hook

外殼應(yīng)用程序可以使用WH_SHELL Hook去接收重要的通知。當(dāng)外殼應(yīng)用程序是激活的并且當(dāng)頂層窗口建立或者銷毀時，系統(tǒng)調(diào)用WH_SHELL Hook子程。

WH_SHELL 共有５鐘情況：

1. 只要有個top-level、unowned 窗口被產(chǎn)生、起作用、或是被摧毀；

2. 當(dāng)Taskbar需要重畫某個按鈕；

3. 當(dāng)系統(tǒng)需要顯示關(guān)于Taskbar的一個程序的最小化形式；

4. 當(dāng)目前的鍵盤布局狀態(tài)改變；

5. 當(dāng)使用者按Ctrl+Esc去執(zhí)行Task Manager（或相同級別的程序）。

按照慣例，外殼應(yīng)用程序都不接收WH_SHELL消息。所以，在應(yīng)用程序能夠接收WH_SHELL消息之前，應(yīng)用程序必須調(diào)用SystemParametersInfo function注冊它自己。

     摘要: 類成員函數(shù)指針  閱讀全文