《数据结构与算法课程设计》任务书2014资料

《数据结构与算法课程设计》任务书

一、课程设计目的

数据结构与算法课程设计是《数据结构与算法》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。

2二、课程设计题目

2.1 棋盘覆盖

【间题描述】

在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

【基本要求】

（1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc。

（2）要求输出每一步用什么形态L型骨牌覆盖，覆盖后得到的棋盘图形。

（3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优。

【测试数据】

【实现提示】

使用分治策略，把棋盘划分成4个小棋盘，然后用一个L型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘。

2.2 Hanoi塔问题（*）

【问题描述】

设a，b，c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,…,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则（1）每次只能移动一个圆盘；

规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；

规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上。

【基本要求】

（1）设计出Hannoi塔游戏，供用户玩；

（2）提供正确的搬运方法。

【实现说明】

正确的搬运方法使用递归方法实现。

【测试数据】

2.3 矩阵连乘问题

【问题描述】

给定n个矩阵{},其中和是可乘的，i＝1,2,…,n-1。考察这n个矩阵的连乘积，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。

【基本要求】

输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如。

【实现说明】

使用动态规划方法。

2.4 多边形游戏（*）

【问题描述】

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“＋”或“*”。所有边依次用整数从1到n编号。

游戏第1步，将一条边删除。

随后n-1步按以下方式操作：

选择一条边E及由E连接着的2个顶点v1和v2；

用一个新的顶点取代边E及用E连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。

【基本要求】

设计该游戏供用户玩；

对于给定的多边形，给出最高得分计算。

【实现说明】

使用动态规划方法。

2.5 0-1背包问题

【问题描述】

给定n种物品和一背包。物品i的重量是，其价值为，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。

【基本要求】

使用动态规划、回溯法以及分支界限三种方法实现。

【测试数据】

【实现提示】

2.6 排序方法

【问题描述】

给定n个元素，要求对这n个元素进行排序。

【基本要求】

使用多种排序方法，越多越好；

比较每种排序方法的时间复杂度和空间复杂度。

【测试数据】

【实现提示】

2.7 哈夫曼编码译码器

【问题描述】

设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件

（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。

【基本要求】

（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；

（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）

（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。

【实现说明】

（1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表；

（2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；

（3）二叉树本身也可以用静态数组模拟；

（4）使用贪心算法

2.8 迷宫问题（*）

【问题描述】

设计一个迷宫并给出正确走法。如：

001111111111111

100011111111111

101100001111111

100011100000111

111011*********

111000000001001

111000000011100

其中0表示可以走，1表示不能走，每一步只能向上下左右移动。

【基本要求】

（1）给出迷宫的正确走法，包括没有解的情况；

（2）要求界面友好。

【测试数据】

【实现提示】

使用回溯的方法。

2.9 继续邮资问题

【问题描述】

假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。

【基本要求】    

 输入任意的m和n都能设计出最佳的方案，并给出连续邮资区间。

【实现说明】

【测试数据】

2.10 图的m着色问题

【问题描述】

给定一个地图，要求给出该地图的最少着色方案

【基本要求】

（1）把地图以及最少着色的方案显示出来则为良好。

（2）有友好的界面则为优

【实现说明】

2.11 猜数字游戏（*）

【问题描述】

孩子想1个由4种颜色组成的序列（4种颜色不一定完全不同）。每种颜色只能是6种颜色之一。方便起见，我们用数字1到6表示6种颜色。

计算机必须根据孩子的回答找出孩子所想的颜色序列。计算机在屏幕上显示一个序列，孩子用键盘回答以下两个问题：

猜对的颜色中位置不对的有几个？

猜对的颜色中位置对的有几个？

【基本要求】

编程使至多6次问答后猜出序列，如果办不到，至多10次问答后猜出序列。

【实现说明】

【测试数据】

 如孩子想的是4655

计算机猜想      颜色对位置错的数目  颜色和位置都对的数目

1234                   1                  0

5156                   2                  1

6165                   1                  1

5625                   1                  2

5653                   1                  2

4655                   0                  4

2.12 大整数计算器

【问题描述】

设计一个计算器实现两个任意长得整数的加、减、乘、除。

【基本要求】

设计一个实现任意长的整数进行四则运算的演示程序，要求输入任意长的整数进行四则运算，都能得到精确的结果。

【实现说明】

2.13 查找搜索技术

【问题描述】

给定任意的数组，对于给定的数，查找是否在数组中，如果在，则返回给定数在数组的位置，不在则返回不在信息。

【基本要求】

（1）使用多种搜索方法，越多越好，其中二分搜索技术、线性时间选择是必须的；

（2）比较每种排序方法的时间复杂度和空间复杂度。

【实现说明】

2.14 Tom,Jerry和奶酪（*）

【问题描述】

猫Tom和鼠Jerry同住在一矩阵地窖中。猫要吃鼠，鼠要吃奶酪。地窖中有2种地砖：有洞砖与无洞砖。一个洞足以让鼠钻入，但猫不能。

以菜单形式完成以下任务：

随机地生成一个地窖，并给猫、鼠和奶酪安排一个位置。如：

fffffffffffffff

fppppppppppppCf

fhfffffffffffpf

fpppjhppppppppf

fpffffffpffffff

fppppppppppTppf

fffffffffffffff

其中c表示猫，j表示鼠，h表示洞，f表示不能通行

（2） 鼠先行，猫后行。两者皆满足以下规定：

1）必须上、下、左或右移动

2）鼠必须走1步（穿过p或h）

3）猫必须走1或2步（穿过p）

（3） 当鼠吃到奶酪或猫抓到鼠时，游戏结束。

【基本要求】

【实现说明】

2.15 布线问题

【问题描述】

印刷电路板将布线区域划分成n×m个方格阵列，精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿着直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过的方格。

【基本要求】

（1）解决题目的问题

（2）提供友好的界面

【实现说明】

使用分支限界法。

2.16 魔方工具包 （*）

【问题描述】

一个魔方是一个由3×3×3个小立方体组成的立方体。最初立方体的6个面分别涂上不同颜色，我们称之为“最初魔方”。魔方的每一面上的3×3个小立方体组成它的一层。

魔方所能见到的每一层（6个面）都能旋转90，180，220或360度。所有层的旋转轴都垂直于面且通过其中心。旋转的结果是另一个魔方，它的所有面的颜色都改变了。

现在我们用字符来代替颜色：U=上，D=下，F=前，B=后，L=左，R=右。任何一个序列的旋转都能表示成{U,R,F,B,L,D}中一些字符组成的字符串，其中每个字符表示它所指定的面顺时针旋转90度。

【基本要求】

（1）编程完成以下3个任务（菜单形式），你可以假设任何输入的字串长度都<=35。

你的算法能处理非法输入的情况，如：

输入               输出

L                  L

LL                 LL

LLL                LLL

LLLL               “”(空串

LLLLL              L

LLRRRFFFFRLB       LLLB

HELLO                “error”

（2）判断输入的2个字串的旋转结果是否相同。如

输入一                   输入二             输出

RU                       UR                 no

RRFFRRFFRRFFRRFF         FFRRFFRR           yes

RRFFRRFFRRFFRRFF         RRFFRRFF           no

（3）求出输入字符串至少须使用几次才能将魔方转回到“最初魔方”（一定大于0）

输入             输出

L                4

DD               2

BULB             36

RUF              80

BLUFF            180

【实现说明】

2.17 图的建立与输出 

【问题描述】

建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

【基本要求】

给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果

【实现说明】

     无

2.18 图的建立与输出 

【问题描述】

建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

【基本要求】

给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果。

【实现说明】

     无

2.19 以队列实现的仿真技术预测理发馆的经营状况（*）

【问题描述】

理发馆一天的工作过程如下：

1)理发馆有N把理发椅，可同时为N位顾客进行理发。

2)理发师分三个等级（一级、二级、三级），对应不同的服务收费。

3)当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。

4)一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。

5)若理发馆每天连续营业T分钟，求

（1）一天内顾客在理发馆内的平均逗留时间；

（2）顾客排队等候理发的队列长度平均值；

（3）营业时间到点后仍需完成服务的收尾工作时间；

（4）统计每天的营业额；

（5）统计每天不同级别理发师的创收。

【基本要求】

1)模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；

2)每个顾客到达和下一顾客到达时间的间隔应是随机的；

3)理发师编号、理发师级别和每天的营业时间由用户输入；

4)某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待 ；

5)每个顾客进门时将生成三个随机数:

(1)durtime:进门顾客理发所需服务时间（简称：理发时间）；

(2)intertime:下一顾客将到达的时间间隔（简称：间隔时间）；

(3)select:服务选项 。

6)服务收费：应包含服务时间和理发师级别两个因素。

7)除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。

【实现说明】

     用户输入每位理发师编号、级别号和营业的时间，结合随机数进行测试。

2.20 防抄袭管理系统（*）

【问题描述】

对于给定的文档，如word文档，txt文档等，找出文档的相似度。

【基本要求】

（1）要求找出给定的两个文档的相似度以及标出相似的地方（1:1）；

（2）要求找出给定的一个文档与给定的文件夹的所有文档的相似度，以及标出相似的地方(1:n)

（3）要求找出给定的文件夹下面所有文档的相似度(n:n)。

【实现说明】

     给定相似文档进行测试。

2.21.设计一个停车场管理系统，模拟停车场的运作

设计要求：通过此程序具备以下功能：1、要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理；2、要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻； 3、该系统完成以下功能：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）； 4、要求栈以顺序结构实现，队列以链表实现。

2.22． 赫夫曼编码

     设计要求：自己找一篇不少于200个单词的英文文章，分析该文章中每一个字符的出现概率（包括标点符号，区分大小写），根据分析结果对文章中每一个字符进行赫夫曼编码，并将编码原则储于一个的文本文件中。最后，根据这个编码原则，将英文文章转换为01

串存储于一个文本文件中，再编写一个解码程序，将编码解码为原文件。 

如：英文文章为

aaabbc 

则编码规则为

a-----0 

b-----10 

c-----11 

英文文章将被转化为

000101011 

2.23.并查集：检查网络

题目要求：给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？

输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。

当N为0时，表示全部测试结束，不要对该数据做任何处理。

输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。

当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。

两组测试数据之间请输出一空行分隔。

2.24.教学计划编制问题（图的应用）

[问题描述]

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

[实现提示]

1、 输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。

2、 应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

3、 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式可以自己设计。

4、 可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。

===========================================================================

2.25.药品销售统计系统（排序应用）

【问题描述】

设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。

【实现提示】

在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。

药品信息的元素类型定义：

typedef struct node

{ char num[4];  /*药品编号*/

  char name[10]; /*药品名称*/

  float price;  /*药品单价*/

  int count;    /*销售数量*/

  float sale;  /*本药品销售额*/

 }DataType;

存储药品信息的顺序表的定义：

typedef struct

{ DataType r[MaxSize];  

  int length;

}SequenList;

2.26梯运行仿真程序  

[问题描述] 

办公大楼有若干层（例如，十层），每层有电梯，同时有步行楼梯； 

全楼有若干部（例如，不多于10部）电梯同时供使用，电梯容量为24人，速度每上下一层需5秒，在某一层停下至少15秒。其运行状态可分：向上、向下、停止，当前乘客数，当前所在层数。它设有一个“按钮数组”，例如第五层的按钮按下，意味着有乘客在第5层到达目标层，等等。 

在楼的每一层，有电梯数，有按钮表示有人等待向上或向下，由若干人在等待，有若干电梯在本层停下，等等。 

在大楼中（包括进出）的总人数不超过500 人，每个人站在电梯前有个目标层，他有一个最大的忍受等待时间，因为他可以选择电梯或是步行走楼梯，等等。 

还有下面若干假设：在每个时间段要进大楼的人数在0～199 之间随机取值； 

用电梯的每个人的目标层在1～10 之间取值；一个人在进电梯或改走楼梯之前的等待时间在180～360 秒范围内随机发生；一个人到达目标层后第二次再乘电梯中间的工作时间在400～6600 秒间随机取值。 

[基本要求] 

编写一个程序，模拟办公大楼中全部电梯的工作过程。这个仿真程序可以用来监测系统运行情况，改善大楼管理，它也可以看成是一种游戏程序。  

2.27国交通咨询模拟  

[问题描述] 

处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅

途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供最优决策的交通咨询。  

[基本要求]  

（1）提供对城市信息进行编辑（如：添加或删除）的功能； 

（2）城市之间有两种交通工具：火车或飞机，提供对全国城市交通图和列车时刻表及飞机航班表进行编辑的功能。（信息的输入方式可以是文件输入和键盘输入两种方式）  

（3）提供两种最优决策：最快到达和最省钱到达。（选作：旅途中转次数最少的最优决策） 

（4）旅途中耗费的总时间应该包括中转站的等候时间。  （5）咨询以用户和计算机的对话方式进行。 

a）由用户输入起始站、终点站、最优决策原则和交通工具； 

b）输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详

细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

三、课程设计的基本要求

1．问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）条件是什么？ 

2．逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。

3．详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。

4．程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。

    5．程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。

    6．结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。

    7．编写课程设计报告并提交相关内容

设计最终需提交的内容包括：

A）课程设计报告（1份，A4纸打印，同时包括一份电子版）

报告要求版面清晰，格式规范，否则重新编写。

报告内容要求包括：

（1）问题的概述、分析及研究意义；

（2）数据结构的逻辑设计和物理存储设计；

（3）重要算法的设计、流程描述或伪代码描述；

（4）数据结构的时空复杂性分析以及重要算法的复杂性分析；

（5）程序最终实现结果（包括重点结果界面的抓取，能过说明问题的重要实验结果数据的打印或其可视化结果等）。

（6）参考文献（如果需要）。

（7）附录部分附上关键数据结构的定义及关键算法的源代码。

B）完整的程序系统（电子方式提交）

能够对输入产生相应的输出，同时尽量的完成可视化演示。

该部分包括源代码和可执行文件两个部分（提交的时候需清楚的注明个人姓名，班级）。

C）源程序文档（电子方式提交）

源程序代码要求结构清晰、可读性好。应对源程序中的类说明（如果采用面向对象方法设计），函数说明，接口说明，关键变量说明等进行注释；源程序要进行适当的缩进编排。

D）答辩报告（编写Power Point答辩报告，电子方式提交）

要求突出重点，思路清晰。同时就此报告准备答辩。

E）所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后的文件按规定格式进行命名，命名格式为：学号+姓名.rar（如060701014石海杭.rar）。

8．每位同学只能选择一个题目并完成

四、评分标准

1、基本功能：                    50分。

通过功能的实现情况、界面的完成情况、软件的实现情况进行评分。

2、设计报告及使用说明书：    20分

按照报告的要求进行评分。

3、回答问题：                    15分

4、平时考勤：                    15分

5、核分标准：                    100分

（90~100为优、80~为良、70~79为中、60~69为及格、，60以下为不及格）

五、参考书目

严蔚敏. 《数据结构》（C语言版）. 清华大学出版社

刘玉龙．《数据结构与算法》.电子工业出版社.

严蔚敏等《数据结构题集》（C语言版）. 清华大学出版社

徐孝凯. 数据结构实用教程（C/C++描述）. 北京:清华大学出版社. 

陈慧南. 数据结构（使用C++语言描述）. 南京:东南大学出版社. 

殷人昆, 陶永雷, 谢若阳等. 数据结构（用面向对象方法与C++描述）. 北京:清华大学出版社.