《数据结构课程设计报告_数据结构演示系统.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告_数据结构演示系统.doc（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 中南大学数据结构课程设计报告题 目： 数据结构演示系统（1） 院 系： 信息科学与工程学院 班 级： 计算机 0904 姓 名： 张 学 程 学 号： 指导老师： 陈 再 良 完成时间： 2011. 07 目录第1章需求分析3一、顺序表部分3二、链表部分3三、KMP部分3第2章概要设计5一、数据结构5二、程序主流程6三、模块层次6第3章详细设计8一、数据类型8二、相关函数9三、详细流程10四、重要算法10五、重要存储结构25第4章调试分析26一、问题与解决26二、性能分析26第5章测试结果27一、主窗口27二、顺序表演示27三、链表演示28四、KMP演示29五、错误输入处理30六、设计总结3
2、1七、参考文献32八、附录32第1章 需求分析一、 顺序表部分1. 创建根据用户输入，创建顺序表，表中各元素以空格分隔显示。非空顺序表为后续其它操作的前提。输入数据为各合法字符（含中文）。2. 插入根据用户输入，在指定位置插入指定元素，其中位置标识从0开始。若用户输入位置超出顺序表位置范围，给出越界错误提示；若用户未输入插入元素，亦给出相应提示。插入元素为各合法字符，插入位置为0-100间整数。3. 删除根据用户输入，删除顺序表中指定位置对应元素，并返回被删除元素，其中位置标识从0开始。若用户输入位置超出顺序表位置范围，给出相应错误提示。删除位置输入为0-100间整数。4. 合并根据用户输入，
3、将输入无序表排序后，进行有序合并。输入数据为各合法字符。二、 链表部分1. 创建根据用户输入，创建顺序表，表中各元素以 - 分隔显示。创建过程中采用头插法创建。非空链表为后续其它操作的前提。输入数据为各合法字符（含中文）。2. 查找根据用户输入，返回指定元素在链表中的位置（其中位置坐标从0开始）。若所查找元素在链表中不存在，给出提示相应信息，并设置坐标位置为 -1。查找输入为各合法字符。3. 插入根据用户输入，在指定位置插入指定元素，若输入位置超出链表范围，给出越界错误提示；若用户未输入插入元素，亦给出相应提示提示。入元素为各合法字符，插入位置为0-100间整数。4. 删除根据用户输入，删除链
4、表中指定位置对应元素，并返回被删除元素。若用户输入位置超出链表范围，给出相应错误提示。删除位置输入为0-100间整数。5. 合并根据用户输入，将输入无序表排序后，进行有序合并。输入数据为各合法字符。三、 KMP部分1. 数据输入输入主串及模式串元素为各合法输入（含中文）。2. 求解next对用户输入模式串T根据KMP算法求解各元素对应next值。3. 模式匹配利用求得的next值对用户输入的主串S及模式串T进行模式匹配，并返回匹配结果信息。4. 求解nextval对用户输入模式串T根据改进算法求解各元素对应nextval值。第2章 概要设计一、 数据结构1. 主对话框class CDS_DEM
5、O_1Dlg : public CDialog /构造函数 及 其它基本数据元素与操作 public:各控件事件2. 顺序表class CSqDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元3. 链表class CListDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元4. KMPclass CKmpDialog : publ
6、ic CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元二、 程序主流程主对话框顺序表演示链表演示KMP演示插入删除合并查找插入删除合并NEXT求解NEXTVAL求解模式匹配三、 模块层次主对话框响应三个不同单击事件，对应打开三个模态对话框：顺序表演示、链表演示、KMP演示。1. 顺序表演示创建按钮：响应事件，将用户输入转换为以空格分隔的顺序表输出到对应文本框。若此时顺序表非空，启用插入、删除按钮。插入按键：响应事件，在顺序表非空及插入位置合法时，按用户输入将元素插入到指定位置。删除按钮：响应
7、事件，在顺序表非空及删除位置合法时，将用户指定位置对应元素从顺序表中删除，并返回该元素。合并按钮：响应事件，将用户输入的两个无序表排序后进行有序合并。合并操作不依赖于创建操作。2. 链表演示创建按钮：响应事件，将用户输入转换为以 - 分隔的链表输出到对应文本框。若此时链表非空，启用查找、插入、删除按钮。查找按钮：响应事件，从链表中查找用户输入元素。查找成功时，返回元素位置；查找失败时，给出提示信息。插入按钮：响应事件，在链表非空及插入位置合法时，在链表中指定位置插入指定元素。删除按钮：响应事件，在链表非空及删除位置合法时，删除链表中指定位置元素，并返回被删除元素。合并按钮：响应事件，将用户输入
8、的两个无序表排序后进行有序合并。合并操作不依赖于创建操作。3. KMP演示输入按钮：响应事件，获取用户主串及模式串数据输入。当模式串非空时，启用求NEXT、求NEXTVAL按钮；当模式串及主串均非空时，启用匹配按钮。求NEXT按钮：响应事件，求取KMP算法中模式串各元素的next值。匹配按钮：响应事件，根据KMP算法，对主串及模式串进行匹配操作。求NEXTVAL按钮：响应事件，求取KMP改进算法中模式串各元素的nextval值。4. 窗口关闭按钮无演示操作时，单击关闭按钮，关闭当前对话框并返回上级对话框或退出演示程序；演示操作进行过程中，关闭按钮禁用，防止意外程序终止发生。第3章 详细设计一、
9、 数据类型1. 顺序表CString m_CurrSq; / 当前顺序表 各元素以 空格 分隔int m_CurrLength; / 当前顺序表 表长int m_CurrSize; / 当前顺序表 容量int m_InsertPos; / 元素插入位置CString m_InsertValue; / 待插入元素CString m_OpValue; / 当前操作元素int m_OpPos; / 当前操作位置int m_DeletePos; / 删除元素位置CString m_DeleteValue; / 删除元素值CString m_StringA; / 待排序原始表ACString m_Str
10、ingB; / 待排序原始表BCString m_SortedA; / 已排序有序表ACString m_SortedB; / 已排序有序表BCString m_SortedC; / 排序后合并表Cint m_PosA; / 当前有序A操作元素位置int m_PosB; / 当前有序表B操作元素位置CString m_ValueA; / 当前有序表A操作元素CString m_ValueB; / 当前有序表B操作元素2. 链表CString m_CreateList; / 创建操作中原始链表int m_CurrLength; / 当前表长 不含头结点CString m_CurrList; /
11、当前链表 以 - 分隔CString m_OpValue; / 当前操作元素int m_OpPos; / 当前操作元素原始位置CString m_ListA; / 待排序原始链表ACString m_ListB; / 待排序链表BCString m_SortedC; / 合并后链表C - 分隔CString m_SortedA; / 已排序链表ACString m_SortedB; / 已排序链表Bint m_PosA; / 当前操作中链表A元素位置int m_PosB; / 当前操作中链表B元素位置CString m_ValueA; / 当前操作中链表A元素值CString m_ValueB
12、; / 当前操作中链表B元素值int m_DeletePos; / 待删除元素位置CString m_DeleteValue; / 待删除元素值CString m_FindValue; / 待查找元素int m_FindPos; / 待查找元素所以位置 -1为元素不存在int m_InsertPos; / 元素待插入位置CString m_InsertValue; / 待插入元素3. KMPCString m_S; / 原始输入主串 无空格分隔CString m_T; / 原始输入子串 无空格分隔CString m_IndexS; / 模式匹配过程中主串S 以空格分隔 操作字符以 () 标识C
13、String m_IndexT; / 模式匹配过程中子串T 以空格分隔 操作字符以 () 标识CString m_NextT1; / 求next过程中模式串T1CString m_NextT2; / 求next过程中模式串T2CString m_Next; / 模式串的next值CString m_NextvalT1; / 求nextval操作中模式串T1CString m_NextvalT2; / 求nextval操作中模式串T2CString m_Nextval; / 求nextval操作中nextval值二、 相关函数1. 顺序表afx_msg void OnSqCreateButton
14、(); / 响应创建按钮事件afx_msg void OnSqInsertButton(); / 响应插入按钮事件afx_msg void OnSqDeleteButton(); / 响应删除按钮事件afx_msg void OnSqMergeButton(); / 响应合并按钮事件afx_msg LRESULT OnSqUpdate(WPARAM wParameter,LPARAM lpParameter); /响应对话框数据更新2. 链表afx_msg void OnListCreateButton(); / 响应创建按键事件afx_msg void OnListFindButton();
15、 / 响应查找按钮事件afx_msg void OnListInsertButton(); / 响应插入按钮事件afx_msg void OnListDeleteButton(); / 响应删除按钮事件afx_msg void OnListMergeButton(); / 响应合并按钮事件afx_msg LRESULT OnListUpdate(WPARAM wParameter,LPARAM lpParameter); / 响应对话框数据更新3. KMPafx_msg void OnKmpInputButton(); / 响应数据输入事件afx_msg void OnKmpIndexButt
16、on(); / 响应模式匹配事件afx_msg void OnKmpNextButton(); / 响应求Next值事件afx_msg void OnKmpNextvalButton(); / 响应求Nextval事件afx_msg LRESULT OnKmpUpdate(WPARAM wParameter,LPARAM lpParameter); / 响应对话框数据更新4. 线程处理UINT sqDlgCreate(LPVOID lpParam); /顺序表创建UINT sqDlgInsert(LPVOID lpParam) ; /顺序表插入UINT sqDlgDelete(LPVOID l
17、pParam); /顺序表删除UINT sqDlgMerge(LPVOID lpParam); /顺序表合并UINT listDlgCreate(LPVOID lpParam); /链表创建UINT listDlgFind(LPVOID lpParam); /链表查找UINT listDlgInsert(LPVOID lpParam); /链表插入UINT listDlgDelete(LPVOID lpParam); /链表删除UINT listDlgMerge(LPVOID lpParam); /链表合并UINT kmpDlgIndex(LPVOID lpParam); /模式匹配UINT
18、kmpDlgNext(LPVOID lpParam); /求Next值UINT kmpDlgNextval(LPVOID lpParam); /求Nextval值5. 其它函数void GetNext(CKmpDialog* pDlg, int next); /求Next 用于模式匹配三、 详细流程四、 重要算法1. 顺序表算法1.1/顺序表创建 线程函数UINT sqDlgCreate(LPVOID lpParam)CSqDialog* pDlg = (CSqDialog*)lpParam;/更新过程中 禁用 相关按钮 及 系统菜单关闭按钮for(int i = 0; i m_CreateS
19、q.GetLength(); +i)pDlg-m_OpPos = i;pDlg-m_CurrSq += pDlg-m_CreateSq.GetAt(i);pDlg-m_OpValue.SetAt(0, pDlg-m_CreateSq.GetAt(i);pDlg-m_CurrSq += _T( );+(pDlg-m_CurrLength);if(pDlg-m_CurrSize m_CurrLength)pDlg-m_CurrSize *= 2; /增加容量到原容量2倍Sleep(1000);/发送消息给主线程 更新对话框pDlg-SendMessage(WM_USER+1, NULL, NULL
20、);/重新启用创建按钮 及 系统菜单关闭按钮/若顺序表不为空 启用相关控件if(0 != pDlg-m_CurrLength)(pDlg-GetDlgItem(IDC_SQ_INSERT_BUTTON)-EnableWindow(TRUE);(pDlg-GetDlgItem(IDC_SQ_DELETE_BUTTON)-EnableWindow(TRUE);return 0;算法1.2/顺序表插入 线程函数UINT sqDlgInsert(LPVOID lpParam)CSqDialog* pDlg = (CSqDialog*)lpParam;if(pDlg-m_InsertValue.IsEm
21、pty()MessageBox(NULL, _T(不能插入空元素！), _T(插入元素非法), MB_OK);return 0;if(pDlg-m_InsertPos pDlg-m_CurrLength)MessageBox(NULL, _T(请输入正确的插入位置！), _T(插入位置越界), MB_OK);return 0;/更新过程中 禁用相关按钮 及 系统菜单关闭按钮+(pDlg-m_CurrLength); /元素长度加 1if(pDlg-m_CurrSize m_CurrLength)pDlg-m_CurrSize *= 2;pDlg-m_CurrSq += _T( ); /给显示串
22、增加两个空字符for(int i = pDlg-m_CurrLength-1; i pDlg-m_InsertPos; -i)pDlg-m_OpPos = i;if(1 = i)/当 i 为 1 时 保留紧接元素 0 的空格pDlg-m_CurrSq.SetAt(2, pDlg-m_CurrSq.GetAt(0);pDlg-m_OpValue.SetAt(0, pDlg-m_CurrSq.GetAt(0);elsepDlg-m_CurrSq.SetAt(2*i, pDlg-m_CurrSq.GetAt(2*i-2);pDlg-m_CurrSq.SetAt(2*i-1, pDlg-m_CurrS
23、q.GetAt(2*i-3);pDlg-m_OpValue.SetAt(0, pDlg-m_CurrSq.GetAt(2*i-2);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);/插入元素pDlg-m_OpPos = pDlg-m_InsertPos;pDlg-m_CurrSq.SetAt(2 * pDlg-m_InsertPos, pDlg-m_InsertValue.GetAt(0);pDlg-m_OpValue.SetAt(0, pDlg-m_InsertValue.GetAt(0);Sleep(1000);pDlg-SendMe
24、ssage(WM_USER+1, NULL, NULL);/重新启用相关按钮 及 系统菜单关闭按钮return 0;算法1.3/顺序表删除 线程函数UINT sqDlgDelete(LPVOID lpParam)CSqDialog* pDlg = (CSqDialog*)lpParam;if(pDlg-m_DeletePos pDlg-m_CurrLength-1)MessageBox(NULL, _T(请输入正确的删除位置！), _T(删除位置越界), MB_OK);return 0;/更新过程中 禁用相关按钮 及 系统菜单关闭按钮/获取待删除元素pDlg-m_DeleteValue.Set
25、At(0, pDlg-m_CurrSq.GetAt(2*pDlg-m_DeletePos);/删除前 顺序表只有一个元素if(1 = pDlg-m_CurrLength)pDlg-m_OpPos = 0;pDlg-m_OpValue.SetAt(0, pDlg-m_CurrSq.GetAt(0);pDlg-m_CurrLength = 0;pDlg-m_CurrSq = _T(); /清空顺序表Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);/删除成功后 顺序表空 只启用创建按钮和合并按钮(pDlg-GetDlgItem(IDC_SQ_C
26、REATE_BUTTON)-EnableWindow(TRUE); (pDlg-GetDlgItem(IDC_SQ_MERGE_BUTTON)-EnableWindow(TRUE);EnableMenuItem(hSysMenu, nCloseItemID, MF_ENABLED);return 0;for(int i = pDlg-m_DeletePos; i m_CurrLength-1; +i)pDlg-m_OpPos = i;if(0 = i)pDlg-m_CurrSq.SetAt(0, pDlg-m_CurrSq.GetAt(2);pDlg-m_OpValue.SetAt(0, pD
27、lg-m_CurrSq.GetAt(2);elsepDlg-m_CurrSq.SetAt(2*i, pDlg-m_CurrSq.GetAt(2*i+2);pDlg-m_CurrSq.SetAt(2*i+1, pDlg-m_CurrSq.GetAt(2*i+3);pDlg-m_OpValue.SetAt(0, pDlg-m_CurrSq.GetAt(2*i+2);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);pDlg-m_CurrSq.Delete(pDlg-m_CurrSq.GetLength()-2,2);-(pDlg-m_CurrL
28、ength);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL); /重新启用相关按钮 及 系统菜单关闭按钮return 0;算法1.4/顺序表合并 线程函数UINT sqDlgMerge(LPVOID lpParam)CSqDialog* pDlg = (CSqDialog*)lpParam;/更新过程中 禁用相关按钮 及 系统菜单关闭按钮int pa = 0;int pb = 0;int pc = 0;/m_SortedA m_SortedB 含空格分隔符 长度判断时应忽略while(pa m_StringA.GetLength() &
29、pb m_StringB.GetLength()if(pDlg-m_SortedA.GetAt(2*pa) m_SortedB.GetAt(2*pb)pDlg-m_SortedC += pDlg-m_SortedA.GetAt(2*pa);pDlg-m_CurrSq += pDlg-m_SortedA.GetAt(2*pa);pDlg-m_SortedC += _T( );pDlg-m_CurrSq += _T( );pDlg-m_OpPos = pc;pDlg-m_OpValue = pDlg-m_SortedA.GetAt(2*pa);pDlg-m_PosA = pa;pDlg-m_Val
30、ueA = pDlg-m_SortedA.GetAt(2*pa);+pa;+pc;elsepDlg-m_SortedC += pDlg-m_SortedB.GetAt(2*pb);pDlg-m_CurrSq += pDlg-m_SortedB.GetAt(2*pb);pDlg-m_SortedC += _T( );pDlg-m_CurrSq += _T( );pDlg-m_OpPos = pc;pDlg-m_OpValue = pDlg-m_SortedB.GetAt(2*pb);pDlg-m_PosB = pb;pDlg-m_ValueB = pDlg-m_SortedB.GetAt(2*p
31、b);+pb;+pc;+(pDlg-m_CurrLength);if(pDlg-m_CurrSize m_CurrLength)pDlg-m_CurrSize *= 2;Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);while(pa m_StringA.GetLength()pDlg-m_SortedC += pDlg-m_SortedA.GetAt(2*pa);pDlg-m_CurrSq += pDlg-m_SortedA.GetAt(2*pa);pDlg-m_SortedC += _T( );pDlg-m_CurrSq += _T(
32、 );pDlg-m_OpPos = pc;pDlg-m_OpValue = pDlg-m_SortedA.GetAt(2*pa);pDlg-m_PosA = pa;pDlg-m_ValueA = pDlg-m_SortedA.GetAt(2*pa);+pa;+pc;+(pDlg-m_CurrLength);if(pDlg-m_CurrSize m_CurrLength)pDlg-m_CurrSize *= 2;Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);while(pb m_StringB.GetLength()pDlg-m_Sort
33、edC += pDlg-m_SortedB.GetAt(2*pb);pDlg-m_CurrSq += pDlg-m_SortedB.GetAt(2*pb);pDlg-m_SortedC += _T( );pDlg-m_CurrSq += _T( );pDlg-m_OpPos = pc;pDlg-m_OpValue = pDlg-m_SortedB.GetAt(2*pb);pDlg-m_PosB = pb;pDlg-m_ValueB = pDlg-m_SortedB.GetAt(2*pb);+pb;+pc;+(pDlg-m_CurrLength);if(pDlg-m_CurrSize m_Cur
34、rLength)pDlg-m_CurrSize *= 2;Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);/重新启用相关按钮 及 系统菜单关闭按钮return 0;2. 链表算法2.1/链表创建 线程函数UINT listDlgCreate(LPVOID lpParam)CListDialog* pDlg = (CListDialog*)lpParam;/更新过程中 禁用 相关按钮 及 系统菜单关闭按钮for(int i = 0; i m_CreateList.GetLength(); +i)if(1 = pDlg-m_CreateLis
35、t.GetLength()pDlg-m_CurrList += _T( - );pDlg-m_CurrList.SetAt(5, pDlg-m_CreateList.GetAt(0);+pDlg-m_CurrLength;pDlg-m_OpPos = 0;pDlg-m_OpValue = pDlg-m_CreateList.GetAt(0);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);elsepDlg-m_CurrList.Insert(1, _T( - );Sleep(1000);pDlg-SendMessage(WM_USER+1
36、, NULL, NULL);pDlg-m_CurrList.SetAt(5, pDlg-m_CreateList.GetAt(pDlg-m_CreateList.GetLength()-i-1);+pDlg-m_CurrLength;pDlg-m_OpPos = pDlg-m_CreateList.GetLength()-i-1;pDlg-m_OpValue = pDlg-m_CreateList.GetAt(pDlg-m_CreateList.GetLength()-i-1);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);/重新启用创
37、建按钮 及 系统菜单关闭按钮return 0;算法2.2/链表元素查找 线程函数UINT listDlgFind(LPVOID lpParam)CListDialog* pDlg = (CListDialog*)lpParam;/更新过程中 禁用 相关按钮 及 系统菜单关闭按钮int i = 1;for( ; i m_CurrLength; +i)pDlg-m_OpPos = i-1;pDlg-m_OpValue = pDlg-m_CurrList.GetAt(5*i);Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);if(pDlg-m_
38、CurrList.GetAt(5*i) = pDlg-m_FindValue.GetAt(0)pDlg-m_FindPos = i-1;Sleep(1000);pDlg-SendMessage(WM_USER+1, NULL, NULL);break;if(i pDlg-m_CurrLength)MessageBox(NULL, _T(所查找元素不存在！), _T(查找失败), MB_OK);/重新启用相关按钮 及 系统菜单关闭按钮return 0;算法2.3/链表元素插入 线程函数UINT listDlgInsert(LPVOID lpParam)CListDialog* pDlg = (C
39、ListDialog*)lpParam;if(pDlg-m_InsertValue.IsEmpty()MessageBox(NULL, _T(不能插入空元素！), _T(插入元素非法), MB_OK);return 0;if(pDlg-m_InsertPos pDlg-m_CurrLength)MessageBox(NULL, _T(请输入正确的插入位置！), _T(插入位置越界), MB_OK);return 0;/更新过程中 禁用 相关按钮 及 系统菜单关闭按钮for(int i = 0; i m_InsertPos; +i)pDlg-m_OpPos = i;pDlg-m_OpValue = pDlg-m_CurrList.GetAt(5*(i+1);Sleep(1000);