摘要: 哈希結構

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

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

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

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

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

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

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

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

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

                        SetWindowsHookEx函數詳解

         轉正自：http://blog.csdn.net/hejinjiang/archive/2008/03/19/2197066.aspx






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

運行機制

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

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

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

鉤子子程是一個應用程序定義的回調函數(CALLBACK Function),不能定義成某個類的成員函數，只能定義為普通的C函數。用以監視系統或某一特定類型的事件，這些事件可以是與某一特定線程關聯的，也可以是系統中所有線程的事件。

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

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

HookProc是應用程序定義的名字。

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

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

2、鉤子的安裝與釋放：

使用API函數SetWindowsHookEx()把一個應用程序定義的鉤子子程安裝到鉤子鏈表中。 SetWindowsHookEx函數總是在Hook鏈的開頭安裝Hook子程。當指定類型的Hook監視的事件發生時，系統就調用與這個Hook關聯的 Hook鏈的開頭的Hook子程。每一個Hook鏈中的Hook子程都決定是否把這個事件傳遞到下一個Hook子程。Hook子程傳遞事件到下一個 Hook子程需要調用CallNextHookEx函數。

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

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

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

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

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

hhk為當前鉤子的句柄，由SetWindowsHookEx()函數返回。

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

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

鉤子函數也可以通過直接返回TRUE來丟棄該消息，并阻止該消息的傳遞。否則的話，其他安裝了鉤子的應用程序將不會接收到鉤子的通知而且還有可能產生不正確的結果。

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

UnHookWindowsHookEx
(
HHOOK hhk;
);

函數成功返回TRUE，否則返回FALSE。

3、一些運行機制：

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

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

#pragma data_seg預處理指令用于設置共享數據段。例如：

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

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

當進程隱式或顯式調用一個動態庫里的函數時，系統都要把這個動態庫映射到這個進程的虛擬地址空間里(以下簡稱"地址空間")。這使得DLL成為進程的一部分，以這個進程的身份執行，使用這個進程的堆棧。

4、系統鉤子與線程鉤子：

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

線程勾子用于監視指定線程的事件消息。線程勾子一般在當前線程或者當前線程派生的線程內。

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

幾點說明：

（1）如果對于同一事件（如鼠標消息）既安裝了線程勾子又安裝了系統勾子，那么系統會自動先調用線程勾子，然后調用系統勾子。

（2）對同一事件消息可安裝多個勾子處理過程，這些勾子處理過程形成了勾子鏈。當前勾子處理結束后應把勾子信息傳遞給下一個勾子函數。

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

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

鉤子類型

每一種類型的Hook可以使應用程序能夠監視不同類型的系統消息處理機制。下面描述所有可以利用的Hook類型。

1、WH_CALLWNDPROC和WH_CALLWNDPROCRET Hooks

WH_CALLWNDPROC和WH_CALLWNDPROCRET Hooks使你可以監視發送到窗口過程的消息。系統在消息發送到接收窗口過程之前調用WH_CALLWNDPROC Hook子程，并且在窗口過程處理完消息之后調用WH_CALLWNDPROCRET Hook子程。

WH_CALLWNDPROCRET Hook傳遞指針到CWPRETSTRUCT結構，再傳遞到Hook子程。

CWPRETSTRUCT結構包含了來自處理消息的窗口過程的返回值，同樣也包括了與這個消息關聯的消息參數。

2、WH_CBT Hook

在以下事件之前，系統都會調用WH_CBT Hook子程，這些事件包括：

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

2. 完成系統指令；

3. 來自系統消息隊列中的移動鼠標，鍵盤事件；

4. 設置輸入焦點事件；

5. 同步系統消息隊列事件。

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

3、WH_DEBUG Hook

在系統調用系統中與其他Hook關聯的Hook子程之前，系統會調用WH_DEBUG Hook子程。你可以使用這個Hook來決定是否允許系統調用與其他Hook關聯的Hook子程。

4、WH_FOREGROUNDIDLE Hook

當應用程序的前臺線程處于空閑狀態時，可以使用WH_FOREGROUNDIDLE Hook執行低優先級的任務。當應用程序的前臺線程大概要變成空閑狀態時，系統就會調用WH_FOREGROUNDIDLE Hook子程。

5、WH_GETMESSAGE Hook

應用程序使用WH_GETMESSAGE Hook來監視從GetMessage or PeekMessage函數返回的消息。你可以使用WH_GETMESSAGE Hook去監視鼠標和鍵盤輸入，以及其他發送到消息隊列中的消息。

6、WH_JOURNALPLAYBACK Hook

WH_JOURNALPLAYBACK Hook使應用程序可以插入消息到系統消息隊列。可以使用這個Hook回放通過使用WH_JOURNALRECORD Hook記錄下來的連續的鼠標和鍵盤事件。只要WH_JOURNALPLAYBACK Hook已經安裝，正常的鼠標和鍵盤事件就是無效的。

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

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

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

7、WH_JOURNALRECORD Hook

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

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

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

8、WH_KEYBOARD Hook

在應用程序中，WH_KEYBOARD Hook用來監視WM_KEYDOWN and WM_KEYUP消息，這些消息通過GetMessage or PeekMessage function返回。可以使用這個Hook來監視輸入到消息隊列中的鍵盤消息。

9、WH_KEYBOARD_LL Hook

WH_KEYBOARD_LL Hook監視輸入到線程消息隊列中的鍵盤消息。

10、WH_MOUSE Hook

WH_MOUSE Hook監視從GetMessage 或者 PeekMessage 函數返回的鼠標消息。使用這個Hook監視輸入到消息隊列中的鼠標消息。

11、WH_MOUSE_LL Hook

WH_MOUSE_LL Hook監視輸入到線程消息隊列中的鼠標消息。

12、WH_MSGFILTER 和 WH_SYSMSGFILTER Hooks

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

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

通過調用CallMsgFilter function可以直接的調用WH_MSGFILTER Hook。通過使用這個函數，應用程序能夠在模式循環期間使用相同的代碼去過濾消息，如同在主消息循環里一樣。

13、WH_SHELL Hook

外殼應用程序可以使用WH_SHELL Hook去接收重要的通知。當外殼應用程序是激活的并且當頂層窗口建立或者銷毀時，系統調用WH_SHELL Hook子程。

WH_SHELL 共有５鐘情況：

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

2. 當Taskbar需要重畫某個按鈕；

3. 當系統需要顯示關于Taskbar的一個程序的最小化形式；

4. 當目前的鍵盤布局狀態改變；

5. 當使用者按Ctrl+Esc去執行Task Manager（或相同級別的程序）。

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

     摘要: 類成員函數指針  閱讀全文