2022年数据结构课程方案报告数据结构演示系统 .pdf

《2022年数据结构课程方案报告数据结构演示系统 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案报告数据结构演示系统 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、个人资料整理仅限学习使用中南大学数据结构课程设计报告题目：数据结构演示系统 1）院系：信息科学与工程学院班级：计算机 0904 姓名：张 学程学号： 0909091322 指导老师：陈再良完成时间： 2018.07 目录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页个人资料整理仅限学习使用第1章 需求分析一、顺序表部分1.创建根据用户输入，创建顺序表，表中各元素以空格分隔显示。非空顺序表为后续其它操作的前提。输入数据为各合法字符 分隔显示。创建过程中采用头插法创建。非空链表为后续其它操作的前提。输入数据为各合法字符含中文）。2

2、.查找根据用户输入，返回指定元素在链表中的位置其中位置坐标从0 开始）。若所查找元素在链表中不存在，给出提示相应信息，并设置坐标位置为 -1 。查找输入为各合法字符。3.插入根据用户输入，在指定位置插入指定元素，若输入位置超出链表范围，给出越界错误提示；若用户未输入插入元素，亦给出相应提示提示。入元素为各合法字符，插入位置为0-100 间整数。4.删除根据用户输入，删除链表中指定位置对应元素，并返回被删除元素。若用户输入位置超出链表范围，给出相应错误提示。删除位置输入为0-100 间整数。5.合并根据用户输入，将输入无序表排序后，进行有序合并。输入数据为各合法字符。三、KMP 部分1.数据输入

3、 输入主串及模式串元素为各合法输入 分隔的链表输出到对应文本框。若此时链表非空，启用 查找、插入、删除按钮。查找按钮：响应事件，从链表中查找用户输入元素。查找成功时，返回元素位置；查找失败时，给出提示信息。插入按钮：响应事件，在链表非空及插入位置合法时，在链表中指定位置插入指定元素。删除按钮：响应事件，在链表非空及删除位置合法时，删除链表中指定位置元素，并返回被删除元素。合并按钮：响应事件，将用户输入的两个无序表排序后进行有序合并。合并操作不依赖于创建操作。3. KMP 演示输入按钮：响应事件，获取用户主串及模式串数据输入。当模式串非空时，启用求 NEXT 、求 NEXTVAL 按钮；当模式串

4、及主串均非空时，启用匹配按钮。求 NEXT 按钮：响应事件，求取KMP 算法中模式串各元素的next 值。匹配按钮：响应事件，根据KMP 算法，对主串及模式串进行匹配操作。求 NEXTVAL 按钮：响应事件，求取KMP 改进算法中模式串各元素的nextval值。4. 窗口关闭按钮无演示操作时，单击关闭按钮，关闭当前对话框并返回上级对话框或退出演示程序；演示主对话框顺序表演示链表演示KMP演示插入删除合并查找插入删除合并NEXT求解NEXTVAL 求解模式匹配精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页个人资料整理仅限学习使用

5、操作进行过程中，关闭按钮禁用，防止意外程序终止发生。第3章 详细设计一、数据类型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_St

6、ringA。/ 待排序原始表 ACString m_StringB。/ 待排序原始表 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 。/

7、 当前表长不含头结点CString m_CurrList。/ 当前链表以 - 分隔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_Valu

8、eA 。/ 当前操作中链表 A元素值CString m_ValueB 。/ 当前操作中链表 B元素值int m_DeletePos 。/ 待删除元素位置CString m_DeleteValue。/ 待删除元素值CString m_FindValue。/ 待查找元素int m_FindPos。/ 待查找元素所以位置 -1 为元素不存在int m_InsertPos 。/ 元素待插入位置CString m_InsertValue。/ 待插入元素3. KMP CString m_S 。/ 原始输入主串无空格分隔CString m_T 。/ 原始输入子串无空格分隔CString m_IndexS 。

9、/ 模式匹配过程中主串 S 以空格分隔操作字符以 ( 标识CString m_IndexT 。/ 模式匹配过程中子串 T 以空格分隔操作字符以 ( 标识CString m_NextT1 。/ 求next 过程中模式串 T1CString m_NextT2 。/ 求next 过程中模式串 T2CString m_Next 。/ 模式串的 next 值CString m_NextvalT1。/ 求nextval 操作中模式串 T1CString m_NextvalT2。/ 求nextval 操作中模式串 T2精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -

10、第 5 页，共 12 页个人资料整理仅限学习使用CString m_Nextval。/ 求nextval 操作中 nextval 值二、 相关函数1. 顺序表afx_msg void OnSqCreateButton( 。/ 响应创建按钮事件afx_msg void OnSqInsertButton(。/ 响应插入按钮事件afx_msg void OnSqDeleteButton(。/ 响应删除按钮事件afx_msg void OnSqMergeButton( 。/ 响应合并按钮事件afx_msg LRESULT OnSqUpdate(WPARAM wParameter,LPARAM lpPa

11、rameter。/ 响应对话框数据更新2. 链表afx_msg void OnListCreateButton(。/ 响应创建按键事件afx_msg void OnListFindButton(。/ 响应查找按钮事件afx_msg void OnListInsertButton(。/ 响应插入按钮事件afx_msg void OnListDeleteButton(。/ 响应删除按钮事件afx_msg void OnListMergeButton(。/ 响应合并按钮事件afx_msg LRESULT OnListUpdate(WPARAM wParameter,LPARAM lpParamete

12、r。/ 响应对话框数据更新3. KMP afx_msg void OnKmpInputButton( 。/ 响应数据输入事件afx_msg void OnKmpIndexButton( 。/ 响应模式匹配事件afx_msg void OnKmpNextButton( 。/ 响应求 Next值事件afx_msg void OnKmpNextvalButton( 。/ 响应求 Nextval 事件afx_msg LRESULT OnKmpUpdate(WPARAM wParameter,LPARAM lpParameter。/ 响应对话框数据更新4. 线程处理UINT sqDlgCreate(LP

13、VOID lpParam 。/ 顺序表创建UINT sqDlgInsert(LPVOID lpParam 。/ 顺序表插入UINT sqDlgDelete(LPVOID lpParam。/ 顺序表删除UINT sqDlgMerge(LPVOID lpParam 。/ 顺序表合并UINT listDlgCreate(LPVOID lpParam。/ 链表创建UINT listDlgFind(LPVOID lpParam。/ 链表查找UINT listDlgInsert(LPVOID lpParam。/ 链表插入UINT listDlgDelete(LPVOID lpParam。/ 链表删除UIN

14、T listDlgMerge(LPVOID lpParam。/ 链表合并UINT kmpDlgIndex(LPVOID lpParam 。/ 模式匹配UINT kmpDlgNext(LPVOID lpParam 。/ 求Next值UINT kmpDlgNextval(LPVOID lpParam 。/ 求Nextval 值5. 其它函数void GetNext(CKmpDialog* pDlg, int next。/ 求Next 用于模式匹配精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页个人资料整理仅限学习使用三、 详细流程演

15、示系统主对话框顺序表演示链表演示KMP演示创建顺序表合并顺序表元素插入元素删除创建顺序表合并顺序表元素插入元素删除元素查找数据输入Next模式匹配Nextval四、 重要算法1.顺序表算法 1.1 / 顺序表创建线程函数UINT sqDlgCreate(LPVOID lpParam CSqDialog* pDlg = (CSqDialog*lpParam。/ 更新过程中禁用 相关按钮及 系统菜单关闭按钮for ( int i = 0。 i m_CreateSq.GetLength(。 +i pDlg-m_OpPos = i 。pDlg-m_CurrSq += pDlg-m_CreateSq.G

16、etAt(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。 / 重新启用创建按钮及 系统菜单关闭按钮/ 若顺序表不为空启用相关控件精选学习资料 - - - - - - - - - 名师归纳总结 -

17、 - - - - - -第 7 页，共 12 页个人资料整理仅限学习使用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.IsEmp

18、ty( 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(

19、。/ 给显示串增加两个空字符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。 else pDlg-m_CurrSq.SetAt(2*i, pDlg-m_CurrSq.GetAt(2*i-2。pDlg-m_CurrSq.SetAt(2*i-1, p

20、Dlg-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_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 。pD

21、lg-SendMessage(WM_USER+1, NULL, NULL。/ 重新启用相关按钮及 系统菜单关闭按钮return 0 。 算法1.3/ 顺序表删除线程函数UINT sqDlgDelete(LPVOID lpParam 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页个人资料整理仅限学习使用CSqDialog* pDlg = (CSqDialog*lpParam。if (pDlg-m_DeletePos pDlg-m_CurrLength-1 MessageBox(NULL, _T( 请输入正确的删除位置！ , _T

22、( 删除位置越界 , MB_OK 。return 0 。 / 更新过程中禁用相关按钮及 系统菜单关闭按钮/ 获取待删除元素pDlg-m_DeleteValue.SetAt(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-Se

23、ndMessage(WM_USER+1, NULL, NULL。/ 删除成功后顺序表空只启用创建按钮和合并按钮(pDlg-GetDlgItem(IDC_SQ_CREATE_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 。i

24、f (0 = i pDlg-m_CurrSq.SetAt(0, pDlg-m_CurrSq.GetAt(2。pDlg-m_OpValue.SetAt(0, pDlg-m_CurrSq.GetAt(2。 else pDlg-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,

25、 NULL, NULL。 pDlg-m_CurrSq.Delete(pDlg-m_CurrSq.GetLength(-2,2。-(pDlg-m_CurrLength。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

26、pc = 0。/m_SortedA m_SortedB 含空格分隔符长度判断时应忽略精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页个人资料整理仅限学习使用while (pa m_StringA.GetLength( & 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

27、(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_ValueA = pDlg-m_SortedA.GetAt(2*pa。+pa。+pc。 else pDlg-m_SortedC += pDlg-m_SortedB.GetAt(2*pb。pDlg-m_CurrSq += pDlg-m_SortedB.GetAt(2*pb。pDlg-m_SortedC += _T( 。pDlg

28、-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_CurrLength pDlg-m_CurrSize *= 2。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。 while (pa m_StringA.GetLe

29、ngth( 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_ValueA = pDlg-m_SortedA.GetAt(2*pa。+pa。+pc。+(pDlg-m_CurrLength 。if (pDlg-m_C

30、urrSize m_CurrLength pDlg-m_CurrSize *= 2。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。 while (pb m_StringB.GetLength( pDlg-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_S

31、ortedB.GetAt(2*pb。pDlg-m_PosB = pb 。pDlg-m_ValueB = pDlg-m_SortedB.GetAt(2*pb。+pb。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页个人资料整理仅限学习使用+pc。+(pDlg-m_CurrLength 。if (pDlg-m_CurrSize m_CurrLength pDlg-m_CurrSize *= 2。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。 / 重新启用相关按钮及 系统菜单关

32、闭按钮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_CreateList.GetLength( pDlg-m_CurrList += _T( - 。pDlg-m_CurrList.SetAt(5, pDlg-m_CreateList.GetAt(0。+pDlg-

33、m_CurrLength 。pDlg-m_OpPos = 0。pDlg-m_OpValue = pDlg-m_CreateList.GetAt(0。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。 else pDlg-m_CurrList.Insert(1, _T( - 。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。pDlg-m_CurrList.SetAt(5, pDlg-m_CreateList.GetAt(pDlg-m_CreateList.GetLength(-i-1。+pD

34、lg-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。 / 重新启用创建按钮及 系统菜单关闭按钮return 0 。 算法 2.2/ 链表元素查找线程函数UINT listDlgFind(LPVOID lpParam CListDialog* pDlg = (CListDi

35、alog*lpParam。/ 更新过程中禁用 相关按钮及 系统菜单关闭按钮int i = 1。for ( 。 i m_CurrLength。 +i pDlg-m_OpPos = i-1 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页个人资料整理仅限学习使用pDlg-m_OpValue = pDlg-m_CurrList.GetAt(5*i。Sleep(1000 。pDlg-SendMessage(WM_USER+1, NULL, NULL。if (pDlg-m_CurrList.GetAt(5*i = pDlg-m_Fin

36、dValue.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 = (CListDialog*lpParam。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页