⑴ 急求哈夫曼編碼/解碼器課程設計
我給你個差不多的，你自己修改一下就可以用了
/************Huffman編碼和解碼****************/
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ch;
char *chs;
}HuffmanCode;
typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1; int n3;
while(HT[i].parent!=0)
i++;
*n1=i;
i++;
while(HT[i].parent!=0) i++;
*n2=i;
if(HT[*n1].weight<HT[*n2].weight)
for(i++;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[*n1].weight)
*n1=i;
else if(HT[i].weight<HT[*n2].weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n<=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++,w++)
for(;i<=m;i++,p++)
for(i=n+1;i<=m;i++)
{
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;
}
HC=(HuffmanCode *)malloc((n+1)*sizeof(char));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
for(c=i,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].ch=HT[i].ch;
HC[i].chs=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i].chs,&cd[start]);
printf("%c %-10s\n",HC[i].ch,HC[i].chs);
}
HUF->HT=HT;
HUF->HC=HC;
return HUF;
}
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
strcpy(chars1,"");
while(*p)
{
i=1; while(hc[i].ch!=*p&&i<=n) i++;
strcat(chars1,hc[i].chs); p++;
}
printf("the chars translate are:%s\n",chars1);
return chars1;
}
void transcode(HuffmanTree ht,char *chars2,char*chars3)
{
int i=1,p; char *q=chars2;char *r=chars3;
while(ht[i].parent!=0) i++;
p=i;
while(*q)
{
while(ht[p].lchild!=0 && *q)
{
if(*q=='0')
p=ht[p].lchild;
else p=ht[p].rchild;
q++;
}
if(ht[p].lchild==0)
p=i;
}
*r='\0';
printf("the chars are:");
puts(chars3);
}
void input(int *n,sw *w)
{
int i;
printf("input the mount of char:");
scanf("%d",n);
for(i=1;i<=*n;i++,w++)
{printf("input the %dth char and weight:",i);
fflush(stdin);
scanf("%c%d",&w->ch,&w->weight);
}
}
void main(void)
{HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w[40];
char ch,inchar[500],outchar[1000];
char *abc;
char *p=inchar;
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate,ends of '#':");
fflush(stdin);//清除流,解決輸入干擾
ch=getchar();
while(ch!='#')
{*p=ch;
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
}
⑵ 求一個<哈夫曼編碼>數據結構課程設計（C語言版）
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define M 50
#define MAX 1000;
typedef struct
{
int weight;//結點權值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//動態分配數組存儲哈夫曼編碼表
HUFFMANTREE huffmantree(int n,int weight[])//構建哈夫曼樹
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼樹中各結點的數據，沒初始值的賦值為0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循環從森林中選擇最小的兩棵樹組建成一顆新樹
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(const int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n個字元編碼的頭指針
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]='\0';//編碼結束符
for(i=1;i<=n;++i)//逐個字元求哈夫曼編碼
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*從葉子結點到根結點求逆向編碼*/
if(ht[father].lchild==child)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char*)malloc((n-start)*sizeof(char));//為i個字元編碼分配空間
strcpy(hc[i],&cd[start]);//從cd復制哈夫曼編碼串到hc
}
free(cd);//釋放工作空間
for(i=1;i<=n;++i)
{
printf("%c的編碼:",str[i]);
printf("%s\n",hc[i]);
}
}
void main()
{
int i,j,k;
char str[50];
int weight[50];
printf("請輸入字元(一次性連續輸入所求的字元):");/*如:abcjhjg不要輸成ab cj hig,即字元間不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
const int n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("請輸入%c的權值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
⑶ 哈夫曼編/解碼器的問題：請求高手幫幫忙，課程設計用的，自己寫的錯誤太多了，萬分感謝，c描述。拜託了
以下程序在c-free下測試成功。
演算法參考 數據結構（C語言版）——清華大學出版社
請根據題目具體要求進行修改！有問題找我……
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef char** HuffmanCode;
typedef int Status;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
//w存放n個字元的權值（均>0），構造Huffman樹HT，並求出n個字元的Huffman編碼HC
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用
for(p=HT,i=1;i<=n;++i,++p,++w)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i,++p)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
//在HT[1...i-1]選擇parent為0且weight最小的兩個結點，其序號分別為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].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
//從葉子到根逆向求每個字元的Huffman編碼
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //逐個字元求編碼
{
start=n-1;
for(c=i,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]); //從cd復制編碼到HC
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else
(*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else
if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c;
int i,n;
int wei;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}
⑷ 急求課程設計：哈夫曼編譯碼器
這個是我課程設計弄的，也是哈弗曼編碼解碼器
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct{
int weight;
int parent,lchild,rchild;
int asc;
}HTNode,*HuffmanTree; //定義赫夫曼存儲結構
struct node{
int ASCII;
int n;
};
struct node a[127];
struct node w[127];
//一些全局變數
int count;
HTNode H_T[250];
char ** HC;
char filename[20];
//函數聲明
void menu1(); //菜單1
HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序
void MinHeapify(HuffmanTree HT, int k,int len); //調整成一個小頂堆
void buildMinHeap(HuffmanTree HT,int len); //建一個小頂堆
void swap(HTNode &t1,HTNode &t2); //交換兩結構體
void savefile(); //把輸入的英文文章保存到文件
void loadfile(); //從文件中讀取文章
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼數並存入文件
void BianMa(HuffmanTree HT,int n ); //字元編碼
void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章編碼
int loadfile2(); //從文件讀入文章
void JieMa(); //解碼
//主函數
int main()
{
char s;
while(s!='0')
{
system("cls");
cout<<"\n\n\n";
cout<<"\t\t\t\t赫夫曼編碼/解碼器"<<endl<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 1.編碼"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 2.解碼"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 0.退出"<<endl<<endl<<endl<<endl;
cout<<"\t請輸入0—2進行選擇，按回車確認";
cin>>s;
switch(s)
{
case '1': menu1(); break;
case '2':
{
system("cls");
JieMa();
system("pause");
break;
}
}
}
}
//菜單1
void menu1(){
char s;
int i;
int a;
char c;
char fpname[20]="article.txt";
HuffmanTree HT;
while(s!='0'){
system("cls");
cout<<"\n\t\t\t\t編碼界面";
cout<<"\n\n\n\t\t\t\t1.輸入英文文章"<<endl;
cout<<"\n\n\t\t\t\t2.從文件中讀入文章"<<endl;
cout<<"\n\n\t\t\t\t0.返回上一層"<<endl;
cout<<"\n\t請輸入0—2進行選擇，按回車確認";
cin>>s;
switch(s){
case'1':
system("cls");
savefile();
loadfile();
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,fpname);
system("cls");
cout<<"出現字元種類共計：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;
cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字元：";
cout<<c<<endl;
cout<<"\t\t\tASCII碼：";
cout<<a<<endl;
cout<<"\t\t\t頻數：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼編碼：";
cout<<HC[i]<<endl;
}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的編碼已存入文件「赫夫曼編碼.txt」"<<endl;
system("pause");
break;
case'2':
system("cls");
if(loadfile2())
{ system("pause");
return;}
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,filename);
system("cls");
cout<<"出現字元種類共計：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;
cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字元：";
cout<<c<<endl;
cout<<"\t\t\tASCII碼：";
cout<<a<<endl;
cout<<"\t\t\t頻數：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼編碼：";
cout<<HC[i]<<endl;
}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的編碼已存入文件「赫夫曼編碼.txt」"<<endl;
system("pause");
break;
}
}
}
//交換結構體
void swap(HTNode &t1,HTNode &t2)
{
HTNode m;
m = t1;
t1 = t2;
t2 = m;
}
//從鍵盤輸入文章並保存
void savefile(){
FILE *fp;
char article;
if((fp=fopen("article.txt","w"))==NULL){
printf("打開文件不成功！");
exit(0);
}
cout<<"請輸入英文文章,以#結束:";
getchar();
article=getchar();
while(article!='#'){
fputc(article,fp);
article=getchar();
}
fclose(fp);
}
//從文件讀取文章，並統計字元出現頻數
void loadfile(){
FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++) //把所有字元的ascii碼存在數組
{ a[i].ASCII=i;
a[i].n=0;
}
if((fp=fopen("article.txt","r"))==NULL){
printf("打開文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);
for(i=0;i<=127;i++) //統計字元種類總數
{
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}
}
//調整為小頂堆
void MinHeapify(HuffmanTree HT, int k,int len)
{
int left=k*2;
int right=k*2+1;
int large;
int l=len;
large = k;
if (left<=l&&HT[left].weight<HT[large].weight)
large = left;
if (right<=l&& HT[right].weight<HT[large].weight)
large=right;
if (large!=k)
{
swap(HT[k],HT[large]);
MinHeapify(HT,large,l);
}
}
//建立小頂堆
void buildMinHeap(HuffmanTree HT,int len)
{
int i;
for (i=len/2;i>=1;i--)
{
MinHeapify(HT,i,len);
}
}
//堆排序
HuffmanTree HeapSort(HuffmanTree HT,int length)
{
int i;
int l=length;
buildMinHeap(HT,length);
for (i=length;i>= 2;i--)
{
swap(HT[1],HT[i]);
length--;
MinHeapify(HT,1,length);
}
return HT;
}
//建立赫夫曼數
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
{
int i,m,s1,s2,k1,k2,j,x,a;
FILE *fp,*fp2;
if(n<=1) return HT;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用
for(i=1,j=0;i<=n;i++,j++)
{ HT[i].asc=w[j].ASCII;
HT[i].weight=w[j].n;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;i++)
{ a=250+i;
HT[i].asc=a;//父親節點的asc可以是大於127的任意值
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=1;i<=n;i++){
H_T[i].asc=HT[i].asc;
H_T[i].parent=HT[i].parent;
H_T[i].lchild=HT[i].lchild;
H_T[i].rchild=HT[i].rchild;
H_T[i].weight=HT[i].weight;
}
for(i=n+1,x=n;i<=m;i++,x--)
{
HeapSort(H_T,x);
k1=H_T[x].asc;
k2=H_T[x-1].asc;
for(j=1;j<=127;j++)
{
if(HT[j].asc==k1)
{ s1=j;break;}
}
for(j=1;j<=127;j++)
{
if(HT[j].asc==k2)
{ s2=j;break;}
}
HT[s2].parent=i;
HT[s1].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
H_T[x-1].asc=HT[i].asc;
H_T[x-1].lchild=HT[i].lchild;
H_T[x-1].parent=HT[i].parent;
H_T[x-1].rchild=HT[i].rchild;
H_T[x-1].weight=HT[i].weight;
}
if((fp2=fopen("count.txt","w"))==NULL) //保存赫夫曼樹
{
cout<<"文件打開不成功！"<<endl;
exit(0);
}
fputc(count,fp2);
if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
{ cout<<"文件打開不成功！"<<endl;
exit(0);
}
for(i=1;i<=(2*count-1);i++){
fwrite(&HT[i],sizeof(HTNode),1,fp);
}
fclose(fp);
fclose(fp2);
return HT;
}
//逆向編碼
void BianMa(HuffmanTree HT,int n){
char *cd,temp;
int c,f,i,j,len,p,q;
cd=(char *)malloc(n*sizeof(char));
HC=(char * *)malloc(n*sizeof(char*));
for(i=1;i<=n;i++){
for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
{ if(HT[f].lchild==c) cd[j]='0';
else cd[j]='1';
if(HT[f].parent==0)
cd[j+1]='\0';
}
len=strlen(cd);
for(p=0,q=len-1;p<=q;p++,q--)
{
temp=cd[q];
cd[q]=cd[p];
cd[p]=temp;
}
cd[len]='\0';
HC[i]=(char*)malloc((len+10)*sizeof(char));
strcpy(HC[i],cd);
}
}
//整篇文章編碼，並存入文件
void BianMa_all(HuffmanTree HT,char**HC,char *filename){
char ch;
int k,i;
FILE *fp,*fp2;
char code[100];
if((fp=fopen(filename,"r"))==NULL){
printf("打開文件不成功！");
exit(0);
}
if((fp2=fopen("赫夫曼編碼.txt","w"))==NULL){
printf("打開文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
while(!feof(fp))
{
for(i=1;i<=count;i++)
{
if(k==HT[i].asc)
strcpy(code,HC[i]);
}
fputs(code,fp2);
ch=fgetc(fp);
k=(int)ch;
}
fclose(fp);
fclose(fp2);
}
void JieMa(){
int i,k,a,t,n=0;
FILE *fp1,*fp2,*fp3;
char ch,c;
HuffmanTree ht;
if((fp3=fopen("count.txt","r"))==NULL) //從文件讀出字元總數
{
printf("打開文件不成功！");
exit(0);
}
n=fgetc(fp3);
ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
if((fp1=fopen("赫夫曼編碼.txt","r"))==NULL)
{
printf("打開文件不成功！");
exit(0);
}
if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
{ cout<<"文件打開不成功！"<<endl;
exit(0);
}
for(i=1;i<=2*n-1;i++)
fread(&ht[i],sizeof(HTNode),1,fp2);
for(i=1;i<=2*n-1;i++)
{
if(ht[i].parent==0){t=k=i;break;}
}
ch=fgetc(fp1);
while(!feof(fp1)){
if(ch=='0')
{
k=ht[k].lchild;
if(ht[k].lchild==0)
{a=ht[k].asc;
c=(char)a;
printf("%c",c);;
k=t;
}
}
if(ch=='1')
{
k=ht[k].rchild;
if(ht[k].lchild==0)
{ a=ht[k].asc;
c=(char)a;
printf("%c",c);
k=t;
}
}
ch=fgetc(fp1);
}
fclose(fp1);
fclose(fp2);
}
//讀取文件中的文章，可自己選擇文件
int loadfile2(){
FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++)
{ a[i].ASCII=i;
a[i].n=0;
}
cout<<"\n\n\n\t\t\t請輸入你要打開的文件名：";
cin>>filename;
if((fp=fopen(filename,"r"))==NULL){
printf("打開文件不成功！");
return 1;
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);
for(i=0;i<=127;i++){
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}
return 0;
}
⑸ 我們有個數據結構的哈夫曼編碼解碼的課程設計，你能幫幫我嗎
樹和哈夫曼樹實驗報告
一．實驗目的
練習樹和哈夫曼樹的有關操作，和各個演算法程序，理解哈夫曼樹的編碼和解碼
二．實驗環境
Microsoft visual c++
三．實驗問題描述
1. 問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，並對其進行遍歷（先序、中序和後序），列印輸出遍歷結果。
基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），並將此二叉樹按照「樹狀形式」列印輸出，然後對其進行遍歷（先序、中序和後序），最後將遍歷結果列印輸出。在遍歷演算法中要求至少有一種遍歷採用非遞歸方法。
測試數據：
ABCØØDEØGØØFØØØ（其中Ø表示空格字元）
輸出結果為：
先序：ABCDEGF
先序：CBEGDFA
先序：CGEFDBA
2. 問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮簡訊息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接受端將傳來的數據進行解碼（復原）。對於雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/解碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/解碼系統。
基本要求：(至少完成功能1-2）
一個完整的系統應具有以下功能：
I：初始化（Initialization）。從終端讀入字元集大小n，以及n個字元和n個權值，建立哈夫曼樹，並將它存於文件hfmTree中。
基本要求：
E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然後將結果存入文件CodeFile中。
D：解碼（Decoding )。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行解碼，結果存入文件TextFile中。
P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字元形式的編碼文件寫入文件CodePrint中。
T：印哈夫曼樹（TreePrinting）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字元形式的哈夫曼樹寫入文件TreePrint中。
測試數據：
設權值w=（5，29，7，8，14，23，3，11），n=8。
按照字元『0』或『1』確定找左孩子或右孩子，則權值對應的編碼為：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
用下表給出的字元集和頻度的實際統計數據建立哈夫曼樹，並實現以下報文的編碼和解碼：「THIS PROGRAM IS MY FAVORITE」。
四．實驗主要程序流
實驗題目一主要程序：
1．
void CreatBiTree(BitTree *bt)//用擴展先序遍歷序列創建二叉樹，如果是#當前樹根置為空，否則申請一個新節點//
{
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
}
2．void Visit(char ch)//訪問根節點
{
printf("%c ",ch);
}
3．
void PreOrder(BitTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
4． void InOrder(BitTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
5．int PostTreeDepth(BitTree bt) //後序遍歷求二叉樹的高度遞歸演算法//
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); //求左子樹的深度
hr=PostTreeDepth(bt->RChild); //求右子樹的深度
max=hl>hr?hl:hr; //得到左、右子樹深度較大者
return(max+1); //返回樹的深度
}
else return(0); //如果是空樹，則返回0
}
6．void PrintTree(BitTree Boot,int nLayer) //按豎向樹狀列印的二叉樹 //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",Boot->data);
PrintTree(Boot->LChild,nLayer+1);
}
7．void main()
{
BitTree T;
int h;
int layer;
int treeleaf;
layer=0;
printf("請輸入二叉樹中的元素(以擴展先序遍歷序列輸入,其中.代表空子樹):\n");
CreatBiTree(&T);
printf("先序遍歷序列為:");
PreOrder(T);
printf("\n中序遍歷序列為:");
InOrder(T);
printf("\n後序遍歷序列為:");
PostOrder(T);
h=PostTreeDepth(T);
printf("\此二叉樹的深度為:%d\n",h);
printf("此二叉樹的橫向顯示為：\n");
PrintTree(T,layer);
}
實驗二主要程序流：
1．int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n**********************歡迎使用哈夫曼編碼/解碼系統**********************\n";
cout<<"*您可以進行以下操作: *\n";
cout<<"*1.建立哈夫曼樹 *\n";
cout<<"*2.編碼(源文已在文件ToBeTra中，或鍵盤輸入) *\n";
cout<<"* 3.解碼(碼文已在文件CodeFile中) *\n";
cout<<"* 4.顯示碼文 *\n";
cout<<"* 5.顯示哈夫曼樹 *\n";
cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n";
cout<<"請選擇一個操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感謝使用本系統!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
2．// 建立哈夫曼樹函數
// 函數功能：建立哈夫曼樹（調用鍵盤建立哈夫曼樹或調用從文件建立哈夫曼樹的函數）
void HuffmanTree::CreateHuffmanTree()
{char Choose;
cout<<"你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？";
cin>>Choose;
if(Choose=='2') { //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
}
}
3. // 從鍵盤建立哈夫曼樹函數
// 函數功能：從鍵盤建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
cout<<"\n請輸入源碼字元集個數：";
cin>>Num;
if (Num<=1) {
cout<<"無法建立少於2個葉子結點的哈夫曼樹。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
for(int i=0;i<Num;i++) {//讀入哈夫曼樹的葉子結點信息
cout<<"請輸入第"<<i+1<<"個字元值";
getchar();
Node[i].sourcecode=getchar(); //源文的字元存入字元數組Info[]
getchar();
cout<<"請輸入該字元的權值或頻度";
cin>>Node[i].weight; //源文的字元權重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for(int j=Num;j<2*Num-1;j++) {//循環建立哈夫曼樹內部結點
int pos1,pos2;
int max1,max2;
pos2=pos1=j;
max2=max1=numeric_limits<int>::max( );
//在所有子樹的根結點中，選權重最小的兩個根結點，pos1最後應指向權重最小的根結點的下標
//pos2最後應指向權重第二小的根結點的下標
//max1存放當前找到的權重最小的根結點的權重
//max2存放當前找到的權重第二小的根結點的權重
for(int k=j-1;k>=0;k--) {
if (Node[k].parent==-1){//如果是某棵子樹的根結點
if (Node[k].weight<max1){ //發現比當前最大值還大的權重
max2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if(Node[k].weight<max2){ //發現比當前次大值還大的次大權重
max2=Node[k].weight;
pos2=k;
}
}//if (Node[j].parent==-1)
} //for
//在下標i處新構造一個哈夫曼樹的內部結點，其左、右孩子就是以上pos1、pos2所指向的結點
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
} //for
//產生所有葉子結點中字元的編碼
for (int m=0;m<Num;m++) {
//產生Node[i].sourcecode的編碼，存入Node[i].code中
int j=m;
int j1;
while(Node[j].parent!=-1) { //從葉結點開始往根結點走，每往上走一層，就產生一位編碼存入code[]
j1=Node[j].parent;
if(Node[j1].lchild==j)
Node[m].code.insert(0,"0");
else
Node[m].code.insert(0,"1");
j=j1; }}
cout<<"哈夫曼樹已成功構造完成。\n";
//把建立好的哈夫曼樹寫入文件hfmTree.dat
char ch;
cout<<"是否要替換原來的哈夫曼樹文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件
if(fop.fail()) {
cout<<"\n哈夫曼樹文件打開失敗，無法將哈夫曼樹寫入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數
for(int n=0;n<2*Num-1;n++) { //最後寫入哈夫曼樹的各個結點（存儲在Node[]中）
fop.write((char*)&Node[n],sizeof(Node[n]));
flush(cout); }
fop.close(); //關閉文件
cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n";}
4. // 從文件建立哈夫曼樹函數
// 函數功能：從文件建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromFile(){
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼樹文件hfmTree.dat打開失敗，無法建立哈夫曼樹。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼樹文件中的數據有誤，葉子結點個數少於2個，無法建立哈夫曼樹。\n";
fip.close();
return;
}
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼樹已從文件成功構造完成。\n";
}
5. // 編碼函數
// 函數功能：為哈夫曼樹編碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Encoder()
{
if(Node==NULL) { //內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}//if
char *SourceText; //字元串數組，用於存放源文
//讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入
char Choose;
cout<<"你要從文件中讀入源文(按1)，還是從鍵盤輸入源文(按2)？";
cin>>Choose;
if(Choose=='1') {
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) {
cout<<"源文文件打開失敗!無法繼續執行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次讀文件只統計文件中有多少個字元，將字元數存入k
fip1.close();
SourceText=new char[k+1]; //申請存放源文的字元數組空間
ifstream fip2("ToBeTran.txt"); //第二次讀源文文件，把內容寫入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
}
else { //從鍵盤輸入源文
string SourceBuff;
cin.ignore();
cout<<"請輸入需要編碼的源文(可輸入任意長，按回車鍵結束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需編碼的源文為：";
cout<<SourceText<<endl;
//開始解碼
ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件
int k=0;
while(SourceText[k]!='\0') //源文串中從第一個字元開始逐個編碼
{
int i;
for(i=0;i<LeafNum;i++){ //找到當前要編碼的源文的字元在哈夫曼樹Node[]中的下標
if(Node[i].sourcecode==SourceText[k]) { //將對應編碼寫入碼文文件
fop<<Node[i].code;
break;
};
}
if (i>=LeafNum) {
cout<<"源文中存在不可編碼的字元。無法繼續執行。\n"<<endl;
fop.close();
return;
}
k++; //源文串中的字元後移一個
}
fop.close();
cout<<"已完成編碼，碼文已寫入文件CodeFile.dat中。\n\n";
}
6. // 解碼函數
// 函數功能：對哈夫曼樹進行解碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Decoder()
{//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
//將碼文從文件CodeFile.dat中讀入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail()) {
cout<<"沒有碼文，無法解碼。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"經解碼得到的源文為：";
ofstream fop("TextFile.dat");
int j=LeafNum*2-1-1; //j指向哈夫曼樹的根
int i=0; //碼文從第一個符號開始，順著哈夫曼樹由根下行，按碼文的當前符號決定下行到左孩子還是右孩子
while(CodeStr[i]!='\0') { //下行到哈夫曼樹的葉子結點處，則譯出葉子結點對應的源文字元
if(CodeStr[i]=='0')
j=Node[j].lchild;
else
j=Node[j].rchild;
if(Node[j].rchild==-1) { //因為哈夫曼樹沒有度為1的結點，所以此條件等同於Node[j]為葉結點
cout<<Node[j].sourcecode; //屏幕輸出譯出的一個源文字元
fop<<Node[j].sourcecode;
j=LeafNum*2-1-1; //j再指向哈夫曼樹的根
}
i++;
}
fop.close();
cout<<"\n解碼成功且已存到文件TextFile.dat中。\n\n";
}
7. // 輸出碼文函數
// 函數功能：從文件中輸出哈夫曼樹的碼文
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"沒有碼文文件，無法顯示碼文文件內容。\n";
return;
}
while(fip.get(ch))
{cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
8. // 輸出函數
// 函數功能：從內存或文件中直接輸出哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintHuffmanTree()
{
//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return; }}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
⑹ 哈夫曼編碼系統（數據結構課程設計）
我也 做這個 ........悲劇了 .
⑺ 急求哈夫曼編碼/解碼器（80）課程設計，望高手幫忙
我給你個差不多的，你自己修改一下就可以用了
/************Huffman編碼和解碼****************/
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ch;
char *chs;
}HuffmanCode;
typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1; int n3;
while(HT[i].parent!=0)
i++;
*n1=i;
i++;
while(HT[i].parent!=0) i++;
*n2=i;
if(HT[*n1].weight<HT[*n2].weight)
{ n3=*n1;*n1=*n2;*n2=n3;}
for(i++;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[*n1].weight)
*n1=i;
else if(HT[i].weight<HT[*n2].weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n<=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++,w++)
{p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;}
for(;i<=m;i++,p++)
{p->weight=0;p->ch='^';p->parent=0;p->lchild=0;p->rchild=0;}
for(i=n+1;i<=m;i++)
{
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;
}
HC=(HuffmanCode *)malloc((n+1)*sizeof(char));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
for(c=i,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].ch=HT[i].ch;
HC[i].chs=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i].chs,&cd[start]);
printf("%c %-10s\n",HC[i].ch,HC[i].chs);
}
HUF->HT=HT;
HUF->HC=HC;
return HUF;
}
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
strcpy(chars1,"");
while(*p)
{
i=1; while(hc[i].ch!=*p&&i<=n) i++;
strcat(chars1,hc[i].chs); p++;
}
printf("the chars translate are:%s\n",chars1);
return chars1;
}
void transcode(HuffmanTree ht,char *chars2,char*chars3)
{
int i=1,p; char *q=chars2;char *r=chars3;
while(ht[i].parent!=0) i++;
p=i;
while(*q)
{
while(ht[p].lchild!=0 && *q)
{
if(*q=='0')
p=ht[p].lchild;
else p=ht[p].rchild;
q++;
}
if(ht[p].lchild==0)
{*r=ht[p].ch;r++;}
p=i;
}
*r='\0';
printf("the chars are:");
puts(chars3);
}
void input(int *n,sw *w)
{
int i;
printf("input the mount of char:");
scanf("%d",n);
for(i=1;i<=*n;i++,w++)
{printf("input the %dth char and weight:",i);
fflush(stdin);
scanf("%c%d",&w->ch,&w->weight);
}
}
void main(void)
{HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w[40];
char ch,inchar[500],outchar[1000];
char *abc;
char *p=inchar;
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate,ends of '#':");
fflush(stdin);//清除流,解決輸入干擾
ch=getchar();
while(ch!='#')
{*p=ch;
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
}
⑻ 哈夫曼編\解碼器的課程設計
你郵箱發過來啊
⑼ 課程設計-哈夫曼編碼/解碼的設計與實現
哈哈~~~南工的同志？？、、、、、、我也不會。
⑽ 哈夫曼編碼課程設計
郵箱留下
我給你發過去。。
這樣可以么？