数据结构 基于哈夫曼编码的通信系统的设计与实现

Question

实验题。最好别复制
因为实验要求可能不一样。看清楚再答。
3、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统
4、基本要求
一个完整的系统应具有以下功能：
1）初始化处理：建立通信系统
（1）建立有100句中文的信息集合，每个句子称为一条信息。
（2）输入编码参数：
① 从终端输入编码字符集大小n，字符编码长度m（设n为4，m为8）；
② 从终端输入编码字符（设为A，B，C，D）；
（3）生成每条信息的字符编码，构造字符编码集合；
（4）计算每个字符在字符编码集合中出现的概率；
（5）根据字符概率构造哈夫曼树，求出每个字符的二进制编码。
2）发送端信息编码
（1）用户从信息集合中选择一条信息，找到该信息对应的字符编码；
（2）根据该信息的字符编码，哈夫曼树求出的每个字符的二进制编码，构造出该信息的二进制编码，记录该二进制编码。（由于是软件模拟，没有发送设备，发送端的编码工作完成）。
3）接受端信息译码
（1）根据得到的信息的二进制编码，利用哈夫曼树求出的每个字符的二进制编码，还原出信息的字符编码；
（2）根据信息的字符编码，找到对应的信息。
5、实现提示
（1）本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。
（2）根据参数生成的通信系统的所有信息的有效存储问题。
（3）信息字符编码可参考随机数的方式生成，且要求保持唯一性。
今天晚上交，我在这方面很水啊，那岂不是让老师把整个学期的课程再讲一遍。各位帮忙了，大不了答完再多加些分。

Answer 1

一样的实验题
呵呵。
自己写的，能够运行（在vs2005下通过)
你看看吧

文件Main.cpp

#include "main.h"

//在HT[1...i-1]选择parent为且weigth最小的两个节点，其序号分别为s1和s2。
void SelectNode(HuffmanTree &HT,int max,int &s1,int &s2)
{
unsigned int maxWeight=0;
for(int i=0;i<max;i++)
maxWeight+=HT[i].weight;
unsigned int minWeight=maxWeight;
s1=-1;
for(int i=0;i<max;i++)
{
if( minWeight>=HT[i].weight && HT[i].parent==0 )
{
s1=i;
minWeight=HT[i].weight;
}
}

minWeight=maxWeight;
s2=-1;
for(int i=0;i<max;i++)
{
if( minWeight>=HT[i].weight && HT[i].parent==0 && s1!=i)
{
s2=i;
minWeight=HT[i].weight;
}
}
if(s1>s2){int tmp=s1;s1=s2;s2=tmp;}
return;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
// w存放n个字符的权值（均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
if(n<=1)return ;
int m=2*n;

HT=(HuffmanTree)malloc(m*sizeof(HTNode));
for(int i=0;i<n;++i)
{
HT[i]=HTNode(w[i],0,-1,-1);
}
for(int i=n;i<m;++i)
{
HT[i]=HTNode(0,0,0,0);
}

//建立赫夫曼树
for(int i=n;i<m;++i)
{
//在HT[0...i]选择parent为且weigth最小的两个节点，其序号分别为s1和s2。
int s1,s2;
SelectNode(HT,i,s1,s2);
if(s1>=0 && s2>=0){
HT[s1].parent=i;HT[i].lchild=s1;
HT[i].weight+=HT[s1].weight;
HT[s2].parent=i;HT[i].rchild=s2;
HT[i].weight+=HT[s2].weight;
}
}

//---从叶子到根逆向求每个字符的赫夫曼编码---
HC=(HuffmanCode)malloc(n*sizeof(char *));
char *cd=(char *)malloc(n*sizeof(char)+1);
cd[n]=0;

int start,c,f;
for(int i=0;i<n;++i)
{
start=n;
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
{
if(HT[f].lchild == c && HT[f].lchild>=0 )
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
}
free(cd);
}

//对中文句子进行编码
//并构造编码集。

void StartEncoding(int M,int N,char *EWords[100],char *CCode)
{
printf("生成句子对应编码...");
for(int i=0;i<100;i++)
{
char *eword=(char *)malloc((M+1)*sizeof(char));
eword[M]='\0';

int k=0;
do
{
for(int j=0;j<M;j++)
eword[j]=CCode[rand()%N];
for(k=0;k<i;k++)
if(strcmp(EWords[k],eword)==0)
break;
}while(k<i);//随机生成的编码存在
EWords[i]=eword;
}
printf("ok\n");
}

char *Encoding(int N,char *pew,char *CCode,HuffmanTree &HT,HuffmanCode &HC)
{//根据所选择的句子编码
//1-分析句子中各字符编码的权值

//权值
int *ewg=(int *)malloc(N*sizeof(int));
memset(ewg,0,N*sizeof(int));

for(int i=0;i<strlen(pew);i++)
{
int k;

//B在{A.B.C.D}中的第几个？
for (k=0;k<N;k++)
if(pew[i]==CCode[k])
break;

if(k>=N)//出错了..查查吧
exit(0);
ewg[k]++;
}

printf("权值分析：字符总数%d\n",strlen(pew));
for(int i=0;i<N;i++)
printf("%c=%d\t",CCode[i],ewg[i]);

//2-构建赫夫曼树
printf("\n构造赫夫曼树....\n");
HuffmanCoding(HT,HC,ewg,N);

printf("获得的二进制编码为:\n");
for(int i=0;i<N;i++)
printf("%c=%s\t",CCode[i],HC[i]);

int BinSize=0;
for(int i=0;i<N;i++)
BinSize+=ewg[i]*strlen(HC[i]);

char *BinCode=(char *)malloc(BinSize+1);
BinCode[BinSize]=0;
int start=0;

for(int i=0;i<strlen(pew);i++)
{
int k;
for (k=0;k<N;k++)
if(pew[i]==CCode[k])
break;
strcpy((BinCode+start),HC[k]);
start+=strlen(HC[k]);
}
printf("\n编码后二进制编码为: %s\n",BinCode);

free(ewg);
return BinCode;
}

char *Decoding(int N,char *BinCode,char *CCode,HuffmanTree &HT,HuffmanCode &HC)
{
char *DeCode=(char *)malloc(strlen(BinCode));
memset(DeCode,0,strlen(BinCode));
int readp=0,writep=0;
while(readp<=strlen(BinCode))
{
int i=0;
for(i=0;i<N;i++)
{
int j=0;
for(j=0;j<strlen(HC[i]);j++)
if(BinCode[readp+j]!=HC[i][j])break;
if(j==strlen(HC[i]))
{
DeCode[writep++]=CCode[i];
readp+=strlen(HC[i]);
break;
}
}
if(i==N)readp++;
}

printf("二进制编码解码得: %s\n",DeCode);
return DeCode;
}

void main()
{
//从终端输入编码字符集大小n，字符编码长度m（设n为，m为）；
int N,M;

//从终端输入编码字符（设为A，B，C，D）；
char *CCode;

//编码集
char *EWords[100];
unsigned long maxEncode=0;

printf("请输入编码字符集大小N=");
scanf("%d",&N);
if(N<1)exit(0);

printf("请输入字符编码长度M=");
scanf("%d",&M);
if(M<1)exit(0);

//初始化编码字符集
CCode=(char*)malloc(N);

for(int i=0;i<N;i++)
{
char c[2];
do{
printf("\n请输入第%d个编码字符:",i+1);
scanf("%s",&c);
}while(c[0]<32);
CCode[i]=c[0];
}

//开始编码
StartEncoding(M,N,EWords,CCode);

int Choice=1;
do
{
system("cls");
printf("请输入句子编号(1~100):");
scanf("%d",&Choice);
}while(Choice<1 || Choice>100);
printf("------------------------------------------\n第%d句：\n%s\n",Choice,Words[Choice-1]);
printf("编码为：%s\n",EWords[Choice-1]);

HuffmanTree HT;
HuffmanCode HC;
char *BinCode=Encoding(N,EWords[Choice-1],CCode,HT,HC);

//编码部分完成，现在进入解码部分
printf("------------------------------------\n进入解码阶段:\n获得二进制编码:\n%s\n",BinCode);
char *DeCode=Decoding(N,BinCode,CCode,HT,HC);

for(int i=0;i<100;i++)
if(strcmp(EWords[i],DeCode)==0)
printf("对应第%d句: \n%s\n",i+1,Words[i]);

//释放资源
free(BinCode);
free(DeCode);

free(CCode);
for(int i=0;i<100;i++)
free(EWords[i]);
}

文件Main.h
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <malloc.h>
#include <math.h>
#include <string.h>

//words.h包含了句中文的定义
//char *Words[100];
#include "words.h"

//赫夫曼编
typedef struct HTNode{
unsigned int weight;
unsigned int parent,lchild,rchild;
HTNode(unsigned int w,unsigned int p,unsigned int l,unsigned int r)
{
weight=w;
parent=p;
lchild=l;
rchild=r;
}
}HTNode,*HuffmanTree;

typedef char** HuffmanCode;

void SelectNode(HuffmanTree &HT,int max,int &s1,int &s2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);

char *Encoding(int M,int N,char *EWords[100],char *CCode,HuffmanTree &HT,HuffmanCode &HC);

文件Words.h
char *Words[100]={
"从中国人的角度去看，西方对付中国，无非就两点：",
"第一就是用弹道导弹防御系统迟滞你手中的核武器，防止你跟他拼命；",
"第二就是金融工具，整个操控你。",
"当然，金融工具操控你的前提是你对他开放产业转移的通道。",
"当年我们没有1929年时苏联那样的机会，",
"借助西方大规模的经济危机，低价买那么多技术、设备，雇佣那么多西方工程技术人员。",
"我们要实现现代化，只好充当人家产业转移的基地，所谓“用市场换技术”。",
"但是，应该说我们在决定这样做时并没有精打细算，也不可能有设计精细的战略指向：",
"总有一天我要超过你的“大目标”。",
"1996年《中国可以说不》一书横空出世，冷静地梳理了中西方关系，在当时引发了世界范围内的讨论和争议。",
"从《中国可以说不》到《中国不高兴》走过了12年的历程，",
"中国也从“只想领导自己”将变成“有能力领导世界”的国家。",
"它是一本呼吁“正视内政愤懑”“呼唤高尚集团”“要做英雄国家”的“复兴宣言”。",
"从这个意义上说，《中国不高兴》的确称得上是《中国可以说不》的“升级版”。",
"昨日在网上看了此书，",
"着重看了第一，二部分（后面的章节不想看了，只大略翻了一下目录）和王小东等四位作者的主要言论访谈录，",
"本不想跟风瞎评，但还是忍不住夜撰此文，",
"因为国人的劣根性并不因为鲁迅和柏杨的口诛笔伐而正逐渐改观进步，反而愈演愈烈，",
"竟然上升到动辄以国家的名义来说事，狭隘的民族主义和盲目的爱国热情成就的此书，",
"我只想对它说——为赚钱而出书是可耻和可悲的。",
"“中国需要英雄，需要尚武精神，要在世界上管理，利用好更多的资源，负有除暴安良的任务。”",
"中国从来就不缺少英雄，欠缺的是团结，“窝里斗”才是国人的强项。",
"地球正在走向多元化和平共处的时代，王小东们的潜台词难道是要中国去侵略扩张吗？",
"中国男足何时能在世界足坛拥有一席之地，我认为比除暴安良更能抬高中国的地位。",
"“中国需要建立大目标，否则就没机会了。”",
"中国究竟需要什么样的大目标？",
"书曰：“领导和管理世界。”",
"这岂非霸权主义的思想，难道我们要一面反对美国的霸权主义，一面理直气壮的要当地球村的村长？",
"奥运也开了，神七也上天了，是不是一定要再造几艘航空母舰（书后面有提及），就是国富民强了？",
"中国还有3000万的贫困人口，还有不通公路的乡镇，还有不通水电的村落，",
"我们的目标是不是可以多贴近“地面”一些？",
"国人向有大国“情结”，大唐盛世虽已过去了一千多年，但总有人念念不忘，",
"最近祭这祭那的层出不穷，国学也是谁都可以乱品一把。",
"王小东们，那已经是历史了，我们需要着眼当代，开拓未来。",
"爱国不代表一定要喊出来，叫出来，",
"王小东们鼓吹的民族主义从某种意义上说就是夜郎自大，我想他们的眼里只有北京上海吧？",
"正如老外眼中的中国，一叶障目。",
"书中着重提到“持剑经商”，何谓持剑？何谓经商？",
"中国政治（尤其是体制和机制）对经济的制约和影响难道还不够深重吗？",
"政治需要清明而不是暴力，经济需要和平而不是控制，",
"违反市场经济规律，剑只会伤己。",
"“文艺腔不是我们现在该玩的。”",
"并把矛头对准已故的王小波，真真是“文人相轻”，",
"王小波的小说，几位真正读懂了吗？",
"亏了你们也是学理工科的，知道什么是逻辑思维吗？",
"又知道什么是文学吗？",
"中国自鲁迅之后，还有大师吗？",
"我同意王小东们指谪文化的凋零，恰因如此时代更加呼唤文艺的复兴，",
"软实力是以文字为载体的，我钦佩王小东们的务实精神，但我们亦更需要精神食粮。",
"“大时代应有大文化”，此观点我亦不能苟同，我们不需要凡事求大，",
"当今之中国人最缺的是平常心，当今之文化也应当向下看（当然绝对不是去看超女超男）。",
"我们不再需要《英雄儿女》，",
"我们需要《我的团长我的团》。",
"话说回来，既然不该耍文艺腔，那么几位又出书干吗？",
"“解放军要跟着中国核心利益走，中国的核心利益在什么地方，解放军就应该覆盖到什么地方。”",
"何谓中国的核心利益？",
"我认为是最广大的人民群众的利益。",
"民族主义是一面旗帜，民主主义是另一面旗帜。",
"尤其在目前并没有敌人侵略我国的情况下，这是避重就轻，甚至是向权力抛媚眼。",
"民族主义是一个族群的价值；",
"民主主义是普遍价值。",
"尤其在我们这样一个缺乏民主传统，监察机制软弱的国家，",
"目前知识分子和爱国志士的主要责任是推动中国的民主进程，而不是煽动狭隘民族主义情绪。",
"书中最主要的恐怕是要表明“对美国说不”，我不明白，美国如果是老黄瓜，那么中国是什么呢？",
"中国还没有完成工业化进程，还有那么多欠发达（说难听一点是贫困）地区，",
"是不是在修明内政的同时，着力民生，才是当前最主要的？",
"联想起去年的神七飞天，我真的并不以为然，",
"在“512”灾后重建百废待兴的局面下，我们究竟是在太空走两步重要还是受灾群众的安居乐业重要？",
"《霍元甲》中霍母的一句台词说的好：别人怕你和敬重你是两回事。",
"中国现在离别国怕我们还有距离，",
"“炸馆”和“南海坠机”事件已经说明问题；",
"离敬重我们就更远，无数移民的真实现状是那么的不堪是可以看见听见的。",
"我们还不清醒的认识到自身的不足，光顾扯着民族主义的大旗叫嚣唯我独尊的话，",
"那么中国永远只能在“第三世界”徘徊下去。",
"书名“中国不高兴”，“说不”这话粗粗一听，很长中国人的志气。",
"特别是去年“五月青年”们的言行再加上今年这本书的流行，",
"国人的民族主义空前高涨，韬光养晦可以不必再提了。",
"三十年前，邓小平为中国所制定的“韬光养晦、绝不当头”的国际战略，",
"是中国近二十年经济腾飞的基础，大部分中国人都从中获益。",
"这一战略的核心，就是在国际上采取低调、搭便车的方针，利用而非挑战现有的国际秩序。",
"中国加入WTO、大量引起外资、人民币长期与美元固定汇率、乃至最近中国企业的一系列海外收购，",
"都体现了中国利用现有国际秩序为自己服务的战略。",
"然而，正是由于这一战略使中国的国力逐渐大增，放弃韬光养晦的呼声渐起，",
"特别是在民间，要求中国要说“不”的呼声越来越大。",
"于是，王小东们的不高兴适时新鲜出炉了。",
"中国确实有很值得骄傲的几千年文明，",
"但这种文明，并没有创造一个国际秩序。",
"即使在东亚大陆，从唐安史之乱后汉人政权就丧失了对周边地区的政治秩序的主宰，更何况世界。",
"真正把世界打造成一体的，还是哥伦布以来的欧洲人。",
"从大英帝国到如今美国，从以WTO为代表的世界贸易体系、到联合国等国际政治体制，",
"都说明制造现在这个世界秩序的，主要是西方发达国家。",
"我并不是说这样的秩序就代表了正义，只想指出这套秩序是我们必须面临的现实。",
"目前还是我们要进入现有的国际秩序、而非要求人家进入我们的秩序的时代。",
"因为中国现在还不具备自己打造一个新的国际秩序的能力，",
"必须利用人家的资本、人家的市场、人家的技术、甚至人家的制度，",
"在现有的秩序中求得生存空间。",
"以中国为中心并没有错。",
"但这必须是以中国的利益为中心，而不是以某些中国人的心态为中心。",
"王小东们的言论如此煽情，未免有清谈误国之嫌。",
"最后，我想说的是，我们总自诩“大国”，别忘了我们首先是面积大，人口多。"
};

Answer 2

问你的老师

Answer 3

关于C++的 我也是没好好学啊,..