算法设计与分析实验3报告.docx
《算法设计与分析实验3报告.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验3报告.docx（18页珍藏版）》请在冰点文库上搜索。
算法设计与分析实验3报告
湖南科技学院实验报告
系部
数学与计算科学
专业
信息与计算科学
成绩评定
班级
信计0902班
学号
200905002231
姓名
易丹
课程名称
算法设计与分析
实验时间
2012.4.16
实验编号
实验三
实验名称
贪心算法
实验环境
D315、一台电脑、Codeblocks10.05
实验目的
1.理解贪心算法的概念。
2.理解贪心算法与动态规划算法的差异。
3.掌握贪心算法的基本要素。
4.掌握设贪心设计策略。
实验内容（①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）
实验内容：
1.最小生成树的Kruskal算法
实现最小生成树的Kruskal算法。
数据文件见附件。
2.哈夫曼编码（选做）
实现哈夫曼算法。
数据文件见附件。
实验要求：
1.实验报告只写实验⑴。
2.写出算法思想、主要程序代码、算法复杂性分析。
实验
（1）的步骤、算法及运行结果：
⑴打开Codeblocks10.05，编辑如下程序如下：
UnionFind.h
#ifndefUNIONFIND_H_INCLUDED
#defineUNIONFIND_H_INCLUDED
//并查集（Union-Find-Sets）
classUnionFind//并查集的类定义
{
private:
int*parent;//集合元素数组（存放各元素的双亲结点的指针）
intsize;//集合元素的数目
public:
UnionFind（ints=10）;//构造函数
~UnionFind（）//析构函数
{
delete[]parent;
}
UnionFind&operator=（UnionFindconst&Value）;//集合赋值
voidUnion（intRoot1,intRoot2）;//两个子集合合并
intFind（intx）;//搜寻集合x的根
};
UnionFind:
:
UnionFind（ints）//构造函数，s是集合元素个数
{
size=s;
parent=newint[size+1];//创建双亲指针数组
for（inti=0;i<=size;i++）
parent[i]=-1;//每一个自成一个单元素集合
}
intUnionFind:
:
Find（intx）//搜索并返回包含元素x的树的根
{
if（parent[x]<=0）
returnx;
else
returnFind（parent[x]）;
}
voidUnionFind:
:
Union（intRoot1,intRoot2）//并
{
parent[Root2]=Root1;//将根Root2连接到另一个根Root1下面
}
#endif//UNIONFIND_H_INCLUDED
MinHeap.h
#ifndefMINHEAP_H_INCLUDED
#defineMINHEAP_H_INCLUDED
#include
#include
usingnamespacestd;
#defineDefaultSize20
templateclassMinHeap;
template
ostream&operator<<（ostream&os,constMinHeap&）;
////////////////////////////////////////////////////////
//MinHeap堆类最小堆的声明和定义
//即以完全二叉树的顺序存储方式来实现优先级队列
//T为结点的类型
////////////////////////////////////////////////////////
template//T为结点的类型
classMinHeap
{
public:
MinHeap（intsz=DefaultSize）;//构造函数,建立一个空堆
MinHeap（T*arr,intn）;//构造函数,通过数组来建堆
~MinHeap（）//析构函数,释放堆的内存空间
{
if（heap!
=NULL）
delete[]heap;
}
boolInsert（constT&x）;//将元素x插入到最小堆中
voidInitialize（T*arr,intn,intm）;//用有n个元素的数组arr建容量为m的堆
boolDeleteMin（T&x）;//删除堆顶的最小元素
boolIsEmpty（）const//判断当前堆是否为空
{
returncurrentSize==0;
}
boolIsFull（）const//判断当前堆是否为满
{
returncurrentSize==MaxHeapSize;
}
voidMakeEmpty（）//把当前堆置空
{
currentSize=0;
}
voidDisplay（）;//显示当前堆的内容
voidsiftDown（）;//下浮全部调整
voidsiftUp（）;//上浮全部调整
voidDeactivate（）;//释放内存空间
friendostream&operator<<<>（ostream&os,constMinHeap&）;//友元重载运算浮输出堆的内容
intGetCurrentSize（）//获取堆中元素个数
{
returncurrentSize;
}
intGetMaxheapSize（）//获取当前堆的最大容量
{
returnMaxHeapSize;
}
private:
T*heap;//存放最小堆中元素的数组的首指针
intcurrentSize;//最小堆中当前元素的个数
intMaxHeapSize;//最小堆中最多允许的元素的个数
voidsiftDown（intstart,intm）;//从start到m下滑调整成为最小堆
voidsiftUp（intstart）;//从start到0上滑调整成最小堆
};
///////////////////////////////////////MinHeap类声明结束
////////////////////////////////////////////////////////
//构造函数
//建立一个空的最小堆,并在定义的时指定堆的尺寸大小
//T为结点的类型
////////////////////////////////////////////////////////
template
MinHeap:
:
MinHeap（intsz）
{
//设定堆的最多允许的元素的个数
MaxHeapSize=（DefaultSizesz:
DefaultSize;
//为堆的顺序存储结构开辟内存空间
heap=newT[MaxHeapSize];
//如果内存分配失败
if（heap==NULL）
{
cout<<"最小堆的内存分配失败!
"<exit
（1）;
}
//刚开始堆中的元素的个数是0个
currentSize=0;
}
////////////////////////////////////////////构造函数结束
////////////////////////////////////////////////////////
//带参数的构造函数用数组中的元素创建堆
////////////////////////////////////////////////////////
template
MinHeap:
:
MinHeap（T*arr,intn）//arr的下标从1开始
{
MaxHeapSize=（DefaultSizen:
DefaultSize;//得到最大允许的元素的个数
heap=newT[MaxHeapSize];//开辟最小堆的内存
if（heap==NULL）//如果内存分配失败
{
cout<<"最小堆的内存分配失败!
"<exit
（1）;
}
for（inti=1;i<=n;i++）//把参数数组中的元素一次复制到堆中
Insert（arr[i]）;
currentSize=n;
}
////////////////////////////////////带参数的构造函数结束
//释放内存空间
template
voidMinHeap:
:
Deactivate（）
{
delete[]heap;
}
////////////////////////////////////////////////////////
//siftDown（）私有成员函数
//从start到m下滑调整成为最小堆
//下滑调整的前提是当前结点的左右子树都已经成堆
////////////////////////////////////////////////////////
template
voidMinHeap:
:
siftDown（intstart,intm）
{
inti=start;//i从start开始调整
intj=2*i+1;//用于指向要和i对调的结点,先指向i的左子结点
Ttemp;//交换时用到的中间结点
while（j<=m）//到m时调整结束
{
//如果至少有一个子结点小于根结点,则需要调整
if（heap[j]{
//如果左子结点大于右子结点
if（heap[j]>heap[j+1]）
j=j+1;//跟较小的子结点进行位置调整
//如果根根结点更大,则要进行调整
if（heap[i]>heap[j]）
{
//交换Heap[i]和Heap[j]的数据内容
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
}
i=j;//从刚对调完的子结点继续调整下去
j=2*i+1;
}
else
break;
}
}
//////////////////////////////////////siftDown（）函数结束
////////////////////////////////////////////////////////
//siftDown（）公有成员函数
//对堆进行全部的下浮调整,只针对所有分支结点从后往前即可
////////////////////////////////////////////////////////
template
voidMinHeap:
:
siftDown（）
{
//找到最后一个还有子结点的结点
intcurrentPos=（currentSize-2）/2;
//从当前的currentPos依次向前进行下滑调整
while（currentPos>=0）
{
//局部自上而下地下滑调整
siftDown（currentPos,currentSize-1）;
//再向前换一个分支结点
currentPos--;
}
}
/////////////////////////////////////siftDown（）函数结束
////////////////////////////////////////////////////////
//siftUp（）私有成员函数
//从start开始向上调整到根结点（0）
//利用了一个子结点都至多有一个父结点的特性
////////////////////////////////////////////////////////
template
voidMinHeap:
:
siftUp（intstart）
{
inti=start;//从i结点开始向上浮动调整
intj;//指向要调整的父结点
Ttemp;//交换用的临时变量
while（i>0）
{
//得到当前结点i的父结点的指针
if（i%2==1）//如果i是奇数结点
j=（i-1）/2;//说明i是j的左子结点
else
j=（i-2）/2;//说明i是j的右子结点
if（heap[i]{
//交换Heap[i]和Heap[j]的数据内容
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
}
i=j;//继续上浮调整
}
}
////////////////////////////////////////siftUp（）函数结束
////////////////////////////////////////////////////////
//siftUp（）公有成员函数
//对堆进行全部的上浮调整,即堆所有的叶子结点从后往前调整
////////////////////////////////////////////////////////
template
voidMinHeap:
:
siftUp（）
{
//通过上浮的方法来调整堆
//从最后一个结点进行上浮调整
intcurrentPos=currentSize-1;
//从后往前调整到第一个叶子结点就可以了
intend=currentSize-int（（currentSize-1）/2）-1;
//从后往前对每个叶子结点进行上浮调整
while（currentPos>=end）
{
siftUp（currentPos）;
currentPos--;
}
}
////////////////////////////////////////siftUp（）函数结束
////////////////////////////////////////////////////////
//Display（）公有成员函数
//显示当前堆序列的内容
////////////////////////////////////////////////////////
template
voidMinHeap:
:
Display（）
{
//显示堆的内容
for（inti=0;icout<}
///////////////////////////////////////Display（）函数结束
////////////////////////////////////////////////////////
//友元重载输出运算符<<输出当前堆的内容
////////////////////////////////////////////////////////
template
ostream&operator<<（ostream&os,constMinHeap&MH）
{
//显示堆中的内容
for（inti=0;ios<returnos;
}
//////////////////////////////////////////<<友元重载结束
////////////////////////////////////////////////////////
//Insert（）公有成员函数
//在堆的尾部插入一个元素,并进行重新调整
////////////////////////////////////////////////////////
template
boolMinHeap:
:
Insert（constT&x）
{
//如果堆中的元素已经满了
if（currentSize==MaxHeapSize）//堆满则调整容量
{
T*p=heap;
heap=newT[MaxHeapSize+DefaultSize];
if（heap==NULL）
{
cout<<"最小堆的内存分配失败!
"<exit
（1）;
}
for（inti=0;iheap[i]=p[i];
MaxHeapSize+=DefaultSize;
delete[]p;
}
//把新元素先放在最后一个位置
heap[currentSize]=x;
currentSize++;
//对堆进行重新调整,只要对最后一个结点作一次上浮调整即可
siftUp（currentSize-1）;
returntrue;
}
////////////////////////////////////////Insert（）函数结束
//用有n个元素的数组arr建容量为m的堆
template
voidMinHeap:
:
Initialize（T*arr,intn,intm）//arr的下标从1开始
{
delete[]heap;
intk=n>m?
n:
m;
heap=newT[k];
if（heap==NULL）
{
cout<<"最小堆的内存分配失败!
"<exit
（1）;
}
MaxHeapSize=m;
for（inti=1;i<=n;i++）
Insert（arr[i]）;
currentSize=n;
}
////////////////////////////////////////////////////////
//DeleteMin（）公有成员函数
//删除堆顶的最小的结点,并进行再次调整
//（只需对新堆顶作一次下沉调整即可）
////////////////////////////////////////////////////////
template
boolMinHeap:
:
DeleteMin（T&x）
{
//如果堆中的元素已经没有了
if（currentSize==0）
{
cout<<"堆中已经没有元素了!
"<returnfalse;
}
//删除堆顶的元素
x=heap[0];
//把最后一个元素替换到堆顶的位置
heap[0]=heap[currentSize-1];
//现存的元素个数减一
currentSize--;
//对堆顶元素作一次下沉调整即可
siftDown（0,currentSize-1）;
returntrue;
}
/////////////////////////////////////DeleteMin（）函数结束
#endif//MINHEAP_H_INCLUDED
Main.cpp
#include
#include"MinHeap.h"
#include"UnionFind.h"
usingnamespacestd;
template
classEdgeNode//声明边类
{
template
friendostream&operator<<（ostream&,EdgeNode）;
template
friendboolKruskal（int,int,EdgeNode*,EdgeNode*）;
public:
EdgeNode（）{}
EdgeNode（inta,intb,Typew）:
u（a）,v（b）,weight（w）{}
operatorType（）const
{
returnweight;
}
private:
intu,v;//边的两个顶点
Typeweight;//边的权
};
template
boolKruskal（intn,inte,EdgeNodeE[],EdgeNodet[]）
{
//n，顶点数
//e，边数
//E，边数组
//t，存储生成树的边
MinHeap>H
（1）;
H.Initialize（E,e,e）;//按边的权建立边的最小堆
UnionFindU（n）;//建n个元素的并查集
intk=0;//用于记录合并的次数
while（e&&k{
EdgeNodex;//定义边数组
H.DeleteMin（x）;//取权最小的一条边
cout<<"MIN:
"<e--;
inta=U.Find（x.u）;//找边的两个顶点所在的集合
intb=U.Find（x.v）;
if（a!
=b）//两顶点不属于同一集合，则合并两边所在的集合
{
t[k++]=x;//记下此边
U.Union（a,b）;
}
}
H.Deactivate（）;
return（k==n-1）;
}
template
ostream&operator<<（ostream&os,EdgeNodee）
{
os<returnos;
}
intmain（）
{
int**M;
charfilename[]="boat.txt";
ifstreaminfile（filename）;
intn=0;
infile>>n;
constinte=10;
EdgeNode
E[]={EdgeNode（0,0,0）,EdgeNode（1,2,6）,EdgeNode（2,5
升级会员 