C/C++《数据结构》课程设计指导书[2023-06-15]
《数据结构》课程设计指导书
适用专业：计算机2022级
编写人：李玉龙
2023年5月
《数据结构》课程设计指导书
一、设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
二、设计内容与任务
根据教材选择下列题目中任选一题作为课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目如下：
课程设计题一：四则变量表达式计算
设计目的：
1.掌握结构体的用法以及采用结构体定义线性表。
2.学会利用线性表保存变量名及其代入值。
3.理解堆栈在四则运算中的应用价值。
4.自学第五章字符串的基本操作并用于子串分割，实现更复杂的四则运算。
设计内容：
输入一组单字符变量名及其对应数值存入线性表，再输入一个关于这些变量的四则运算表达式，代入其数值计算表达式的最终结果并显示。
设计要求：
1.单字符变量名与取值必须成对输入某结构体元素，再建立这些元素构成的线性表。
2.变量名与取值输入后立即显示变量信息，如“A=3,B=6，……”。
3.四则运算表达式必须以一个完整的字符串输入后，计算得出最终结果并显示。比如，运行阶段“(A+B)*3 回车”后，换行显示“=27”。
4.思考：若为四则运算增添函数计算功能，使其支持绝对值函数abs()、平方根函数sqr()、较大值函数max()、较小值函数min()等，表达式如A+abs(C+D)+max(E,F)，应如何处理整个计算过程？
5.实现前3个要求，作品得分80分；实现要求4，作品得分90分或以上。
源码
https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111
课程设计题二：哈夫曼树及其应用
设计目的：
1.熟悉树的各种存储结构及其特点。
2.掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。
3.深刻理解哈夫曼编码在数据压缩方面的应用价值。
设计内容：
发一封内容为“AABECAB …… DEFF”(共长 20 字符,字符集为:A、B、C、D、E、F)的电报报文,实现哈夫曼编码完成报文压缩节省带宽占用。
设计要求：
1.统计报文中各字符出现频次，并为字符集建立哈夫曼树。
2.构造哈夫曼树要求同层叶子结点权值从左到右、从小到大。
3.每个字符进行哈夫曼编码,并求出字符集平均编码长度。
4.建立两个文本文件hufcode.txt和compress.txt，分别用于存放字符的哈夫曼编码表和报文压缩内容，hufcode.txt中的每一行存放格式为“字符+空格+哈夫曼编码，最后一行存放报文长度值；compress.txt存储内容为电报报文中各字符哈夫曼编码按位拼接得到的字节码序列，举例：若A、B的哈夫曼编码分别为110和1111，报文“AAB”哈夫曼编码拼接得到的字节码为11011011、11000000，其中最后一个字节的冗余空间默认补0。这些字节码以字节为单位存入compress.txt文件，表现形式为一串乱码。
5.根据hufcode.txt指定的编码表读取compress.txt解压恢复报文原文，输出显示解码结果。
6.实现前3个要求，作品得分80分；实现要求4和5，作品得分90分或以上。
源码
https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111
课程设计题三：哈希表及其应用
设计目的：
1.熟练掌握哈希表相关算法,能够利用它们解决数据查询或加密问题。
2.能够利用哈希表实现数据加密，并采用哈希碰撞方法实现破解。
设计内容：
假设某系统前端登录采用4个英文字母组成的密码，为防止密码明文被窃取，后台系统验证模块采用长度m=6哈希表进行加密、存储和验证，请采用除p留余法和二次探测法将密码明文中各个英文字母按输入顺序散列到哈希表中，其余空白单元默认为0，最终得到6字节的不可逆杂文作为加密后的密码。
设计要求：
1.密码中不能重复出现相同的字母。
2.模拟登录输入明文密码，代入哈希算法产哈希序列与已存储的不可逆杂文比对，实现密码校验，显示验证是否匹配成功。
3. 假设针后台加密存储的不可逆杂文被泄露，根据已获得的加密杂文进行模拟破解，采用哈希碰撞方法检测出所有可能验证通过的密码明文。
4.优化碰撞算法，利用最少碰撞次数破解所有可能碰撞成功的密码明文。
5.实现前2个要求，作品得分80分；实现要求3和4，作品得分90分或以上。
源码
https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111
课程设计题四：冒泡排序、快速排序、堆排序的性能比较
设计目的：
1.熟练掌握冒泡排序、快速排序、堆排序算法的差异，给出时间复杂度与空间复杂度的优劣对比。
2.了解堆排序性能改进的原理以及应用场合。
设计内容：
调用随机函数生成一组无序关键字，采用三种方法分别进行排序，统计并输出排序过程消耗的比较次数、移动次数、额外空间，观察三种排序算法的优劣对比。
设计要求：
1.采用随机函数生成三种不同规模（如100、1000、10000）的无序关键字序列。
2.统计三种算法在以上三种不同规模下需要的比较次数、移动次数、额外空间，进行特定算法在不同规模下的横向对比，观察其复杂度变化趋势，并在三种不同算法之间对比变化趋势。
3.根据各算法的复杂度预测规模N=50000时大致的比较次数、移动次数、额外空间，并随机生成该规模的无序关键字序列，统计实际的比较次数、移动次数、额外空间进行对比，观察预测值是否大致准确。
4.完成要求1和要求2，作品得分80分；完成要求3，作品得分100分。
源码
https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111
三、设计要求
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后续上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。
2、设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;
4、每位同学需提交可独立运行的程序，进行现场答辩或提交答辩视频；
5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（源码、插图、表格不计在内）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。
程序和课程设计报告电子版和打印稿统一提交。
四、设计的一般步骤与方法
- 问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？
- 逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；
- 详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；
- 程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；
- 程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；
- 结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；
- 编写课程设计报告。
五、设计报告
设计报告书封面和正文格式按说明书模板要包含：题目及任务分析、思路及算法设计、调试分析、测试结果、附录和设计心得体会等。
六、成绩考核
成绩考核依据学生的过程表现和设计成果综合评定，按百分制评定，包括：
1、文档检测：（20%）：根据学习态度、诚信纪律问题，按源码与说明书查重结果评分；课设说明书相似度超过50%或源码相似度超过80%的，一律返工。
2、设计报告（20%）：按设计报告的完成质量评分（设计报告的具体要求参见模板），提交word文档请先另存为doc文件，查重时拒绝检测docx文件；
源码命名规范:计算机大类220X-学号-姓名-数据结构课设-选题1.cpp
说明书命名规范: 计算机大类220X-学号-姓名-数据结构课设-课设说明书.doc
视频命名规范: 计算机大类220X-学号-姓名-数据结构课设-答辩视频.mp4
说明书一定要打开OFFICE软件另存为doc文件，直接修改文件后缀名无效！！！！！
3、作品展示与答辩：（60%）：根据作品实际完成的质量、答辩情况考核评分。上机时间无法按时答辩的，可录制答辩视频（时长3分钟以内）提交。