原題為某游戲公司試題，大意如下：  對于一個單向鏈表，試寫出找到它的倒序第m個元素(m >= 1)的函數，注意變量命名、注釋、時間復雜度、空間復雜度。注：要求寫出可編譯并可以運行通過的程序代碼。

  這道題的常規做法或者說首先想到直覺的方法M1是先求得鏈表的長度，即元素總個數n，然后問題轉化為求順序第n-m+1個元素。下面給出第2種方法M2：先求得順序第m個元素，用一指針P指向這個元素，用另一指針PR指向鏈表的頭部，現在好了，P和PR同時向右移動，直到P為空，則PR就是要求的倒序第m個元素，如果因m超越界限，則PR為空，表示沒找到，這樣一來，只需一次循環就夠了。C++代碼描述如下

 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**//**//**////< 數據
 5     Node* next;  ///< 指向下一結點的指針
 6 } ;
 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++n == m)
16        {
17            pR = head;
18            continue;
19        }
20        if (pR)
21        {
22            pR = pR->next;
23        }
24    }
25    return pR;
26}

  現在分析這2種方法的時間復雜度，假設鏈表元素個數為N，所求倒序為第M元素，N>=M，則M1方法為0(N)+0(N-M)=0(2N-M)，M2方法為O(M)+O(N-M)=0(N)，因此M2快于M1。

   原題為某游戲公司的試題，大意如下：寫一個千位分隔符算法，函數原型是 char * format_thousands_separator(unsigned long val); 要求實現效果是 1.使用者不需要釋放返回的字符串指針 2.支持最多調用16次而不返回相同指針地址。可以用以下方法測試       
    printf("num1(%s), num2(%s), num3(%s)\n", format_thousands_separator(0),format_thousands_separator(123456),format_thousands_separator(23456789)); 
   注：要求寫出可編譯并可以運行通過的程序代碼。

   經過修改后，我目前最簡潔的C代碼描述如下      摘要:    一般地，泛型容器的設計實現大多只是存儲了類型的單個對象，而沒有存儲類型的多個對象，如果有這樣特定的需求，容器內的元素要求都是某個類型的多個對象，那么這時就可以考慮用模板類的數組特化來實現了，作為例程，下面C++代碼描述了主模板實現 Code highlighting produced by Actipro CodeHighlighter (freewa...  閱讀全文    原為某軟件公司試題，大意如下：對于給定的有符號32位整數，寫一個函數，當該數為正數時返回1，為負數時返回-1，為零時返回零，要求不能使用任何的條件判斷分支跳轉語句。在這里，稍微擴展了一下，給出了對應無符號32位整數的情形。解決思路是符號位和值分開處理，對于有符號32位整數，符號位右移31位即得a，若為非負數則a=0x00000000，否則a=0xFFFFFFFF；然后將值部分各位的值（0或1）不斷縮小合并到一位中去得到b，這是針對0和正數的情況處理，再將a和b位或即可。C++代碼描述如下    若哪位有更好的解法，還望多多分享    WTL是窗口模板庫(Windows Library Template)的簡稱，是一套輕量級C++ GUI庫，因為它使用了C++模板封裝了窗口界面操作API和消息映射處理，它擴展了ATL中的UI窗口部分，并支持如下更多的功能特性：
    (1)   對話框和通用控件：包括對話框數據交換(DDX)，子類化，控件消息通知與反射等
    (2)   工具欄和狀態欄：包括工具條UI狀態更新，多窗格狀態條及UI狀態更新等
    (3)   分隔窗口：包括窗格容器，嵌套分隔，特殊繪制等
    (4)   屬性頁和向導：包括屬性表，普通屬性頁，向導屬性頁等
    (5)   GDI類等：包括GDI封裝類，通用對話框等
    (6)   使用ActiveX控件：包括使用控件類，調用控件的方法，控件事件映射處理等
    (7)   高級對話框UI類：包括自繪和外觀定制類，新控件類，控件UI狀態更新，對話框數據驗證DDV等
    (8)   支持拖放操作：包括拖放接口實現類，最近使用文件列表等
   綜上所述，使用WTL幾乎可以實現MFC所能實現的功能與界面，而且生成的執行文件體積更小，不需要動態鏈接庫就可直接快速地執行。

   根據WIN32窗口原理，當事件發生的時候，一般由父窗口接收其子窗口或控件的通知或命令消息，在這里父窗口是消息接收者，子窗口或控件是消息發送者，那么誰是消息處理者呢？實際上由誰來處理消息只是代碼上的邏輯，既可以在父窗口的窗口過程回調內處理，也可以在子窗口或控件的窗口過程回調內處理，在哪處理更方便合理就在哪處理，如果是在子窗口或控件窗口過程回調內處理，那么就需要作額外的處理了，也就是在父窗口中將消息反射給發送者，進而再由發送者處理。下面以父窗口為打開文件對話框，雙擊它的列表視圖控件為例，給出運用上面(1)中的控件消息通知與反射來處理NM_DBLCLK消息的兩種實現方式。

   繼承方式：由控件處理消息
   從CWindowImpl模板基類派生一個子窗口或控件子類即listview子類，添加消息映射項和消息處理函數，消息映射項用REFLECTED_NOTIFY_XXX或REFLECTED_COMMAND_XXX系列反射宏實現，具體使用哪個宏，決定于是否通知或命令消息，及消息對應的ID和通知碼。    
   在父窗口類消息映射鏈中最后添加反射通知宏REFLECT_NOTIFICATIONS()項。                                           
　成員方式：由父窗口處理消息 
   直接使用ATL中的包含窗口模板類CContainedWindowT，參數為子控件的類名即listviewctrl，實例化為父窗口類的一個成員變量，在父窗口類消息映射鏈中添加ALT_MSG_MAP宏來實現消息分派，其參數為分派ID，這個ID為成員變量初始化時指定的常量；添加反射通知宏REFLECT_NOTIFICATIONS()，注意ALT_MSG_MAP宏必須在反射通知宏REFLECT_NOTIFICATIONS之后。  
   在父窗口內需要初始化m_list_File以指定分派ID號。                                                               

   MFC將windows消息系統進行了高度的抽象和封裝，其根本原理是運用C++的高級特性并結合一定的設計模式（如工廠模式，模板方法等）來實現的。一般的windows消息（WM_XXX），則一定是由派生類流向基類，沒有旁流的可能。如果是命令消息（WM_COMMAND），那就有比較奇特的路線了。下面就針對多文檔/單文檔（Document-View）、對話框兩種應用程序比較討論WM_COMMAND消息的傳遞處理過程。討論前首先得明確命令消息的來源，命令消息一般是用戶選擇某個菜單項，或一個加速鍵被翻譯，或一個子控件發送一個通知消息給它的父窗口時產生的。對一個菜單而言，消息接收者是Frame窗口或擁有它的對話框；對一個工具欄而言，消息接收者是它的父窗口。兩種應用程序命令消息處理流程如下圖所示。                   

   從上圖可知，文檔視圖型的處理路線是先向下再向上，而對話框型的路線是一直向上，消息接收者只有一個，而處理者次序有多個，每個處理者內部首先都是調用根基類CCmdTarget的OnCmdMsg虛函數，在這個函數內逐級向基類遍歷消息映射表，根據命令ID和通知碼找到對應的消息映射結構體AFX_MSGMAP_ENTRY，如果找到再處理這個命令消息，否則返回FALSE，退回到this對象所在的OnCmdMsg函數進行下一步處理。如果到最后一層都沒有找到對應命令的消息映射，則返回到系統的默認處理DefWindowProc。再綜合考慮下，如果一個對話框接收到了一個命令消息例如是點擊它的子控件工具欄某個按鈕發出的，而這個對話框類沒有添加相應的ON_COMMAND映射，就會進入到它的父窗口類OnCmdMsg函數進行處理，如果這個父窗口正好是Frame窗口，那么命令消息的處理流程就由上圖右邊轉到左邊了。而最終命令消息能否得處理，就看上圖5種對象（Frame、View、Document、Dialog、App、Thread）是否添加了對應的ON_COMMAND映射。
   
   到此為止，我們已經明確了WM_COMMAND消息的處理流程，但是發現最終處理卻是由收到消息的窗口傳遞的，不是消息通知者自己處理的，有的時候為了提高代碼的封裝性，可能需要自己處理這些命令比較方便，比如有一個工具欄CPlayToolBar子類從CToolBar繼承，有播放、暫停、停止3個按鈕，它的父窗口是CPlayDialog對話框。按照常規，這3個按鈕命令事件的處理一般是在CPlayDialog類中3個ON_COMMAND映射宏和處理函數的，但如果在CPlayToolBar類中添加3個ON_COMMAND映射宏和處理函數，是得不到處理的，其原因在于對話框型的路線是一直向上，再者MFC中沒有對應的命令反射ON_COMMAND_REFLECT這個宏。為了能使CPlayToolBar類自己處理這3個按鈕命令事件，就需要從CPlayDialog類中轉移路線，使之流向其子窗口工具欄，這樣CPlayToolbar 類就得到了自己處理的機會。具體操作是重載CPlayToolBar和CPlayDialog的OnCommand虛函數,  CPlayDialog代碼如下所示：    CPlayToolBar類代碼如下所示     現在，3個按鈕命令事件能在CPlayToolBar類中獨立處理了，這樣一來就提高了代碼的封裝性，簡化了父窗口CPlayDialog類的處理。    最近在工作中,寫一計算桿塔絕緣子中心點的GPS坐標程序時，定義了一結構，里面用到了string類型來存儲桿塔所屬線路號、桿塔號，桿塔模型名稱。代碼如下:

 1/*
 2  @brief 桿塔信息結構
 3*/
 4typedef struct   _TOWER_INFO
 5{
 6       string    strLineNo;           ///< 線路號 
 7       string    strTowerNo;         ///< 桿塔號
 8       string    strTowerType;     ///< 桿塔類型
 9       double  dDangDistance;    ///< 檔距
10      double  dHCHeight;           ///< 呼稱高
11      double  dLongitude;          ///< 經度
12      double  dLatitude;              ///< 緯度
13      double  dAltitude;              ///< 海拔高度
14      double  dLineCorners;      ///< 線路轉角 
15      long      lCornerDirection;  ///< 左轉還是右轉: 0不轉, 1左轉, 2右轉
16      vector<INSULATOR_INFO::CENTER_POINT_INFO>  vecInsulatorCenterPointInfo; ///< 桿塔所有絕緣子中心點信息
17       _TOWER_INFO() { memset(this, 0, sizeof(_TOWER_INFO)); }       //該行代碼可能會引起string內存泄露
18
19}TOWER_INFO,*PTOWER_INFO;

   在后面對該結構的string型變量有賦值操作, 代碼如下

1   ......
2       TOWER_INFO cur_tower_center_info;
3   cur_tower_center_info.strLineNo = sheetLine->Cell(i, 2)->GetText(); //調度碼
4   cur_tower_center_info.strTowerNo = sheetLine->Cell(i, 7)->GetText(); //桿塔號
5   cur_tower_center_info.strTowerType = sheetLine->Cell(i, 8)->GetText(); //桿塔類型
6      ......

   運行程序,待程序結束后,發現有內存泄露,提示信息如下

 1Detected memory leaks!
 2Dumping objects ->
 3{235250} normal block at 0x01774A60, 16 bytes long.
 4 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
 5{235237} normal block at 0x01774CB0, 16 bytes long.
 6 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
 7{235234} normal block at 0x01774A10, 16 bytes long.
 8 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
 9{235184} normal block at 0x01774200, 16 bytes long.
10 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
11{235171} normal block at 0x01774450, 16 bytes long.
12 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
13{235168} normal block at 0x017741B0, 16 bytes long.
14 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
15{235118} normal block at 0x017739A0, 16 bytes long.
16 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
17{235105} normal block at 0x01773BF0, 16 bytes long.
18 Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD 
19..

   經過一番源代碼跟蹤調試后,發現原因在于TOWER_INFO結構體的構造函數內調用了memset(this, 0, sizeof(_TOWER_INFO);使得string內部指針_Bx._Ptrr值為0,_Myres為0,在這種情況下當string對象被賦值為小字符串(字節數包括結束符小于等于16的字符串)時,因新申請的內存在后來得不到釋放,所以這塊內存被泄露了,根據string類內存管理算法(ms vc版本)得知這塊內存大小總是16個字節.但當被賦值為大字符串(字節數包括結束符大于16的字符串)時,反而沒有內存泄露,這是因為新申請的內存在析構或下次賦值時總能被釋放.
  從該泄露問題的分析解決過程中，總結得到規律：不要輕易零初始化string, vector等stl標準容器及具有動態內存管理的類。

   上次介紹了一種字符串轉化為16進制顯示的算法，并封裝成了API，這個API可用于串口收到數據后按16進制顯示字符串，這次介紹串口按16進制發送字符串的算法，使用基于字符類型參數的模板函數實現。算法原理是遍歷字符串，將在區間'0'--'9','A'--'F','a'--'f'的字符轉化成對應的16進制整數(范圍為閉區間0-15)，如遇到連續2個可以轉換的字符，則將它們存儲在一個無符號字節內，如遇到不能轉化的字符，則略過繼續。代碼如下:

 1/**//**
 2    @brief 將字符轉化為對應的10進制數整數 ASCII版本 
 3    * 若字符不能轉化則返回-1
 4*/
 5template<typename charT>
 6inline char ConvertHexChar(charT ch)
 7{
 8    if(ch>=(charT)'0'&&ch<=(charT)'9')
 9        return ch-(charT)'0';
10    else if(ch>=(charT)'A'&&ch<=(charT)'F')
11        return ch-(charT)'A'+10;
12    else if(ch>=(charT)'a'&&ch<=(charT)'f')
13        return ch-(charT)'a'+10;
14    else 
15        return -1;
16}
17
18typedef std::vector<unsigned char> CByteArrayEx;
19
20/**//**
21    @brief 將字符串轉化成對應的16進制數形式存儲
22    @param template charT 源字符類型
23    @param src 源數據串
24    @param size 要轉換的長度,字符數
25    @param ByteArray 存放結果的字節數組
26
27    * 如字符串80 12 34 46 AD FF,對應的就是0x80,0x12,0x34,0x46,0xAD,0xFF
28    該函數會自動過濾不能轉換的字符,可轉換字符范圍在0--9,a--f,A--F區間   
29*/
30template<typename charT>
31inline void StrToHex(const charT* src,size_t len,CByteArrayEx& ByteArray)
32{
33    char low = -1, high = -1;
34    for (size_t n = 0; n < len; )
35    {
36        high = ConvertHexChar(src[n++]); 
37        if (-1 == high)
38        {
39            continue;
40        }
41        if (n >= len)
42        {
43            ByteArray.push_back(high);
44            break;
45        }
46        low = ConvertHexChar(src[n++]);
47        if (-1 == low)
48        {
49            ByteArray.push_back(high);
50            continue;
51        }
52        ByteArray.push_back(high * 16 + low);  
53    }
54}
55
56/**//**
57    @brief 將字符串轉化成對應的16進制數形式存儲
58    @param template charT 源字符類型
59    @param src 源數據串
60    @param ByteArray 存放結果的字節數組  
61*/
62template<typename charT>
63inline void StrToHex(const charT* src,CByteArrayEx& ByteArray)
64{
65    StrToHex(src,select_variable<is_ansi_char<s_charT>::value>(strlen,wcslen)(src),ByteArray);
66}

 

   最近在項目中調試串口,,總結封裝了字符串轉化為16進制顯示的算法,串口數據發送一般為ASCII和16進制兩種,當收到數據時數據也有ASCII和16進制顯示兩種方式,下面給出一種轉化算法,該算法基于字符類型參數化的模板實現，字符串的轉化只是調用其內存版本，算法原理是對字符串內存進行操作轉化,以一個字節(unsigned char類型)為單位,分別取其高4位和低4位(范圍為0x0--0xF), 轉化為對應的目標字符('0'--'F')顯示,代碼如下    在應用中需要轉化時, 只需調用StrToHex函數,示例如下:      結果輸出如下:    在WINDOWS NT4.0 以上操作系統中，串口通訊有2種模式：同步方式和異步方式。由CreateFile中的dwFlagsAndAttributes參數決定，若指定FILE_FLAG_OVERLAPPED標志則為異步方式，否則為同步方式。當為同步模式時,調用ReadFile或WriteFile會阻塞調用線程直到讀完或寫完指定量的數據才返回，這樣就有可能出現無法退出程序的現象，解決方法是為讀寫操作設置超時，注意這種超時指的是ReadFile或WriteFile函數的返回時間，僅對同步模式有效。代碼如下    當為異步模式時，由于讀寫操作會立即返回，因此設置超時指的是設置等待操作完成的時間，而不是ReadFile或WriteFile函數返回的時間，代碼如下    這里的ReadComm和WriteComm的實現內部針對不同模式作了不同處理，異步模式時即調用了WaitForSingleObject等待函數來設置超時。同步模式時即調用不帶重疊結構的ReadFile或WriteFile函數來接收或發送指定量的數據。另外在這介紹下串口虛擬軟件vspd，這個軟件能模擬在同一臺計算機上進行兩個串口的通訊，有利于沒有實際設備情況下的串口調試。