关于课程设计的程序

Question

要求用哈弗曼树做一个编码译码的程序，首先从一个文件中读取信息，统计所有的字符频率，根据这个做成哈弗曼树，根据哈弗曼树得到每一个字符的代码（1010之类的），再编译源文件并存到另一个文件中，然后再编译后的文件通过这个哈弗曼树翻译回来，并存到另一个文件中。我要源程序啊，就是那种粘贴下来就能运行的！！！求各位大侠帮帮忙！！！

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;/*动态分配数组存储哈夫曼树*/
typedef char **HuffmanCode;/*动态分配数组存储哈夫曼编码表*/

typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
MinCode Select(HuffmanTree HT,int n);

HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
{ /* w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.*/
int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
int f,c,start,m;
MinCode min;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未用*/
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++){ /*建哈夫曼树*/
/*在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2.*/
min=Select(HT,i-1);
s1=min.s1;
s2=min.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 *)); /*分配n个字符编码的头指针向量*/
cd=(char *)malloc(n*sizeof(char *)); /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=0;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); /*释放工作空间*/
return HC;
}

MinCode Select(HuffmanTree HT,int n)
{
int min,secmin;
int temp;
int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=0;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=0;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}

void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
int i,n=8;
char c[8]={'A','B','C','D','E','F','G','H'};
int w[8]={5,29,7,8,14,23,3,11};
HC=HuffmanCoding(HT,HC,w,n);
printf("HuffmanCode:\n");
printf("Char\t\tWeight\t\tCode\n");
for(i=0;i<=n-1;i++)
printf("%c\t\t%d\t\t%s\n",c[i],w[i],HC[i]);

getch();
}
运行成功了的,你可以改一下里面的数据.

Answer 2

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define LEN sizeof(node)

typedef struct polynode
{
int coef;
int exp;
struct polynode *next;
}node;

node * create(void)
{
node *h,*r,*s;
int c,e;
h=(node *)malloc(LEN);
r=h;
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
while(c!=0)
{ s=(node *)malloc(LEN);
s->coef=c;
s->exp=e;
r->next=s;
r=s;
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
}
r->next=NULL;
return(h);
}

void polyadd(node *polya, node *polyb)
{
node *p,*q,*pre,*temp;
int sum;
p=polya->next;
q=polyb->next;
pre=polya;
while(p!=NULL&&q!=NULL)
{
if(p->exp<q->exp)
{
pre->next=p;
pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
else
{
pre->next=q;
pre=pre->next;
q=q->next;
}
}
if(p!=NULL)
pre->next=p;
else
pre->next=q;
}

void print(node * p)
{
while(p->next!=NULL)
{
p=p->next;
printf(" %d*x^%d",p->coef,p->exp);

}
}

main() /*主函数*/
{
node * polya,* polyb;
printf("Welcome to use!\n");
printf("\nPlease input the ploya include coef && exp:\n");
polya=create();
print(polya);
printf("\nPlease input the ployb include coef && exp:\n");
polyb=create();
print(polyb);
printf("\nSum of the poly is:\n");
polyadd(polya,polyb);
print(polya);
printf("\n");
}