1. 用c语言完成：1.哈夫曼编码/译码器2.内部排序算法的性能分析
我把网上的程序修改了一下，并整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//结点权值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//动态分配数组存储哈夫曼编码表
typedef struct
{
int key; /*关键字*/
}RecordNode; /*排序节点的类型*/
typedef struct
{
RecordNode *record;
int n; /*排序对象的大小*/
}SortObject; //待排序序列
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(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("\n%c的编码:",str[i]);
printf("%s\n",hc[i]);
}
}
void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);
printf("\n请输入字符(一次性连续输入所求的字符):");/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n请输入%c的权值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}
void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("请输入待排序的随机数个数：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比较如下");
for(j=0;j<5;j++)
{
printf("\n\n对%d个数进行排序，结果为：\n",k);
printf("1.插入排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.选择排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希尔排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回车继续\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n对%d个随机数进行5次排序，平均比较次数和平均移动次数为：\n",k);
printf("1.插入排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.选择排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希尔排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}
void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("请选择要运行的功能：\n");
printf("1.哈夫曼编码译码器\n");
printf("2.内部排序性能分析\n");
printf("3.退出该程序\n\n");
printf("你的选择为：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
2. C语言哈夫曼树的编码及其解码问题，数据结构与算法，求解
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree ElemType;
typedef struct code Code;
struct TreeNode{
char c;
int Weight;
HuffmanTree Left,Right;
};
typedef struct Heap{
ElemType Data[MAXSIZE];
int Size;
int Capacity;
}*MinHeap;
struct code{
char c;
char code[10];
};
struct TNode{
int Data;
struct TNode* lchild;
struct TNode* rchild;
};
MinHeap BuildHeap()
{
MinHeap tmpH;
tmpH=(MinHeap)malloc(sizeof(struct Heap));
ElemType Min=(ElemType)malloc(sizeof(ElemType));
Min->Weight=-1,Min->Left=Min->Right=NULL;
tmpH->Size=0;
tmpH->Capacity=MAXSIZE;
tmpH->Data[0]=Min;
return tmpH;
}
int isFull(MinHeap H)
{
return H->Size>=H->Capacity;
}
int isEmpty(MinHeap H)
{
return H->Size==0;
}
void Insert(MinHeap H,ElemType T)
{
int i;
if(isFull(H)){
printf("MinHeap is Full");
return ;
}
i=++H->Size;
for(;H->Data[i/2]->Weight>T->Weight;i/=2)
H->Data[i]=H->Data[i/2];
H->Data[i]=T;
}
ElemType DeleteMin(MinHeap H){
int Parent,child;
ElemType min,tmp;
if(isEmpty(H)){
printf("The Heap is Empty");
return NULL;
}
min=H->Data[1];
tmp=H->Data[H->Size--];
for(Parent=1;Parent*2<H->Size;Parent=child)
{
child=Parent*2;
if(child!=H->Size-1&&H->Data[child]->Weight>李缺H->哪租辩Data[child+1]->Weight)
child++;
if(tmp->Weight>H->Data[child]->Weight)
{
H->Data[Parent]=H->Data[child];
}else break;
}
H->Data[Parent]=tmp;
return min;
}
void InitHeap(MinHeap H,int n)
{
ElemType tmp;
for(int i=0;i<n;i++)
{ getchar();
tmp=(ElemType)malloc(sizeof(ElemType));
scanf("%c,%d",&tmp->c,&tmp->Weight);
tmp->Left=tmp->Right=NULL;
Insert(H,tmp);
}
}
HuffmanTree Huffman(MinHeap H)
{
int i;
HuffmanTree T;
for(i=1;i<H->Size;i++)
{
T=(HuffmanTree)malloc(sizeof(HuffmanTree));
T->Left=DeleteMin(H);
T->型基Right=DeleteMin(H);
T->Weight=T->Left->Weight+T->Right->Weight;
Insert(H,T);
}
T=DeleteMin(H);
return T;
}
int main()
{
int n;
scanf("%d",&n);
Code ans[n];
MinHeap H=BuildHeap();
HuffmanTree T;
InitHeap(H,n);
T=Huffman(H);
return 0;
}
哈夫曼树的构造，编码有01左右子树之分，稍微复杂
3. huffman编码译码的c语言实现
留个脚印，晚上回去看看
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
//typedef int TElemType;
const int UINT_MAX=1000;
char str[50];
typedef struct
{
int weight,K;
int parent,lchild,rchild;
}HTNode,* HuffmanTree;
typedef char **HuffmanCode;
//-----------全局变量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n;
char z[50];
int flag=0;
int numb=0;
// -----------------求赫夫曼编码-----------------------
struct cou{
char data;
int count;
}cou[50];
int min(HuffmanTree t,int i)
{ /核毕/ 函数void select()调用
int j,flag;
int k=UINT_MAX; // 取k为不小拍氏庆于可能的值,即k为最大的权值1000
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
//--------------------slect函数----------------------
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1为最小的两个值中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ //袭握 w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
//unsigned c,f;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;//检测结点数是否可以构成树
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=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=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*));
// 分配n个字符编码的头指针向量([0]不用)
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));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
//---------------------获取报文并写入文件---------------------------------
int InputCode()
{
//cout<<"请输入你想要编码的字符"<<endl;
FILE *tobetran;
if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return 0;
}
cout<<"请输入你想要编码的字符"<<endl;
gets(str);
fputs(str,tobetran);
cout<<"获取报文成功"<<endl;
fclose(tobetran);
return strlen(str);
}
//--------------初始化赫夫曼链表---------------------------------
void Initialization()
{ int a,k,flag,len;
a=0;
len=InputCode();
for(i=0;i<len;i++)
{k=0;flag=1;
cou[i-a].data=str[i];
cou[i-a].count=1;
while(i>k)
{
if(str[i]==str[k])
{
a++;
flag=0;
}
k++;
if(flag==0)
break;
}
if(flag)
{
for(j=i+1;j<len;j++)
{if(str[i]==str[j])
++cou[i-a].count;}
}
}
n=len-a;
for(i=0;i<n;i++)
{ cout<<cou[i].data<<" ";
cout<<cou[i].count<<endl;
}
for(i=0;i<=n;i++)
{*(z+i)=cou[i].data;
*(w+i)=cou[i].count;
}
/* 原来未修改的初始化程序段:
flag=1;
int num;
int num2;
cout<<"下面初始化赫夫曼链表"<<endl<<"请输入结点的个数n：";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));
z=(char*)malloc(n*sizeof(char));
cout<<"\n请依次输入"<<n<<"个字符(字符型)："<<endl;
char base[2];
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"个字符:"<<endl;
gets(base);
*(z+i)=*base;
}
for(i=0;i<=n-1;i++)
{
cout<<setw(6)<<*(z+i);
}
cout<<"\n请依次输入"<<n<<"个权值："<<endl;
for(i=0;i<=n-1;i++)
{
cout<<endl<<"第"<<i+1<<"个字符的权值:";
cin>>num2;
*(w+i)=num2;
}*/
HuffmanCoding(HT,HC,w,n);
//------------------------打印编码-------------------------------------------
cout<<"字符对应的编码为:"<<endl;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout<<"下面将赫夫曼编码写入文件"<<endl<<"...................."<<endl;
FILE *htmTree;
char r[]={' ','\0'};
if((htmTree=fopen("htmTree.txt","w"))==NULL)
{
cout<<"can not open file"<<endl;
return;
}
fputs(z,htmTree);
for(i=0;i<n+1;i++)
{
fprintf(htmTree,"%6d",*(w+i));
fputs(r,htmTree);
}
for(i=1;i<=n;i++)
{
fputs(HC[i],htmTree);
fputs(r,htmTree);
}
fclose(htmTree);
cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl;
}
//---------------------编码函数---------------------------------
void Encoding()
{
cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl;
FILE *tobetran,*codefile;
if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char));
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打开文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
if(j>n)
{
cout<<"字符错误，无法编码!"<<endl;
break;
}
}
}
}
}
cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------译码函数---------------------------------
void Decoding()
{
cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("txtfile.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
char *work,*work2,i2;
int i4=0,i,i3;
unsigned long length=10000;
work=(char*)malloc(length*sizeof(char));
fgets(work,length,codef);
work2=(char*)malloc(length*sizeof(char));
i3=2*n-1;
for(i=0;*(work+i-1)!='\0';i++)
{
i2=*(work+i);
if(HT[i3].lchild==0)
{
*(work2+i4)=*(z+i3-1);
i4++;
i3=2*n-1;
i--;
}
else if(i2=='0') i3=HT[i3].lchild;
else if(i2=='1') i3=HT[i3].rchild;
}
*(work2+i4)='\0';
fputs(work2,txtfile);
cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
//-----------------------打印编码的函数----------------------
void Code_printing()
{
cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl;
FILE * CodePrin,* codefile;
if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *work3;
work3=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work3,51,codefile)==NULL)
{
cout<<"不能读取文件"<<endl;
break;
}
fputs(work3,CodePrin);
puts(work3);
}while(strlen(work3)==50);
free(work3);
cout<<"打印工作结束"<<endl<<endl;
fclose(CodePrin);
fclose(codefile);
}
//-------------------------------打印译码函数---------------------------------------------
void Code_printing1()
{
cout<<"下面打印根目录下文件txtfile.txt中译码字符"<<endl;
FILE * CodePrin1,* txtfile;
if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((txtfile=fopen("txtfile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *work5;
work5=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work5,51,txtfile)==NULL)
{
cout<<"不能读取文件"<<endl;
break;
}
fputs(work5,CodePrin1);
puts(work5);
}while(strlen(work5)==50);
free(work5);
cout<<"打印工作结束"<<endl<<endl;
fclose(CodePrin1);
fclose(txtfile);
}
//------------------------打印赫夫曼树的函数-----------------------
void coprint(HuffmanTree start,HuffmanTree HT)
{
if(start!=HT)
{
FILE * TreePrint;
if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
{cout<<"创建文件失败"<<endl;
return;
}
numb++;//该变量为已被声明为全局变量
coprint(HT+start->rchild,HT);
cout<<setw(5*numb)<<start->weight<<endl;
fprintf(TreePrint,"%d\n",start->weight);
coprint(HT+start->lchild,HT);
numb--;
fclose(TreePrint);
}
}
void Tree_printing(HuffmanTree HT,int w)
{
HuffmanTree p;
p=HT+w;
cout<<"下面打印赫夫曼树"<<endl;
coprint(p,HT);
cout<<"打印工作结束"<<endl;
}
//------------------------主函数------------------------------------
void main()
{
char choice;
while(choice!='q')
{ cout<<"\n******************************"<<endl;
cout<<" 欢迎使用赫夫曼编码解码系统"<<endl;
cout<<"******************************"<<endl;
cout<<"(1)要初始化赫夫曼链表请输入'i'"<<endl;
cout<<"(2)要编码请输入'e'"<<endl;
cout<<"(3)要译码请输入'd'"<<endl;
cout<<"(4)要打印编码请输入'p'"<<endl;
cout<<"(5)要打印赫夫曼树请输入't'"<<endl;
cout<<"(6)要打印译码请输入'y'"<<endl;
if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"<<endl;
cin>>choice;
switch(choice)
{
case 'i':
Initialization();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT,2*n-1);
break;
case 'y':
Code_printing1();
break;
default:
cout<<"input error"<<endl;
}
}
free(z);
free(w);
free(HT);
}
4. 怎么样用c语言程序编码哈夫曼树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
// algo6-1.cpp 求赫夫曼编码。实现算法6.12的程序
int min(HuffmanTree t,int i)
{
// 函数void select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{
// s1为最小的两个值中序号小的那个
s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=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=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);
}
return 0;
}
5. 哈夫曼编/译器(c语言)
用C语言实现的哈夫曼编码的完整代码
#define N 7 /*叶子数目,需要时更改此值即可*/
#define M 2*N-1 /*节点总数*/
typedef struct
{
char bits[N];/*编码存储，位串*/
int start; /*编码在位串中的位置*/
}codetype;
typedef struct
{
float weight;
int lchild,rchild,parent;
}hufmtree;
void HUFFMAN(tree1)
hufmtree tree1[];
{
int i,j,p1,p2;
float small1,small2,f;
hufmtree *tree;
tree=tree1;
for(i=0;i<M;i++) /*初始化*/
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0.0;
}
printf("please input a possible data weight:\n"); /*输入信源数据*/
for(i=0;i<N;i++) /*输入前n个节点的权值*/
{
scanf("%f",&f);
tree[i].weight=f;
}
for(i=N;i<M;i++) /* 进行n-1次合并，产生n-1个新的节点*/
{
p1=0,p2=0;
small1=1;small2=1;
for(j=0;j<=i-1;j++) /*从所有的节点中，选出两个权值最小的根节点*/
if(tree[j].parent==0) /*parent值为0，则显示根节点，否则便是非根节点*/
if(tree[j].weight<small1)
{
small2=small1; /*改变最小权，次小权及对应的位置*/
small1=tree[j].weight;
p2=p1; /*p1、p2记住这两个根节点在向量tree中的下标*/
p1=j;
}
else if(tree[j].weight<small2)
{
small2=tree[j].weight;/*次小权及位置*/
p2=j;
}
tree[p1].parent=i+1; /*节点分量与下标之间差值为1*/
tree[p2].parent=i+1; /*节点的标号i+1*/
tree[i].lchild=p1+1; /*最小值根节点是新节点的左孩子，分量标号是其下标加1*/
tree[i].rchild=p2+1; /*次小权根节点是新节点的右孩子*/
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}/*HUFFMANTREE()*/
void HUFFMANCODE(code1,tree1) /*根据哈夫曼树求出哈夫曼编码*/
codetype code1[]; /*求出的哈夫曼编码所在*/
hufmtree tree1[];/*已知的哈夫曼树*/
{
int i,j,c,p;
codetype cd;/*缓冲变量*/
codetype *code;
hufmtree *tree;
code=code1;
tree=tree1;
for(i=0;i<N;i++)
{
cd.start=N;
c=i+1; /*从叶节点出发向上回溯*/
p=tree[i].parent;/*tree[p-1]是tree[i]的双亲*/
while(p!=0)
{
cd.start--;
if(tree[p-1].lchild==c)
cd.bits[cd.start]='0'; /*tree[i]是左子树。生成代码'0'*/
else
cd.bits[cd.start]='1'; /*否则tree[i]是右子树。生成代码'1'*/
c=p;
p=tree[p-1].parent;
}
code[i]=cd; /*第i+1个字符的编码存入code[i]*/
}
} /*HUFFMANCODE*/
#include "stdio.h"
main()
{
int k1,k2;
hufmtree tree_fina[M];
hufmtree *p11=tree_fina;
codetype code_fina[N];
codetype *p21=code_fina;
HUFFMAN(p11); /*建立huffman树*/
HUFFMANCODE(p21,p11); /*haffman码*/
for(k1=0;k1<N;k1++) /*输出编码*/
{
printf("number %d haffmancode: ",k1+1);
for(k2=code_fina[k1].start;k2<N;k2++)
printf(" %c",code_fina[k1].bits[k2]);
printf("\n");
}
}
说明：本程序运用C语言中结构化程序的思想，将程序分为函数模块的方法逐一实现。程序分为2个函数模块HUFFMAN(tree1)、HUFFMANCODE(code1,tree1)，和主体函数main；程序结构清楚，运行正常，正常实现哈夫曼编码。拱你参考吧