数据结构专业课程设计题目.doc

数据结构课程设计一、教学目标和要求为了配合数据结构课程教学，使学生能更深刻地领会数据结构这门课程关键性，特开设此课程设计；编写部分在特定数据结构上算法，经过上机调试，愈加好掌握多种数据结构及其特点，同时提升处理计算机应用实际问题能力。二、课程设计要求1、选好题目：每题一人，每班每个题目最多许可三人选做，必需确保每题有两人选做，学习委员将选题情况先统计上交。 2、独立思索，独立完成：课程设计中各任务设计和调试要求独立完成，碰到问题能够讨论，但不能够拷贝。相同题目标同学，算法思绪能够相同，不过程序和课设汇报不能相同。3、做好上机准备：每次上机前，要事先编制好准备调试程序，认真想好调试步骤和相关环境设置方法，准备好相关文件。4、设计关键点：需求分析：在该部分中叙述总共多个模块，每个模块功效要求。系统设计总体设计：定义某个数据结构抽象数据类型及其它算法功效说明。具体设计：在此定义存放结构，每个部分算法设计说明（提议描述算法采取步骤图）。编码实现各个算法实现源程序，对每个题目要有对应源程序（每个功效模块采取不一样函数实现）。源程序要根据程序规则来编写，要结构清楚，关键函数关键变量，关键功效部分要加上清楚程序注释。程序能够运行，要有基础容错功效，尽可能避免出现操作失误时出现死循环。调试分析给出实现功效一组或多组测试数据，程序调试后，将根据此测试数据进行测试结果列出来。时间复杂度分析，每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想。课设总结：课程设计过程收获、碰到问题、碰到问题处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在课程设计过程中对数据结构课程认识等内容。5、实现结果必需进行检验和演示；程序源代码和程序说明文件必需上交，作为考评内容一部分；（上交时文件夹取名规则为：“课设题目（*设计完成）”，如“资源管理系统设计和实现（张三设计完成）”。该文件夹下包含三个目录：“源代码”、“可实施文件”、“张三_课程设计汇报”。由学习委员按要求时间统一上交）。6、汇报提交时间: 待定。形式: 纸介质(要求B5纸张打印，加封皮)和电子文档。三、考评方法和内容依据课程设计过程中学生学生态度、题目完成情况、课程设计汇报书质量和回复问题情况等根据10%、40%、30%、20%加权综合打分。成绩评定实施优异、良好、中等、及格和不及格五个等级。评分标准：优异：答辩+汇报优异良好：答辩+汇报通常 或 汇报优异+没答辩中等：答辩+汇报稍差 或 汇报通常+没答辩及格：汇报稍差+没答辩 或 答辩但被发觉不是自己编写实现不及格：汇报几乎全部是代码 或 类同部分达成70% 课设汇报装订次序以下：封面-任务书-目录-设计任务-需求分析-系统设计-编码实现-调试分析-课设总结-谢辞-参考文件-附录（可选）等；汇报总页数控制在102页内，汇报中不能全是代码，汇报中代码控制在150行内。四、课程设计题目1、运动会分数统计2、集合并、交和差运算程序3、长整数加法运算4、一元多项式计算器5、车厢调度问题6、文章编辑7、识别广义表头或尾演示8、哈夫曼树及其编码9、校园导游咨询10、地图着色问题11、内部排序算法比较12、哈希表设计和实现13、火车售票系统14、图书管理系统15、用户消费积分管理系统16、产品进销存管理系统五、数据结构课程设计具体内容要求：全部采取数据结构课程中线性结构、树型结构、图型结构、集合结构中一个，不能用数据库。1、运动会分数统计问题描述：参与运动会n个学校编号为1n。比赛分成m个男子项目和w个女子项目，项目编号分别为1m和m+1mw。因为各项目参与人数差异较大，有些项目取前五名，得分次序为7，5，3，2，1；还有些项目只取前三名，得分次序为5，3，2。写一个统计程序产生多种成绩单和得分报表。基础要求： 每个项目结束时，输入前三名或前五名项目编号、运动员姓名、校名和名次（成绩）；产生各学校成绩单，内容包含各学校所取得每项成绩项目号、名次（成绩）、姓名和得分，并统计各学校总分；产生团体总分报表，内容包含校号、男子团体总分、女子团体总分和团体总分。2、集合并、交和差运算程序问题描述：编制一个能演示实施集合并、交和差运算程序。基础要求：集合元素限定为小写字母符a.z ，集合大小n27。集合输入形式为一个以回车符为结束标志字符串，串中字符次序不限，且许可出现反复字符或非法字符，程序应能自动滤去。输出运算结果字符串中将不含反复字符或非法字符。演示程序以用户和计算机对话方法实施。3、长整数加法运算 问题描述： 设计一个实现任意长整数进行加法运算演示程序。 基础要求： 1利用链表实现长整数存放，每个结点含一个整型变量。2任何整型变量范围是-(215-1)(215-1)。3输入和输出形式根据中国对于长整数表示习惯，每四位一组,组间用逗号隔开。 如：-2345，6789，3211；4、一元多项式计算器问题描述：设有一元多项式Am(x) 和Bn(x). Am(x) = A0+A1x1+A2x2+A3x3+ +Amxm Bn(x) = B0+B1x1+B2x2+B3x3+ +Bnxn试求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。基础要求： 首先判定多项式是否稀疏；分别采取次序和链式结构实现；结果M(x)中无反复阶项和无零系数项；要求输出结果升幂和降幂两种排列情况。5、车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所表示)入口处车厢系列编号依次为1，2，3，n。设计一个程序,求出全部可能由此输出长度为n 车厢系列。基础要求：设计一个程序，求出由一个编号依次为1，2，、，n车厢序列可能产生全部出栈系列。利用双向栈存放结构实现调度站和输出序列这两个栈空间共享。 对于每个输出序列演示出全部操作序列改变过程 。6、文章编辑问题描述：输入一页文字，能够统计出文字、数字、空格个数。基础要求：静态存放一页文章，每行最多不超出80个字符，共N行。分别统计出其中英文字母和空格数及整篇文章总字数。统计某一字符串在文章中出现次数，并输出该次数。 删除某一子串，并将后面字符前移。存放结构使用线性表，分别用多个子函数实现对应功效。7、识别广义表头或尾演示问题描述：写一个程序，建立广义表存放结构，演示在此存放结构上定义广义表求头、求尾操作序列结果。基础要求：组成广义表正当字符：小写或大写字母、空白字符、圆括号和逗号，且设广义表原子为单个字母。以用户和计算机对话方法实施，广义表建立方法为边输入边建立；分解操作进行方法为，输入整个命令串，然后分步显示每一个操作结果。输入过程中自动滤去正当字符以外其它字符，并能在输入步当初输入对应提醒信息。8、哈夫曼树及其编码问题描述：设计一个利用哈夫曼算法编码系统，反复地显示并处理以下项目，直到选择退出为止。基础要求：初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好哈夫曼树生成哈夫曼编码；输出其哈夫曼树及哈夫曼编码；设字符集及频度以下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 9、校园导游咨询问题描述：设计一个校园导游程序，为来访客人提供多种信息查询服务。基础要求：设计华东交通大学校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、介绍等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点相关信息查询。为来访客人提供图中任意景点问路查询，即查询任意两个景点之间一条最短简单路径。10、地图着色问题问题描述：已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用颜色不一样，并确保使用颜色最少。基础要求：地图采取图型数据结构，每个地级市为一个节点，边表示对应两个地级市相邻。设计着色算法，确保邻接点不是同一个颜色。演示程序以用户和计算机对话方法进行。11、内部排序算法比较问题描述：试经过随机数据比较各算法关键字比较次数和关键字移动次数，以取得直观感受。基础要求：最少采取三种方法实现上述问题求解（提醒，可采取方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。待排序表表长大于100，其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据作比较；比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）。最终对结果作出简单分析，包含对各组数据得出结果波动大小解释。12、哈希表设计和实现问题描述：设计哈希表实现电话号码查找系统。基础要求：设每个统计有下列数据项：电话号码、用户名、地址；从键盘输入各统计，分别以电话号码和用户名为关键字建立哈希表；采取一定方法处理冲突；查找并显示给定电话号码统计；查找并显示给定用户名统计。13、火车售票系统问题描述：经过此系统能够实现售票、退票、车票剩下情况查询等功效。每张车票包含车次、座位信息。基础要求：在售票、退票、查询剩下票等步骤中，全部必需显示出车票信息，即车次、座位情况。为简单起见，在此假设全部出售车票均为同一车次车票。退票时，必需是车站售出车票才能退，不然视为无效票，不能退票。14、图书管理系统问题描述：设计一个计算机管理系统完成图书管理基础业务。基础要求：每种书登记内容包含书号、书名、著作者、现存量和库存量；对书号建立索引表（线性表）以提升查找效率；系统关键功效以下：采编入库：新购一个书，确定书号后，登记到图书帐目表中，假如表中已经有，则只将库存量增加；借阅：假如一个书现存量大于0，则借出一本，登记借阅者书证号和归还期限，改变现存量；归还：注销对借阅者登记，改变该书现存量。15、用户消费积分管理系统问题描述：针对用户消费情况，进行用户管理，依据用户消费积分对用户实施不一样程度打折优惠。基础要求：采取一定存放结构进行用户信息存放；对用户信息能够进行修改、删除、添加；能够依据消费情况进行用户积分计算；依据积分情况实施不一样程度打折优惠；16、产品进销存管理系统问题描述：针对某一个行业库房产品进销存情况进行管理。基础要求：采取一定存放结构对库房货物及其数量进行分类管理；能够进行产品类添加、产品添加、产品数量添加；能够查询库房每种产品总量、进货日期、销出数量、销售时间等。