《数据结构课程设计报告数据结构演示系统》由会员分享，可在线阅读，更多相关《数据结构课程设计报告数据结构演示系统（32页珍藏版）》请在金锄头文库上搜索。
1、 中南大学数据结构课程设计报告题 目： 数据结构演示系统（1） 院 系： 信息科学与工程学院 班 级： 计算机 0904 姓 名： 张 学 程 学 号： 0909091322 指导老师： 陈 再 良 完成时间： 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五、错误输入
2、处理30六、设计总结31七、参考文献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. 主对话框cl
5、ass CDS_DEMO_1Dlg : public CDialog /构造函数 及 其它基本数据元素与操作 public:各控件事件2. 顺序表class CSqDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元3. 链表class CListDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元4. KMPclass CKmpDi
6、alog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元二、 程序主流程主对话框顺序表演示链表演示KMP演示插入删除合并查找插入删除合并NEXT求解NEXTVAL求解模式匹配三、 模块层次主对话框响应三个不同单击事件，对应打开三个模态对话框：顺序表演示、链表演示、KMP演示。1. 顺序表演示创建按钮：响应事件，将用户输入转换为以空格分隔的顺序表输出到对应文本框。若此时顺序表非空，启用插入、删除按钮。插入按键：响应事件，在顺序表非空及插入位置合法时，按用户输入将元素插入到指
7、定位置。删除按钮：响应事件，在顺序表非空及删除位置合法时，将用户指定位置对应元素从顺序表中删除，并返回该元素。合并按钮：响应事件，将用户输入的两个无序表排序后进行有序合并。合并操作不依赖于创建操作。2. 链表演示创建按钮：响应事件，将用户输入转换为以 - 分隔的链表输出到对应文本框。若此时链表非空，启用查找、插入、删除按钮。查找按钮：响应事件，从链表中查找用户输入元素。查找成功时，返回元素位置；查找失败时，给出提示信息。插入按钮：响应事件，在链表非空及插入位置合法时，在链表中指定位置插入指定元素。删除按钮：响应事件，在链表非空及删除位置合法时，删除链表中指定位置元素，并返回被删除元素。合并按钮
8、：响应事件，将用户输入的两个无序表排序后进行有序合并。合并操作不依赖于创建操作。3. KMP演示输入按钮：响应事件，获取用户主串及模式串数据输入。当模式串非空时，启用求NEXT、求NEXTVAL按钮；当模式串及主串均非空时，启用匹配按钮。求NEXT按钮：响应事件，求取KMP算法中模式串各元素的next值。匹配按钮：响应事件，根据KMP算法，对主串及模式串进行匹配操作。求NEXTVAL按钮：响应事件，求取KMP改进算法中模式串各元素的nextval值。4. 窗口关闭按钮无演示操作时，单击关闭按钮，关闭当前对话框并返回上级对话框或退出演示程序；演示操作进行过程中，关闭按钮禁用，防止意外程序终止发生
9、。第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_StringA; / 待排序原始表ACS
10、tring 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; / 当前表长 不含头结点CString m_C
11、urrList; / 当前链表 以 - 分隔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元素值CStri
12、ng m_ValueB; / 当前操作中链表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 以空格分隔 操作字符以 () 标识CString 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;
