杨玉森实验报告(刘改)

《数据结构》Huffman树实验报告

班级：电信0608

姓名：杨玉森

学号：012006013509

完成日期：2007年12月1日

指导教师：刘玉

目录

需求分析 .......................................................................................... 1

2 详细设计 .......................................................................................... 1

2.1程序简单流程图 ...................................................................................... 1

2.2 ？ ............................................................................................................. 1

3 调试分析 .......................................................................................... 5

3.1 出现的问题及解决 ................................................................................. 5

3.2 算法分析 ................................................................................................. 5 经验和体会 ............................................................................................. 5

4 用户使用说明 ................................................................................... 7

5 测试结果 .......................................................................................... 8 附录 9 1

数据结构实验报告

1 需求分析

本实验要求建一棵Huffman树并求树中各节点字符的Huffman编码并打印输出，本程序完成了此项要求。

程序要求输入一字符串，以#结束，其中用户可以输入任何字符，但本程序仅视小写英文字母和空格键为有效值，将其读入指定位置对其他形式的输入不作处理，即视为不存在，不做保存。

程序的输出位用户输入的有效字符，并统计其出现的次数（权值）一并输出到屏幕上；然后，程序对输入的字符进行Huffman编码并输出。

本程序能成功的完成一段任意字符串的录入并记录其中出现过的小写英文字母和空格，然后统计上述字符出现的次数（权值），然后根据以上得到的信息对有效字符（小写英文字母和空格）进行Huffman编码并输出其编码。

一、 详细设计

1.程序简单流程图如下：

2.

本程序可分为主程序、数据输入、建Huffman树并进行Huffman编码这三个模块，各模块具体说明如下：

1

1) 主函数模块：

完成各个函数的调用，及输出经处理后的输入字符，以及它们对应的权值和

Huffman编码。伪码如下：

void main()

{

getdata(&da); //调用函数完成数据的输入

Huffmancoding(&HT,&HC,count,da); //调用Huffmancoding函数

Printf(整理后的输入数据);

printf(Huffman编码); //输出Huffman编码

}

2) 数据输入模块：

完成从键盘输入一任意长度的字符串，并对其进行处理，从中提取有效的字符，

并按其ASCII码的先后顺序存入数组da的数据域中，同时统计各有效字符的权值，将其存到da中和字符对应的权值域中。伪码如下：

void getdata(HTdata **da)

{

if(!(da1 = (HTdata *)malloc(28*sizeof(HTdata)))) //给da1分配存储空间

{

error;

}

da1[1].data = ' '; //初始化da1

da1[1].w = 0;

for(i = 2;i <= 27;i++)

{

da1[i].data = 'a' + i - 2;

da1[i].w = 0;

}

while(1) // 从键盘输入数据，并将其临时存

//放在da1中并统计各个字母的权值

{ ch = getchar(); if(ch == '#') //#为输入结束标志 break; else if(ch == ' ') { if(da1[1].w == 0) count ++; //count用于记录输入字符的个数（不包括重复的） da1[1].data = ch; da1[1].w ++; } else if(ch >= 'a' && ch <= 'z') { 2

数据结构实验报告

if(da1[ch - 'a' + 2].w == 0)

count ++;

da1[ch - 'a' + 2].w ++;

}

}

if(!(*da = (HTdata *)malloc((count + 1)*sizeof(HTdata))))//da用于存放经处理过的

//数据及其权值

{

error;

}

for(i = 1;i <= 27;i ++) //将da1中的数据及其权值整理后存入da中

{

if(da1[i].w)

{

(*da)[j].data = da1[i].data;

(*da)[j++].w = da1[i].w;

}

}

}

3) 建Huffman树并进行Huffman编码模块：

本程序的关键函数，用于根据da中个字符对应的权值生成一棵Huffman树，

并求各字符所对应的Huffman编码。伪码如下：

void Huffmancoding(HTnode **ht,Huffmancode *hc,int n,HTdata *da)

{

if(n <= 1) //若结点数为一或数为空，给出相应提示并返回？

{

error;

}

if(!(*ht = (HTnode *)malloc((m +1)*sizeof(HTnode))))//动态分配存储空间存放

//Huffman树，若分配失败则提示并退出

{

error;

}

for(i = 1;i <= n;i++) //将数据存入Huffman树的前部分（数组的第一个元素未用）

{

(*ht)[i].weight =da[i].w;

(*ht)[i].lchild = 0;

(*ht)[i].parent = 0;

(*ht)[i].rchild = 0;

}

for(;i <= m;i++) //初始化后面的元素

{

(*ht)[i].weight = 0;

3

(*ht)[i].lchild = 0; (*ht)[i].parent = 0; (*ht)[i].rchild = 0; } for(i = n + 1;i <= m;i++) //生成Huffman树 { Select(*ht,i - 1,&s1,&s2); (*ht)[s1].parent = i; (*ht)[s2].parent = i; (*ht)[i].lchild = s1; (*ht)[i].rchild = s2; (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight; } if(!(*hc = (Huffmancode)malloc((n + 1)*sizeof(char *)))) { error; } if(!(cd = (char *)malloc(n*sizeof(char))))//动态分配数组存储指向Huffman编码的指 //针，若失败则提示并退出 //动态分配用来存储Huffman编码的数组，若失败则提示并退出 { error; } cd[n -1] = '\0'; //字符串结束符 for(i = 1;i <= n;i++) //对各个字符逐个进行Huffman编码 { start = n - 1; for(c = i,f = (*ht)[i].parent;f != 0;c = f,f = (*ht)[f].parent)//逆序生成Huffman编码 { if((*ht)[f].lchild == c) cd[--start] = '0'; else cd[--start] = '1'; } if(!((*hc)[i] = (char *)malloc((n - start)*sizeof(char))))//动态分配空间存放

//Huffman编码，若失败则退出

{

error;

}

strcpy((*hc)[i],&cd[start]);

}

free(cd);

} //释放存储空间

4

数据结构实验报告

二、 调试分析

1 . 出现的问题及解决

本次调试中出现的最大问题就是函数间参数的传递问题，为了解决这个问题我花了大量的时间。开始时，程序明明编译通过但是运行就是得 …… 此处隐藏：7108字，全部文档内容请下载后查看。喜欢就下载吧 ……