数据结构与算法分析课程设计(5篇)

数据结构与算法分析课程设计篇一

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

一、课程设计目的

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

2二、课程设计题目

2.1 棋盘覆盖

【间题描述】

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

【基本要求】

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

1（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个矩阵{a1,a2,...,an},其中ai和ai1是可乘的，i＝1,2,„,n-1。考察这n个矩阵的连乘积a1a2,...,an，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。

【基本要求】

输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如(a1(a2(a3a4)))。【实现说明】 使用动态规划方法。

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的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。

【基本要求】

使用动态规划、回溯法以及分支界限三种方法实现。【测试数据】 【实现提示】

2.6 排序方法

【问题描述】

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

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

比较每种排序方法的时间复杂度和空间复杂度。【测试数据】 【实现提示】

2.7 哈夫曼编码译码器

【问题描述】

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

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

【基本要求】

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

（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。【实现说明】

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

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

（3）二叉树本身也可以用静态数组模拟；（4）使用贪心算法

2.8 迷宫问题（*）

【问题描述】

设计一个迷宫并给出正确走法。如： *** *** *** *** *** *** *** 其中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 8 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}中一些字符组成的字符串，其中每个字符表示它所 11 指定的面顺时针旋转90度。

【基本要求】

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