计算机软件基础实验报告
学号实验目的
1. 掌握C语言程序设计方法，并学会上机调试。
2. 熟悉Huffman编码源程序，并构造Huffman树。
实验内容
1.试设计一算法，从包括n个元素的数组中，求最大和最小元素，并使得当n
个元素为有序排列时，元素之间的比较次数仅为n-1次。
2.在给出的Huffman编码源程序基础上，要求画出Huffman树，求出与等长编
码相比时的压缩比。
实验要求
1.根据实验内容编写算法，并用C 语言进行程序设计。
2. 将所编程序在计算机上调试通过，并全面测试。
实验结果
1．以一个含有8个元素的一维数组{1，2，3，5，7，8，9，12}为例,设计程序如下：
#include
int maxArray(int x ,int y);
int minArray(int x ,int y);
int main(void)
{
int i = 0 ;
int array[8]={ 1，2，3，5，7，8，9，12} ;
printf;
do
{
scanf("%d",&array[i]);
i++;
} while(i < 8);
int maxTemp = array[0];
int minTemp = array[0];
int maxIndex = 0;
int minIndex = 0;
for(i=1;i<8;i++)
{
maxTemp = maxArray(array[i] , maxTemp);
minTemp = minArray(array[i] , minTemp);
}
for(i=0;i<8;i++)
{
if (maxTemp == array[i])
{
maxIndex = i;
}
if (minTemp == array[i])
{
minIndex = i;
}
}
printf;
return 0;
}
运行结果如下：
2.Huffman编码源程序
#include
#include
#include
#include
#include
typedef struct
{unsigned int weight; //结点权值
unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成哈夫曼树void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点void main()
{HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
int n,i; //n是哈夫曼树叶子结点数
unsigned int *w; //w存放叶子结点权值
char j='y';
printf("演示构造哈夫曼树.\n");
printf("输入需要进行编码的字符数目.\n例如:8\n");
printf("然后输入每个字符出现的次数/权值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("自动构造一棵哈夫曼树并显示哈夫曼编码.\n");
printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n"); printf(" 23---00\n 3---0111\n 11---010\n");
while(j!='N'&&j!='n')
{printf("请输入字符数目:");
scanf("%d",&n); //输入字符数目
if(n<=1) {printf("该数不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值
printf("请输入各字符出现的次数/权值:\n");
for(i=0;iCreateHuffmanTree(HT,w,n); //生成哈夫曼树
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
PrintHuffmanCode(HC,w,n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c",&j);
}
}
void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n<=1) return;
