哈弗曼編碼課程設計
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");
}