曼码编程思路
A. 用哈夫曼编码 编程
手打的,你最好编译一下以免我哪里敲错了
(网络不能显示行首空格真是不爽)
//哈夫曼树和~编码的存储表示
typedef struct{
unsigned int weight;//权值
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树
typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表
void HoffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
if (n<=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0号单元未采用
for (p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
for (;i<=m;++i;++p) *p={0,0,0,0}
for (i=n+1;i<=m;++i){//建哈夫曼树
//在HT[1..i-1]选择parent为0且weight最小的两个结点编号分别为s1,s2
Select(HT,i-1,s1,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=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));//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC
}
free(cd);//释放工作空间
}//HuffmanCoding
B. 哈夫曼编码码长怎么算
设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。
霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。
实际应用中
除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。
按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。
C. 编程实现赫夫曼编码：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef char** HaffmanCode;
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
void Select(HuffmanTree &HT,int i,int &s1,int &s2)
{
int n,m=0;
for(n=1,m=0;n<=i&&m!=2;n++)
{
if(HT[n].parent==0)
{
if(m==0)
{
s1=n;
m=1;
continue;
}
if(m==1)
{
s2=n;
m=2;
break;
}
}
}
n++;
for(;n<=i;n++)
{
if(HT[n].parent==0)
{
if(HT[n].weight<HT[s1].weight)
{
if(HT[s1].weight<HT[s2].weight)
s2=s1;
s1=n;
continue;
}
if(HT[n].weight<HT[s2].weight)
{
if(HT[s2].weight<HT[s1].weight)
s1=s2;
s2=n;
}
}
}
printf("%d %d\n",s1,s2);
}
void HuffmanCoding(HuffmanTree &HT,HaffmanCode &HC,int *w,int n)
{
int m,i,s1,s2,start,c,f;
char *cd;
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<=m;++i)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n;i<m;i++)
{
Select(HT,i,s1,s2);
HT[s1].parent=i+1;
HT[s2].parent=i+1;
HT[i+1].lchild=s1;
HT[i+1].rchild=s2;
HT[i+1].weight=HT[s1].weight+HT[s2].weight;
}
/*********************************************/
HC = (HaffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc(n*sizeof(char));
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]);
//printf("%s\n",HC[i]);
}
free(cd);
}
int main()
{
HuffmanTree HT;
HaffmanCode HC;
int n,i,j;
int *w;
printf("请输入赫夫曼数的个数：\n");
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
printf("请输入第%d个数：",i+1);
scanf("%d",&w[i]);
}
HuffmanCoding(HT,HC,w,n);
printf("赫夫曼编码为：\n");
for(i=1;i<=n;i++)
{
printf("%s\n",HC[i]);
}
system("pause");
return 0;
}
希望对你能有所帮助。
D. 什么是曼码
曼彻斯特（
Manchester
）码是一种双相码。用高电平到低电平的转换边表示
0
，而用低电平到高高电平的转换边表示
1
在监控中用得比较多，原因之一是像AD、AB等矩阵与解码器都用的的曼码。它的工作在31K左右。
E. 霍夫曼编码的编码效率怎么求
求效率首先要求得信号的熵，也就是最小的编码长度，比如是2.3，然后再求霍夫曼码的平均编码长度（各个概率和码位相乘再求和）比如是2.7，那么效率就是0.85。
霍夫曼编码的编码效率，我想可以用压缩率来表示吧。随机选取一段字符，计算其编码长度为 n。再对其用霍夫曼编码，得到长度为 m。于是 m/n 就是压缩率。
霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。
(5)曼码编程思路扩展阅读：
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
F. 89c52单片机用曼码读/写T5557卡的C语言程序
//---------------------------------------------------------------------------- |
// 标题： 曼彻斯特和差分曼彻斯特编码的实现 |
// 分析：曼彻斯特编码是将每个码元的中央实现跳变，具体的码字表示为： |
// 1->10,0->01. |
// 差分曼彻斯特编码每个码元依前一码元而定，遇1跳变，遇0保持 |
// 若前为：01，则1->10 0->01 |
// 若前为：10，则1->01 0->10 |
// 实现：定义两个数组，一个用来放置输入要编码的序列，另一个用来放编码后的序列 |
// |
// |
//----------------------------------------------------------------------------
/**/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 头文件
#include <stdio.h>
#include <assert.h>
#include<string.h>
/**/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 全局变量
#define M 10
int j; //指向编码后序列的数组下标
int i; //输入码字的数组下标
int length; //求值输入数组的长度
/**/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 参数表
int Direct_code(char str0[]) //直接编码
...{
char dirct_code[2*M];
memset(dirct_code,0,2*M);
dirct_code[0]='0';
dirct_code[1]='1';
j=2;
extern length;
for(i=0;i<length;i++)
...{
// 循环入口数据
printf("current character is: %c ",str0[i]);
// 循环处理，0 ->01 1 ->10
if(str0[i]=='0') ...{dirct_code[j++]='0';dirct_code[j++]='0';}
else if(str0[i]=='1') ...{dirct_code[j++]='1';dirct_code[j++]='1';}
else ...{printf("input error,exit........ "); return 1;} // 输入出错
// 循环处理后数据
printf("-----");
printf("after process: %c%c ",dirct_code[j-2],dirct_code[j-1]);
}
// 结果字符串加上终结符
dirct_code[j]=0;
// 输出结果
printf("------------------------------------------- ");
printf("Direct_code coding is:%s ",dirct_code);
return 0;
}
int Manchester(char str0[]) //曼彻斯特编码
...{
char Manchester[2*M];
memset(Manchester,0,2*M);
Manchester[0]='0';
Manchester[1]='1';
j=2;
extern length;
for(i=0;i<length;i++)
...{
// 循环入口数据
printf("current character is: %c ",str0[i]);
// 循环处理，0 ->01 1 ->10
if(str0[i]=='0') ...{Manchester[j++]='0';Manchester[j++]='1';}
else if(str0[i]=='1') ...{Manchester[j++]='1';Manchester[j++]='0';}
else ...{printf("input error,exit........ "); return 1;} // 输入出错
// 循环处理后数据
printf("-----");
printf("after process: %c%c ",Manchester[j-2],Manchester[j-1]);
}
// 结果字符串加上终结符
Manchester[j]=0;
// 输出结果
printf("------------------------------------------- ");
printf("Manchester coding is :%s ",Manchester);
return 0;
}
int Dif_Manchester(char str0[]) //差分曼彻斯特编码
...{
char Dif_Manch[2*M];
memset(Dif_Manch,0,2*M); //初始化数组
Dif_Manch[0]='0';
Dif_Manch[1]='1';
j=2;
extern length;
for(i=0;i<length;i++)
...{
// 循环入口数据
printf("current character is: %c ",str0[i]);
// 循环处理，0 ->01 1 ->10
if(str0[i]=='0')
...{
Dif_Manch[j++]=Dif_Manch[j-3];
Dif_Manch[j++]=Dif_Manch[j-2];
}
else if(str0[i]=='1')
...{
Dif_Manch[j++]=Dif_Manch[j-2];
Dif_Manch[j++]=Dif_Manch[j-3];
}
else ...{printf("input error,exit........ "); return 1;} // 输入出错
// 循环处理后数据
printf("-----");
printf("after process: %c%c ",Dif_Manch[j-2],Dif_Manch[j-1]);
}
// 结果字符串加上终结符
Dif_Manch[j]=0;
// 输出结果
printf("------------------------------------------- ");
printf("Dif_Manchester coding is :%s ",Dif_Manch);
return 0;
}
/**/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// 入口点
int main(int argc, char* argv[])
...{
char str0[M];
// 获取输入数据
printf("please input the number string u want(it must less than 10): ");
scanf("%s",str0);
// 验证输入数据是否正确，可以用assert之类
printf("what u input is------:: %s ",str0);
length=strlen(str0);
assert(length <M ); //设置断言，数组越界检查
// 输出数据区置0
//memset(str1,0,2*M);
Direct_code(str0);
Manchester(str0);
Dif_Manchester(str0);
return 0;
}
/**///////////////////////////////////////////////////////////////////////////////
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
/**/////////////////////////////////////////这是刚刚开始自己写的程序////////////////////////////////////////////////////////////////////////
#define M 10
#include<stdio.h>
void main()
...{
int i=0;
int str0[M];
int str1[2*M];
printf("please input the number string u want: ");
scanf("%s",str0);
do
...{
if(str0[i]==0) ...{str1[i]=0;str1[i+1]=1;}
else if(str0[i]==1) ...{str1[i]=1;str1[i+1]=0;}
i++;
}while(str0[i]!='
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
总结几点：
A：字符串和数字是不同的，例如‘1’，‘0’表示的是字符，而1，0表示的数字(但是有个问题还是不太明白，数 组中存放数字有什么错误吗？为何要用字符呢？哈哈，别骂我....)。一个字符用‘’表示时，它传递给计算机的是它的ASCII码值
B：编写程序时候每一段代码做了什么都应该清晰明了，设定一定的提示输出，显示程序所做的事情，结构要清晰，每一次数据处理得到了什么结果 每一步数据处理我都清楚的想知道他做了什么
C:重要的一点是写程序前，自己脑子里面应该有个很清晰的思路，画流程图是重点，我常常在还没有想好是怎么回事的情况下就匆忙动笔了，结果进展反而非常之慢 “问题是你没有 把问题先搞清楚，没有把输入，处理输入，输出这些过程在脑袋里搞清楚”
D：个人问题：付出时间的同时不能付出同等的精力，并不是不想，虽然已经很专注了，但是我知道自己脑袋里面还在想其他的事情，没有事先把头脑清空了，再来写程序。
另外自己做事情不够专心，三心二意：写程序的时候可能同时在看网页，或者是其他的，遇到一个问题不懂，去网上查很久，走很大一个弯路回来，虽然懂了不明白的那一点，但是目前进行的却被打断了。
E：目前为止比较完整的程序写了三个了，每个都不容易，不是程序难，是我写的不容易> 大家认为我可能不是编程的料
F:突然想起ziji 一个致命的缺点： 拖拉。
G：补充：这个只是模拟，其实曼彻斯特编码应该是对应与位的运算
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
新知识点一：ASSERT()
ASSERT()是一个调试程序时经常使用的宏。
assert是验证assert后面的括号里的表达式是否为真的函数，若为假，程序运行的时候就会报错.
当构造一个应用程序的时候，应该始终记住：应该让程序在出现bug或非预期的错误的时候，应该让程序尽可能早地突然死亡。这样做可以帮助你在开发 ——测试循环中尽早地发现错误。不导致突然死亡的错误将很难被发现；它们通常会被忽略，直到程序在客户系统中运行以后才被注意到。
检查非预期状态的最简单的方式是通过标准C库的assert宏。这个宏的参数是一个布尔表达式（Boolean expression）。当表达式的值为假的时候，assert会输出源文件名、出错行数和表达式的字面内容，然后导致程序退出。Assert宏可用于大量程序内部需要一致性检查的场合。例如，可以用assert检查程序参数的合法性、检查函数（或C++中的类方法）的前提条件和最终状态（postcondition）、检查非预期的函数返回值，等等。
每次使用assert宏，不仅可以作为一项运行期的检查，还可以被当作是嵌入代码中的文档，用于指明程序的行为。如果你的程序中包含了assert( condition )，它就是在告诉阅读代码的人：condition在这里应该始终成立；否则很可能是程序中的bug。
对于效率至上的代码，assert这样的运行时检查可能引入严重的效率损失。在这种情况下，你可以定义NDEBUG宏并重新编译源码（可以通过在编译器参数中添加 –DNDEBUG参数做到）。在这种情况下，assert宏的内容将被预处理器清除掉。应该只在当效率必须优先考虑的情况下，对包含效率至上的代码的文件设置NDEBUG宏进行编译。
因为assert可能被预处理过程清除，当使用这个宏的时候必须确信条件表达式不存在副作用。特别的，不应该在assert的条件表达式中使用这些语句：函数调用、对变量赋值、使用修改变量的操作符（如 ++ 等）。
例如，假设你在一个循环中重复调用函数do_something。这个函数在成功的情况下返回0，失败则返回非0值。但是你完全不期望它在程序中出现失败的情况。你可能会想这样写：
for (i = 0; i < 100; ++i)
assert (do_something () == 0);
不过，你可能发现这个运行时检查引入了不可承受的性能损失，并因此决定稍候指定NDEBUG以禁用运行时检测。这样做的结果是整个对assert的调用会被完全删除，也就是说，assert宏的条件表达式将永远不会被执行，do_something一次也不会被调用。因此，这样写才是正确的：
for (i = 0; i < 100; ++i) {
int status = do_something ();
assert (status == 0);
}
另外一个需要记住的是，不应该使用assert去检测不合法的用户输入。用户即使在输入不合适的信息后也不希望看到程序仅在输出一些含义模糊的错误信息后崩溃。你应该检查用户的非法输入并向用户返回可以理解的错误信息。只当进行程序内部的运行时检查时才应使用assert宏。
一些建议使用assert宏的地方：
• 检查函数参数的合法性，例如判断是否为NULL指针。由 { assert (pointer != NULL)} 得到的错误输出
Assertion ‘pointer != ((void *)0)’ failed.
与当程序因对NULL指针解引用得到的错误信息
Segmentation fault (core mped)
相比而言要清晰得多。
• 检查函数参数的值。例如，当一个函数的foo参数必须为正数的时候我们可以在函数开始处进行这样的检查：
assert (foo > 0);
这会帮助你发现错误的调用；同时它很清楚地告诉了读代码的人：这个函数对参数的值有特殊的要求。
不要就此退缩；在你的程序中适当地时候使用assert宏吧。
使用Assertion来提高你代码的可靠性
以下是一些使用assertion的四种情况及其对应的例子，这些方式可以让java程序的可靠性更高。
一、检查控制流； 在if-then-else和swith-case语句中，我们可以在不应该发生的控制支流上加上assert false语句。如果这种情况发生了，assert能够检查出来。
例如：x取值只能使1,2,3，我们的程序可以如下表示
switch (x)
{ case 1: …;
case 2: …;
case 3: …
default: assert false:"x value is invalid: "+x;
}
二、在私有函数计算前，检查输入参数是否有效；对于一私有些函数，要求输入满足一些特定的条件，那么我们可以在函数开始处使用assert进行参数检查。对于公共函数，我们通常不使用assertion检查，因为一般来说，公共函数必须对无效的参数进行检查和处理。而私有函数往往是直接使用的。
例如：某函数可能要求输入的参数必须不为null。那么我们可以在函数的一开始加上 assert parameter1!=null : "paramerter is null in test method";
三、在函数计算后，检查函数结果是否有效；对于一些计算函数，函数运行完成后，某些值需要保证一定的性质，因此我们可以通过assert检查该值。
例如，我们有一个计算绝对值的函数，那么我们就可以在函数的结果处，加上一个语句：
assert value>=0:"Value should be bigger than 0:"+value;
通过这种方式，我们可以对函数计算完的结果进行检查。
四、检查程序不变量；有些程序中，存在一些不变量，在程序的运行生命周期，这些不变量的值都是不变的。这些不变量可能是一个简单表达式，也可能是一个复杂的表达式。对于一些关键的不变量，我们可以通过assert进行检查。
例如，在一个财会系统中，公司的支出和收入必须保持一定的平衡关系，因此我们可以编写一个表达式检查这种平衡关系，如下表示。
private boolean isBalance() {
……
}
在这个系统中，在一些可能影响这种平衡关系的方法的前后，我们都可以加上assert验证：assert isBalance():"balance is destoried";
///////////////////////////////////////////////////////////////////////////////////////////////
新知识点（二）memset
。void *memset(void *s,int c,size_t n)
总的作用：将已开辟内存空间 s 的首 n 个字节的值设为值 c。
2。例子
＃i nclude
＃i nclude
main(){
char *s="Golden Global View";
clrscr();
memset(s,'G',6);
printf("%s",s);
getchar();
return 0;
}
3。memset() 函数常用于内存空间初始化。如：
char str[100];
memset(str,0,100);
4。memset()的深刻内涵：用来对一段内存空间全部设置为某个字符，一般用在对定义的字符串进行初始化为‘ ’或‘\0’；例:char a[100];memset(a, '\0', sizeof(a));
memcpy用来做内存拷贝，你可以拿它拷贝任何数据类型的对象，可以指定拷贝的数据长度；例：char a[100],b[50]; memcpy(b, a, sizeof(b));注意如用sizeof(a)，会造成b的内存地址溢出。
strcpy就只能拷贝字符串了，它遇到'\0'就结束拷贝；例：char a[100],b[50];strcpy(a,b);如用strcpy(b,a)，要注意a中的字符串长度（第一个‘\0’之前）是否超过50位，如超过，则会造成b的内存地址溢出。
5.补充：某人的一点心得
memset可以方便的清空一个结构类型的变量或数组。
如：
struct sample_struct
{
char csName[16];
int iSeq;
int iType;
};
对于变量
struct sample_strcut stTest;
一般情况下，清空stTest的方法：
stTest.csName[0]='\0';
stTest.iSeq=0;
stTest.iType=0;
用memset就非常方便：
memset(&stTest,0,sizeof(struct sample_struct));
如果是数组：
struct sample_struct TEST[10];
则
memset(TEST,0,sizeof(struct sample_struct)*10);
6。strcpy
原型：extern char *strcpy(char *dest,char *src);
用法：＃i nclude
功能：把src所指由NULL结束的字符串复制到dest所指的数组中。
说明：src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。
返回指向dest的指针。
memcpy
原型：extern void *memcpy(void *dest, void *src, unsigned int count);
用法：＃i nclude
功能：由src所指内存区域复制count个字节到dest所指内存区域。
说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针。
memset
原型：extern void *memset(void *buffer, int c, int count);
用法：＃i nclude
功能：把buffer所指内存区域的前count个字节设置成字符c。
说明：返回指向buffer的指针。
参考资料：开发者在线http://www.builder.com.cn/
G. 霍夫曼编码如何解码
只要给你码表就行了.
编码的结果就是使每一个字符的编码都与另一个字符编码的前一部分不同.不可能出现像a:00,b:001这种情况.这样就不会遇到莫棱两可的情况了.
这是由二叉树的特点决定的,编码是由从根结点到一个叶子的路径决定的.不同的叶子对应的这种路径不可能出现像a:00,b:001这种情况.你可以画画二叉树图,就懂了.
霍夫曼编码重要作用就是用最少的编码长度表示相同的内容,主要依据"频率大的编码短,频率小的编码长".
H. 哈夫曼编码/译码器编程
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000 //定义字符串最大长度
#define N 128 //定义叶子节点个数
typedef struct node //定义哈夫曼树节点结构体
{
int weight;
struct node *LChild,*RChild,*Parent; //分别指向该节点的左孩子，右孩子，和双亲节点
struct node *next; //指向建立的哈夫曼树的下一个节点
}HFMNode,*HFMTree;
typedef struct //定义哈夫曼编码的结构体
{
char ch; //存储对应的字符
char code[N+1]; //存储对应字符的编码
int start; //存储编码的起始位置
}CodeNode;int n; //存储真正叶子节点个数
void clearscreen()
{
system("cls");
}
void Open(char s[]) //打开存放字符或编码的文件，将其存入字符串数组中
{
char name[10];
FILE *fp;
int i=0;
printf("请输入要打开的文件名：");
gets(name); //要打开的文件名
if((fp=fopen(name,"rt"))==NULL)
{
printf("打开失败！\n"); //若打开失败，则直接退出
exit(1);
}
s[i++]=fgetc(fp);
while(s[i-1]!=EOF)
s[i++]=fgetc(fp);
s[i]='\0'; //存取字符串结束
fclose(fp);
}
void Save(char s[]) //保存字符或编码到文件中
{
char name[10];
FILE *fp;
printf("请输入要保存的文件名：");
gets(name);
if((fp=fopen(name,"wt"))==NULL)
{
printf("存储失败！");
exit(1);
}
fputs(s,fp);
printf("\n保存成功，文件名为:%s。\n",name);
printf("\n按回车键继续...");
getchar();
fclose(fp);} void SearchStr(char s[],char str[],int count[])
{
//查找字符串中字符的个数和每个字符出现的次数
int i,j,k=0;
for(i=0;i<N;i++) //初始化每个字符出现的次数
count[i]=0;
for(i=0;s[i];i++)
{
for(j=0;j<k;j++) //在str[]中查找是否有该字符
if(str[j]==s[i])
{
count[j]++;
break;
}
if(j==k) //在str[]中无该字符，将其存入最后一个单元
{
str[k]=s[i];
count[k++]++;
}
}
str[k]='\0'; //将字符串结尾置\0
n=k; //将实际的字符个数作为叶子节点个数存入n
}void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)
{
//查找哈夫曼链表中两个权值最小的节点
int i,min;
HFMTree p;
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0)
{
min=p->weight;
*HT1=p;
}
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0&&p!=*HT1) //令第二个最小的节点不等于第一个节点
{
min=p->weight;
*HT2=p;
}}
void CreatHFMTree(HFMTree *HT,int count[])
{
//创建哈夫曼树
int i;
HFMTree p,HT1,HT2; //HT1，HT2分别存放权值最小和次小的节点的位置
p=*HT=(HFMTree)malloc(sizeof(HFMNode));
p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化哈夫曼链表且有2n-1个节点
for(i=1;i<2*n-1;i++)
{
p->next=(HFMTree)malloc(sizeof(HFMNode));
p=p->next;
p->next=p->LChild=p->RChild=p->Parent=NULL;
}for(i=0,p=*HT;i<n;i++) //将各个字符出现的次数作为权值
{ //存入哈夫曼链表的前n个单元中
p->weight=count[i];
p=p->next;
}for(i=n;i<2*n-1;i++) //将后n-1个节点赋权值，建树
{
SelectMin(*HT,i,&HT1,&HT2); //每次从前i个节点中选取权值最小的两个节点
HT1->Parent=HT2->Parent=p;
p->LChild=HT1;
p->RChild=HT2;
p->weight=HT1->weight+HT2->weight; //将两个节点的权值相加存入最后一个节点中
p=p->next; //p指向下一个没有存储权值的节点
}}
void HFMCode(HFMTree HT,CodeNode HC[],char str[])
{
//从每个叶子节点开始，利用哈夫曼树对每个字符进行编码，最终建立一个哈夫曼表
int i;
HFMTree q,p=HT;
for(i=0;i<n;i++) //将字符存入哈夫曼编码结构体数组的字符单元中
{
HC[i].ch=str[i];
HC[i].code[n-1]='\0'; //初始化编码的最后一位
}
for(i=0;i<n;i++)
{
HC[i].start=n-1;
for(q=p;q->Parent;q=q->Parent) //判断q所指向的节点，左孩子置0，右孩子置1
if(q==q->Parent->LChild)
HC[i].code[--HC[i].start]='0';
else HC[i].code[--HC[i].start]='1';
p=p->next; //判断下一个叶子节点
}
}
void TotalCoding(char s[],CodeNode HC[],char code[])
{
//利用哈夫曼编码表对整个字符串进行编码
int i,j;
code[0]='\0'; //编码数组初始化
for(i=0;s[i];i++) //将每个字符在哈夫曼编码表中对应的编码存入存放总编码的数组中
for(j=0;j<n;j++)
if(s[i]==HC[j].ch)
strcpy(code+strlen(code),HC[j].code+HC[j].start);
}void DeCoding(char code[],HFMTree HT,char str[],char s[])
{
//对哈夫曼编码进行解码，放入字符串s中
int i,j,k=0;
HFMTree root,p,q;
for(root=HT;root->Parent;root=root->Parent); //用root指向哈夫曼树的根结点
for(i=0,p=root;code[i];i++) //从根结点开始按编码顺序访问树
{
if(code[i]=='0')
p=p->LChild;
else p=p->RChild;
if(p->LChild==NULL&&p->RChild==NULL) //到根节点时将该节点对应的字符输出
{
for(j=0,q=HT;q!=p;q=q->next,j++);
s[k++]=str[j];
p=root; //回溯到根结点
}
}
s[k]='\0'; //解码完毕，在字符串最后一个单元存入'\0'
}
void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打开存放字符串的文件...\n\n");
Open(s); //打开源码文件
SearchStr(s,str,count); //查找字符串中不同的字符及其出现的次数
CreatHFMTree(HT,count); //用每个字符出现的次数作为叶子节点的权值建立哈夫曼树
HFMCode(*HT,HC,str); //利用哈夫曼树对每个叶子节点进行编码，存入编码表中
TotalCoding(s,HC,code); //利用编码表对字符串进行最终编码
printf("\n读入的字符串为:\n");
puts(s);
printf("\n最终的哈夫曼编码是:\n");
puts(code);
printf("\n保存编码,");
Save(code); //保存最终的哈夫曼编码
}
void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打开编码的文件...\n\n");
Open(code); //打开编码文件
DeCoding(code,*HT,str,ss); //将编码进行解码存入字符串数组ss[]中
printf("\n得到的最终字符串为:\n");
puts(ss);
printf("\n保存译码，");
Save(ss); //保存译码后的字符串
}void main()
{
//主函数
char s[M],ss[M]; //定义字符串数组，s[]存放将要编码的字符串，ss[]存解码后的字符串
char str[N]; //存放输入的字符串中n个不同的字符
int count[N]; //存放n个不同字符对应的在原字符串中出现的次数
char code[M]; //存放最终编码完成后的编码
char choice;
HFMTree HT; //定义一个哈夫曼树的链表
CodeNode HC[N]; //定义一个哈夫曼编码表的数组，存放每个字符对应的哈夫曼编码
do
{
clearscreen();
printf("\n\n");
printf(" ************哈夫曼树************\n");
printf(" ** **\n");
printf(" ** 1.编码。 **\n");
printf(" ** 2.译码。 **\n");
printf(" ** 0.退出。 **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** 请输入相应操作的序号(0-2) **\n");
printf(" ********************************\n");
scanf("%c",&choice);
getchar();
switch(choice)
{
case '1': Coding(s,str,code,count,&HT,HC);break; //对字符串进行编码
case '2': TransCode(code,str,ss,&HT,HC);break; //对编码进行解码
case '0': break;
default : printf(" 输入错误！请重新输入！\n");
}
}while(choice!='0');
}
I. 曼码编解码是怎么样一种编解码方式
曼彻斯特编码（Manchester Encoding），也叫做相位编码(PE)，是一个同步时钟编码技术，被物理层使用来编码一个同步位流的时钟和数据。曼彻斯特编码被用在以太网媒介系统中。曼彻斯特编码提供一个简单的方式给编码简单的二进制序列而没有长的周期没有转换级别，因而防止时钟同步的丢失，或来自低频率位移在贫乏补偿的模拟链接位错误。在这个技术下，实际上的二进制数据被传输通过这个电缆，不是作为一个序列的逻辑1或0来发送的（技术上叫做反向不归零制(NRZ)）。相反地，这些位被转换为一个稍微不同的格式，它通过使用直接的二进制编码有很多的优点。
曼彻斯特编码，常用于局域网传输。在曼彻斯特编码中，每一位的中间有一跳变，位中间的跳变既作时钟信号，又作数据信号；从高到低跳变表示"1"，从低到高跳变表示"0"。还有一种是差分曼彻斯特编码，每位中间的跳变仅提供时钟定时，而用每位开始时有无跳变表示"0"或"1"，有跳变为"0"，无跳变为"1"。
对于以上电平跳变观点有歧义：关于曼彻斯特编码电平跳变，在雷振甲编写的＜＜网络工程师教程＞＞中对曼彻斯特编码的解释为：从低电平到高电平的转换表示1，从高电平到低电平的转换表示0，模拟卷中的答案也是如此，张友生写的考点分析中也是这样讲的，而《计算机网络（第4版）》中（P232页）则解释为高电平到低电平的转换为1，低电平到高电平的转换为0。清华大学的《计算机通信与网络教程》《计算机网络（第4版）》采用如下方式：曼彻斯特编码从高到低的跳变是 0 从低到高的跳变是 1 。
两种曼彻斯特编码是将时钟和数据包含在数据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，每位编码中有一跳变，不存在直流分量，因此具有自同步能力和良好的抗干扰性能。但每一个码元都被调成两个电平，所以数据传输速率只有调制速率的1/2。
就是说主要用在数据同步传输的一种编码方式。
【在曼彻斯特编码中，用电压跳变的相位不同来区分1和0，即用正的电压跳变表示0，用负的电压跳变表示1。因此，这种编码也称为相应编码。由于跳变都发生在每一个码元的中间，接收端可以方便地利用它作为位同步时钟，因此，这种编码也称为自同步编码。】
Manchester encoding uses the transition in the middle of the timing window to determine the binary value for that bit period. In Figure , the top waveform moves to a lower position so it is interpreted as a binary zero. The second waveform moves to a higher position and is interpreted as a binary one .
【关于数据表示的约定】
事实上存在两种相反的数据表示约定。
第一种是由G. E. Thomas, Andrew S. Tanenbaum等人在1949年提出的，它规定0是由低-高的电平跳变表示，1是高-低的电平跳变。
第二种约定则是在IEEE 802.4(令牌总线)和低速版的IEEE 802.3 (以太网)中规定, 按照这样的说法, 低-高电平跳变表示1, 高-低的电平跳变表示0。
由于有以上两种不同的表示方法,所以有些地方会出现歧异。当然,这可以在差分曼彻斯特编码(Differential Manchester encoding)方式中克服.
J. 哈夫曼编码算法的实现
在网上看到一个，刚好用到，我试过的，正确
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,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 *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}