算法实验报告

算法设计与分析实验报告 实验题目：活动安排

姓名：裴敏 班级：计算机1202 学号：1211610129

哈夫曼编码

一：实验目的 加深对算法的理解 二：实验要求

用C语言实现活动安排 哈夫曼编码 单源最短路径 三：程序代码 1.活动安排

#include

#define active_num 5 //活动数

#define true 1 //记录被选的活动 #define false 0 //未被选择的活动 int greedySelector(int s[],int f[],int b[]) // 算法 {

b[0] = true; int j = 0; int i = 1; int count = 1;

for(i = 1;i <=active_num; i++ ) {

if(s[i] > f[j]) {

b[i] = true; j = i; count++; } else

b[i] = false; }

printf(\"active number is %d\\n\ for(i=0;iif(b[i] == 1)

printf(\"%d \ }

return 0; }

int main() {

int i;

int start_time[active_num]; int finish_time[active_num]; int boolean[active_num];

printf(\"please input the start time\\n\"); for(i = 0; i < active_num; i++)

scanf(\"%d\

printf(\"please input the finish time\\n\"); for(i = 0; i < active_num; i++)

scanf(\"%d\

greedySelector(start_time ,finish_time ,boolean);

return 0; }

2：哈夫曼编码

#define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE 59 #define MAXBIT 10 #include

typedef struct { int data;//结点值 int weight;//权重 int flag;//表示是否带结构节点，是的话用0表示，否则1表示 int parent;//父结点 int lchild;//左结点 int rchild;//右结点 }hnodetype;

typedef struct { int bit[MAXBIT]; int start; }hcodetype;

void InitHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n) { int i;//把生成的节点初始化，把指向父结点的指针，左孩子、右孩子置空 for(i=0;i<2*n-1;i++) { HuffNode[i].weight=0; HuffNode[i].flag=0; HuffNode[i].parent=0;

HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for(i=0;ivoid OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n) { int i,j; printf(\"%d个叶结点对应编码为:\\n\ for(i=0;ivoid Haffman(hnodetype HuffNode[],hcodetype HuffCode[],int n) { int i,j,m1,m2,x1,x2,c,p; hcodetype cd; for(i=0;i{ m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j;//记下x1的地址 } else if((HuffNode[j].weight} for(j=cd.start+1;jvoid main() { hnodetype HuffNode[MAXNODE]; hcodetype HuffCode[MAXLEAF]; int n; printf(\"输入编码个数n:\\n\"); scanf(\"%d\ printf(\"\\n\");

InitHaffman(HuffNode,HuffCode,n); Haffman(HuffNode,HuffCode,n); OutputHaffman(HuffNode,HuffCode,n); }

四：实验运行结果