【正文】 CKmpDialog* pDlg = (CKmpDialog*)lpParam。//更新過程中 禁用 相關(guān)按鈕 及 系統(tǒng)菜單關(guān)閉按鈕 ………… int* next = new int[pDlg()+1]。 int i = 1。 int j = 0。 next[1] = 0。 while(i pDlg()) { pDlg(2*i, CString::XCHAR(39。(39。))。 pDlg(2*i+2, CString::XCHAR(39。)39。))。 pDlg(2*i, CString::XCHAR(39。(39。))。 pDlg(2*i+2, CString::XCHAR(39。)39。))。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 //分隔符重置為空 pDlg(2*i, CString::XCHAR(39。 39。))。 pDlg(2*i+2, CString::XCHAR(39。 39。))。 pDlg(2*i, CString::XCHAR(39。 39。))。 pDlg(2*i+2, CString::XCHAR(39。 39。))。 if(0 == j || pDlgm_T[i1] == pDlgm_T[j1]) { ++i。 ++j。 next[i] = j。 CString temp = _T( )。 (_T(%d), j)。 pDlg(2*i1, (0))。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 } else { for(int k = 0。 k jnext[j]。 ++k) pDlg(0, _T( ))。 j = next[j]。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 } } delete []next。 next = NULL。//重新啟用相關(guān)按鈕 及 系統(tǒng)菜單關(guān)閉按鈕 ………… return 0。} //KMP Nextval 處理UINT kmpDlgNextval(LPVOID lpParam){ CKmpDialog* pDlg = (CKmpDialog*)lpParam。//更新過程中 禁用 相關(guān)按鈕 及 系統(tǒng)菜單關(guān)閉按鈕 ………… int* nextval = new int[pDlg()+1]。 int i = 1。 int j = 0。 nextval[1] = 0。 while(i pDlg()) { pDlg(2*i, CString::XCHAR(39。(39。))。 pDlg(2*i+2, CString::XCHAR(39。)39。))。 pDlg(2*i, CString::XCHAR(39。(39。))。 pDlg(2*i+2, CString::XCHAR(39。)39。))。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 //分隔符重置為空 pDlg(2*i, CString::XCHAR(39。 39。))。 pDlg(2*i+2, CString::XCHAR(39。 39。))。 pDlg(2*i, CString::XCHAR(39。 39。))。 pDlg(2*i+2, CString::XCHAR(39。 39。))。 if(0 == j || pDlgm_T[i1] == pDlgm_T[j1]) { ++i。 ++j。 if(pDlgm_T[i1] != pDlgm_T[j1]) nextval[i] = j。 else nextval[i] = nextval[j]。 CString temp = _T( )。 (_T(%d), nextval[i])。 pDlg(2*i1, (0))。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 } else { for(int k = 0。 k jnextval[j]。 ++k) pDlg(0, _T( ))。 j = nextval[j]。 Sleep(1000)。 pDlgSendMessage(WM_USER+1, NULL, NULL)。 } } delete []nextval。 nextval = NULL。//重新啟用相關(guān)按鈕 及 系統(tǒng)菜單關(guān)閉按鈕 ………… return 0。} 4. 其它//GetNext 求next值 用于模式匹配void GetNext(CKmpDialog* pDlg, int next[]){ next[1] = 0。 int i = 1。 int j = 0。 while(i pDlg()) { if(0 == j || pDlgm_T[i1] == pDlgm_T[j1]) { ++i。 ++j。 next[i] = j。 } else { j = next[j]。 } }}五、 重要存儲結(jié)構(gòu)1. 文本框控件變量CString 順序表、鏈表、主串、模式串輸入與顯示類型。int 順序表、鏈表位置類型。2. 內(nèi)部數(shù)據(jù)處理變量int [] next、nextval存儲類型。第4章 調(diào)試分析一、 問題與解決1. 程序假死使用Sleep函數(shù)使程序出現(xiàn)“動態(tài)”效果時，導(dǎo)致程序主線程被掛起，程序出現(xiàn)假死。通過運用多線程，創(chuàng)建新的線程實例，循環(huán)處理數(shù)據(jù)與休眠，并發(fā)送消息給主線程使對話框得到更新，既保持了“動態(tài)”效果，又防止了程序“假死”。2. 意外終止在演示進(jìn)行過程中，如若單擊窗口“關(guān)閉”按鈕，導(dǎo)致程序意外終止。通過在線程處理函數(shù)開始時加入相關(guān)代碼，禁用“關(guān)閉”按鈕，防止意外終止的發(fā)生；同時在線程函數(shù)退出前，重新啟用“關(guān)閉”按鈕。3. 操作沖突在進(jìn)行一項演示時，如同時觸發(fā)其它演示事件，導(dǎo)致數(shù)據(jù)同時被不同操作修改，出現(xiàn)訪問錯誤。通過在各操作處理函數(shù)中加入相關(guān)代碼禁用其它事件按鈕，防止操作沖突；同時在處理函數(shù)退出前重新啟用相關(guān)事件按鈕。4. 文本對齊在模式匹配等操作中，由于各字符寬度不同，導(dǎo)致演示效果不佳。通過修改字體為宋體等中文字體，使各字符等寬，達(dá)到更好的演示效果。二、 性能分析1. 順序表部分創(chuàng)建、插入、刪除算法平均時間復(fù)雜度均為O(n)。合并操作利用“冒泡”排序，平均時間復(fù)雜度為O(n2)。2. 鏈表部分創(chuàng)建、查找、插入、刪除算法平均時間復(fù)雜度均為O(n)。合并操作平均時間復(fù)雜度為O(n2)。3. KMP部分模式匹配時間復(fù)雜度為0(n+m)，其中n、m分別為主串和模式串長度。4. 改進(jìn)通過將“冒泡”排序改進(jìn)為快速排序等可提高算法效率。第5章 測試結(jié)果一、 主窗口單擊三個不同按鈕，選擇三種不同演示。單擊窗口關(guān)閉按鍵（X）退出演示系統(tǒng)。二、 順序表演示通過“創(chuàng)建”、“插入”、“刪除”及“合并”按鈕進(jìn)行相關(guān)算法演示，一個算法演示期間，所有操作按鈕均被禁用。當(dāng)前順序非空而無演示時，“插入”與“刪除”按鍵啟用。演示過程中，“變量”區(qū)中各值動態(tài)變化，展示當(dāng)前操作元素及順序表形態(tài)變化等信息。三、 鏈表演示通過“創(chuàng)建”、“查找”、“插入”、“刪除”及“合并”按鈕進(jìn)行相關(guān)算法演示，一個算法演示期間，所有操作按鈕均被禁用。當(dāng)前鏈表非空而無演示時，“查找”、“插入”及“刪除”按鈕啟用。演示過程中，“變量”區(qū)各值動態(tài)變化，展示當(dāng)前操作元素及鏈表形態(tài)變化等信息。四、 KMP演示通過“輸入”、“求NEXT”、“匹配”及“求NEXTVAL”按鍵進(jìn)行相關(guān)算法演示。在模式串T非空時，“求NEXT”及“求NEXTVAL”按鈕啟用；在模式串T和主串S均非空時，“匹配”按鈕啟用。三個算法演示可同時進(jìn)行，但當(dāng)某個算法演示完成后又無新的模式串或主串輸入時，該算法演示按鈕禁用。 模式匹配成功或失敗時，均給出相應(yīng)提示信息。五、 錯誤輸入處理對于用戶的錯誤輸入數(shù)據(jù)，跳過算法演示并給出相應(yīng)的錯誤提示信息。如用戶錯誤的插入、刪除位置輸入，錯誤的插入元素輸入等。六、 設(shè)計總結(jié)通過本次課程設(shè)計，加深了對順序表、鏈表相關(guān)算法及串的模式匹配（KMP）算法理解，而在實際編碼、調(diào)試過程中也發(fā)現(xiàn)了一些自己在程序設(shè)計方面的不足。同時，此算法演示系統(tǒng)也是自己利用MFC編寫的第一個真正比較完美的程序。通過對本演示系統(tǒng)的編寫，對Windows程序設(shè)計、Windows消息處理、MFC編程、用戶交互等概念有了一定的了解。尤其是在對演示過程實行“動態(tài)化”的過程中，對多線程（MultiThreading）進(jìn)行了初步學(xué)習(xí)，并學(xué)會了利用MFC進(jìn)行簡單的多線程編程。另外，在設(shè)計對用戶輸入數(shù)據(jù)進(jìn)行處理的過程中，對Unicode、ANSI編碼等進(jìn)行了相關(guān)了解學(xué)習(xí)，并使程序能夠成功處理用戶的中文輸入等。而在對程序的編譯、鏈接過程中，對動態(tài)鏈接庫（DLL）的相關(guān)知識有了一定的了解。最后，通過本此課程設(shè)計，對Windows環(huán)境下的Visual Studio + Windows SDK桌面應(yīng)用編程有了初步的了解，并學(xué)會了簡單的Windows圖形用戶界面（GUI）編程。七、 參考文獻(xiàn)《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 嚴(yán)蔚敏 吳偉民 著 清華大學(xué)出版社《Beginning Visual C++ 2010》 Ivor Horton 著 Wiley Publishing, Inc.MSND 文檔及論壇資源八