数据结构实验指导书06(4)

int i,j; FILE *fp;

fp=fopen(“codefile.txt”,”w”); while(*str) {

for(i=1;i<=num;i++) if(HC[i].ch==*str) {

for(j=0;j

} str++; } fclose(fp); }

⑶代码文件的译码

读文件中编码，并与原生成的哈夫曼编码表比较，遇到相等时，即取出起相应的字符存入一个新串中。

char *decode(HuffmanCode HC) {//代码文件codefile.txt译码 FILE *fp;

char str[254]; //假设元文本文件不超过254 char *p;

static char cd[n+1]; int i,j,k=0,cjs;

fp=fopen(“codefile.txt”,”r”); while(!fopen(fp)) {

cjs=0; //一个字符的编码是否读结束 for(i=0;i

16

cd[i]=’ ’;

cd[i+1]=’\\0’; //初始化cd串 cd[i]=fgetc(fp); for(j=1;j<=num;j++)

if(strcmp(HC[j].bits,cd)==0)

{

str[k]=HC[j].ch; k++; cjs=1; break; }

} }

str[k]=’\\0’; p=str; return p; }

参考程序

类型及相关变量定义存放在（shiyan6_2_1.h） #define n 100 #define m 2*n-1 typedef struct { char ch;

char bits[n-1]; int len; }CodeNode;

typedef CodeNode HuffmanCode[n+1]； typedef struct{ int weight;

int lchild,rchild,parent;

}HTNode; // 树中结点类型

typedef HTNode HuffmanTree[m+1] //0号单元不用 int num;

以下程序存放在（shiyan6_2_2.h）

void select(HuffmanTree HT,int k,int &s1,int &s2)

{ //在HT[1..k]中选择parent为0且权值最小的两个根结点 //其序号分别为s1和s2，通过引用参数带回主调函数

17

int i,j;

int min1=32767;

for(i=1;i<=k;i++) // 找s1

if (HT[i].weight

min1=HT[i].weight; } s1=j; min1=32767;

for(i=1;i<=k;i++) // 找s1

if (HT[i].weight

min1=HT[i].weight; } s2=j;

}

jsq(char *s,int cnt[],char str[]) {

char *p; int i,j,k;

int temp[27];

for(i=1;i<=26;i++) temp[i]=0;

for(p=s;*p!=’\\0’;p++) //统计各字符的个数

if(*p>=’A’ && *P<=’Z’) {

k=*p-64; tepm[k]++; } j=0;

for(i=1,j=0;i<=26;i++) if(temp[i]!=0) {

j++;

str[j]=i+64; //存入对应的字母到数组中

18

cnt[j]=temp[i] //存入对应字母的权值 } return j;

}

void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]) {//构造哈夫曼树HT int i,s1,s2;

for(i=1;i<=2*num-1;i++) //初始化HT {

HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].weight=0; }

for(i=1;i<=num;i++) //输入n个结点的权值 HT[i].weight=cnt[i];

for(i=num+1;i<=2*num;i++); //生成其余n-1个结点

{// 在HT[1..k]中选择parent=0且权值最小的两个根结点s1和s2 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; }

for(i=0;i<=num;i++) HC[i].ch=str[i]; i=1;

while(i<=num) {

printf(“字符 %c, 次数为: %d\\n”,HC[i].ch,cnt[i]); i++; } }

void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) {//根据哈夫曼树HT求哈夫曼编码

int c,p,i; //c和p分别指示HT中孩子和双亲的位置 char cd[n]; //临时存放编码串

int start ; //指示编码在cd 中的起始位置 cd[num]=’\\0’; //最后一位放串结束符 for(i=1;i<=num;i++) {

start=num;

c=i; //从叶结点HT[i]开始上朔

19

while((p=HT[c].parent)>0) //直至回朔到HT[c]的根为止 {//若HT[c]是HT[p]的左孩子,则生成0,否则生成代码1 cd[--start]=(HT[p].lchild==c)? ’0’ : ’1’; c=p; }

strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; } }

void coding(HuffmanCode HC,char *str)

{//对str 所代表的字符串进行编码并写入磁盘文件 int i,j; FILE *fp;

fp=fopen(“codefile.txt”,”w”); while(*str) {

for(i=1;i<=num;i++) if(HC[i].ch==*str) {

for(j=0;j

} str++; } fclose(fp); }

char *decode(HuffmanCode HC)

{//代码文件codefile.txt译码 FILE *fp;

char str[254]; //假设元文本文件不超过254 char *p;

static char cd[n+1]; int i,j,k=0,cjs;

fp=fopen(“codefile.txt”,”r”);

20