哈弗曼编码课程设计
A. 数据结构课程设计 哈夫曼编码解码 用c语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 8
#define m 2*n-1
#define max 2000
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
huffm HT[m+1];
typedef struct
{
char bits[n+1];
int start;
char ch;
}ctype;
void HuffmTree(huffm HT[m+1]);
void Huffmcode(ctype code[n+1]);
void Output (ctype code[n+1]);
/* 构造HuffmTree的函数*/
void HuffmTree(huffm *HT)
{
int i,j,p1,p2;
int s1,s2;
// for(i=1;i<=n;i++)
// {
// scanf("%d",&w);
// HT[i].wi = w;
// }
for(i=n+1;i<=m;i++)
{
p1=p2=0;
s1=s2=max;
for(j=1;j<=i-1;j++)
if(HT[j].Parent ==0)
if(HT[j].wi <s1)
{
s2=s1;
s1=HT[j].wi;
p2=p1; p1=j;
}
else if(HT[j].wi<s2)
{
s2=HT[j].wi ;
p2=j;
}
HT[p1].Parent = HT[p2].Parent =i;
HT[i].Lchild =p1;
HT[i].Rchild =p2;
HT[i].wi =HT[p1].wi + HT[p2].wi ;
}
// printf("\n OK!");
// for(i=1;i<=m;i++)
// {
// printf("\n");
// printf("%d ",HT[i].wi);
// }
// getchar();
return ;
}
/* 求HuffmTree编码的函数*/
void Huffmcode(ctype code[n+1])
{
int i,p,s;
ctype md;
for(i=1;i<=n;i++)
{
md.ch = code[i].ch;
md.start = n+1;
s = i;
p = HT[i].Parent;
while(p!=0)
{
md.start--;
if(HT[p].Lchild ==s)
md.bits[md.start]='0';
else
md.bits[md.start] ='1';
s=p;
p=HT[p].Parent;
}
code[i] = md;
}
}
/*打印编码函数*/
void Output(ctype code[n+1])
{
int i,j;
for(i=1;i<=n;i++)
{
printf("\n");
printf("%c ",code[i].ch );
for(j=1;j<=8;j++)
{
if(j<code[i].start)
printf(" ");
else
if((code[i].bits[j] == '0')||(code[i].bits[j] == '1'))
printf("%c",code[i].bits[j]);
}
printf(" %d",code[i].start);
}
}
void main()
{
int i,j;
int w;
int flag=1;
int choice;
ctype code[n+1];
char temp[n+1];
int temp2[n+1];
printf("Would you want to play?(1-Yes and Start/0-No and Exit)");
scanf("%d",&choice);
while(flag&&(choice==1))
{
choice = 0;
for(i=1;i<=m;i++)//初始化
{
HT[i].data =NULL;
HT[i].wi=0;
HT[i].Parent = 0;
HT[i].Lchild = HT[i].Rchild = 0;
}
for(i=1;i<=n;i++)
{
code[i].start = 0;
code[i].ch = NULL;
for(j=1;j<=n;j++)
code[i].bits[j] = NULL;
}
printf("Please input %d char: \n",n);
getchar();
scanf("%c %c %c %c %c %c %c %c",&temp[1],&temp[2],&temp[3],&temp[4],&temp[5],&temp[6],&temp[7],&temp[8]);
for(i=1;i<=n;i++)
{
// scanf("%c",&w);
code[i].ch =temp[i];
HT[i].data =temp[i];
}
printf("Please input %d rate: \n",n);
getchar();
scanf("%d %d %d %d %d %d %d %d",&temp2[1],&temp2[2],&temp2[3],&temp2[4],&temp2[5],&temp2[6],&temp2[7],&temp2[8]);
for(i=1;i<=n;i++)
{
//scanf("%d",&w);
w= temp2[i];
HT[i].wi = w;
}
HuffmTree(HT);
Huffmcode(code);
Output(code);
printf("\nContinue?1-Contine,0-Exit\n");
scanf("%d",&choice);
if(choice!=1)
break;
}
getchar();
return;
}
运行过，正确的
B. 急！！高分求关于 哈夫曼编码 课程设计程序
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}
C. 求个哈夫曼编码的设计与实现（数据结构课程设计）拜托各位了 3Q
#include<string.h> #include<stdlib.h> #include<stdio.h> int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char *HuffmanCode; void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i <= n;i++) if(![i].parent){s1 = i;break;} for(j = i+1;j <= n;j++) if(!HT[j].parent){s2 = j;break;} for(i = 1;i <= n;i++) if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j <= n;j++) if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) { int i, j; char *cd; int p; int cdlen; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); for (i=1; i<=n; i++) { HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i<=m; i++) { HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } puts("\n哈夫曼树的构造过程如下所示："); printf("HT初态:\n 结点 weight parent lchild rchild"); for (i=1; i<=m; i++) printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild); printf(" 按任意键，继续 ..."); getchar(); for (i=n+1; i<=m; i++) { Select(HT, i-1); 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; printf("\nselect: s1=%d s2=%d\n", s1, s2); printf(" 结点 weight parent lchild rchild"); for (j=1; j<=i; j++) printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, HT[j].parent,HT[j].lchild, HT[j].rchild); printf(" 按任意键，继续 ..."); getchar(); } cd = (char *)malloc(n*sizeof(char)); p = m; cdlen = 0; for (i=1; i<=m; ++i) HT[i].weight = 0; while (p) { if (HT[p].weight==0) { HT[p].weight = 1; if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } else if (HT[p].rchild == 0) { HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); cd[cdlen] ='\0'; strcpy(HC[p], cd); } } else if (HT[p].weight==1) { HT[p].weight = 2; if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } } else { HT[p].weight = 0; p = HT[p].parent; --cdlen; } } } void main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts("输入结点数:"); scanf("%d",&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf("输入%d个结点的权值\n",n); for(i = 0;i < n;i++) scanf("%d",&w[i]); HuffmanCoding(HT,HC,w,n); puts("\n各结点的哈夫曼编码:"); for(i = 1;i <= n;i++) printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); getchar(); }
D. 课设题目：哈夫曼编码与译码的实现
妄末卉丫丫,yffrskngiw7112244622,辖回答.
E. C++课程设计“基于哈夫曼编码的数据压缩/解压程序”
This may be help:
http://www.diybl.com/course/3_program/c++/cppjs/20071024/79743.html
F. 哈弗曼树课程设计
大一时的课程设计，现在看看实在是简单的要死。
如果你要做输入字符串然后自动判断概率的话就自己做，同样用vector。
如果你用.Net做的话就更简单了。
一、设计目的：
1、 掌握HUFFMAN编码的原理及步骤；
2、 熟悉用C++语言进行编码程序设计，并检验程序的正确性。
二、设计所需的软硬件：
PC机一台、DEV C++软件开发平台
三、设计原理与内容：
基本原理：
首先将q个信源符号按概率分布P(si)的大小，以降序排列。其次选出两个概率最小的信源符号合并成一个符号，变成q-1个符号。循环这个步骤直到得到最后一个符号为止。从根部分配0和1到两臂，依次进行分配即可。
设计内容：
对n（n<50）个字符进行Huffman编码,用户输入每个字符的概率，程序输出每个字符及其码字。
程序设计的思路：
（1） 定义霍夫曼树的结点结构huffnode.
（2）定义霍夫曼编码的结构huffcode.
（3）数组初始化
（4）构造霍夫曼树
(4.1) 构造n棵只有一个叶结点的二叉树，并找出根结点权值最小的两棵树
(4.2) 将找出的两棵树合并为一棵子树
（5）求各字符的霍夫曼编码
（6）输出字符的霍夫曼编码
四、设计步骤：
1、 写出HUFFMAN编码源程序，编译通过；
2、 运行程序，输入验证码，根据输出结果进行分析、调试。
附：源程序代码
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class node{
public:
char data;
float weight;
};
class huffnode :public node
{
public:
string code;
int lchild,rchild,parent;
int flag;
};
void select(vector<huffnode> s,int &s1,int &s2){
s[0].weight = 1;
s1 = s2 = 0;
for(int i = 0; i < s.size(); i++)
if (s[i].parent == -1)
{
if (s[i].weight < s[s1].weight)
{ s2 = s1; s1 = i;}
else if (s[i].weight < s[s2].weight)
{ s2 = i; }
}
}
void code(vector<node> weights)
{
vector<huffnode> h;
vector<node>::iterator pit_i = weights.begin();
int nozero_num = 0;
huffnode m;
m.weight = 1;
h.push_back(m);
while(pit_i != weights.end()){
if((*pit_i).weight != 0){
huffnode n;
n.data = (*pit_i).data;
n.weight = (*pit_i).weight;
n.lchild = n.rchild = n.parent = -1;
h.push_back(n);
nozero_num++;
}
pit_i++;
}
int s1,s2;
int j = nozero_num;
cout<<j<<endl;
do
{
select(h,s1, s2);
huffnode hn;
hn.weight = h[s1].weight + h[s2].weight;
hn.lchild = s1;
hn.rchild = s2;
h.push_back(hn);
h[s1].parent = h[s2].parent = 1;
j--;
}while(j != 1);
int p = h.size()-1;
while(p != 0)
{
if(h[p].lchild != -1){
h[h[p].lchild].code = h[p].code + '0';
h[h[p].rchild].code = h[p].code + '1';}
p--;
}
for (int temp = 1;temp<=nozero_num;temp++) cout<<h[temp].data<<" "<<h[temp].code<<endl;
}
int main(int argc, char *argv[])
{
vector<node> weights;
int N;
cout<<"请输入要编码的字符个数："<<endl;
cin>>N;
cout<<"请输入相应的字符以及其概率:"<<endl;
while(N>0)
{
node n;
cout<<"字符："; cin>>n.data;
cout<<"概率："; cin>>n.weight;
weights.push_back(n);
N--;
}
cout<<"所得编码为："<<endl;
code(weights);
system("PAUSE");
return EXIT_SUCCESS;
}
G. 求一个<哈夫曼编码>数据结构课程设计（C语言版）
我帮你测试了，这个可以满足你的要求！#include<stdio.h>
#include<stdlib.h>
#define max 50
struct a
{
int weight;
int parent,lchild,rchild;
};
struct b
{
char cd[max];
int start;
};
void main()
{
struct a ht[2*max];
struct b hcd[max],d;
int i,k,n,c,s1,s2,m1,m2,f;
printf("输入n:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("输入权值:");
scanf("%d",&ht[i].weight);
ht[i].parent=0;
}
for(;i<=2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=30000;
s1=s2=0;
for(k=1;k<=i-1;k++)
{
if(ht[k].parent==0 && ht[k].weight<m1)
{
m2=m1;
s2=s1;
m1=ht[k].weight;
s1=k;
}
else if(ht[k].parent==0 && ht[k].weight<m2)
{
m2=ht[k].weight;
s2=k;
}
}
ht[s1].parent=ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=1;i<=n;i++)
{
d.start=n-1;
c=i;
f=ht[i].parent;
while(f)
{
if(ht[f].lchild==c)d.cd[--d.start]='0';
else d.cd[--d.start]='1';
c=f;
f=ht[f].parent;
}
hcd[i]=d;
}
printf("输出哈夫编码:");
for(i=1;i<=n;i++)
{
printf("%d ",ht[i].weight);
for(k=hcd[i].start;k<n-1;k++)
printf("%c",hcd[i].cd[k]);
printf(" ");
}
printf("\n");
}