求大神发一个用树或链表写的C语言程序代码，注释越多越好，满意加分。。十万火急啊

Question

用VC6.0做的

Answer 1

//赫夫曼编码的应用
//头文件
#define MAXSIZE 30 //最大叶子数
#define MAXCODE 10000 //编码最大长度
#define OK 1
#define ERROR 0
#define OVERLOW -2
//赫夫曼树和赫夫曼编码的存储表示
typedef struct
{
char ch;
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树
typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表

int js(char s[],int cnt[],char str[])
{
//统计字符串中各种字母的个数
int i,j,k;
int temp1[27],temp2[27],temp3[11];
for(i=1;i<=26;i++)
{
temp1[i]=0;
temp2[i]=0;
}
for(i=1;i<=10;i++)
temp3[i]=0;
for(i=1;s[i]!='#';i++)
{ //统计各种字符的个数
if(s[i]>='A'&&s[i]<='Z'){
k=s[i]-64;
temp1[k]++;
}
if(s[i]>='a'&&s[i]<='z'){
k=s[i]-96;
temp2[k]++;
}
if(s[i]>='0'&&s[i]<='9'){
k=s[i]-47;
temp3[k]++;
}
}
i=1;
if(s[i]>='A'&&s[i]<='Z')
{
for(k=1,j=0;k<=26;k++)
{
if(temp1[k]!=0)
{
j++; //j保存字符的个数
str[j]=k+64; //送对应的字母到数组str[]中
cnt[j]=temp1[k]; //存入对应字母的权值到数组cnt[]中
}
}
i++;
}
if(s[i]>='a'&&s[i]<='z')
{
for(k=1,j=0;k<=26;k++)
{
if(temp2[k]!=0)
{
j++;
str[j]=k+96;
cnt[j]=temp2[k];
}
}
i++;
}
if(s[i]>='0'&&s[i]<='9')
{
for(k=1,j=0;k<=10;k++)
{
if(temp3[k]!=0)
{
j++;
str[j]=k+47;
cnt[j]=temp3[k];
}
}
i++;
}
return j;
}

void Select(HuffmanTree HT, int n, int *s1, int *s2)
//选择parent为0且weight最小的两个结点,其序号分别为s1和s2。
{
unsigned int minsum = 10000;
int i,j;
for(i=1; i<=n; i++)
{
if(HT[i].parent)
continue;
for(j=i+1; j<=n; j++)
{
if(HT[j].parent)
continue;
if(HT[i].weight + HT[j].weight<minsum)
{
minsum = HT[i].weight + HT[j].weight;
*s1 = i;
*s2 = j;
}
}
}
}

void CreateHuffmanTree(HuffmanTree &HT, int cnt[], char t[],int n)
{//建立赫夫曼树叶
int m, s1, s2, i;
if(n <= 1)
return;
m = 2*n-1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));//0号单元未用
for( i = 1; i <= n; i++)
{
HT[i].ch=t[i];
HT[i].weight = cnt[i];
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for( ;i <= m; ++i)
{
HT[i].ch=0;
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
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[i].weight = HT[s1].weight + HT[s2].weight;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[s1].parent = i;
HT[s2].parent = i;
}

}

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//从叶子到根逆向求每个字符的赫夫曼编码
int start, f,i;
unsigned int c;
char *cd;
cd = (char *)malloc(n * sizeof(char)); //分配求编码的工作空间
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
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]);
}
free(cd);
}

void print(HuffmanTree &HT, int i)
{//输出构造的树
int k;
printf("\n构造出来的赫夫曼树是:\n");
printf(" weight parent lchild rchild");
for(k = 1; k <= 2*i -1; ++k)
{
printf("\n%2d*%7d%7d%7d%7d",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);
}
}

void printcode(HuffmanTree HT,HuffmanCode HC,int n,char str[])
{//输出得到的各权Huffman编码
int j;
printf("\n得到的各权Huffman编码是:\n");
printf("\t weight code\n");
for(j=1; j <= n; j++)
{
printf("%7c%7d%10s\n",str[j],HT[j].weight,HC[j]);
}
}

char printcoding(HuffmanTree HT,HuffmanCode HC,int x1,int x,char str[])
{

FILE *fp;
if((fp=fopen("coding.txt","w"))==NULL)
printf("The file coding.txt can not open!");
int i,j;
for(i=1;i<=x1;i++)
{
for(j=1;j<=x;j++)
if(str[i]==HT[j].ch)
{
fputs(HC[j],fp);
printf("%s",HC[j]);
break;
}
}
printf("\n");
fclose(fp);
return 1;
}
//主函数

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"hfm.h"
void main()
{
char ch;
char t[100];
char str[100];
int cnt[100];
FILE *fp;
if((fp=fopen("code.txt","r"))==NULL)
{
printf("The file can not be read!");
exit(0);
}
ch=fgetc(fp);
int i=1;
t[i]=ch;
printf("原码为:\n");
while(ch!='#')
{
putchar(ch);
ch=fgetc(fp);
i++;
t[i]=ch;
}
int x1=i-1;
printf("\n\n");
int x=js(t,cnt,str);
//printf("字符个数为j=%d\n",j);
fclose(fp);
HuffmanTree HT;
HuffmanCode HC;
for(i=1;i<=x;i++)
{
printf("%7c的权值=%d\n",str[i],cnt[i]);
}
cnt[i] ='\0';
CreateHuffmanTree(HT, cnt, t,i-1);
print(HT,i-1);
printf("\n");
HuffmanCoding(HT, HC, i-1);
printcode(HT,HC,i-1,str);
printf("\n译码后的字符串：\n");
printcoding(HT,HC,x1,x,t);
}