合肥学院
计算机科学与技术系
课程设计报告
2011 ～2012 学年第二学期
课程数据结构与算法
课程设计名称合并果子问题
学生姓名杜双双
学号1004013037
专业班级计算机科学与技术10级3班
指导教师李红陈艳平王竹婷
2012 年2 月
课程设计报告
一、问题分析和任务定义
此程序需要完成如下要求：在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。
多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。
假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。
可以先将1、2堆合并，新堆数目为3，耗费体力为3。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。
所以多多总共耗费体力3+12=15。
可以证明15为最小的体力耗费值。
实现本程序需要解决以下几个问题：
1、要使每次合并的体力消耗最小应该选择数目最小的两堆果子，那么如何选择出两堆最小的呢？
2、选择出了两堆果子如何进行合并？
3、如何计算最小的体力耗费值？
本问题的关键和难点在于数据结构的选择，找出最优的方法，在此选择哈夫曼树数据结构。
示例：三种果子，果子数目分别为1,2，3
哈夫曼树
最小体力消耗值：3+6=9
二、数据结构的选择和概要设计
上面采用哈夫曼树，则其存储就是哈夫曼树的存储结构。
采用数组顺序存储结点信息。
每一个结点包括四个域：存放该结点的weight 域、分别存放其左右孩子结点在数组中下标的lchild 域和rchild 域，以及记录该结点的父结点信息的parent 域。
只需用一个主函数就能解决问题。
三、详细设计和编码
数据结构：
typedef struct {
int weight;
int parent,lchild,rchild;
}hufmtree;
若给定n种果子的数目，则可定义数组tree[]存储哈夫曼树上的结点：
详细设计算法如下：
（1）初始化数组tree[]；读入给定的n种果子每种果子数，分别放入数组的前n个分量的weight域中，并将数组中所有分量的lchild域、rchild域和parent域置0.
for(i=0;i<n;i++)//初始化数组
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0;
}
（2）从数组的前n个分量中选择果子数目最小和次小的两个结点（假设下标分别为p1和p2）合并，产生新结点，将新结点的信息存放在第n+1个分量中；新结点的数目为两个结点数目值之和，左右孩子域中的值分别修改为p1和p2；同时，改变下标为p1和p2结点的parent域中的值，使其等于n+1。
for(i=n;i<m;i++)//进行合并
{
p1=p2=0;
s1=s2=ma;
for(j=0;j<=i-1;j++)//选出两个果子数目最小的根结点
{
if(tree[j].parent==0)
if(tree[j].weight<s1)//查找最小
{s2=s1;
s1=tree[j].weight;
p2=p1;
p1=j;
}
else if(tree[j].weight<s2)//查找次小
{
s2=tree[j].weight;
p2=j;
}
tree[p1].parent=tree[p2].parent=i;
tree[i].weight=tree[p1].weight+tree[p2].weight;
tree[i].lchild=p1;
tree[i].rchild=p2;
}
}
（3）重复（2），每次均从parent域的值为0的所有结点中选择数目最小和次小的两个结点合并，产生的新结点顺次存放在weight域值为0的分量中，同时修改该分量的左右孩子域值和
被合并的两个结点的parent域值，知道数组的第2n-1个分量的weight域、lchild域和rchild 域中的值被修改为止。
（4）将每次合并后产生的新结点的weight域中的值进行求和
sum=sum+tree[i].weight;
四、上机调试过程
1、语法错误及修改：由于本程序只使用了哈夫曼树的构造，所以程序可以相对来说得到简化，语句很少。
出现的问题主要是变量的定义，括号的配对。
这些问题均根据编译器的警告提示，对应将其解决。
2、逻辑问题修改和调整：本程序虽然只用到了哈夫曼树的构造，但在构造哈夫曼树的过程中也有不少是值得关注的。
寻找最小和次小结点，将它们合并，也是说易不易的。
其中主要运用了for循环语句，根据指定条件的判断，找结点，合并结点，并将产生的新结点求和。
3、时间，空间性能分析：本算法的空间复杂度很低，只需要一个一维数组存放结果即可。
因此空间复杂度为O(n)。
选取两个最小值需要逐个比较，所以时间复杂度为O(n^2)。
4、经验和体会：初拿到本课题，开始想到的是堆栈，后分析觉得用哈夫曼树，在考虑问题时要全面，不要总在字面意思上看，思考建立模型，解决问题的能力得以提高。
五、测试结果及其分析
在运行环境中运行程序显示：
根据显示说明按要求输入数据：3
键盘输入3，按enter，显示如下：
根据要求输入三个数字：
程序根据输入的数据计算出最小体力耗费值
重新运行输入其他数据情况：
输入不正确情况：将数据输入改为字符输入程序运行后如下
六、用户使用说明
程序名为果子合并问题.c，运行环境为vc++。
程序执行后显示
输入果子的种类（1到10000之间）：
在键盘按要求输入数字之后如3，按enter键显示：
输入果子的种类（1到10000之间）：3
依次输入每种果子的数目（1到20000之间）：
在键盘按要求输入数字（如1,2,3），按enter键显示结果：
依次输入每种果子的数目（1到20000之间）：1 2 9
最小体力消耗值：15
七、参考文献
[1] 王昆仑，李红.数据结构与算法. 北京：中国铁道出版社，2006年5月。
八、附录
#include "stdio.h"
#define max 10000
#define ma 20000
typedef struct
{
int weight;
int parent,lchild,rchild;
}hufmtree;
hufmtree tree[2*max-1];
main()
{
int i,m,f,n,j;
int sum=0,p1,p2,s1,s2;
printf("输入果子的种类：");
scanf("%d",&n);
m=2*n-1;
for(i=0;i<n;i++)//初始化数组
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0;
}
printf("依次输入每种果子的数目:");
for(i=0;i<n;i++)//读入果子的数目
{
scanf("%d",&f);
tree[i].weight=f;//依次赋值每种果子的数目
}
for(i=n;i<m;i++)//进行合并
{
p1=p2=0;
s1=s2=ma;
for(j=0;j<=i-1;j++)//选出两个果子数目最小的根结点 {
if(tree[j].parent==0)
if(tree[j].weight<s1)//查找最小
{s2=s1;
s1=tree[j].weight;
p2=p1;
p1=j;
}
else if(tree[j].weight<s2)//查找次小
{
s2=tree[j].weight;
p2=j;
}
tree[p1].parent=tree[p2].parent=i;
tree[i].weight=tree[p1].weight+tree[p2].weight; tree[i].lchild=p1;
tree[i].rchild=p2;
}
sum=sum+tree[i].weight;
}
printf("最小体力耗费值：");
printf("%d\n",sum);
}。