数据结构课程设计（论文）任务书--每章算法及常规基本应用的演示系统.docVIP

课程设计(论文)任务书 信息 　学　　院　　计算机　专　　业　2007—02--12 班　　 一、课程设计(论文)题目　每章算法及常规基本应用的演示系统　 　 二、课程设计(论文)工作自 2009 年6月 22 日起至 2009 年 7月 5 日止。 三、课程设计(论文) 地点: 5-402 四、课程设计(论文)内容要求： 1．本课程设计的目的 1、?使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。1.?分析题目，查阅相关资料；2.?算法设计、数据结构设计；3.?编写代码并调试；4.?完成课程设计报告。算法思想数据结构测试数据(论文)评审意见 （1）完成问题分析（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （2）算法思想数据结构测试数据 目 录 一、 课程设计目的 4 二、课程设计内容 4 （一）、课程设计的题目及简介 4 （二）、设计说明 5 （三）、程序流图 6 （四）、部分程序清单 6 Ⅰ.线性表ADT基本操作 6 Ⅱ.链表ADT基本操作 9 Ⅲ.堆栈ADT基本操作 10 Ⅳ.队列ADT基本操作 12 Ⅴ.字符串ADT基本操作 13 Ⅶ.二叉树ADT基本操作 15 Ⅷ.MGraph图ADT基本操作 17 三、测试数据 20 （一）、从键盘输入测试数据及运行结果 20 （二）、从文件输入测试数据及运行结果 21 四、课程设计总结（写出心得和总结） 23 五、参考文献 23 课程设计目的 数据结构（C++描述）是计算机很重要一门很重要的基础性课程，它不仅涉及到软件程序设计，而且还涉及到计算机硬件（特别是编码理论、存储装置和存储方法等），无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。因此可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。由此，我觉得有必要大好基础并学会应用所学，为将来学习编译原理、操作系统、数据库系统及其他大型应用程序设计做好基础。 同时，为了掌握、巩固本学习所学数据结构的一些重要算法和获取实现大型程序设计架构思想，也为了将整个数据结构课程各个知识点有条不紊的联系起来，由此我选择了“每章算法及常规基本应用的演示系统”这一任务，同时附上了一些数据结构的基本应用算法（如堆栈中任意数制转换、表达式求值、括号匹配、迷宫游戏等）。 另一方面，我用的计算机语言是C++，在程序当中用到了C++ template泛型编程这一技术的精华（比如说模板特例化）,一定程度上巩固了、加深了C++程序设计思想及技术。 二、课程设计内容 （一）、课程设计的题目及简介 课程设计题目：每章算法及常规基本应用的演示系统。 程序设计源文件所实现的功能，是用C++模板泛型技术实现课本上每章ADT（所学及教师要求的）算法实现，主要包括：线性表、链表、堆栈、队列、二叉树、图的建立、插入、删除、销毁等其他需求的基本算法实现。 另外，演示系统中有一些“数据结构”的基本应用，例如链表和线性表的“纸牌游戏”，堆栈的堆栈中任意数制转换、表达式求值、括号匹配、迷宫游戏等。 （二）、设计说明 本次课程设计的主线是每章ADT算法演示系统，从中穿插的程序功能是所定义的数据结构类型的基本应用（比如说堆栈的表达式求值、迷宫游戏，线性表、链表的纸牌游戏，二叉树类型数据结构的动态管理等）。 另外演示系统设计的理念是要更好地引导试验者知道某操作的功能，及其演示系统界面友好。 下图是进入演示系统的界面，用户可通过选择输入1-8来查看本演示系统所定义数据结构的基本操作与功能，并在查看完毕后能够返回到这一界面（清屏与按键延时功能），按0键便可退出整个演示系统。 比如按下‘3’键，便有Stack的基本应用演示界面： 本次课程设计是在赵海霞老师的教导下，由07级信息学院计算机科学与技术（2）班 罗桂林设计，谢谢赵老师！ （三）、程序流图 演示系统程序流程示意图 （四）、部分程序清单 Ⅰ.线性表ADT基本操作 /*线性表ADT操作：线性表建立、插入、删除、逆置、排序、查找、遍历、合并两线性表、销毁，适用数据类型：整形、字符型、浮点型、自定义的数据类型*/ /*线性表的建立及销毁操作*/ templateclass T //不带参数构造函数 ListT::List() { elem=new T; if(!elem) { std: