数据结构课程设计任务书
适用专业：计算机科学与技术信息安全适用年级：2012级
华中科技大学计算机科学与技术学院
数据结构课程组
2014年5月
数据结构课程设计任务书
数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课，牢固掌握数据结构的基础知识，熟练地运用数据结构的思想与技术方法解决实际应用问题是是本课程学习的基本任务与目标。而课程设计是实现这一学习目标的重要环节和组成部分。通过课程设计的训练，使学生加深对数据结构知识的理解，牢固掌握其应用方法，并合理灵活地解决一定实际问题，增强和提高综合分析问题与解决问题的能力。
本学期课程设计提供三个实际问题或综合实验专题，同学们可根据个人的兴趣偏好，选择其中一个作为自己数据结构课程设计的题目。
题目一英语单词学习助手
?设计目的：掌握线性表、串、查找表等数据结构的物理存储结构与基本算法，通过解决较复杂的实际问题，提高学生对数据结构知识综合运用的技能与实践能力。
?设计内容：以大学英语相关英语文章为语料素材，设计有效的数据结构及其存储结构表示英语单词表，并建立相应的倒排索引，帮助英语学习者在遇到生词时能方便找到生词的相应例句，熟悉其应用语境与地道的用法；设计有效的算法对语料进行清理与分句处理，实现基于索引的快速例句搜索程序。?设计要求：
（1）输入某一个（或若干个）英语单词，要求返回相应的英语例句。
（2）根据单词与语句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次启动程序时不必重新建立索引，只需将索引文件导入内存。
（3）采用图形界面，便于输入单词，例句展现直观，界面布局合理。
?设计提示：按三步进行：（1）准备英语语料。寻找英语文章，可下载英语新闻，托福、GRE文章，或大学英语课文等。（2）处理语料。对语料进行清理、分句、索引、生成字典。需要进行取词干的操作，分句可以直接根据标点符号处理。（3）根据索引进行查询。支持一个或多个查询，基于对词干的处理，当查go、going等时也能够有返回。由于查询的结果是语句，如果直接按照词与文章的关系建立索引，这样需要从文章中找句子，太多的串匹配操作可能导致查询较慢，所以要设计好索引的粒度。
?参考文献：
[1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,1997
[2] 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,1999
[3] URL: https://www.doczj.com/doc/342546056.html,/computing/research/stemming/index.htm
[4] URL: https://www.doczj.com/doc/342546056.html,/wiki/stemming
[5] URL: https://www.doczj.com/doc/342546056.html,/index.php
[6] URL: https://www.doczj.com/doc/342546056.html,/wiki 维基百科：倒排索引
题目二国际跳棋
?内容
设计一个程序实现国际跳棋的人机对弈。国际跳棋的对弈规则可上网查阅。?要求
⑴查阅相关的文献资料；
⑵使用图形界面，要求界面美观，操作方便；
⑶除实现人机对弈功能外，其它功能上可自由发挥。
?参考文献
[1] 严蔚敏,吴伟民. 数据结构(C语言版). 北京: 清华大学出版社,1997
[2] 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 2007.
[3] 蒋浩,郑金华. 国际跳棋游戏中的进化策略.中国人工智能进展(2005).
题目三校园导游
?内容
以本校校园景点为背景，设计一个程序，为来访的客人提供任意景点相关信息的查询。以及规划游览的最佳线路等。
?要求
⑴按校园实际情况处理景点；
⑵能计算出每对景点间的最短距离，以及为从某景点出发,游览所有或选定景点后回到起点，设计一条最短路径；
⑶界面友好、美观，要求用图形界面显示,能直观显示游览线路。
?参考文献
[1] 严蔚敏,吴伟民. 数据结构(C语言版). 北京: 清华大学出版社,1997
[2] 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 2007
[3] 严蔚敏,吴伟民,米宁. 数据结构题集(C语言版). 北京: 清华大学出版社,1999
课程设计要求
1.三个题目任选其一，独立完成，第18周后检查程序。(注意：所用的数据结构与算法应与课程紧密相关；抄袭他人程序者记零分。)
2.各题目的难度系数
⑴英语单词学习助手1.0
⑵国际跳棋1.0
⑶校园导游0.95
3. 按华中科技大学计算机科学与技术学院制定的课程设计报告文本结构及写作规范撰写课程设计报告，报告主要内容应至少涵盖如下方面(以下非报告目录)。
一、问题描述与技术现状分析
二、系统总体设计(含模块结构图)
三、数据结构和算法详细设计
四、C语言程序实现的简要说明
(开发环境、支持包、函数原型与功能及调用关系；全部源程序以电子版提供)
五、程序测试及结果分析
六、复杂度分析
七、软件的用户使用说明
八、特色与不足
九、主要参考文献
4. 报告提交方式
⑴打印《课程设计报告》(A4纸双面打印)；
⑵以班为单位提交光盘(至少含课程设计报告、源程序和脱离开发环境独立运行的目标程序)；
⑶按课表上课程设计结束2-3周后提交。
附：
数据结构课程设计指导用书
——数据结构题集（C语言版），严蔚敏等编著，清华大学出版社
数据结构课程设计参考书
——数据结构（C语言版），严蔚敏、吴伟民编著，清华大学出版社