曼碼編程思路
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);
}
}