C/C++《数据结构课程设计》[2023-10-08]

《数据结构课程设计》实验任务书

2023年秋季

一、课程说明
《数据结构课程设计》是配合《数据结构》课程理论教学独立开设的一个重要的设计性、综合性实践教学环节。通过课程设计环节，使学生能综合运用在《数据结构》课程中学习到的理论知识，完成具有一定规模和难度的软件设计与开发任务，在文献检索、算法设计、数据组织和处理、软件编程等方面对学生进行一次全面的训练。

1. 通过课程设计实践，使学生掌握正确的数据组织和数据处理的方法，培养学生综合运用数据结构及其他课程的相关知识与实际问题相结合解决数据组织与分析、数据处理与算法设计等方面能力。
2. 学习从具体应用到数据抽象、从逻辑数据设计到物理数据组织的一般方法，掌握应用数据结构的基本知识解决一般应用问题的规律和方法。
3. 训练软件设计开发的基本技能和方法，为学生后续课程的学习打下坚实的基础。

二、课程设计的要求

1. 选题
   根据本任务书公布的题目，学生自由选题，1人完成一题或2人合作完成一题。1人一题时，由一人独立完成；2人一题时，由二人分工合作，共同完成。
2. 时间安排
   本次课程设计课内学时18学时，课外学时自行安排。
   本次课程设计自课程开始5周内完成，其中前三周为课内学习，每周6学时，需要按照课表的时间安排到教师（实验室）完成，具体上课时间见课表；课内学习期间，课外学习同步进行，自主安排；后两周为课外学习，自主安排。第三周检查课程设计的实验成果并进行答辩，时间另行通知；第五周提交最终成果并评定成绩。
   实验成果检查前须完成编程工作，最终成果提交截止期限前提交最终成果，逾期将影响成绩，甚至取消成绩。
3. 工作规范
   对所承担的任务，按照以下工作规范完成，并在“课程设计报告”中逐一详细描写。
   （1）问题分析和任务定义：查阅文献，了解问题背景及相关知识，根据设计题目的要求，充分分析和理解问题，明确问题要求做什么，目标是什么。
   （2）逻辑设计：对问题中涉及到的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，明确各模块之间的调用关系。
   （3）详细设计：定义相应的存储结构并写出各函数的伪码算法。要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。抽象数据类型的实现要尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据结构存储结构的类型定义，写出函数的算法框架。
   （4）程序编码：根据详细设计的结果选择一种程序设计语言编码实现程序，可分模块逐一实现，源代码中应加入必要的注释和断言，使程序中逻辑概念清晰。
   （5）程序调试和测试：熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来修改程序中的BUG。调试正确后，认真整理源程序和注释，形成格式和风格良好的源程序清单和结果。
   （6）结果分析：程序运行结果包括正确的输入及其输出结果、含有错误的输入和输出结果、算法时间复杂度和空间复杂度分析；对结果反映的现象（尤其是错误的结果）做必要的分析。
   （7）撰写课程设计报告：总结和提升上述过程和步骤，写出结构严谨、表述清楚、符合撰写规范的报告。
   4.纪律要求
   （1）课内学习（上课）严格考勤，不得无故旷课；
   （2）不管是一人一题还是二人一题，都需要独立完成个人负责的任务。在二人一题时，要明确分工，工作量均衡，每人有独立的子任务，不能仅有一人代劳。可以共同讨论、给予或接受他人适当的帮助，但程序代码和课设报告均不得抄袭他人。如有抄袭，不管抄袭者还是被抄袭者均将视情节予以严肃处理。
   5.成果和成绩评定
   （1）成果形式：两种，1）源程序及测试数据，2）课程设计报告。
   （2）成果提交：两种，1）将程序源代码/工程文件、可独立运行的可执行程序、测试数据集、简要操作手册及课程设计报告电子版打包，文件夹名称格式为“专业班级-学号-姓名”,如：XJKX202201-20220711010200-李某某。2）课程设计报告打印为纸质版（A4双面打印，纸质报告中可不打印源代码），然后以班为单位在指定时间（一般在设计课结束后两周内）由学委收齐后交到指导老师。
   （3）成绩评定
   课程设计成绩总分100分，由过程性评价成绩（百分制）和终结性评价(百分制)两部分构成，其中：
   过程性评价：50%。
   考勤：占20%，要求学生准时到实验室开展课程设计工作。
   课程设计报告：占80%，主要考查课程设计报告的质量，含问题定义、需求分析、系统设计、数据结构设计、算法设计、测试分析等方面的内容，及写作质量、格式规范等。
   终结性评价：50%。主要考查课程设计完成的质量，包括项目演示和汇报。
   总评成绩 = 过程性评价（50%）+ 终结性评价（50%）
   附：实验成绩和报告成绩评价标准
   （A）课程设计报告评价标准
   评价标准
   优秀（90~100） 良好（80~89） 及格（60~79） 不及格（0~59）
   能按时提交实验报告，设计方案论述清楚，内容充实，格式规范。 能按时提交实验报告，设计方案论述较清楚，内容较充实，格式较规范。 能按时提交实验报告，设计方案论述较清楚，内容欠充实，格式存在不规范之处。 未按时交作业,设计方案欠合理，表述不清晰，格式欠规范。
   （B）答辩汇报评价标准
   评价标准
   优秀（90~100） 良好（80~89） 及格（60~79） 不及格（0~59）
   设计方案合理，在规定的时间内完成实验任务，结果正确，验收时回答问题清晰。 设计方案较合理，能完成实验任务，结果正确，验收时回答问题较清晰。 设计方案基本合理，能完成实验任务，结果存在少量问题，验收时能回答大部分问题。 设计方案欠合理，实验任务完成情况差，结果存在较多问题，验收时回答问题不清楚。

三、课程设计题目

源码联系UP主 -> https://space.bilibili.com/329101171

题目1：简单计算器

【问题描述】
设计一个简单的计算器，可以实现基本算术表达式、常用函数的计算。
【任务点及要求】
（1）能够以交互式的方式输入数学表达式；
（2）能够对标准整数的四则运算表达式的求值，能正确处理正负数（正负号）、括号（包括单层及多层嵌套的括号），如：
1+2、(1+2)*3、((1+2)3+4)/5、1+(-2)、(+1-2)(-3)
（3）能够对标准浮点数四则运算表达式的求值，能正确处理正负数（正负号）、括号（包括单层及多层嵌套的括号），如：
1.0+2.0、(1.0+2)*3.0、((1+2.0)3.0+4)/5.0、(+1.0-2)(-3.0)
（4）能够计算一个标准整数/浮点数范围内的数的平方、平方根，如：
power(2)、power(3.0)、sqrt(2)、sqrt(3.0)
（5）能够计算指定区间的整数的和，如：
sum(1:5)
（6）能够计算一个标准整数范围内的整数的阶乘，如：
5!
（7）方便易用的交互界面。
【说明】
（1）第（7）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（2）自行设计一些非法表达式，进行程序测试，以保证程序的稳定运行。
【提示】
1.可以参考教材关于中缀表达式、后缀表达式、表达式求值的内容，在此基础上进行扩充。
2.输入一个“表达式”后，应先判断是否为合法的表达式，即是否由合法的数字符、运算符、数学函数名以合法的顺序组成，如果包含非法字符或顺序错误，提示相关信息后终止计算或重新输入。
3.对合法“表达式”，首先将其中的数字串（正负号+连续的数字字符）转换为对应的数值，注意处理整数、浮点数和正负号。
4.正确解释表达式中的运算符或数学函数，实现相应的计算。注意运算符的优先级和括号的处理。
5.数学函数（平方、平方根等）可以以表达式的方式表示在数学表达式中，也可以采用热键（按钮）的方式调用。

题目2：数制转换系统

【问题描述】
十进制数N和其它R进制数之间的转换是计算机实现计算的基本问题，设计一个数制转换系统，实现不同数制的转换功能。
【任务点及要求】
（1）能够以交互式的方式选择不同的数制进行转换；
（2）实现十进制数N和其它R进制数（二进制、八进制、十六进制）之间的转换；
（3）实现R进制数（二进制、八进制、十六进制）之间的转换；
（4）方便易用的交互界面。
【说明】
（1）本题限1人独立完成。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（4）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目3：约瑟夫（Joeph）环

【问题描述】编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
【任务点及要求】
（1）利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。
（2）测试数据：m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
（3）程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。
（4）方便易用的交互界面。
（5）以文件的方式保存数据。
【说明】
（1）本题限1人独立完成。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（4）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目4：病房管理系统

【问题描述】
设计一个病房管理系统，可以实现简单的患者住院管理。
【任务点及要求】
（1）建立学生信息表，登记患者的基本信息。患者信息至少包括：就诊号、姓名、性别、族别、出生年月、联系电话，备用电话，可根据设计需要自行补充其他信息。
（2）建立病房信息表，登记病房的相关信息：楼宇号、楼层号、所属科室、病房ID、床位数、类型（如是否是公寓式等），可根据需要自行补充其他信息。
（3）建立病床信息表，登记病床信息：病床ID、床位号、病房ID、状态等信息，可根据需要自行补充其他信息。
（3）建立入住关系表，登记患者入住病房的对应关系。入住信息至少包括：患者就诊号、住院号、入住科室、病房ID、床铺号，入住时间、退床时间、状态（正常/异常入住、正常/异常退住）、备注（登记一些说明信息），可根据需要自行补充其他信息。
（4）能够以交互式方式增加、删除、修改患者记录。
（5）能够以交互式方式增加、删除、修改病房、病床记录。
（6）能够以交互式方式增加、删除、修改入住记录。
（7）查询功能：能够根据患者的就诊号、姓名、病房ID查询一个或多个患者的信息或患者入住时间、退床时间等；能够查询空余床位、空闲方间、还未分配床位的患者；有异常情况的房间或患者；其他查询功能自行扩充。查询结果可以排序。
（8）统计功能：能够统计各楼宇房间数、床位总数；对当前或指定时间点，能够统计空闲床位数、空闲房间数；能够统计历史入住的患者数、指定的时间期限内入住的患者人数、调换病床的人次；其他查询功能自行扩充。
（9）方便易用的交互界面。
（10）以文件的方式保存数据。
【说明】
（1）本题可以1人独立完成或2人合作完成。一人独立完成时，查询和统计功能可适当减少；二人合作时，需分工合作，工作量均衡，每人独立完成自己的工作，成果要分开，并各自汇报自己负责的内容，不得只由一人代劳。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（9）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目5：图书管理系统

【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【任务点及要求】
（1）建立图书信息表，登记内容包括书号、书名、著作者、出版社、出版日期、现存量和库存量等信息；
（2）对书号建立索引表（线性表）以提高查找效率；
（4）建立借阅者信息表，记录借阅者姓名、借阅证号、有效期限等信息；
（4）建立借阅信息表，记录图书号、借阅证号、借阅时间，归还情况等信息；
（5）能够以交互式方式增加、删除、修改图书记录，包括采编入库、借阅和归还等。
 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
 归还：注销对借阅者的登记，改变该书的现存量。
（6）能够以交互式方式增加、删除、修改借阅证信息。
（7）查询功能：能够根据书名、作者名、出版社等信息查找图书；能够根据借阅者或借阅证号查询该借阅者的借阅情况；其他查询功能自行扩充。查询结果可以排序。
（8）方便易用的交互界面。
（9）以文件的方式保存数据。
【说明】
（1）本题可以1人独立完成或2人合作完成。一人独立完成时，查询和统计功能可适当减少；二人合作时，需分工合作，工作量均衡，每人独立完成自己的工作，成果要分开，并各自汇报自己负责的内容，不得只由一人代劳。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（8）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目6：哈夫曼编码/译码器

【问题描述】
设计一个利用哈夫曼算法的编码和译码系统。
【任务点及要求】
（1）统计字符集及权值：找一篇不少于200个单词的英文文章，分析文章中的每一个字符（区分大小写，不含标点符号）的出现频率。
（2）编码：根据分析结果对文章中的每一个字符进行赫夫曼编码，并将编码原则存储在一个独立的文本文件中。
（3）译码：根据编码原则，对英文文章进行译码，结果存储于一个文本文件。
（4）方便易用的交互界面。
（5）以文件的方式保存数据。
【说明】
（1）本题限1人独立完成。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（4）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目7：校园导览咨询系统

【问题描述】
设计一个校园导览咨询程序,为来访的客人提供各种信息查询服务。
【任务点及要求】
（1）设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
（2）建立场所信息表，记录场所的相关信息。场所信息至少包括：场所ID号、场所名称、类型（教学楼、食堂、公寓式等），可根据需要自行补充其他信息。
（3）建立路径关系表，记录场所之间的路径对应关系。路径信息至少包括：路径ID号、路径起点（或编号）、路径终点（或编号），路径长度（单位米）、路径状态（正常通行、施工维护）、备注（登记一些说明信息），可根据需要自行补充其他信息。
（4）能够以交互式方式增加、删除、修改场所记录
（5）能够以交互式方式增加、删除、修改路径记录。
（6）导览功能：能够根据用户的需求，选择起点和终点，系统自动给出最佳路径（最短路径），同时，可以给出所有备选路径。有异常情况的路径可以备注；其他功能自行扩充。
（7）方便易用的交互界面。
（8）以文件的方式保存数据。
【说明】
（1）本题可以1人独立完成或2人合作完成。一人独立完成时，查询和统计功能可适当减少；二人合作时，需分工合作，工作量均衡，每人独立完成自己的工作，成果要分开，并各自汇报自己负责的内容，不得只由一人代劳。
（2）在以上基本功能的基础上增加新功能的，视情况可加1-10分；
（3）第（7）部分交互界面可以以文本或图形方式实现，如果以图形界面方式实现+5分。
（4）数据以文件形式保存即可，不要求用数据库。

题目8：迷宫游戏

【问题描述】
设计一个走迷宫的游戏。
【任务点及要求】
（1）能够随机生成指定大小的迷宫棋盘。
（2）设计一个宽度优先搜索算法（分支限界算法）完成走迷宫的游戏。
（3）设计一个深度优先搜索算法（回溯算法）完成走迷宫的游戏。
（4）能够设计多种剪枝策略来提高算法的搜索速度和效率。
（5）对所设计的算法进行对比分析。
（6）要以图形方式动态展示算法搜索迷宫路径的过程。
【说明】
（1）参考数据结构教材第三章、第八章的内容，或查阅相关文献资料，了解迷宫的定义和表示方法并予以实现。
（2）查阅文献和相关资料，自行学习迷宫生成的方法。
（3）本题可以1人独立完成或2人合作完成。一人独立完成时，任务（1）生成迷宫可以不做，代之以预先定义好的迷宫，但迷宫规模和结构要有代表性，不能过于简单；二人合作时，需分工合作，工作量均衡，每人独立完成自己的工作，成果要分开，并各自汇报自己负责的内容，不得只由一人代劳。
（4）开展多人对抗，看谁的算法快，可加5分。
（5）第（6）部分界面可以以文本模拟图形的方式实现，也可以以纯图形的方式实现。
（6）生成的迷宫可以以文件形式保存。保存的迷宫文件可以重复打开使用。

源码联系UP主 -> https://space.bilibili.com/329101171