数据结构（C语言版）实验报告（哈夫曼树）

cout<<\ \ cout<

outstuf.open(\

for(i=1;i<=27;i++) {outstuf<

int inputInit(){ //通过手动输入字符初始化哈夫曼树 cout<<\ 请输入字符集n\\t\ cin>>n;

int *w=(int *)malloc((n+1)*sizeof(int)); if(!w) {cout<<\

ch=(char *)malloc((n+1)*sizeof(char)); if(!ch) {cout<<\ cout<<\ 请输入各字符\\t\ for(int i=1;i<=n;i++) cin>>ch[i]; cout<<\ 请输入各权值\\t\ for(i=1;i<=n;i++) cin>>w[i]; //outstuf.close();

outstuf.open(\

for(i=1;i<=n;i++){outstuf<

HuffmanCoding(w);

cout<<\ 各字符编码如下：\ for(i=1;i<=n;i++) {

cout<<\ \ cout<

outstuf.open(\

for(i=1;i<=n;i++){outstuf<

int HuffmanCoding(int *w){ //哈夫曼编码 if(n<=1) return 1; int m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); if(!HT) {cout<<\ for(int i=1; i<=n; ++i)

{

HT[i].weight=w[i];

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

for(;i<=m; ++i) HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0; int s1=0; int s2=0;

for(i=n+1;i<=m; ++i){

Select(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; }

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); char *cd=(char*) malloc(n*sizeof(char)); if(!cd) {cout<<\ cd[n-1]='\\0'; int start;

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

start=n-1;

for(int c=i,unsigned int f=HT[i].parent;f!=0;c=f,f=HT[f].parent) {if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; }

HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); }

free(cd); return 0; }

void Select(int j,int &s1,int &s2){ //选择parent为0，且weight最小的两个节点序号为s1，s2 for(int h=1;h<=j;h++)

if(HT[h].parent==0) {s1=h;break;} h++;

for(;h<=j;h++)

if(HT[h].parent==0) {s2=h;break;} int m;

if(HT[s1].weight>HT[s2].weight) {m=s1;s1=s2;s2=m;} h++;

for(;h<=j;h++)

if(HT[s1].weight>HT[h].weight&&HT[h].parent==0) s1=h; for(m=1;m<=j;m++)

if(HT[s2].weight>HT[m].weight&&m!=s1&&HT[m].parent==0) s2=m;

}

void encoding(){ //选择哈夫曼编码方式 int sel=0; for(;;){

if(!HT) {cout<<\对不起，哈夫曼树不存在！请先建立哈夫曼树。\ cout<<\ cout<<\ \要编码的文件来源\\t\\t\\t\\t\\t*\

cout<<\使用已有文件encode.txt进行编码\\t\\t*\ cout<<\自行输入文件进行编码\\t\\t\\t\\t*\ cout<<\返回上层\\t\\t\\t\\t\\t*\

cout<<\ cout<<\请输入您的选择\ \ cin>>sel;

if(sel==3) break; switch(sel)

{case 1:openfileEnco();break; case 2:inputEnco();break;

default:cout<<\对不起，您输入的数据有误！请重新输入。\ } }

void openfileEnco(){ //通过打开文件encode.txt的方式进行编码 cout<<\ encode.txt文件内容如下（#代表空格）：\ ifstream infile(\ if(!infile){

cerr<<\ exit(1); }

char *file=(char *)malloc(200*sizeof(char)); for(int i=1;infile.eof()==0&&i!=200;i++){ infile>>file[i]; cout<

file=(char *)realloc(file,(200+80)*sizeof(char)); for(;infile.eof()==0&&i!=280;i++){

infile>>file[i]; cout<

int m=i;

cout<<\ 编码结果是：\ //outstuf.close();

outstuf.open(\ for(i=1;i

for(int j=1;j<=n;j++)if(file[i]==ch[j]) {cout<

if(j==(n+1)) {cout<

} cout<

void inputEnco(){ //通过手动输入的方式进行编码

cout<<\ 请输入您要编码的文章（以$作为文章结尾）\ char *file=(char *)malloc(200*sizeof(char)); for(int i=1;i<200;i++){ cin>>file[i];

if(file[i]=='$') break; }

if(i==200) {

file=(char *)realloc(file,(200+80)*sizeof(char)); for(;i<280;i++){

cin>>file[i];

if(file[i]=='$') break; } } int m=i;

cout<<\ 编码结果是：\ //outstuf.close();

outstuf.open(\ for(i=1;i

for(int j=1;j<=n;j++)if(file[i]==ch[j]) { cout<

if(j==(n+1)) {cout<