#2012级数据结构实训指导书

1、数据结构课程设计指导书说明：本指导书适用于 2012级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. 设计报告，

4、占总成绩 30%3答辩，占总成绩10%4.出勤，占总成绩10%五、实习过程项目实训过程分为以下六个阶段，各阶段如下：1、功能分析（0.25天）2、模块划分及总体设计（0.75天）3、数据结构定义、详细设计（0.5天）4、编码（2.5天）5、测试修订（1天）6、答辩（1天）合计6天。六、备注：1. 选题：（1）以下给出的课程设计题目分为四类，学生可以从任何一类中选择一个题目，并做 好相关准备（注意每一题限报人数）；（2）时间安排：从2013年12月21日一一12月26日，共6天，每天从上午 8: 30 11 ： 30,下午 从 14： 0017： 002. 功能完成及检测（1）要求独立完成规定的

5、工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以 不及格计。（2）鼓励同学们充分发挥主观能动性，结合所选课题，独立思考，努力钻研，勤于实 践，勇于创新，在完成题目的基本要求外，尽量完善程序，提高程序的可读性、 健壮性等，完成好的同学，给以适当加分。课程设计题目1管理类1.1 电子中英文词典难度：中需求功能表序号功能需求简述1启动画面设计友好的启动画面，并在启动画面中为用户提供选择菜单， 包括【单词查询】、【词典管理】和【使用说明】三个主要功 能选项。2词典管理要求：词条内容应保存在文件中。1. 添加词条2. 删除词条3. 更新词条3单词查询要求：能根据输入的中/英文词条进行检索1. 精确查

6、询2. 模糊查询：将匹配单词列出。可以将这些匹配的单词以列 表的方式显示，使用户能够通过输入编号，快速进入词 条。如果用户输入汉字，则能根据汉字列出对应的英文单 词，实现通过汉字关键词查询的功能。4使用说明提供必要的使用说明项目要求：1. 第一阶段要求用控制台使用程序实现该项目需求;2. 项目基本要求：(1) 实现启动画面及选择菜单。(2) 实现简单的文本交互界面。(3) 实现词典管理的功能。(4) 能够按照英文单词检索词条。3. 选做功能及模块：加入按照中文关键词检索词条的功能。4. 在非常漂亮的完成了第一阶段的所有任务之后，如果团队想进一步提高软件的交互性，选择使用 VC+的MFC框架来改

7、造控制台使用程序至Windows桌面使用程序;主要技术点：数组，结构体，链表。技术难点：中文关键词检索团队配置：4人其他：无。1.2 停车场管理系统难度：中问题描述：设计一个停车场管理系统，模拟停车场的运作。（1）要求以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理；（2）要求处理的数据元素包括如下数据项：汽车“到达”或“离去”信息、汽车牌照及“到达”或“离去”的时刻;功能需求表：序号功能需求简述1启动画面设计友好的启动画面2停车管理车辆到达，首先判断停车场是否满1）若有空位置，停车，并输出汽车在停车场内停车位置，并记录停车时间。2）若没有空位，请用户选择离开还是在便道上等待a

8、）右离开，不做任何操作，b）若等待，加入便道上等待队列（若队列满，回到a）,并记录便道上的停车位置；3离开管理1）若在停车场内离开，就输出汽车在停车场内停留的时间和 应交纳的费用，并允许便道上队列前面的汽车进入停车场；2）若是便道上的车辆离开，则不收费。4查询管理提供停车场空位查询及统计信息查询等。5统计管理完成该停车场的一些信息统计功能（如每天到达/离开的车次，停车总时数、每天的停车费用等）。项目要求：1. 人机交互界面友好，对用户的非法输入要有一定的判断及提示；2 .可根据基本要求，对系统的功能作进一步的完善；3. 在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分;

9、主要技术点：数组，链表，队列。技术难点：队列思想团队配置：4人其他：无。1.3 运动会排名系统难度：难需求功能表序号功能需求简述1界面显示界面能够依次显示如下四个选项：查看排名、查询、更 新、帮助。2查看排名1. 按奖牌数排名，按国家获得的金牌数列出排名列表，显示国家获得奖牌情况。2. 按项目排名，按成绩排序该项目的运动员。3按积分排名，以国家积分排名。积分规则是一块金银铜依次是20、16、12分，项目第4名到第10名依次获得9分到3分，其余选手均获得 1分。3查询1. 按国家查询，查看该国家的运动员及奖牌情况。2. 按项目查询，查看该项目的排名情况。3. 按运动员查询，查看运动员信息。4更新

10、1.添加、修改、删除项目信息。2添加、修改、删除国家信息。3添加、修改、删除运动员信息。4更新后自动重新生成各项排名。5帮助提供必要的帮助信息。项目要求：1. 第一阶段要求用控制台使用程序实现该项目需求；2. 实现友好的操作界面，使用户能根据界面提示进入相应的操作模块；3. 基本的功能和模块需要实现：显示界面，按奖牌数排名、按项目排名、按国家查询、 按项目查询、更新项目信息、帮助。通过项目列表中记录的参和运动员及其国家等信 息，生成国家信息列表。4. 选做功能及模块：按积分排序、更新国家信息和运动员信息能同步更新相关列表；5. 在非常漂亮的完成了第一阶段的所有任务之后，如果团队想进一步提高软件

11、的交互性，选择使用 VC+的MFC框架来改造控制台使用程序至Windows桌面使用程序；6. 可根据项目完成情况，在数据输入部分，添加利用文件导入的功能；在数据输出部 分，添加数据导出到文件的功能；7. 关于项目加分：在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相 应个人加分；在很好地利用控制台使用程序完成项目后，如团队使用Windows桌面使用程序实现，将给团队和相应个人加分。主要技术点：数组，队列，链表。技术难点：链表的使用、查找。团队配置：4人1.4 银行营业厅业务模拟系统难度：难问题描述：设计一个银行业务模拟系统，模拟银行营业厅的运作。(1) 业务流程为：客户到达营业听，

12、选择业务类型并取号，然后等待被窗口叫号； 客户被叫号后，到对应窗口办理业务，完成后离开。客户包括普通客户、VIP 客户、团体客户三种。设该营业厅一共有四个窗口。其中有三个窗口为普通窗口，一个窗口是 VIP客户窗口，当有 VIP客户时办理 VIP客户业务，若当前无 VIP客户，则视为普通窗口。普通窗口专为普通客户和团体客户开放。要求以 队列模拟客户到达后的排队等待和办理完业务的离开过程。通过终端读入的输 入数据序列进行模拟管理。(2) 客户所办理的业务包括存款、取款、转账、开户等，每种业务的办理时间不 同。每个窗口业务员为客户办理不通业务时时间也不全相同。设客户是随机到 达银行营业厅。(3) 设

13、银行工作时间从 8： 30AM- 17 : 30PM。功能需求表:序号功能需求简述1启动画面设计友好的启动画面。2排号管理客户到达，若客户所办业务能在营业时间内办完，进行取号， 否则，不予办理。取号过程中，客户需要选择所要办理的业务类型。根据前面办 理和等待的人数给客户排号。并为客户输出排号数，至泌时 间，前面需要等待的人数(以及可能需要等待的时间)，需要办理的业务类型。2叫号、显示官理每个窗口均有显示和叫号功能。在办理业务时，显示当前办理 业务客户的号数，若当前客户业务办理完成，显示在某一窗口 办理业务的下一位客户号数。特别，VIP窗口当无 VIP客户时，应该显示和呼叫普通客户号 数。3业务

14、办理管理模拟不冋业务的办理时间，通过随机函数根据每位客户的业务 类型生成相应办理业务的时间。4统计、查询管理可以根据客户的排号查询每一位客户的到达时间、离开时间和 办理业务的类型。统计每种业务办理的客户数，每个窗口办理的客户数及其效 率，并按照每个窗口办事效率对窗口业务员进行排序，统计以 天为单位。以文件形式保存以上相关信息。项目要求:1 .根据以上描述的流程和功能要求，灵活使用相关数据结构只是模拟实现系统;2 .人机交互界面友好，对用户的非法输入要有一定的判断及提示；3. 可根据基本要求，对系统的功能作进一步的完善；4. 在很好完成必做模块的前提下，如又实现如下加分项：（1）若能给出每位客户

15、排号时的预计等待时间，（2） 天中客户在银行逗留的平均时间，（3）若能形象模拟整个银行营业厅业务流程，将给团队及相应个人加分。主要技术点：队列技术难点：队列思想团队配置：4人其他：无。2通信类2.1邮件发送程序客户端-C或C+技术难度：难需求描述：SMTP协议是用于发送电子邮件的主要通信协议，是C语言进行网络编程时经常都会使用到的基础协议之一。邮件发送客户端程序要求使用C语言socket通信来完成SMTP协议，同时结合路由（图）等知识实现邮件发送程序的客户端使用，通过该程序能够向远程 的SMTP服务器发送电子邮件的请求，并发送到指定的电子邮箱之中。项目要求：本程序需要完成的功能较多，因此在实现

16、时建议通过以下两个阶段来完成。第一阶段：只要求通过 dos窗口实现简单文本邮件的发送，具体的要求如下：程序启动后录入SMTP服务器地址；录入SMTP服务器用户名和密码；录入收件人地址和抄送人地址（允许录入多个，中间以分号分隔）；录入邮件主题；录入邮件内容完成后发送邮件；邮件发送成功后系统提供邮件发送成功；第二阶段：要求能够实现发送MIME格式邮件或利用 Win32编程将程序升级为桌面使用程序，进入第二阶段必须满足以下条件：必须是在充分理解 SMTP协议的基础上； 必须是在充分理解 MIME格式的基础上； 利用C语言将发送的内容格式化为MIME格式；可以首先考虑只实现 MIME格式的一部分格式化

17、需求； 升级桌面使用程序必须对 Win32 API有一定的理解和掌握；整个邮件发送程序必须首先要对SMTP协议有比较全面的理解，并且对如何使用socket进行网络通信要有较为熟悉的使用，同时还需要对base64编码有所了解，并利用C语言实现对其编码。SMTP协议可以参考附件中的 SMTP协议说明； 主要技术点：C语言基础、字符串处理、指针、socket编程、图、SMTP协议、base64编码；技术难点：socket编程、SMTP协议的理解、base64编码团队配置：4人其它：无2.2电子邮件管理程序-C或C+技术难度难 需求描述：POP3协议是实现邮件服务器邮件管理的基础协议之一，和SMTP协

18、议一起构成了整个电子邮件的基础。电子邮件管理程序要求利用C语言的socket通信，运用指针、栈等知识，实现POP3协议管理远程电子邮件服务器系统中的电子邮件，并执行POP3协议中规定的服务项目。项目要求：POP3协议规定的服务项目较多，因此在实现时建议采用以下两个阶段来完成： 第一阶段：只要求通过 dos窗口来实现POP3协议中规定的服务项目；启动程序后录入 POP3服务器地址、用户名、密码、建立和邮件服务器的连接。 系统显示允许执行的 POP3服务项目（获取邮件列表、删除邮件、获取邮件）； 系统根据执行的服务，执行相应的服务；如果选择获取邮件，将获取的邮件显示在dos窗口中；第二阶段：要求能

19、够通过 Win32 API将程序升级为 Windows桌面使用程序，进入第二 阶段必须满足以下条件：必须熟悉 Win32 API的基础知识；能够创建 Win32窗体并能够利用 Win32进行子窗口的创建和管理；POP3协议较SMTP协议更为复杂和实现更多的功能，因此对于POP3协议的理解是完成项目首先需要解决的问题，同时如何利用C语言的socket编程来实现相关协议也是开发过程中的一大考验； 主要技术点：C语言基础、字符串处理、指针、socket编程、栈、SMTP协议、base64编码；技术难点：socket编程、POP3协议理解、base64编码；团队配置：5人其它：无2.3安全文件传输-C

20、语言难度：难需求描述：运用C语言，结合数据结构的指针、链表、堆栈等知识，使用CS的模式，实现文件的传输客户端的功能要求有传输文件、下载文件、设置属性等，三个功能的详细需求如下： 传输文件：向服务端传送本地文件；下载文件：从服务端下载文件；设置属性：设置服务端的相关信息，如地址、端口等； 项目要求：1. 在第一阶段采用dos来完成以下功能；2. 需要对录入数据进行有效性检查；3. 在完成以上功能的基础上可以选择完成以下需求：a）将界面修改为 Windows界面（可以考虑使用 MFC或Win32）b）用 C+写;4. 在完成选择功能后，将提高小组的项目成绩；主要技术：C语言基础、指针、链表、排序、

21、文件操作、队列、栈等；技术难点：socket编程、文件流操作、 base64编码；团队配置：4人其它说明：无2.4网络聊天室-C+和MFC难度：难需求描述：使用C/S模式，实现聊天室的功能主要功能有：服务器端：监听客户端的连接，发送并接收消息；客户端：连接服务器端，发送并接收消息；客户端设置属性：设置相关信息，如服务器IP地址、端口等;项目要求：1. 界面使用 Windows界面（可以考虑使用 MFC或Win32）；2. 连接有效性检查；3. 能相互发送消息主要技术：C+语言基础；socket编程；指针；队列等 技术难点：socket 编程、MFC;团队配置：4人其它说明：3游戏类3.1连连看

22、技术难度：难需求描述：1）12*12图形界面（12行，12列）2）使用QT作为开发框架3）软件上能够提供良好的用户界面，具有良好的运行效率，能快速的。4）发现自我的目的，有良好的扩充性，容易转入其他系统运行。5）系统能够提供友好的用户界面，使操作人员的工作量最大限度的减少；6）系统具有良好的运行效率，能够得到提高生产率的目的；7）系统应有良好的可扩充性，可以容易的加入其它系统的使用；8）平台的设计具有一定的超前性，灵活性，能够适应企业生产配置的变化；9）通过这个项目可以锻炼队伍，提高团队的开发能力和项目管理能力。项目要求：连连看游戏算法较为复杂，要实现的功能如下：该题目涉及界面设计，根据实际情

23、况可采用QT环境进行开发；建议利用QT工具构造 Windows环境下的桌面游戏界面；（老师在实训时会对该工具进行介绍）启动游戏后，初始程序界面，加载图库；启动游戏后，根据算法随机初始放置图片位置；游戏过程中，判断鼠标点击位置，传入后台代码；游戏过程中，判断两次点击是否可以消除算法；游戏过程中，判断是否消除图片已经结束；游戏结束后，显示当前玩家的统计信息，可以选择重新开始；主要技术点：C+语言基础、QT开发库、二维数组、指针技术难点：游戏的算法问题、二维数组的灵活使用 团队配置：4人其它：3.2五子棋技术难度：难需求描述：国际比赛规则规定：对局中如黑方出现禁手，白方应立即指出禁手点，黑方即负。女

24、口白方在黑方出现禁手后，又落一步白子，黑棋禁手则不成立了。所以在有禁手”的房间里，如果黑方出现禁手，白方应立即按下禁手按钮。程序会判黑方负。如果这时白方又在棋盘上落一子，黑棋禁手则不成立了。为了简化用户对”禁手按钮的使用，也有”走禁手就输”和禁手不能落子规则的房间，顾名思义不多介绍。虽然采取了禁手的限制，黑棋先行仍有优势，黑棋 仍可以必胜。所以如果用户是高段位的棋手，或者想成为高手一定要选择国际上比赛选用的比赛标准，即“三手交换，五手两打”项目要求：俄罗斯方块游戏算法较为复杂，要实现的功能如下：启动游戏后，初始界面，18*18的交叉网格线，用户使用白棋，计算机使用黑棋；游戏过程中，根据白棋当前

25、情况判断黑棋落子点；游戏过程中，后台逻辑代码和界面分离；游戏过程中，判断用户按键位置；游戏过程中，按空格键暂停和恢复游戏；游戏过程中，按 Esc键退出游戏；游戏结束后，显示当前玩家的统计信息，可以选择重新开始；利用C语言的I/O实现游戏的保存和读取；该题目涉及界面设计，根据实际情况可采用QT环境进行开发；建议利用QT工具构造 Windows环境下的桌面游戏界面；（老师在实训时会对该工具进行介绍）主要技术点：C语言基础、二维数组、指针技术难点:游戏的算法问题、二维数组的灵活使用团队配置:4人其它：无3.3俄罗斯方块技术难度：难需求描述：俄罗斯方块是一个很多人都玩过的游戏，游戏开始后一个用于摆放小

26、型正方形的平面虚拟场地，其标准大小：行宽为10，列高为20，以每个小正方形为单位；一组由4个小型正方形组成的规则图形，英文称为Tetromino，中文通称为方块，共有 7种，分别以S、Z、L、J、I、0、T这7个字母的形状来命名；通过设计者预先设置的随机发生器不断地输出单个方 块到场地顶部，以一定的规则进行移动、旋转、下落和摆放，锁定并填充到场地中。每次摆放 如果将场地的一行或多行完全填满，则组成这些行的所有小正方形将被消除，并且以此来换取 一定的积分或者其他形式的奖励。而未被消除的方块会一直累积，并对后来的方块摆放造成各 种影响；如果未被消除的方块堆放的高度超过场地所规定的最大高度（并不一定

27、是20或者玩家所能见到的高度），则游戏结束。项目要求：俄罗斯方块游戏算法较为复杂，要实现的功能如下：启动游戏后，左边显示游戏平面虚拟场地，右边显示下一方块和分数等统计信息；游戏过程中，录入左、右控制下落方块的左右位置；游戏过程中，录入向上键旋转下落方块；游戏过程中，按下键则下落方块下落到底部；游戏过程中，按空格键暂停和恢复游戏；游戏过程中，按 Esc键退出游戏；在消除一定数量的方块后，游戏速度自动提高，增加游戏难度；游戏结束后，显示当前玩家的统计信息，可以选择重新开始；利用C语言的I/O实现游戏的保存和读取；该题目涉及界面设计，根据实际情况可采用QT环境进行开发；建议利用QT工具构造 Wind

28、ows环境下的桌面游戏界面；（老师在实训时会对该工具进行介绍）俄罗斯方块游戏的算法较为复杂，需要首先考虑好游戏中的算法问题，再利用C语言实现其中的算法。主要技术点：C语言基础、二维数组、指针技术难点：游戏的算法问题、二维数组的灵活使用团队配置：4人其它：无4算法类4.1表达式计算器难度：难需求描述:用户输入一个完整的四则运算表达式，程序能够求出表达式的值。要求能够处理括号、正 负符号、加减乘除四则运算等。基本要求：1. 第一阶段要求用控制台使用程序实现该项目需求；2. 项目基本要求：括号处理、正负符号处理、加减乘除四则运算以及浮点数在表达式中的处理。主要技术点：数组、栈、二叉树。技术难点：表达式合法性检查、栈的使用、优先级别的判定团队配置：4人其他：无。4.2哈夫曼编码/译码器难度：中 需求描述：哈夫曼编码在通讯、网络、数据压缩、图像处理中的得到广泛使用，在一个通讯系 统中，采用图形界面设计哈夫曼树，对通讯信息进行编码和解码。基本要求：（1）打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，建立一棵哈夫曼树，利用已经建好的哈夫曼树，对每个字符进行编码，结果存入文件CodeFile中，并将文件CodeFile显示在终端上。（2） 利用编码规则，将文章进行变慢，写入文件C