数据结构课程设计说明.doc

《数据结构课程设计说明.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计说明.doc（24页珍藏版）》请在三一文库上搜索。

1、放假前需要完成的任务1、15号下午5点之前交作业本和实验报告。2、课程设计于21号下午1点半开始答辩，22号中午12点前提交实验报告的纸质文档和电子文挡。3、各小组组长每天汇报课程设计进度情况。4、下学期课程表已经出来，组织领教材。5、第19周上机时间：每天下午6点到9点半，秋白楼705。第20周上机时间：每天下午1点半到5点。数据结构课程设计说明2010.1常州工学院计算机信息工程学院 数据结构课程设计报告（模板）题 目 XXXXXXXXXXXXX 年 级 2008级 专 业 08软件 学生学号 XXXX （组长） 学生学号 XXXXXXXXX 学生学号 XXXXXXXXX 指导教师 王树峰

2、 2010 年 1 月 20 日常州工学院计算机信息工程学院数据结构课程设计任 务 书 （模板）设计名称： XXXXXXXXXXXXXXXXXXXXX 指导教师： XXXXX 下达时间： 200X-XX-XX 学生姓名： XXXXX （组长） 学 号： XXXXXXXXX学生姓名： XXXXX 学 号： XXXXXXXXX学生姓名： XXXXX 学 号： XXXXXXXXX专业： XXXXXXXXXXXXXXX一、 课程设计的基本要求二、 课程设计的主要内容（包含分工）三、 课程设计的进程安排1200X年XX月XX日之前：XXXXXXXXXXXXXXX。2200X年XX月XX日XX月XX日：X

3、XXXXXXXXXXXXXX。2200X年XX月XX日前：XXXXXXXXXXXXXXX。200X年 XX月XX日数据结构课程设计报告（模板）一 正文(一) 名称1、名称详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容。2、名称详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细

4、内容详细内容。二 附录(二) 节名称1、名称详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容。2、名称详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容详详细内容详细内容详细内容详细内容详细内容详细内容详细内容详细内容。数据结构课程设计考核评估标准通过程序设计及答辩方式，并结合学生的动手能力（编程及调试程序能力）、独立分析解决问题的能力、创新精神、总结报告、答辩水平、学习态度以及题目难易程度综合考评，成绩分优、良、中、及格和不及格五等。课程设计的量化评分成绩见表（1）数据结构课程设计

5、量化评分标准（每人一页） 学生姓名： XXXX 学生学号 XXXX 指标最高分评分要素评分设计技术水平20程序运行情况良好，结构设计合理，算法说明清晰，理论分析与计算正确，实验数据无误，通用性和可扩充性强实际动手能力20独立完成设计，能够迅速准确的进行调试和纠错 研究成果与专业知识10对研究的问题能较深刻分析或者有独到见解，很好地掌握了有关基础理论与专业知识，总结报告认识深刻写作与总结提炼能力10报告结构严谨，逻辑严密，论述层次清晰，语言流畅，表达准确，重点突出， 文献综述10有较完善的文献综述，能够正确查阅参考文献资料规范化程度10提交的电子文档及打印文档的书写、存放完全符合规范化要求答辩情

6、况10能简明扼要地阐述设计的主要内容，能准确流利地回答各种问题学习态度10端正的学习态度及认真刻苦程度等总 分指导教师：200X年 XX月XX日 注意： 本评分标准适用于数据结构课程设计； 总分满分为100分，成绩参考标准为：优秀（100X90）；良好（90X80）；中等（80X70）；及格（70X60）；不及格（X60）； 发现有拷贝舞弊现象者，一律直接退回不作检查，两次舞弊者按不及格处理。 每组学生至少要回答三个以上的问题，有两个以上问题回答不清楚者，一律不及格。 课程设计报告不交或不规范者一律不及格。数据结构学生课程设计上交时间与上交方法课程设计的上交时间: 2010年1月21号12点前

7、将所有需要上交内容上交至指导老师。课程设计的上交方法:1 每组同学的“课设设计进展情况”以E-mail 形式上交；E-mail地址：2最后上交的“课设设计报告”要求有两部分：一是电子文档（E-mail），二是打印文档。数据结构课程设计上交文档要求1 文档规范化要求最终的“课程设计报告”要求以打印文档和电子文档（E-mail）两种形式上交。1）打印文档要求：打印文档大小统一为 A4纸幅。并按照以下4项内容和次序装订。各部分排版规范参见模板。 课程设计报告上交文档包含如下内容：001封面002任务书003课程设计报告 正文 附录004量化评分（每人一页，便于评分）2）电子文档要求（各部分排版规范参

8、见电子文档中的模板，一组交一份，用组长的学号和姓名提交）：1 电子文档中包含一目录名为“（学号）（姓名）”的文件夹，所有需要上交的电子文档均在此文件夹中。2 学生按照课程设计的具体要求开发的所有源程序，存放至目录名为 “（000）（源程序）（学号）（姓名）”的文件夹中。3 封面存放于名字为“（001）（封面）（学号）（姓名 ）.doc”的word文档中。4 任务书存放于名字为“（002）（任务书）（学号）（姓名 ）.doc”的word文档中。5 课程设计报告存放于名字为“（003）（课程设计报告）（学号）（姓名 ）.doc”的word文档中。6 量化评分标准存放于名字为“（004）（量化评分标

9、准）（学号）（姓名 ）.doc”的word文档中。注意：上述要求中的黑斜体部分根据实际情况填写。2文档正文内容要求 对于正文部分内容要求必须具备如下内容：1） 目的2）需求分析以无二义性的陈述说明程序设计的任务，程序要做什么？明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；列出初步的测试计划。3）概要设计说明本程序中用到的所有数据类型的定义及含义、主程序的流程以及各程序模块的功能要求及各自之间的层次（调用）关系。4）详细设计实现概要设计中定义的所有数据类型，对每个操作需写出伪码算法；对主程序和其他模块也都要写出伪码算法；画出函数的调用关系图。最终实现的源程序要按照良好风格的

10、程序书写规则来编写，要求结构清晰，重点函数、重点变量以及重点功能部分要加上清晰的程序注释。5）调试分析测试数据，测试输出的结果（包括正确的输入及其输出结果和含有错误的输入及其输出结果）。每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？）。 进行时间和空间复杂度分析，算法的改进设想。6）测试结果列出完备的测试计划及其结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中的初步测试计划。7）用户使用说明说明如何使用最终发布的程序，详细列出每一步的操作步骤。8）课设总结课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、经验和体会以及对设计与实

11、现的回顾讨论和分析；在课程设计过程中对课程的认识等内容。 数据结构课程设计题目第一部分（以下题目60分起评，经老师同意的自拟题目按60分起评）1 P96 停车场管理2 P102 电梯模拟3 P123 文学研究助手4 P149 Haffman 编/译码器5 P150 教学计划编制问题 邱文婷6 P151 校园导游咨询7 P153 全国交通咨询模拟 8 P167 图书管理9 P169 内部排序算法比较10 P80 长整数四则运算11 P100银行模拟业务刘任12 P101 航空客运订票系统 张飞13 P150 图遍历的演示14 P168 平衡二叉树操作的演示 杨浩15 P152 表达式类型的实现冯

12、小佩16 P136 稀疏矩阵运算器17 P117 文本格式化 刘嘉骐18 P98 车厢调度19 P81 一元稀疏多项式计算器20 P152 最小生成树问题第二部分（以下题目80分起评）1. 遗传算法的模拟(1) 问题描述 遗传算法是以达尔文生物进化论为基础，借鉴自然界中物种进化原理，依据优胜劣汰而达到优化的规律而创建的一种数学模型和算法，如下图所示。该图以小麦品种改良的过程为例说明遗传算法（也可称为基因算法）的基本原理：优化问题的可能解被称为是个体（individuals），首先考虑可能解（个体）组成的集合，即群体（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适

13、应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。将上述过程形式化后就得到如下图所示的遗传算法结构框图：initialize t=0initialize P(t)evalute Fitness of P(t)while not stopping criterion do P(t) = recombinationP(t) P(t) = mutationP(t) P(t+1) =selectionP(t)+P(t) Ev

14、alute Fitness of P(t) t = t+1其中P(t)为t 时刻的父代，而P(t)为t 时刻的子代。 对于计算机问题而言，一般要将问题的解进行编码，编码成二进制字符串，杂交和变异就在这些字符串上进行。 遗传算法可以很好解决很多的优化问题。(2) 课程设计目的 体会遗传算法思想，能够设计并编写遗传算法的相关操作函数，并能够应用遗传算法求解具体问题。 (3) 基本要求 编写遗传算法的基本操作函数，包括选择，变异，交叉等。 应用遗传算法实现求解如下函数的极值 f(x)=x*sin(10*x)+1.0 x-1,2 结果精度要求在小数点后六位。 给出算法效率分析的实验结果。 (4) 实现

15、提示 根据精度要求确定个体的二进制编码位数，同时要确定该编码和-1,2间数的换算规则，由于是求最大值的问题，所以适应度函数就可选为f(x)，值越大的个体适应度越好。关于交叉和变异的方法参阅相关资料。2. 蚁群算法在旅行商问题中的应用 (1) 问题描述 蚁群算法是在对真实蚂蚁的观测基础上提出的，单个蚂蚁是不具智能的，但生活在一起的蚁群却总是能够在蚁穴和食物间找到一条几乎是最短的路径。这就要靠蚁群的智能，蚁群算法就基于这一智能。下面的图例给出蚁群智能的基本思想。 蚂蚁会在自己走过的路径上留下生化信息素，同时它也会选择地面上信息素较多的路径行走。对于下图的第二种情况，因为路上有了障碍物，所以蚂蚁需要

16、绕过障碍物，该咋么样绕过障碍物，由于没有信息素作为指导，所以起先只能是随机的选择从左或从右走（第三个图所示）；但是随着行走次数的增加，较短的路径上留下的信息素就会较多，就有更多的蚂蚁行走，信息素进一步增多，最终较短的路就成为了选择的路（第四个图）。这就是蚁群智能的基本原理。图6-21 蚁群算法的基本思想 蚁群算法就是应用蚁群智能实现的算法，可以用它来实现在解空间上进行最优解的搜索，很多计算机问题可以转化为搜索最优解的问题。如旅行商问题（求解遍历全部城市的最短路经），就可用蚁群算法求解，在旅行商问题中，蚁穴到食物就对应遍历全部城市，蚂蚁就对应旅行商。 (2) 课程设计目的 了解蚁群算法的思想，并

17、能应用蚁群算法求解具体问题。 (3) 基本要求 应用蚁群算法求解TSP问题。 TSP中的城市数量不少于30个，组成完全图，边上的权值自定。 蚂蚁数量可配置，迭代次数可配置。 给出较全面的实验结果：结果路经及长度；蚁群算法执行时间；不同参数值（蚂蚁数量，迭代次数）的影响等。 迭代过程需要用图形界面表示(可用C的图形库)。 3 实现并对比三种基本的字符串匹配算法 (1) 问题描述 字符串匹配问题是：假定文本时一个长度为n的数组T1.n，模式是一个长度为mn的数组P1.m，如果0sn-m，并且Ts+1.s+m = P1.m，则称模式P完成了和T的匹配，且P在T中出现的位移为s，如下图所示： 图字符串

18、匹配问题本课程设计要实现三种基本的字符串匹配算法：朴素匹配算法；Rabin-Karp算法；KMP算法。 朴素匹配算法 是最简单的匹配算法，可以形象地看成是用一个包含模式P的模板沿文本滑动，同时对每个位移注意模板的上的字符是否与文本中的相应字符相等，如下图所示： Rabin-Karp算法 基本思想是将模板P用一个数p（通常是十进制）表示，如果字符串中的每位都是0-9的整数： p = Pm + 10（Pm-1 + 10（Pm-2+ + 10(P2 + 10P1)） 同时将T中每个m位连续的串上计算出同样的正数值，有n-m个：t1，t2，tn-m。一种较为巧妙的方法是在ts基础上可按如下方式计算ts

19、+1：ts+1 = 10（ts 10m-1 Ts+1）+ Ts+m+1 由于这样的值非常大，可能会导致溢出，通常的处理办法是计算p mod q和ts mod q，计算时会用到性质a+b mod n = a mod n + b mod n；a * b mod n = a mod n * b mod n。 Rabin-Karp算法的具体过程如下图所示：图Rabin-Karp字符串匹配算法示意图 KMP算法图模式匹配中的信息重利用KMP算法是一种设计得很巧妙但也较复杂的一种算法，是应用自动机思想实现的匹配算法。其基本思想是如果已经完成了P部分字符（一个前缀q）的匹配，那么在匹配T后面的字符时可以应用

20、P模式的信息减少比较次数，如图6-29所示。 首先需要计算模式P的前缀函数p：1，2，m 0，1，m-1满足： pq = max k：k 0 and Pq + 1 Ti 7 do q q 8 if Pq + 1 = Ti 9 then q q + 1 10 if q = m 11 then print Pattern occurs with shift i - m 12 qq 图KMP算法伪代码(2) 课程设计目的 应用数据结构与算法基本知识解决实际问题，对字符串匹配形成一定的认识。 (3) 基本要求 编程实现三种字符串匹配算法。 分析三种算法的时间复杂性，通过应用三种算法在一个较长英文文本中

21、查找一个子串的实验数据来对比三种算法的运行时间。 (4) 实现提示 需要查阅相关资料，尤其是KMP算法。4文档集合上的查询 (1) 问题描述 设计数据结构完成在一个文档集合的存储，并构造算法实现其内容的查询。该设计包括三个部分： (一)应用数据结构完成文档集合的内容(基于单词的)存储，并为下一步的查询建立索引。 (二)就单个单词的查询请求，设计算法进行查询。 (三)对多个单词通过AND和OR构造的复杂查询进行处理(此处可只做两个单词的情况)。 具体情形如下面的例子： Example Doc1: I like the class on data structures and algorithms

22、. Doc2: I hate the class on data structures and algorithms. Doc3: Interesting statistical data may result from this survey. Here are the answers to some queries: Query 1: data Doc1, Doc2, Doc3 Query2: data AND structures Doc1, Doc2 Query 3: like OR survey Doc1, Doc3 图文档集合上的查询实例 (2) 课程设计目的 用线性结构组织信息，

23、查找算法的选择与应用。 (3) 基本要求 文档集合中的文档数不能少于20个。 数据结构的设计以及查找算法的构造应考虑如何最大程度的提高查询效率。 查询效率的提高应是综合多种查询的，而不是只针对一种查询的优化。 给出查询效率的模拟实验数据。 (4) 实现提示 AND和OR查询可转变为单个单词查询结果的组合。 5 扫雷游戏李琳峰(1) 问题描述 本题目做一个N x M的扫雷游戏，每个方格包含两种状态：关闭（closed）和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会包含两种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格，如果你打开的是一个bo

24、mb，那么就失败；否则就会打开一个数字，该数字是位于0，8的一个整数，该数字表示其所有邻居方格（neighboring squares）所包含的雷数，应用该信息可以帮助你扫雷。图扫雷游戏的图例具体实现要求的细节： 能够打开一个方格，一个已打开的方格不能再关闭。 能够标记一个方格，标记方格的含义是对该方格有雷的预测（并不表示真的一定有雷），当一个方格标记后该方格不能被打开，只能执行取消标记的操作，只能在取消后才能打开一个方格。 合理分配各个操作的按键，以及各方格各种状态如何合理显示。 (2) 课程设计目的 掌握线性结构的应用，并体会如何用计算机程序完成一个有趣的游戏。 (3) 基本要求 能够给出

25、游戏结果（输、赢、剩余的雷数、用掉的时间按妙计）。 游戏界面最好图形化，否则一定要清楚的字符界面。 (4) 实现提示 用二维数组表示N x M区间，要仔细考虑如何初始的布置各个雷以及各个方格的状态及变化。6公交线路上优化路径的查询 赵杰(1) 问题描述 最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为： 线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过

26、的站点2名(该站坐标)；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 例如：63：A(32,45)；B(76,45)；C(76,90)；N(100,100)。1元。5分钟。1/每分钟。 假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。 对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径等等。 (2) 课程设计目的 从实际问题中合理定义图模型，掌握Dijkstra算法并能用该算法解决一些实际问题。 (3) 基本要求 根据上述公交线路的输入格式，定义并建立

27、合适的图模型。 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x元。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 (4) 实现提示 需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。第三部分：以下题目90分起评（要求提出需要解决的问题、实现目的、基本要求、具体实现）1 DES加密算法的实现： 朱丰2 模拟Sensor network的工作3 聚类分析的初步实践4 实现简单数字图像处理 冷晶晶5 二值图像数字水印技术的实践