搜索
《数据结构》课程设计任务书课程设计名称中文：数据结构英文：DataStructures适用专业计算机科学与技术培养层次本科学期2周数1学分1总学时一周一、课程设计目的与要求《数据结构》是计算机专业的核心课程，是一门实践性很强的课程。为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。针对数据结构的课程设计不仅可以加深对课程内容的理解，并且可以通过实践进一步掌握程序设计的技能与方法，学会数据的组织方法和现实世界问题在计算机内部的表示方法，并针对问题的应用背景分析，选择最佳的数据结构和算法。同时通过课程设计，要求学生在完成程序设计的同时能够写出比较规范的设计报告，初步感受软件开发过程的项目管理方法和规范，为进一步学习打下基础。在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，不允许相互抄袭；（3）认真编写课程设计报告。二、课程设计内容与要求（见附件）三、课程设计方式和教学安排1、每人至少选择一题完成，每道题每个班选择人数不能超过5人。2、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝，不允许雷同。3、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。4、设计出的系统要有一个易于使用人机界面。具体时间安排(第19周的星期一至星期五)时间内容星期一选定题目(学号后3位mod题目总数)+1=题目编号,例如:学号尾数为100,题目总数为13，则应选第10题完成100mod13=9,9+1=10)明确题目要求、确定数据结构、算法描述，准备测试数据等星期二至星期四完成要求问题并测试、归档星期五演示回答教师提问文档及程序的整理并提交作品课程设计期间不迟到，不早退，有特殊情况要事先请假，并经有关老师批准方能有效，无故缺席者作旷课处理。进入机房，应遵守机房规定的各项制度。四、考核内容和方式考核内容1、课程设计报告（打印稿）2、课程设计报告（电子版）3、源程序（运行无误，电子版）考核方式指导教师根据课程设计文档、系统演示和学习态度综合考评，并结合学生的动手能力，独立分析解决问题的能力和创新精神进行评分(成绩为优秀、良好、中等、合格、不合格)。五、其他说明关于课程设计报告课程设计报告是对整个设计工作的陈述和总结，是课程设计最终的文字成果。一、报告内容要求数据结构课程设计报告的内容框架：第一部分：引言引言是报告正文的引子，引言在内容上应包括：为什么要进行课程设计？立题的理论或实践依据是什么？拟创新点何在？理论与（或）实践意义是什么？第二部分：系统功能和原始数据（1）原始数据（2）系统功能第三部分：程序总体设计（1）数据结构（2）模块划分和层次结构（3）函数原型清单（4）程序总体框架（5）程序组织第四部分：功能模块函数设计和调试在报告中学生应对所设计的系统进行详细的功能分析，主要模块的算法描述，绘制出系统功能模块图，并具体给出相关的程序流程图（或盒图）。第五部分：程序清单列出整个系统开发的完整程序源代码，并在清单中给出程序中包含的函数等的文字说明。第六部分：课程设计总结对所选题目对应程序的运行情况做详细分析，总结本次设计所取得的经验和收获。如果程序未能全部调试通过，则应分析其原因。第七部分：参考资料在设计和书写报告中所参考的资料列表。二、报告格式要求（一）报告输出顺序1、封皮；2、目录；3、课程设计内容（上述的七个部分）。（二）排版要求课程设计报告要求用A4纸输出，正文一级标题用黑体三号不加粗，二级标题用宋体四号加粗，三级标题及以下标题均采用黑体四号，正文采用宋体小四。行间距采用行距固定值18磅，段落首行缩进两个汉字，段前段后间距为0行距。课程设计报告字数不少于2000字（不包括程序清单和程序结果的部分）。成绩评定标准1、优：按要求完成题目，有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，其中有总体设计思想的论述，有正确的流程图，程序完全实现设计方案，设计方案先进，软件可靠性好。答辩回答问题正确，对系统的演示流畅，源代码解释清晰。2、良：完成设计题目，有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；有完全实现设计方案的软件，设计方案较先进。答辩回答问题较好，对系统的演示较流畅，源代码解释较清晰。3、中：基本完成题目，有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确。答辩回答问题基本正确，对系统的演示基本完成，源代码解释较清楚。4、及格：基本完成题目，有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确。答辩回答问题基本正确，系统演示能够完成。源代码解释基本清楚。5、不及格：没有完成题目的要求，没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。答辩回答问题不正确，系统演示不能够完成，源代码解释不清楚。提交方式及要求每个人以自己的“学号姓名”形式建立文件夹，每个人的文档及源程序存放在自己的文件夹内。答辩时拷贝给指导教师检查、答辩。答辩结束后拷给学习委员，学习委员将全班的设计报告和程序收集齐后交给指导教师。任选教师（课程负责人）签名：教研室主任签名:学院审批：日期：日期：日期：课程设计内容与要求题目1：运动会分数统计[问题描述]：参加运动会的n个学校编号为1-n。比赛分为m个男子项目和w个女子项目，项目编号为1-m和m+1—m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1;还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。[基本要求]：1产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号，名次（成绩）、姓名和得分；2产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。[实现提示]：可以假设n=20,m=30,w=20,姓名长度步超过20个字符，每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。[选作内容]：允许用户指定某项目采取其他名次取法；可以考虑使用图形界面实现系统。要求：存储结构利用链表题目2：迷宫求解问题【问题描述】以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。（1）以递归方式输出一条从入口至出口的通路。（2）使用栈方式输出一条从入口至出口的通路。（3）输出所有具有迷宫的路径【基本要求】编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，··。【测试数据】迷宫的测试数据如下：左上角(1，1)为入口，右下角(8，9)为出口。12345678001000100010001000001101011100100001000001000101011110011100010111000000(2)以方阵形式输出迷宫及其通路。题目3：二叉排序树操作的演示[问题描述]：利用二叉排序树实现一个动态查找表[基本要求]：实现二叉排序树的查找、插入、删除[实现提示]：1）初始：二叉排序树为空树，操作界面给出查找、插入、删除三种操作供选择，每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新二叉排序树的显示。2）二叉排序树的显示可以采用凹入表或采用图形界面画出树形[选作内容]：合并两棵二叉排序树题目4：内部排序算法比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求：（1）从以下常用的内部排序算法至少选取5种进行比较：直接插入排序；折半折入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序。（2）待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。（3）最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。实现提示：主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序，逆序和不同程序的乱序。选作内容：1）增加折半插入排序、二路插入排序、归并排序、基数排序等。2）对不同的输入表长作试验，观察检查两个指标相对于表长的变化关系。还可以对稳定行作验证。题目5：哈夫曼编码和译码利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求:一个完整的系统应具有以下功能：（1）初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，(选做：并将它存于文件hfmTree中）。并显示出每个字符的编码。（2）编码（Encoding）。利用已建好的哈夫曼树（选做：如不在内存，则从文件htmTree中读入），对输入的字符串文本（选做：对文件ToBeTran中的正文）进行编码，（选做：然后将结果存入文件CodeFile中。）并显示在屏幕上。（3）译码（Decoding）。利用已建好的哈夫曼树将输入的代码进行译码（选做：将文件CodeFile中的代码进行译码，结果存入文件TextFile中。），并显示在屏幕上。（4）打印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。要求：利用文件存储输入和输出结果。题目6：建立N个城市的最小代价通讯网络要求：输入N个城市相互之间建立通讯的代价，并存储在文件中；构造一个通讯网络，使得N个城市能够连通并且代价最小。基本要求：设图的顶点数不超过30，边的权值小于100，可以用随机数函数产生。通过顶点数和边的输入，构造出的逻辑示意图；图需要采用两种存储结构，分别利用prim和kruskal算法实现最小生成树，以文本形式输入生成树中的各条边和权值。选作内容；利用堆排序实现选择权值最小的边。题目7：关键路径算法的实现要求：输入一个表示工程活动关系的AOV网，输出其关键路径，并给出完成该工程所需的最短时间。题目8：校园导游程序【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息;以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【进一步完成内容】(1)求校园图的关节点。(2)提供图中任意景点问路查询，即求任意两个景点之间的所有路径。(3)提供校园图中多个景点的最佳访问路线查询,即求途经这多个景点的最佳(短)路径。(4)校园导游图的景点和道路的修改扩充功能。(5)扩充道路信息,如道路类别(车道、人行道等)、沿途景色等级,以至可按客人所需分别查询人行路径或车行路径或观景路径等。(6)扩充每个景点的邻接景点的方向等信息,使得路径查询结果能提供详尽的导向信息。(7)实现校园导游图的仿真界面。题目9:哈希表问题描