第一部分：软件工程课程设计说明

软件工程是用工程、科学和数学的原则与方法研制、维护计算机软件的有关技术及管理方法，研究领域包括软件工程的目标、原则和软件工程方法学，构成软件工程的3个组成要素是方法、工具和过程。

软件工程方法指的是完成软件工程项目的技术手段，包括支持项目计划和估算、系统和软件需求分析、软件设计、编码、测试和维护的各种方法核技术；软件工具是指用来辅助软件开发、维护和管理的软件，包括项目管理工具、配置管理工具、分析和设计工具、程序设计工具、测试工具、维护工具及集成化的计算机辅助软件工程（CASE）环境等；软件过程是指软件生存周期中的一系列相关活动，包括软件开发活动所需要完成的一系列任务和完成这些任务的工作步骤。

在计算机专业的教学计划中，软件工程一直是重要的主干课程之一。由ACM和IEEE－CS颁布的计算机教程CC2001（Computer Curriculum2001）规定，软件工程是21世纪计算机学科14个核心知识单元之一，占有6个核心专题，在计算机专业的整个课程体系中具有非常重要的地位，是计算机科学与技术专业学生必修的专业课之一。

由课程的性质决定该门课程必须以实际上机作为基础，以便于进行软件开发的综合实践。考虑到实际情况，此次课程设计的内容为：把原来“数据结构课程设计”中的各个题目按照软件工程的规范重新进行实现。所以最终文档名称为“数据结构课程设计报告书”。下面的文档有一部分是你们原来数据结构课程设计任务书中的内容，现在按照我们当时的英文教材进行了一定的改动。本次设计可以选用原来的题目重做，也可以重新选择新的题目。

第二部分：软件工程课程设计的总体要求与评分方法

总体要求：

学生结合自己的实际情况，可以选择三人小组协作的形式（推荐）或者自己独立完成的形式（不推荐）进行课程设计。课程设计的题目可以选择自己感兴趣的问题，也可以选择附录部分给定的题目。

对于每一个设计题目，如果是小组协作，设计小组3人（或者2人）共同商量：该设计题目应采用的数据结构与算法要点和细节，进行角色分工，协力完成设计题目。

⒈编程人员：负责编制程序，注意在代码中加上注释，使用缩进法等，尽量提高程序的可读性；

⒉测试分析人员：要根据所讨论结果提供测试数据，要求每种情况各个出口都要测试到，测试中发现问题和编程人员商量，修改算法。测试通过后，分析一下效率（时间、空间复杂度）；

⒊文档编制人员要详细写出:

① 题目；

② 数据结构；

③ 算法思路；

④ 测试结果；

⑤ 人员分工情况；

整个文档要求按照软件工程的规范撰写，可以在文档对应部分包含上述内容，如分析设计部分可以给出算法思路以及相应图表，测试部分给出测试用例与测试结果（测试报告由测试人员编写），源+代码部分注意各种注释的使用。

4.对于独立完成项目的同学，应该在文档中写清楚是自己独立完成的。由于大型软件的开发都是由开发项目组完成的，所以在软件工程课程设计中我们尽量鼓励大家以设计小组的形式参加。

设计评分方法：

对于每个设计题目，满分将是50分。本次设计每位同学至少要完成两套设计题目。

对于小组合作的同学来说，3人一组，分工负责。每个设计题目中，编程满分20分、测试分析满分10分、文档满分20分。由于三人小组一共应当完成六个设计题目，所以一共最多可以获得(20+10+20)*6=300分，人均100分。在分工中，每位同学都应该自己独立完成两次编程，两次测试分析，两次文档。也就是说各次分工应当不同，不能一个同学负责全部的文档，一个同学负责全部的测试分析，一个同学负责所有的编程工作。每位同学自己完成两大套设计题目。

对于每个设计题目的每一部分，视完成情况得到相应的分数，缺少或抄袭都得0分。抄袭者按照考试作弊不再给出软件工程总成绩。

设计结束后，务必上交以下材料：

每一个设计题目包括两部分：

第一部分：分析设计报告与测试报告，两份报告装订在一起，以纸介质形式提交。分析设计报告在前，测试报告在后（测试报告另起一页）。报告一律用A4纸，正文用宋体5号字。报告封面见附页。

第二部分：源程序、分析设计报告与测试报告。三者以电子版形式提交，软盘上请写清自己的班级和姓名。教师收到电子版文档后两周内会将所有文档拷出，软盘归还学生，并确认所交文档已经接收。

提交设计报告的截止时间为2004.12.22下午5:00，本次设计满分100分，按照20分折入软件工程的总成绩。没有参加设计的同学无软件工程的总成绩。原数据结构课程设计中，由于软盘打不开的原因导致暂时无成绩的同学，此次设计可以同时做为数据结构课程设计的报告。这些同学的名单已经转交给各班学习委员，且由学习委员通知到学生本人；得到通知后，请学生自己发短信给指导教师，以最终确认名单。

参考教材：

Richard F. Gilberg，Behrouz A. Forouzan，Data Structures-A Pseudocode Approach with C++，人民邮电出版社，2002.1。

第三部分：原“数据结构课程设计”的参考题目

一、用循环链表实现约瑟夫（Joseph）环。

⒈问题描述：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）开始任选一个正整数作为报数值m，自第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他持有的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。编写完整的程序求出出列顺序。

⒉具体要求：

⑴ 输入：从键盘输入人数n，n个人的密码，及初始m值。

输入应有提示，输入数据错误应当有出错提示，然后退出。当输入n值过大，而输入的n个整数不够时应有处理措施，将其补够n个整数。

⑵ 输出：输出最好是写到文件中，将原输入的值n，n个整数，初始m值均写入到文件中，出列顺序也写入到文件中，这样文档编制人员将其插入即可。（调试阶段可以先输出到屏幕，以便及时看到结果）。

二、马踏棋盘

⒈问题描述：设计一个国际象棋的马踏棋盘的演示程序。

⒉具体要求：

⑴ 将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵并输出。

⑵ 测试数据由键盘指定出马的起始位置(i,j)，0≤i,j≤7。

⑶ 本题目选作内容：求出从某一点出发的多条以至全部行走路线。

(4)提示：

① 一般来说，当马位于方格(i,j)时，可以走到下列8个位置之一：(i-2,j+1)，(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)，(i+1,j-2)，(i-1,j-2)，(i-2,j-1)。但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。

②每次在多个可走位置中选择其中一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时“回溯”（悔棋）使用。

三 平衡二叉树操作的演示

⒈问题描述：利用平衡二叉树实现一个动态查找表。

⒉具体要求：

⑴ 实现动态查找表的三种基本功能：查找、插入和删除。

⑵ 测试数据自行设定。

⑶ 提示：

① 初始状态下，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个节点后，应更新平衡二叉树的显示。

② 平衡二叉树的显示可以采用凹入表形式，也可以采用图形界面画出树形。

四 实现用Diskstra方法求最短路径的算法。

⒈问题描述：从用户指定的顶点为起点，输出该结点到其余各顶点的最短路径长度及其路径（path）。

⒉具体要求：

① 结点数不应少于30。

② 可以从键盘或从文件输入结点数据：顶点信息、边、权；建议从文件输入，这样可以预先建立输入文件，调试时不用每次都从键盘输入。

五 内部排序算法比较

⒈问题描述：各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶（大概执行时间），本题目要求通过随机函数产生3组，每组不少于300个范围为（1～32767）的整数数据，然后调用各种内部排序方法进行排序。分析在不同的输入顺序下各种排序方法对这组值的执行效率。（调用前、后分别插入时间变量，求得各种排序方法对该组值的精确的执行时间。）

⒉具体要求：

⑴ 对直接插入排序，冒泡排序，简单选择排序，快速排序，堆排序，归并排序，基数排序进行比较。

⑵ 分析人员要对结果作出简单分析，要求产生3组数目（排序文件长度）不同，以比较长度大小对不同的排序方法的影响，包括对各组数据得出结果波动大小的解释。

六 散列（哈希）表设计

⒈问题描述：为你所在班级的学生名设计一个哈希表（学生名单可从教学办公室处复制），完成插入记录建表和根据给定Key值，查找记录的查表程序。

⒉具体要求：

⑴ 完成中文人名转换为整数/英文字符串（作为哈希函数的Key值）的子函数。

⑵ 自选哈希函数与处理冲突的方法。

⑶ 调用建表算法完成本班学生名的插入前/后插入时间变量，得到花费时间。