【正文】 中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目： 數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)（1） 院 系： 信息科學(xué)與工程學(xué)院 班 級(jí)： 計(jì)算機(jī) 0904 姓 名： 張 學(xué) 程 學(xué) 號(hào)： 0909091322 指導(dǎo)老師： 陳 再 良 完成時(shí)間： 2011. 07 目錄第1章 需求分析 3一、 順序表部分 3二、 鏈表部分 3三、 KMP部分 3第2章 概要設(shè)計(jì) 5一、 數(shù)據(jù)結(jié)構(gòu) 5二、 程序主流程 6三、 模塊層次 6第3章 詳細(xì)設(shè)計(jì) 8一、 數(shù)據(jù)類型 8二、 相關(guān)函數(shù) 9三、 詳細(xì)流程 10四、 重要算法 10五、 重要存儲(chǔ)結(jié)構(gòu) 25第4章 調(diào)試分析 26一、 問題與解決 26二、 性能分析 26第5章 測(cè)試結(jié)果 27一、 主窗口 27二、 順序表演示 27三、 鏈表演示 28四、 KMP演示 29五、 錯(cuò)誤輸入處理 30六、 設(shè)計(jì)總結(jié) 31七、 參考文獻(xiàn) 32八、 附錄 32第1章 需求分析一、 順序表部分1. 創(chuàng)建 根據(jù)用戶輸入，創(chuàng)建順序表，表中各元素以空格分隔顯示。非空順序表為后續(xù)其它操作的前提。輸入數(shù)據(jù)為各合法字符（含中文）。2. 插入 根據(jù)用戶輸入，在指定位置插入指定元素，其中位置標(biāo)識(shí)從0開始。若用戶輸入位置超出順序表位置范圍，給出越界錯(cuò)誤提示；若用戶未輸入插入元素，亦給出相應(yīng)提示。插入元素為各合法字符，插入位置為0100間整數(shù)。3. 刪除 根據(jù)用戶輸入，刪除順序表中指定位置對(duì)應(yīng)元素，并返回被刪除元素，其中位置標(biāo)識(shí)從0開始。若用戶輸入位置超出順序表位置范圍，給出相應(yīng)錯(cuò)誤提示。刪除位置輸入為0100間整數(shù)。4. 合并 根據(jù)用戶輸入，將輸入無序表排序后，進(jìn)行有序合并。輸入數(shù)據(jù)為各合法字符。二、 鏈表部分1. 創(chuàng)建 根據(jù)用戶輸入，創(chuàng)建順序表，表中各元素以 分隔顯示。創(chuàng)建過程中采用頭插法創(chuàng)建。非空鏈表為后續(xù)其它操作的前提。輸入數(shù)據(jù)為各合法字符（含中文）。2. 查找 根據(jù)用戶輸入，返回指定元素在鏈表中的位置（其中位置坐標(biāo)從0開始）。若所查找元素在鏈表中不存在，給出提示相應(yīng)信息，并設(shè)置坐標(biāo)位置為 1。查找輸入為各合法字符。3. 插入 根據(jù)用戶輸入，在指定位置插入指定元素，若輸入位置超出鏈表范圍，給出越界錯(cuò)誤提示；若用戶未輸入插入元素，亦給出相應(yīng)提示提示。入元素為各合法字符，插入位置為0100間整數(shù)。4. 刪除 根據(jù)用戶輸入，刪除鏈表中指定位置對(duì)應(yīng)元素，并返回被刪除元素。若用戶輸入位置超出鏈表范圍，給出相應(yīng)錯(cuò)誤提示。刪除位置輸入為0100間整數(shù)。5. 合并 根據(jù)用戶輸入，將輸入無序表排序后，進(jìn)行有序合并。輸入數(shù)據(jù)為各合法字符。三、 KMP部分1. 數(shù)據(jù)輸入 輸入主串及模式串元素為各合法輸入（含中文）。2. 求解next 對(duì)用戶輸入模式串T根據(jù)KMP算法求解各元素對(duì)應(yīng)next值。3. 模式匹配 利用求得的next值對(duì)用戶輸入的主串S及模式串T進(jìn)行模式匹配，并返回匹配結(jié)果信息。4. 求解nextval 對(duì)用戶輸入模式串T根據(jù)改進(jìn)算法求解各元素對(duì)應(yīng)nextval值。第2章 概要設(shè)計(jì)一、 數(shù)據(jù)結(jié)構(gòu)1. 主對(duì)話框class CDS_DEMO_1Dlg : public CDialog{ …… //構(gòu)造函數(shù) 及 其它基本數(shù)據(jù)元素與操作 public:各控件事件}2. 順序表class CSqDialog : public CDialog{ …… //構(gòu)造函數(shù) 及 其它基本數(shù)據(jù)元素與操作 protected:各控件變量 及 其它相關(guān)變量public:各控件事件 及 其它成員函數(shù) 全局友元}3. 鏈表class CListDialog : public CDialog{ …… //構(gòu)造函數(shù) 及 其它基本數(shù)據(jù)元素與操作 protected:各控件變量 及 其它相關(guān)變量public:各控件事件 及 其它成員函數(shù) 全局友元}4. KMPclass CKmpDialog : public CDialog{ …… //構(gòu)造函數(shù) 及 其它基本數(shù)據(jù)元素與操作 protected:各控件變量 及 其它相關(guān)變量public:各控件事件 及 其它成員函數(shù) 全局友元}二、 程序主流程主對(duì)話框順序表演示鏈表演示KMP演示插入刪除合并查找插入刪除合并NEXT求解NEXTVAL求解模式匹配三、 模塊層次主對(duì)話框響應(yīng)三個(gè)不同單擊事件，對(duì)應(yīng)打開三個(gè)模態(tài)對(duì)話框：順序表演示、鏈表演示、KMP演示。1. 順序表演示創(chuàng)建按鈕：響應(yīng)事件，將用戶輸入轉(zhuǎn)換為以空格分隔的順序表輸出到對(duì)應(yīng)文本框。若此時(shí)順序表非空，啟用插入、刪除按鈕。插入按鍵：響應(yīng)事件，在順序表非空及插入位置合法時(shí)，按用戶輸入將元素插入到指定位置。刪除按鈕：響應(yīng)事件，在順序表非空及刪除位置合法時(shí)，將用戶指定位置對(duì)應(yīng)元素從順序表中刪除，并返回該元素。合并按鈕：響應(yīng)事件，將用戶輸入的兩個(gè)無序表排序后進(jìn)行有序合并。合并操作不依賴于創(chuàng)建操作。2. 鏈表演示創(chuàng)建按鈕：響應(yīng)事件，將用戶輸入轉(zhuǎn)換為以 分隔的鏈表輸出到對(duì)應(yīng)文本框。若此時(shí)鏈表非空，啟用查找、插入、刪除按鈕。查找按鈕：響應(yīng)事件，從鏈表中查找用戶輸入元素。查找成功時(shí)，返回元素位置；查找失敗時(shí)，給出提示信息。插入按鈕：響應(yīng)事件，在鏈表非空及插入位置合法時(shí)，在鏈表中指定位置插入指定元素。刪除按鈕：響應(yīng)事件，在鏈表非空及刪除位置合法時(shí)，刪除鏈表中指定位置元素，并返回被刪除元素。合并按鈕：響應(yīng)事件，將用戶輸入的兩個(gè)無序表排序后進(jìn)行有序合并。合并操作不依賴于創(chuàng)建操作。3. KMP演示輸入按鈕：響應(yīng)事件，獲取用戶主串及模式串?dāng)?shù)據(jù)輸入。當(dāng)模式串非空時(shí)，啟用求NEXT、求NEXTVAL按鈕；當(dāng)模式串及主串均非空時(shí)，啟用匹配按鈕。求NEXT按鈕：響應(yīng)事件，求取KMP算法中模式串各元素的next值。匹配按鈕：響應(yīng)事件，根據(jù)KMP算法，對(duì)主串及模式串進(jìn)行匹配操作。求NEXTVAL按鈕：響應(yīng)事件，求取KMP改進(jìn)算法中模式串各元素的nextval值。4. 窗口關(guān)閉按鈕無演示操作時(shí)，單擊關(guān)閉按鈕，關(guān)閉當(dāng)前對(duì)話框并返回上級(jí)對(duì)話框或退出演示程序；演示操作進(jìn)行過程中，關(guān)閉按鈕禁用，防止意外程序終止發(fā)生。第3章 詳細(xì)設(shè)計(jì)一、 數(shù)據(jù)類型1. 順序表 CString m_CurrSq。 // 當(dāng)前順序表 各元素以 空格 分隔 int m_CurrLength。 // 當(dāng)前順序表 表長(zhǎng) int m_CurrSize。 // 當(dāng)前順序表 容量 int m_InsertPos。 // 元素插入位置 CString m_InsertValue。 // 待插入元素 CString m_OpValue。 // 當(dāng)前操作元素 int m_OpPos。 // 當(dāng)前操作位置 int m_DeletePos。 // 刪除元素位置 CString m_DeleteValue。 // 刪除元素值 CString m_StringA。 // 待排序原始表A CString m_StringB。 // 待排序原始表B CString m_SortedA。 // 已排序有序表A CString m_SortedB。 // 已排序有序表B CString m_SortedC。 // 排序后合并表C int m_PosA。 // 當(dāng)前有序A操作元素位置 int m_PosB。 // 當(dāng)前有序表B操作元素位置 CString m_ValueA。 // 當(dāng)前有序表A操作元素 CString m_ValueB。 // 當(dāng)前有序表B操作元素2. 鏈表 CString m_CreateList。 // 創(chuàng)建操作中原始鏈表 int m_CurrLength。 // 當(dāng)前表長(zhǎng) 不含頭結(jié)點(diǎn) CString m_CurrList。 // 當(dāng)前鏈表 以 分隔 CString m_OpValue。 // 當(dāng)前操作元素 int m_OpPos。 // 當(dāng)前操作元素原始位置 CString m_ListA。 // 待排序原始鏈表A CString m_ListB。 // 待排序鏈表B CString m_SortedC。 // 合并后鏈表C 分隔 CString m_SortedA。 // 已排序鏈表A CString m_SortedB。 // 已排序鏈表B int m_PosA。 // 當(dāng)前操作中鏈表A元素位置 int m_PosB。 // 當(dāng)前操作中鏈表B元素位置 CString m_ValueA。 // 當(dāng)前操作中鏈表A元素值 CString m_ValueB。 // 當(dāng)前操作中鏈表B元素值 int m_DeletePos。 // 待刪除元素位置 CString m_DeleteValue。 // 待刪除元素值 CString m_FindValue。 // 待查找元素 int m_FindPos。 // 待查找元素所以位置 1為元素不存在 int m_InsertPos。 // 元