《2024级数据结构实训指导书(2024年12月).docx》由会员分享，可在线阅读，更多相关《2024级数据结构实训指导书(2024年12月).docx（18页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计指导书说明：本指导书适用于2024级1-4班一、课程设计的目的、要求和任务本课程设计是为了协作数据结构课程的开设，通过设计完整的程序，使学生驾驭数据结构的应用、算法的编写、类C语言的算法转换成程序并用上机调试的基本方法。1 .课程的目的（1）使学生进一步理解和驾驭课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的运用方法。（2）使学生驾驭软件设计的基本内容和设计方法，并培育学生进行规范化软件设计的实力。（3）使学生驾驭运用各种计算机资料和有关参考资料，提高学生进行程序设计的基本实力；2 .课程的基本要求与任务（1） 巩固和加深对数据结构基本学问
2、的理解，提高综合运用课程学问的实力。（2）培育学生自学参考书籍，查阅手册、图表和文献资料的实力。（3） 通过实际课程设计，初步驾驭简洁软件的分析方法和设计方法。（4） 了解与课程有关的工程技术规范，能正确说明和分析试验结果。（5） 题目具有足够的工作量。二、课程设计的一般步骤：1 .选题与搜集资料：每人选择一题（每题有几个同学选），进行课程设计课题的资料搜集。2 .分析与概要设计：依据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。3 .程序设计：运用驾驭C/C+语言编写程序，分工实现各个模块功能。4 .调试与测试：调试程序，并记录测试状况
3、。5 .完成课程设计报告。6 .验收与评分：指导老师对每个同学的开发的系统进行综合验收，并由学院考核小组进行随机抽查评分。三、课程设计成果的规范（详见文档模板）课程设计成果应包括如下3个部分：1 一个小组一份设计文档，其中包括：a）系统功能模块图（有流程图附上）b）系统定义的数据结构；C）系统设计的主要功能函数及功能简介d）项目组成员的分工状况2 .每个同学一份实训报告，其中包括：a）问题描述b）基本要求C）系统分析与设计d）测试数据及结果e）总结3 .附录：源程序清单四、成果评定标准学生成果由以下几个方面进行评定：1 .学生编写的实际软件和运行结果，占总成果50%；2 .设计报告，占总成果3
4、0%3 .答辩，占总成果10%4 .出勤，占总成果10%五、实习过程项目实训过程分为以下六个阶段，各阶段如下：1、功能分析（0.25天）2、模块划分及总体设计（0.75天）3、数据结构定义、具体设计（0.5天）4、编码（2.5天）5、测试修订（1天）6、答辩（1天）合计6天。六、备注：1 .选题：（1） 以下给出的课程设计题目分为四类，学生可以从任何一类中选择一个题目，并做好相关打算（留意每一题限报人数）；（2） 时间支配：从2024年12月21日12月26日，共6天，每天从上午8：3011：30,下午从14：0017：002 .功能完成及检测（1） 要求独立完成规定的工作任务，不得弄虚作假，
5、不准抄袭他人内容，否则成果以不及格计。（2） 激励同学们充分发挥主观能动性，结合所选课题，独立思索，努力钻研，勤于实践，勇于创新，在完成题目的基本要求外，尽量完善程序，提高程序的可读性、健壮性等，完成好的同学，给以适当加分。课程设计题目1管理类1.1 电子中英文词典难度：中需求功能表:序号功能需求简述1启动画面设计友好的启动画面，并在启动画面中为用户供应选择菜单，包括【单词查询】、【词典管理】和【运用说明】三个主要功能选项。2词典管理要求：词条内容应保存在文件中。1 .添加词条2 .删除词条3 .更新词条3单词查询要求：能依据输入的中或文词条进行检索1 .精确查询2 .模糊查询：将匹配单词列出
6、。可以将这些匹配的单词以列表的方式显示，运用户能够通过输入编号，快速进入词条。假如用户输入汉字，则能依据汉字列出对应的英文单词，实现通过汉字关键词查询的功能。4运用说明供应必要的运用说明项目要F1 .第一阶段要求用限制台应用程序实现该项目需求;2 .项目基本要求：(1)实现启动画面及选择菜单。(2)实现简洁的文本交互界面。(3)实现词典管理的功能。（4）能够依据英文单词检索词条。3 .选做功能及模块：加入依据中文关键词检索词条的功能。4 .在特别美丽的完成了第一阶段的全部任务之后，假如团队想进一步提高软件的交互性，选择运用VC+的MFC框架来改造限制台应用程序至Windows桌面应用程序；主要
7、技术点：数组，结构体，链表。技术难点：中文关键词检索团队配置：4人其他：无。1.2 停车场管理系统难度：中问题描述：设计一个停车场管理系统，模拟停车场的运作。（1） 要求以队列模拟车场外的便道，依据从终端读入的输入数据序列进行模拟管理；（2） 要求处理的数据元素包括如下数据项：汽车“到达”或“离去”信息、汽车牌照及“到达”或“离去”的时刻；功能需求表:序号功能需求简述1启动画面设计友好的启动画面2停车管理车辆到达，首先推断停车场是否满1）若有空位置，停车，并输出汽车在停车场内停车位置，并记录停车时间。2）若没有空位，请用户选择离开还是在便道上等待a）若离开，不做任何操作，b）若等待，加入便道上
8、等待队列（若队列满，回到a）,并记录便道上的停车位置；3离开管理1）若在停车场内离开，就输出汽车在停车场内停留的时间和应交纳的费用，并允许便道上队列前面的汽车进入停车场；2）若是便道上的车辆离开，则不收费。4查询管理供应停车场空位查询及统计信息查询等。5统计管理完成该停车场的些信息统计功能（如每天到达/离开的车次，停车总时数、每天的停车费用等）。项目要求：1 .人机交互界面友好，对用户的非法输入要有肯定的推断及提示；2 .可依据基本要求，对系统的功能作进一步的完善；3 .在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分;主要技术点：数组，链表，队列。技术难点：队列思想团队
9、配置：4人其他：无。1.3运动会排名系统难度：难需求功能表:序号功能需求简述1界面显不界面能够依次显示如下四个选项：查看排名、查询、更新、帮助。2查看排名L按奖牌数排名，按国家获得的金牌数列出排名列表，显示国家获得奖牌状况。2 .按项目排名，按成果排序该项目的运动员。3 .按积分排名，以国家积分排名。积分规则是一块金银铜依次是20、16、12分，项目第4名到第10名依次获得9分到3分，其余选手均获得1分。3查询1 .按国家查询，查看该国家的运动员及奖牌状况。2 .按项目查询，查看该项目的排名状况。3 .按运动员查询，查看运动员信息。4更新1 .添加、修改、删除项目信息。2 .添加、修改、删除国
10、家信息。3 .添加、修改、删除运动员信息。4 .更新后自动重新生成各项排名。5帮助供应必要的帮助信息。项目要求：1 .第一阶段要求用限制台应用程序实现该项目需求；2 .实现友好的操作界面，运用户能依据界面提示进入相应的操作模块;3 .基本的功能与模块须要实现：显示界面，按奖牌数排名、按项目排名、按国家查询、按项目查询、更新项目信息、帮助。通过项目列表中记录的参加运动员及其国家等信息，生成国家信息列表。4 .选做功能及模块：按积分排序、更新国家信息和运动员信息能同步更新相关列表；5 .在特别美丽的完成了第一阶段的全部任务之后，假如团队想进一步提高软件的交互性，选择运用VC+的MFC框架来改造限制
11、台应用程序至Windows桌面应用程序；6 .可依据项目完成状况，在数据输入部分，添加利用文件导入的功能；在数据输出部分，添加数据导出到文件的功能；7 .关于项目加分：在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；在很好地利用限制台应用程序完成项目后，如团队运用WindoWS桌面应用程序实现，将给团队和相应个人加分。主要技术点：数组，队列，链表。技术难点：链表的运用、查找。团队配置：4人1.4银行营业厅业务模拟系统难度：难问题描述：设计一个银行业务模拟系统，模拟银行营业厅的运作。(1)业务流程为：客户到达营业听，选择业务类型并取号，然后等待被窗口叫号；客户被叫号后，到
12、对应窗口办理业务，完成后离开。客户包括一般客户、VIP客户、团体客户三种。设该营业厅一共有四个窗口。其中有三个窗口为一般窗口，一个窗口是VIP客户窗口，当有VlP客户时办理VIP客户业务，若当前无VIP客户，则视为一般窗口。一般窗口专为一般客户和团体客户开放。要求以队列模拟客户到达后的排队等待和办理完业务的离开过程。通过终端读入的输入数据序列进行模拟管理。(2)客户所办理的业务包括存款、取款、转账、开户等，每种业务的办理时间不同。每个窗口业务员为客户办理不通业务时时间也不全相同。设客户是随机到达银行营业厅。(3) 设银行工作时间从8：30AM-17：30PM,功能需求表:序号功能需求简述1启动
13、画面设计友好的启动画面。2排号管理客户到达，若客户所办业务能在营业时间内办完，进行取号，否则，不予办理。取号过程中，客户须要选择所要办理的业务类型。依据前面办理和等待的人数给客户排号。并为客户输出排号数，到达时间，前面须要等待的人数(以及可能须要等待的时间)，须要办理的业务类型。2叫号、显示管理每个窗口均有显示和叫号功能。在办理业务时，显示当前办理业务客户的号数，若当前客户业务办理完成，显示在某一窗口办理业务的下一位客户号数。特殊，VIP窗口当无VlP客户时，应当显示和呼叫一般客户号数。3业务办理管理模拟不同业务的办理时间，通过随机函数依据每位客户的业务类型生成相应办理业务的时间。4统计、查询
14、管理可以依据客户的排号查询每一位客户的到达时间、离开时间和办理业务的类型。统计每种业务办理的客户数，每个窗口办理的客户数及其效率，并依据每个窗口办事效率对窗口业务员进行排序，统计以天为单位。以文件形式保存以上相关信息。项目要求：1 .依据以上描述的流程和功能要求，敏捷应用相关数据结构只是模拟实现系统；2 .人机交互界面友好，对用户的非法输入要有肯定的推断及提示；3 .可依据基本要求，对系统的功能作进一步的完善；4 .在很好完成必做模块的前提下，如又实现如下加分项：（1）若能给出每位客户排号时的预料等待时间，（2）一天中客户在银行逗留的平均时间，（3）若能形象模拟整个银行营业厅业务流程，将给团队
15、及相应个人加分。主要技术点：队列技术难点：队列思想团队配置：4人其他：无。2通信类2.1 邮件发送程序客户端-C或C+技术难度：难需求描述：SMTP协议是用于发送电子邮件的主要通信协议，是C语言进行网络编程时常常都会运用到的基础协议之一。邮件发送客户端程序要求运用C语言socket通信来完成SMTP协议，同时结合路由（图）等学问实现邮件发送程序的客户端应用，通过该程序能够向远程的SMTP服务器发送电子邮件的恳求，并发送到指定的电子邮箱之中。项目要求:本程序须要完成的功能较多，因此在实现时建议通过以下两个阶段来完成。第一阶段：只要求通过dos窗口实现简洁文本邮件的发送，具体的要求如下：程序启动后
16、录入SMTP服务器地址；令录入SMTP服务器用户名和密码；令录入收件人地址和抄送人地址（允许录入多个，中间以分号分隔）；录入邮件主题；令录入邮件内容完成后发送邮件；令邮件发送胜利后系统供应邮件发送胜利；其次阶段：要求能够实现发送MlME格式邮件或利用Win32编程将程序升级为桌面应用程序，进入其次阶段必需满意以下条件：令必需是在充分理解SMTP协议的基础上；令必需是在充分理解MIME格式的基础上；令利用C语言将发送的内容格式化为MlME格式；令可以首先考虑只实现MIME格式的一部分格式化需求；升级桌面应用程序必需对Win32API有肯定的理解和驾驭；整个邮件发送程序必需首先要对SMTP协议有比
17、较全面的理解，并且对如何运用SOCket进行网络通信要有较为熟识的运用，同时还须要对base64编码有所了解，并利用C语言实现对其编码。SMTP协议可以参考附件中的SMTP协议说明；主要技术点：C语言基础、字符串处理、指针、SOCket编程、图、SMTP协议、base64编码;技术难点：SoCket编程、SMTP协议的理解、base64编码团队配置：4人其它：2.2电子邮件管理程序C或C+技术难度难需求描述：POP3协议是实现邮件服务器邮件管理的基础协议之一，与SMTP协议一起构成了整个电子邮件的基础。电子邮件管理程序要求利用C语言的SOCket通信，运用指针、栈等学问，实现POP3协议管理远
18、程电子邮件服务器系统中的电子邮件，并执行POP3协议中规定的服务项目。项目要求：POP3协议规定的服务项目较多，因此在实现时建议采纳以下两个阶段来完成：第一阶段：只要求通过dos窗口来实现POP3协议中规定的服务项目； 启动程序后录入POP3服务器地址、用户名、密码、建立与邮件服务器的连接。 系统显示允许执行的PoP3服务项目（获得邮件列表、删除邮件、获得邮件）；令系统依据执行的服务，执行相应的服务； 假如选择获得邮件，将获得的邮件显示在dos窗口中；其次阶段：要求能够通过Win32API将程序升级为WindoWS桌面应用程序，进入其次阶段必需满意以下条件： 必需熟识Win32API的基础学问
19、； 能够创建Win32窗体并能够利用Win32进行子窗II的创建和管理；POP3协议较SMTP协议更为困难和实现更多的功能，因此对于POP3协议的理解是完成项目首先须要解决的问题，同时如何利用C语言的SOCket编程来实现相关协议也是开发过程中的一大考验；主要技术点：C语言基础、字符串处理、指针、SOCket编程、栈、SMTP协议、base64编码；技术难点：SoCkel编程、POP3协议理解、base64编码；团队配置：5人其它:2.3 平安文件传输-C语言难度：难需求描述：运用C语言，结合数据结构的指针、链表、堆栈等学问，运用CS的模式，实现文件的传输客户端的功能要求有传输文件、下载文件、
20、设置属性等，三个功能的具体需求如下： 传输文件：向服务端传送本地文件； 下载文件：从服务端下载文件； 设置属性：设置服务端的相关信息，如地址、端口等；项目要求：1 .在第一阶段采纳dos来完成以下功能；2 .须要对录入数据进行有效性检查；3 .在完成以上功能的基础上可以选择完成以下需求：a）将界面修改为Windows界面（可以考虑运用MFC或Win32）b）用C+写；4 .在完成选择功能后，将提高小组的项目成果；主要技术：C语言基础、指针、链表、排序、文件操作、队列、栈等;技术难点：SOCket编程、文件流操作、base64编码；团队配置：4人其它说明：无2.4 网络闲聊室-C+和MFC难度：
21、难需求描述：运用C/S模式，实现闲聊室的功能主要功能有： 服务器端：监听客户端的连接，发送并接收消息; 客户端：连接服务器端，发送并接收消息： 客户端设置属性：设置相关信息，如服务器IP地址、端Ii等;项目要求，1 .界面运用WindOWS界面（可以考虑运用MFC或Win32）；2 .连接有效性检查；3 .能相互发送消息主要技术：C+语言基础；SOCket编程；指针；队列等技术难点：SoCket编程、MFC；团队配置：4人其它说明：3嬉戏类4 .1连连看技术难度：难需求描述：1）12*12图形界面（12行，12列）2）运用QT作为开发框架3）软件上能够供应良好的用户界面，具有良好的运行效率，能
22、快速的。4）发觉自我的目的，有良好的扩充性，简洁转入其他系统运行。5）系统能够供应友好的用户界面，使操作人员的工作量最大限度的削减；6）系统具有良好的运行效率，能够得到提高生产率的目的；7）系统应有良好的可扩充性，可以简洁的加入其它系统的应用；8）平台的设计具有肯定的超前性，敏捷性，能够适应企业生产配置的改变;9）通过这个项目可以熬炼队伍，提高团队的开发实力和项目管理实力。项目要求：连连看嬉戏算法较为困难，要实现的功能如下：该题目涉及界面设计，依据实际状况可采纳QT环境进行开发；建议利用QT工具构造WindOWS环境下的桌面嬉戏界面；（老师在实训时会对该工具进行介绍）启动嬉戏后，初始程序界面，
23、加载图库;启动嬉戏后，依据算法随机初始放置图片位置;嬉戏过程中，推断鼠标点击位置，传入后台代码;嬉戏过程中，推断两次点击是否可以消退算法；令嬉戏过程中，推断是否消退图片已经结束；令嬉戏结束后，显示当前玩家的统计信息，可以选择重新起先;主要技术点：C+语言基础、QT开发库、二维数组、指针技术难点：嬉戏的算法问题、二维数组的敏捷应用团队配置：4人其它：3.2五子棋技术难度：难需求描述：国际竞赛规则规定：对局中如黑方出现禁手，白方应马上指出禁手点，黑方即负。如白方在黑方出现禁手后，又落一步白子，黑棋禁手则不成立了。所以在“有禁手”的房间里，假如黑方出现禁手，白方应马上按下禁手按钮。程序会判黑方负。假
24、如这时白方又在棋盘上落一子，黑棋禁手则不成立了。为了简化用户对“禁手按钮的运用，也有“走禁手就输和“禁手不能落子”规则的房间，顾名思义不多介绍。虽然实行了禁手的限制，黑棋先行仍有优势，黑棋仍可以必胜。所以假如用户是高段位的棋手,或者想成为高手肯定要选择国际上竞赛选用的竞赛标准，即“三手交换，五手两打”项目要求：俄罗斯方块嬉戏算法较为困难，要实现的功能如下:启动嬉戏后，初始界面，18*18的交叉网格线，用户运用白棋，计算机运用黑棋；令嬉戏过程中，依据白棋当前状况推断黑棋落子点；嬉戏过程中，后台逻辑代码与界面分别；嬉戏过程中，推断用户按键位置；令嬉戏过程中，按空格键暂停和复原嬉戏；令嬉戏过程中，按
25、ESC键退出嬉戏；令嬉戏结束后，显示当前玩家的统计信息，可以选择重新起先；令利用C语言的I/O实现嬉戏的保存和读取；令该题目涉及界面设计，依据实际状况可采纳QT环境进行开发；建议利用QT工具构造WindoWS环境下的桌面嬉戏界面；（老师在实训时会对该工具进行介绍）主要技术点：C语言基础、二维数组、指针技术难点：嬉戏的算法问题、二维数组的敏捷应用团队配置：4人其它：无3.3俄罗斯方块技术难度：难希求描述：俄罗斯方块是一个许多人都玩过的嬉戏，嬉戏起先后一个用于摆放小型正方形的平面虚拟场地，其标准大小：行宽为10,列高为20,以每个小正方形为单位；一组由4个小型正方形组成的规则图形，英文称为Tegm
26、inO,中文通称为方块，共有7种，分别以S、Z、L、J、I、0、T这7个字母的形态来命名；通过设计者预先设置的随机发生器不断地输出单个方块到场地顶部，以肯定的规则进行移动、旋转、下落和摆放，锁定并填充到场地中。每次摆放假如将场地的一行或多行完全填满，则组成这些行的全部小正方形将被消退，并且以此来换取肯定的积分或者其他形式的嘉奖。而未被消退的方块会始终累积，并对后来的方块摆放造成各种影响；假如未被消退的方块堆放的高度超过场地所规定的最大高度（并不肯定是20或者玩家所能见到的高度），则嬉戏结束。项目要求：俄罗斯方块嬉戏算法较为困难，要实现的功能如下：令启动嬉戏后，左边显示嬉戏平面虚拟场地，右边显示
27、下一方块和分数等统计信息；令嬉戏过程中，录入左、右限制下落方块的左右位置； 嬉戏过程中，录入向上键旋转下落方块； 嬉戏过程中，按下键则下落方块下落究竟部； 嬉戏过程中，按空格键暂停和复原嬉戏；令嬉戏过程中，按ESC键退出嬉戏；令在消退肯定数量的方块后，嬉戏速度自动提高，增加嬉戏难度；令嬉戏结束后，显示当前玩家的统计信息，可以选择重新起先；令利用C语言的I/O实现嬉戏的保存和读取；该题目涉及界面设计，依据实际状况可采纳QT环境进行开发；建议利用QT工具构造WindoWS环境下的桌面嬉戏界面；（老师在实训时会对该工具进行介绍）令俄罗斯方块嬉戏的算法较为困难，须要首先考虑好嬉戏中的算法问题，再利用C
28、语言实现其中的算法。主要技术点：C语言基础、二维数组、指针技术难点：嬉戏的算法问题、二维数组的敏捷应用团队配置：4人其它：4算法类4.1 表达式计算器难度：难需求描述：用户输入一个完整的四则运算表达式，程序能够求出表达式的值。要求能够处理括号、正负符号、加减乘除四则运算等。基本要求：1 .第一阶段要求用限制台应用程序实现该项目需求；2 .项目基本要求：括号处理、正负符号处理、加减乘除四则运算以及浮点数在表达式中的处理。主要技术点：数组、栈、二叉树。技术难点：表达式合法性检查、栈的应用、优先级别的判定团队配置：4人其他：无。4.2 哈夫曼编码/译码器难度：中需求描述：哈夫曼编码在通讯、网络、数据
29、压缩、图像处理中的得到广泛应用，在一个通讯系统中，采纳图形界面设计哈夫曼树，对通讯信息进行编码和解码。基本要求：（1）打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，建立一棵哈夫曼树，利用已经建好的哈夫曼树，对每个字符进行编码，结果存入文件CodeFiIe中，并将文件CodeFiIe显示在终端上。（2）利用编码规则，将文章进行变慢，写入文件COdePrint中。（3）利用已建好的哈夫曼树将文件CodeFiIe中的代码进行译码，结果存入文件TeXtFiIe中，并输出结果。项目要求：1 .对限制台的输入须要肯定的容错实力，给出肯定的提示信息；2 .对输出的结果进行肯定的美化，
30、做到内容清楚、易懂。主要技术点：哈夫曼编码、文件的输入、文件的输出。团队配置：3人。4.3 关键路径问题难度：难问题描述：当一项工程划分为若干个子任务或活动后，人们不仅须要确定这些活动的先后次序，而且须要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理地组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程供应保证，这就是关键路径问题。关键路径问题相应的网称为Ae）E网，其中：顶点表示事务，边表示活动，边上的权表示活动持续的时间。基本要求：（1）对一个描述工程的AOE网，建立其存储结构；（注：数据的输入可以是键盘输入或文件输入两种方式）（2）推断该AoE
31、网是否能够顺当进行。（3）若该工程能顺当进行，输出完成整项工程至少须要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。（注：结果的输出可以是屏幕输出和文件输出两种方式）项目要求：1 .对于限制台界面的输入须要增加容错实力，对于输入给出完整的提示信息，使得操作者能够轻松操作；2 .对输出的结果进行肯定的美化，做到内容清楚、易懂；主要技术点：AOE网、关键活动的最早发生时间、最迟发生时间。团队配置：3人。3 .4八数码难题难度：难希求描述：在一个33的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。基本要求:1.从文件读取八数码的初始状态和终止状态。如:2831231648475(a)765(b)2 .确定搜寻策略，对八数码难题的全部状态空间图进行搜寻，找出最短移动方案。3 .界面要求：有合理的提示和人机交互。主要技术点：图的存储、状态空间搜寻算法技术难点及关键算法：状态空间构造与搜寻（回溯法、分支限界法、A*算法）团队配置：3人。
