数据结构课程设计——哈夫曼编/译码器

#include<stdio.h> #include<iostream.h> #include<malloc.h> #define ERROR -2 #define OVERFLOW -1 #define OPENFLERR -3 #define OK 1 typedef struct CharSetElem{ int weight; char ch; }CharSetElem; typedef struct CharSetType{ CharSetElem * CSElem; int Size; //字符集大小为Size，而分配的空间+1 }CharSet; typedef struct HTNode{ char hfch; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 ///////////////Inilization's functions/////////////////// int BuildCharSet(CharSet &HCS); // int CreateHuffmanTree(HuffmanTree &HT,const CharSet &HCS); // void SelectTwoMin(const HuffmanTree HT,int n,unsigned int &s1,unsigned int &s2);// int WriteHTtoFile(const HuffmanTree &HT,int n); // int ReadHTfromFile(HuffmanTree &HT,int n); //测试用的 int AllotSpacetoHT(HuffmanTree &HT,int size); //测试用的 void PrintHuffmantree(const HuffmanTree &HT,int n);//测试用的 void Inilization(); int charsetsize; int main(){ Inilization(); /* CharSet HCS;int i;HuffmanTree HT,p,HT2; HCS.CSElem=NULL; HCS.Size=0; BuildCharSet(HCS); for(i=1;i<=HCS.Size;i++){ printf("%c %d\n",HCS.CSElem[i].ch,HCS.CSElem[i].weight); } CreateHuffmanTree(HT,HCS); p=HT+1; for(i=1;i<=2*HCS.Size-1;i++,++p){ if(i<=HCS.Size) cout<<p->hfch; cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl; }//for WriteHTtoFile(HT,2*HCS.Size); HT2=(HuffmanTree)malloc((2*HCS.Size)*sizeof(HTNode)); ReadHTfromFile(HT2,2*HCS.Size); p=HT2+1; for(i=1;i<=2*HCS.Size-1;i++,++p){ if(i<=HCS.Size) cout<<p->hfch; cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl; }//for */ return true; }//main int BuildCharSet(CharSet &HCS){ //建立哈夫曼字符集 //HCS为哈夫曼字符集 int n,k,i; char e,yorn; CharSetElem * p; printf("请输入哈夫曼字符集的大小:"); scanf("%d",&n); if(n<=1) return ERROR; charsetsize=n; //charsetsize是全局变量 p=(CharSetElem*)malloc((n+1)*sizeof(CharSetElem));//0号未用 printf("hello"); if(!p) return OVERFLOW; HCS.CSElem=p; HCS.Size=n; // printf("hello"); cout<<"请问你所要输入的字符集中是否存在空格(y/n):"; cin>>yorn; if(yorn=='y'){ cout<<"请输入空格的权值:"; cin>>HCS.CSElem[1].weight; HCS.CSElem[1].ch=' '; cout<<"在后面就不要输入空格和它的权值了!"<<endl; for(i=2;i<=n;++i){ cout<<"请输入字符集的第"<<i<<"个字符及其权值:"; cin>>e>>k; HCS.CSElem[i].weight=k; HCS.CSElem[i].ch=e; }//for }//if else if(yorn=='n') { for(i=1;i<=n;++i){ cout<<"请输入字符集的第"<<i<<"个字符及其权值:"; cin>>e>>k; HCS.CSElem[i].weight=k; HCS.CSElem[i].ch=e; }//for }//else return OK; }// BuildCharSet int CreateHuffmanTree(HuffmanTree &HT,const CharSet &HCS){ //构造哈夫曼树 unsigned int s1,s2; int m,n,i,j; HuffmanTree p; //CharSetElem *q; n=HCS.Size; m=2*n-1; //注意n是字符集中字符个数 m是将要构造的哈夫曼树的结点个数 p=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); if(!p) return OVERFLOW; HT=p; for(p=HT+1,i=1;i<=n;++i,++p){ //初始化哈夫曼树 0号单元不用管,为用 p->hfch=HCS.CSElem[i].ch; p->weight=HCS.CSElem[i].weight; p->parent=0;p->lchild=0;p->rchild=0; }//for for(;i<=m;++i,++p){ //从n+1到m的哈夫曼字符不用管,在程序中没用到 p->parent=0;p->lchild=0;p->rchild=0;p->weight=0; }//for //开始建立哈夫曼树 for(j=n+1;j<=m;++j){ SelectTwoMin(HT,j-1,s1,s2);//选择两个最小的结点，S1为最小的S2为次小的下标 HT[s1].parent=j;HT[s2].parent=j; HT[j].lchild=s1;HT[j].rchild=s2; HT[j].weight=HT[s1].weight+HT[s2].weight; }//for return OK; }//CreateHuffmanTree void SelectTwoMin(const HuffmanTree HT,int n,unsigned int &s1,unsigned int &s2){ //在HT[1'''n]中选择两个最小权值的结点并且是没有双亲的结点， //再把结点的下标赋给S1与S2 //w1,w2分别为最小的权值，次小的权值 int i; unsigned int w1=65535,w2=65535; //把w1和w2，设为机内最大数(int类型的) for(i=1;i<=n;++i){ if(HT[i].parent==0) //经过一趟循环选择最小与次小的 if(HT[i].weight<w1){ w2=w1; s2=s1; w1=HT[i].weight; s1=i; }//内if else if(HT[i].weight<w2){ w2=HT[i].weight; s2=i; }//else if }//for }//SelectTwoMin int WriteHTtoFile(const HuffmanTree &HT,int n){ //哈夫曼树写入文件hfmTree.dat中，包括0号单元 //n为结点的个数加1即(2*字符集大小) FILE *fp; // int i; fp=fopen("hfmTree.dat","wb+"); if(!fp){ cout<<"Open file error!"; return OPENFLERR;//exit(1); }//if fwrite(HT,sizeof(HTNode),n,fp); // for(i=1;i<=n;++i){ // fwrite(HT,sizeof(HTNode),1,fp); // }//for fclose(fp); return OK; }//WriteHTtoFile int ReadHTfromFile(HuffmanTree &HT,int n){ //从hfmTree.dat文件中读取哈夫曼树入HT所指空间 //n为要读入的HTNode的个数 FILE *fp; fp=fopen("hfmTree.dat","rb"); if(!fp) { cout<<"Open hfmTree.dat error!"; return OPENFLERR; }//if fread(HT,sizeof(HTNode),n,fp); fclose(fp); return OK; }//ReadHTfromFile int AllotSpacetoHT(HuffmanTree &HT,int size){//allot 英文意思是分配 //对哈夫曼树分配空间 HuffmanTree p; p=(HuffmanTree)malloc(size*sizeof(HTNode)); if(!p){ return OVERFLOW; }//if HT=p; return OK; }//AllotSpacetoHT void PrintHuffmantree(const HuffmanTree &HT,int n){ //屏幕输出哈夫曼树 //n为哈夫曼树的结点数 HuffmanTree p=HT+1; int i; for(i=1;i<=n;i++,++p){ if(i<=charsetsize) //(n+1)/2) cout<<p->hfch; cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl; }//for }//PrintHuffmantree void Inilization(){ //创建哈夫曼字符集并且生成哈夫曼树并把哈夫曼树写入文件 CharSet HCS; HuffmanTree HT;//HuffmanTree HT,HT2; BuildCharSet(HCS); CreateHuffmanTree(HT,HCS); //PrintHuffmantree(HT,2*charsetsize-1); WriteHTtoFile(HT,2*HCS.Size);//WriteHTtoFile(HT,2*charsetsize); //AllotSpacetoHT(HT2,(2*charsetsize)); //ReadHTfromFile(HT2,(2*charsetsize)); //PrintHuffmantree(HT2,2*charsetsize-1); }//Inilization