数据结构课程设计报告(C语言版)[精品].doc

数据结构课程设计报告 《数据结构（c语言版）》课程设计 题 目 数据结构演示系统1 和3 学生姓名 学 号 指导教师 学 院 信息科学与工程学院 专业班级 计算机类 完成时间 七月 czlzdj@ 目录 第一章 项目概述…………………………3 1.1 问题的要求分析与描述………………………………………………........3 1.2 问题的要求和限制…………………………………………………………3 第二章 概要设计 …………………………4 第三章 详细设计………………………….8 3.1系统程序的组成框图……………………………………. 8 3.2 程序的流程图………………………………………........11 3.3 算法的源程序……………………………………………15 第四章 调试分析………………………24 4.1 调试方法……………………………………………...24 4.2 算法时间复杂度………………………………………25 第五章 测试结果………………………26 5.1 正确的输入与输出…………………………………...26 5.2 错误的输入与输出……………………………………32 第六章 课程设计总结 6.1 个人的体会和感想…………………………………….41 附录A：演示系统1源代码有详细注释………………………………………….43 附录B：演示系统2源代码………………………………………………………..60 参考文献……………………………………………………………………………..82 项目概述 1.1 问题的描述与分析 本次课程设计，我完成了两个题目，数据结构演示系统1、数据结构演示系统2。 数据结构演示系统1主要有两种数据的存储结构要实现，顺序和链式,每种存储结构都要实现至少四种算法插入、删除、查询、合并。对于串还要实现模式匹配，使用KMP的快速算法，减小时间复杂度。1、顺序表的插入、删除和合并等基本操作。2、利用插入运算建立链表；实现链表的查找、删除、计数、输出等功能以及有序链表的合并。3、串的模式匹配（包括求next和nextval的值）。1、实现静态查找（包括顺序查找、折半查找和插入查找）和动态查找（包括二叉排序树和二叉平衡树）。2、根据输入的数据实现下列内部排序：①直接插入排序、折半插入排序、表插入排序和希尔排序；②快速排序；③简单选择排序和堆排序；④归并排序；⑤链式基数排序。…），当用户输入不正确的选项时，会自动提示输入错误，并返回原菜单要求用户从新输入。其次，每一个子菜单同样有相同的容错能力，对于某些子系统，用户必须先建立线性表才能进行操作，若不先建立线性表，程序同样会回到主菜单，并提示用户建立线性表。 1.2.2 由于用户能输入任意个数字进行演示，并且长度由用户规定。系统规定用户输入的长度应该在1—100以内。长度小于1就没有意义了，但也不能太大，输入长度太大，用户会没有时间去输入线性表的元素。在输入数字时，理论上是表的长度不能小于1。如果小于1，则会提示输入错误，菜单自动返回。此外，在进行某些操作，如插入删除时，用户能在任意位置插入且能在任意位置删除，不过位置必须在线性表的范围之内。若超过线性表的现有长度，那么同样会报错。 1.2.3 在用户界面（DOS界面），用户每执行完一次操作，都会有相应的提示。若用户建立了线性表，则会显示建立成功。若用户进行查找，都会提示查找成功与否。输出地形式是以用户存入线性表的数字为准，一般都是整形。输入其它形式的数字，会自动转化为整形。在串的模式匹配中，模式串和主串的长度输入是整形，规定用户必须输入1—100的数字，否则会提示错误，要求从新输入。而串的值是字符型。必须输入字符，才能得到正确的结果。 1.2.4 数据结构演示系统1主要有四个模块，一个主模块，三个子模块。主模块调用三个函数，SqListfun(),LinkListfun(),Index_SS(),分别指向三个不同功能的子模块。SqListfun()实现上述顺序线性表的算法，LinkListfun()实现上述连是线性表的算法，最后一个Index_SS()实现上述串的模式匹配算法。每一个模块的调用以及返回都是通过用户选择菜单来实现的。这些模块