《数据结构课程设计报告_数据结构演示系统》由会员分享，可在线阅读，更多相关《数据结构课程设计报告_数据结构演示系统（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
2、二、性能分析.26第 5 章 测试结果.27一、主窗口.27 二、顺序表演示.27 三、链表演示.28 四、KMP 演示.29 五、错误输入处理.30六、设计总结.31七、参考文献.32八、附录.32第第 1 1 章章需求分析需求分析一、一、 顺序表部分顺序表部分1.创建根据用户输入，创建顺序表，表中各元素以空格分隔显示。非 空顺序表为后续其它操作的前提。输入数据为各合法字符（含中文） 。 2.插入根据用户输入，在指定位置插入指定元素，其中位置标识从 0 开始。若用户输入位置超出顺序表位置范围，给出越界错误提示；若 用户未输入插入元素，亦给出相应提示。插入元素为各合法字符，插 入位置为 0-1
3、00 间整数。 3.删除根据用户输入，删除顺序表中指定位置对应元素，并返回被删 除元素，其中位置标识从 0 开始。若用户输入位置超出顺序表位置范 围，给出相应错误提示。删除位置输入为 0-100 间整数。 4.合并根据用户输入，将输入无序表排序后，进行有序合并。输入数 据为各合法字符。二、二、 链表部分链表部分1. 创建 根据用户输入，创建顺序表，表中各元素以 - 分隔显示。创 建过程中采用头插法创建。非空链表为后续其它操作的前提。输入数 据为各合法字符（含中文） 。 2. 查找 根据用户输入，返回指定元素在链表中的位置（其中位置坐标 从 0 开始） 。若所查找元素在链表中不存在，给出提示相应
4、信息，并 设置坐标位置为 -1。查找输入为各合法字符。 3. 插入 根据用户输入，在指定位置插入指定元素，若输入位置超出链 表范围，给出越界错误提示；若用户未输入插入元素，亦给出相应提 示提示。入元素为各合法字符，插入位置为 0-100 间整数。 4. 删除 根据用户输入，删除链表中指定位置对应元素，并返回被删除 元素。若用户输入位置超出链表范围，给出相应错误提示。删除位置 输入为 0-100 间整数。 5. 合并 根据用户输入，将输入无序表排序后，进行有序合并。输入数 据为各合法字符。三、三、 KMP 部分部分1. 数据输入 输入主串及模式串元素为各合法输入（含中文） 。 2. 求解 nex
5、t 对用户输入模式串 T 根据 KMP 算法求解各元素对应 next 值。3. 模式匹配 利用求得的 next 值对用户输入的主串 S 及模式串 T 进行模式匹配，并返回匹配结果信息。 4. 求解 nextval 对用户输入模式串 T 根据改进算法求解各元素对应 nextval 值。第第 2 2 章章概要设计概要设计一、一、 数据结构数据结构1. 主对话框class CDS_DEMO_1Dlg : public CDialog /构造函数 及 其它基本数据元素与操作 public:各控件事件 2. 顺序表class CSqDialog : public CDialog /构造函数 及 其它基本
6、数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元 3. 链表class CListDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元 4. KMPclass CKmpDialog : public CDialog /构造函数 及 其它基本数据元素与操作protected:各控件变量 及 其它相关变量public:各控件事件 及 其它成员函数全局友元二、二、 程序主流程程序主流程主 对话 框顺序 表
7、演示链表 演示KMP 演示插入删除合并查找插入删除合并NEXT 求解NEXTV AL 求解模式 匹配三、三、 模块层次模块层次主对话框响应三个不同单击事件，对应打开三个模态对话框：顺序表演示、 链表演示、KMP 演示。 1. 顺序表演示 创建按钮：响应事件，将用户输入转换为以空格分隔的顺序表输出到对应 文本框。若此时顺序表非空，启用插入、删除按钮。 插入按键：响应事件，在顺序表非空及插入位置合法时，按用户输入将元 素插入到指定位置。 删除按钮：响应事件，在顺序表非空及删除位置合法时，将用户指定位置 对应元素从顺序表中删除，并返回该元素。 合并按钮：响应事件，将用户输入的两个无序表排序后进行有序
8、合并。合 并操作不依赖于创建操作。 2. 链表演示 创建按钮：响应事件，将用户输入转换为以 - 分隔的链表输出到对应文 本框。若此时链表非空，启用查找、插入、删除按钮。 查找按钮：响应事件，从链表中查找用户输入元素。查找成功时，返回元 素位置；查找失败时，给出提示信息。 插入按钮：响应事件，在链表非空及插入位置合法时，在链表中指定位置 插入指定元素。 删除按钮：响应事件，在链表非空及删除位置合法时，删除链表中指定位 置元素，并返回被删除元素。 合并按钮：响应事件，将用户输入的两个无序表排序后进行有序合并。合 并操作不依赖于创建操作。 3. KMP 演示 输入按钮：响应事件，获取用户主串及模式串数据输入。当模式串非空时，启用求 NEXT、求 NEXTVAL 按钮；当模式串及主串均非空时，启用匹配按钮。 求 NEXT 按钮：响应事件，求取 KMP 算法中模式串各元素的 ne
