《算法与数据结构》课程设计题目及要求(2015)

1《算法与数据结构》课程设计2目录一、课程性质与教学目的...............................................................................................................3二、课程设计要求.........................................................................................................................31.分组设计...........................................................................................................................32.题目选择...........................................................................................................................33.考核标准...........................................................................................................................34.提交材料...........................................................................................................................35.时间安排...........................................................................................................................3三、开发过程要求...........................................................................................................................4四、课程设计报告要求规范...........................................................................................................4五、课程设计题目：.......................................................................................................................4（一）课程设计1....................................................................................................................41.一元稀疏多项式计算器...........................................................................................42.joseph环...................................................................................................................53.表达式求值...............................................................................................................54.集合基本运算...........................................................................................................65.二叉链表结构的相关函数库...................................................................................6（二）课程设计2....................................................................................................................61.校园导游咨询...........................................................................................................62.设计散列表实现电话号码查找系统.......................................................................73.宿舍管理查询软件...................................................................................................74.学生信息管理问题...................................................................................................75.捉羊计划...............................................................................................................8附件1：封面格式............................................................................................................................9附件2：分组登记表..............................................................................................................10附件3：考核表......................................................................................................................113一、课程性质与教学目的《算法与数据结构》课程设计的目的是利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不算太复杂却具有综合性的问题。在解决实际问题时，可能涉及并运用多个方面的知识，具有较强的综合性，这就需要进行一些综合性的设计练习，来提高分析和解决实际应用问题的能力。通过课程设计，在建立问题模型、构造求解算法、设计数据结构、编写程序代码及上机调试等方面得到全面的锻炼，从而能更深刻地理解《算法与数据结构》的精髓，包括，熟练掌握数据结构的一些常用算法和经典算法；熟练的运用常用的算法和经典算法解决具有一定规模和复杂程度的实际问题；熟练掌握分析问题和解决问题的方法，合理选择数据结构，学会分析算法的优劣，分析算法的复杂度。二、课程设计要求1.分组设计按小组方式进行组织设计，小组成员为4~6人，班级内自由组合，并确定小组组长，分组名单汇总到各班班长，最后交给老师。2.题目选择每个小组至少选择2个题目，其中：在课程设计1中任选1道题，在课程设计2中任选1道题。3.考核标准总的要求：组内每位同学，一起协商承担的任务，每人都要参与设计和编程工作，不能只负责撰写论文。评分组成：1）组长对组内成员学习态度和承担设计任务的评价；2）课程设计完成的效果，采用现场演示和答辩的方式；3）课程设计报告的撰写质量；4.提交材料每小组依据所在小组选择的课程设计题，独立撰写课程设计报告，分题目依次撰写。不允许相互间抄袭，否则均以零分计算。提交材料：纸质的课程设计报告。5.时间安排1)布置设计任务：第13-14周2)提交分组名单：布置设计任务后一周内，班长汇总后将分组结果及分组任务表交给老师；3）设计与撰写：上机时间为课内的上机时间和课外自己找时间完成。4）提交截止日期：第19周周五4三、开发过程要求1.调查，从用户的角度出发，系统应如何设计，实现那些功能才能满足用户需求。2.分析，对调查所得的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。3.设计与开发，设计系统界面并编辑实现各个功能的代码。4.调试，在设计完成后，调试系统运行的状态，修改完善系统，然后进行测试。四、课程设计报告要求规范课程设计报告应包括如下几个部分：（需求分析、概要设计、详细设计、测试数据、测试分析、用户使用手册、收获及体会；附源程序清单）1.需求分析：描述要求编程解决的问题。2.系统设计：a)设计并描述实现系统所需的所有数据结构并进行说明。b)给出系统总体结构图。c)给出各个模块流程图并描述其功能。3.测试：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。给出程序的测试结果系统截图，并分析运行结果。4.用户使用手册：向用户说明如何使用本系统。5.收获及体会。6.附源程序清单：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。五、课程设计题目：（一）课程设计11.一元稀疏多项式计算器【问题描述】设计一个一元稀疏多项式简单计算器。【基本要求】一元多项式简单计算器的基本功能是：5（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列指指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。【实现提示】用带头结点的单链表存储多项式，多项式的项数存在头结点。2.joseph环【问题描述】编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。【测试数据】m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,（正确的出列顺序应为6,1,4,7,2,3,5）。【实现提示】程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。3.表达式求值【问题描述】表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。【基本要求】以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值。【扩展要求】：