《数据结构》课程设计任务书.doc

《数据结构》课程设计任务书
课程代码： B03203
课程名称： 数据结构
英文名称： Data Structures
设计周数： 2 学 分： 1
课程类别： 必修 课程性质： 专业基础课
先修课程： 计算机导论、Java语言程序设计
面向专业： 软件技术、计算机网络技术
开课单位：软件工程系
课程设计题目一 迷宫问题
一．设计的目的和要求
1．设计的目的
数据结构课程设计是在学完数据结构课程之后的实践教学环节。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼：
（1）．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
（2）．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
（3）．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
2．设计的要求：迷宫问题
在一个二维阵列构成的迷宫里，有许多由 1 构成的墙壁, 0表示的走道, 其中左上角是迷宮的入口, 右下角是迷宮的出口, 迷宮出口有一块乳酪, 请帮这只老鼠找到一条路径, 可以走出迷宫去享受乳酪, 在迷宮里面只允許上下左右 四個方向行走。
=> 011111101
010100001
000101101
101001101
100011100 =>
Input file format：
011001
000011
010111
010000
Output file format：
請輸出到螢幕上, 請把你找到的任一條路徑用符號 * 列印在螢幕上
*11001
**011
01*111
01****

二． 设计内容及步骤
1．分析问题，给出数学模型，设计相应的数据结构。
（1）分析问题的特点，用数学表达式或其它形式描述其数学模型。
（2）选择能够体现问题本身特点的逻辑结构。
（3）在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和非顺序存储结构的不同存储方式，其对应的算法也不相同。
2．算法设计
在已经选择好数据结构的前提下，为解决问题设计算法。
（1）确定所需模块
对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。
（2）各子模块功能描述
给出主要模块的算法描述，用流程图或伪代码表示。
（3）模块之间的调用关系
给出算法各模块之间的关系图示
3．源程序清单
为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。
4．用测试数据去验证算法及程序的正确性
读入迷宫二维矩阵表示，输出一条或全部路径
5．算法分析
经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度。
[选作内容]
讨论栈在类似问题中的作用；迷宫问题的其它求解方法

6．编写设计报告
（1）设计题目
（2）设计内容
（3）概要设计：确定所需模块及模块间调用关系
（4）算法描述：给出各模块流程图或代码
（5）调试分析
拟定测试数据进行调试，调试过程中遇到的问题、解决方法、体会
（6）测试结果分析
说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。
三．进度安排
按教学计划规定，数据结构课程设计总学时数为2周，其进度及时间大致分配如下：
序号
设计内容
天数
1
分析问题，给出数学模型，选择数据结构
1
2
设计算法，给出算法描述
1
3
给出源程序清单
1

4
编辑、编译、调试源程序
1
5
撰写课程设计报告
1
总 计
5

课程设计题目二 内部排序算法比较

一． 设计的目的和要求
（一）设计的目的
数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼：
1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
4．在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和移动次数，以取得直观感受。
（二）设计的要求
1．对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
2．待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
3．统计在完全正序、完全逆序情况下的关键字比较次数和移动次数。
4．最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。
二．设计内容及步骤
1．分析问题，给出数学模型，设计相应的数据结构。
（1）分析问题的特点，用数学表达式或其它形式描述其数学模型。
（2）选择能够体现问题本身特点的逻辑结构。
（3）在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和非顺序存储结构的不同存储方式，其对应的算法也不相同。
2．算法设计
在已经选择好数据结构的前提下，为解决问题设计算法。
（1）确定所需模块
对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。
（2）各子模块功能描述
给出主要模块的算法描述，用流程图或伪代码表示。
（3）模块之间的调用关系
给出算法各模块之间的关系图示
3．源程序清单
为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。
4．用测试数据去验证算法及程序的正确性
正序、逆序、随机数
5．算法分析
经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度。
[实现提示]
主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序，逆序和随机数据。注意采用分块调试的方法。
[选作内容]
增加折半插入排序、二路插入排序、归并排序、基数排序等。
对不同的输入表长作实验，观察两个指标相对于表长的变化关系。还可以对稳定性作验证。
6．编写设计报告
（1）设计题目
（2）设计内容
（3）概要设计：确定所需模块及模块间调用关系
（4）算法描述：给出各模块流程图及代码
（5）调试分析
拟定测试数据进行调试调试过程中遇到的问题、解决方法、体会
（6）测试结果分析
（6）参考资料
注：学生完成课程设计后提交课程设计报告，要求将前述全部内容依先后顺序写成设计报告一份，要求文字通畅、字迹工整，装订成册。
说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。
二． 进度安排
按教学计划规定，数据结构课程设计总学时数为1周，其进度及时间大致分配如下：
序号
设计内容
天数
1
分析问题，给出数学模型，选择数据结构
1
2
设计算法，给出算法描述
1
3
给出源程序清单
1
4
编辑、编译、调试源程序
1
5
撰写课程设计报告
1
总 计
5

成绩评定
课程设计成绩根据学生平时工作情况，上机调试程序的能力，算法的效率、课程设计报告质量综合衡量，由指导教师评定。
课程设计成绩=考勤20%+调试程序能力40%+设计报告质量40%
参考文献
1. 《数据结构》.严蔚敏 清华大学出版社
2. 《Java 2 实用教程》.耿祥义 清华大学出版社