c語言實現哈夫曼編碼
㈠ 上海海事大學考研初試復試-計算機專業
上海海事大學考研初試復試計算機專業的情況如下：
初試： 考試科目：828，內容包括c語言、數據結構和操作系統。 題型分析： 判斷題：常規題型，難度不大。 填空題：以基礎題目為主，個別題目涉及圖論，有一定難度。 選擇題：初期涉及C語言，復習後難度降低。難點在於二重指針、數組與指針的轉換。 綜合題：涵蓋哈夫曼編碼、構造二叉樹、最小生成樹、散列表和排序演算法等。 編程題：包含C語言、鏈表題和樹的編程題。 備考建議：初試強調數學和英語的准備，學碩難度較大，需打下堅實基礎。
復試： 形式：網路遠程面試，包含雙機位。 流程：承諾書朗讀、身份證和准考證展示、抽題答題。專業課可能涉及408和資料庫。 綜合面試：佔220分，是復試的重要組成部分。 成績計算：復試成績直接加到初試總分上，具有逆襲和翻車的可能性。 注意事項：復試過程高效，國家線公布後，復試分數線、復試通知和資格審查等都會在較短時間內完成，考生需提前做好准備。
總結： 上海海事大學計算機專業考研初試注重基礎知識的考察，考生需加強C語言、數據結構、操作系統等方面的復習。 復試則更注重綜合素質的考察，包括專業課知識和綜合面試表現。考生需在初試中取得較好成績的同時，也要注重復試的准備。
㈡ 急求c語言或C++高手指點呀。。。需要構建一棵哈夫曼樹。請高手幫忙給出實際的編程代碼。。感激不盡呀！！！
void hfmtree ( huffnode ht[] ) 是用來建立一課哈夫曼樹的，其他函數，視需要可刪除
#include<stdio.h>
#include<string.h>
#define maxsize 10000 /*編碼函數中，被編譯的字元串的最大長度*/
#define max 10000 /*最大字元的個數*/
typedef struct /*定義一個huffnode結點 */
{
char data; /*數據域*/
int weight,parent,left,right;
}huffnode;
typedef struct /*定義一個huffnode結點*/
{
char cd[max]; /*數組cd存放哈夫曼編碼*/
int start;
}huffcode;
huffcode hcd[max];
huffnode ht[2*max];
huffnode a[2*max];
void hfmtree ( huffnode ht[] ) /*創建一棵哈夫曼樹*/
{
int i,k,x1,x2,n,m1,m2;
n = ht[0].weight;
for ( i=1; i<=2*n-1; i++ )
ht[i].parent = ht[i].left = ht[i].right = 0; /*初始化*/
for ( i=n+1; i<=2*n-1; i++ )
{
m1 = m2 = 200000000;
x1 = x2 = 0;
for ( k=1; k<=i-1; k++ ) /*k為可以進行比較的結點的下標*/
if ( ht[k].parent == 0 ) /*當前結點的父結點不存在時*/
if ( ht[k].weight < m1 ) /*當前結點的權值比最小權值還小時*/
{
m2 = m1;
x2 = x1;
m1 = ht[k].weight;
x1 = k;
}
else if ( ht[k].weight < m2 ) /*當前結點的權值比最小權值大但比第二最小權值小時*/
{
m2 = ht[k].weight;
x2 = k;
}
ht[x1].parent = ht[x2].parent = i;
ht[i].weight = ht[x1].weight + ht[x2].weight;
ht[i].left = x1;
ht[i].right = x2;
}
}
void output ( huffnode ht[] ) /*輸出哈夫曼編碼*/
{
huffcode d;
int i,n,c,f,k,x;
n = ht[0].weight;
for ( i=1; i<=n; i++ )
{
d.start = n+1;/*d.start為棧項*/
c = i; /*c存放當前結點*/
f = ht[i].parent;/*f存放當前結點的父結點*/
while ( f != 0 )
{
if ( ht[f].left == c ) /*若當前結點在其父結點的左邊時*/
d.cd[--d.start] = '0';
else
d.cd[--d.start] = '1'; /*當前結點在其父結點的右邊時*/
c = f; /*當前結點的父結點賦予c*/
f = ht[f].parent; /*c的父結點賦予f*/
}
hcd[i] = d; /*將當前結點的哈夫曼編碼賦予hcd[i]數組*/
}
printf ( "哈夫曼編碼: \n" );
for ( i=1; i<=n; i++ ) /*輸出各個結點的哈夫曼編碼*/
{
if ( ht[i].data == ' ' )
printf ( "' ' " );
else
printf ( "%c ",ht[i].data );
x = hcd[i].start;
for ( k=x; k<=n; k++ ) /*通過棧輸出哈夫曼編碼*/
printf ( "%c",hcd[i].cd[k] );
printf ( "\n" );
}
printf ( "* * * * * * * * * * * * * * * * * * * * \n\n" );
}
void coding ( huffcode hcd[],huffnode ht[] ) /*編碼函數，給定一個字元串，輸出其對應的哈夫曼編碼*/
{
int i,j,n,m,k,x;
char in[maxsize],out[2*maxsize];/*in存放需編譯的字元串，out存放編譯後的代碼*/
m = 0;
printf ( "請輸入一串字元串:" );
getchar();
gets(in);
n = strlen(in);
for ( i=0; i<n; i++ )
{
for ( j=1; j<=ht[0].weight; j++ ) /*ht[0].weight 存放的是帶權結點的個數*/
if ( in[i] == ht[j].data ) /*若輸入字元和一個帶權結點相同*/
{
x = hcd[j].start;
for ( k=x; k<=ht[0].weight; k++ )
out[m++] = hcd[j].cd[k];
}
}
printf ( "編碼結果是:\n" );
for ( i=0; i<m; i++ )
printf ( "%c",out[i] );
printf ( "\n" );
}
void decoding ( huffcode hcd[],huffnode ht[] )/*解碼函數，輸入一個代碼流，輸出其對應的字元*/
{
int i,j,n,k,x,m,w;
char in[maxsize*2],out[maxsize];/*in數組存放代碼流，out數組存放對應數組*/
printf ( "請輸入由0和1組成的字元串:\n" );
scanf ( "%s",in );
n = strlen(in);
i = m = 0; /*i為in數組的下標，m為out數組的下標*/
while ( i<n )
{
for ( j=1; j<=ht[0].weight; j++ )/*ht[0].weight為帶權結點的個數*/
{
x = hcd[j].start;
for ( k=x,w=i; k<=ht[0].weight; k++,w++) /*k為hcd[j].cd[]的下標*/
if ( in[w] != hcd[j].cd[k] )
break;
if ( k > ht[0].weight )
{
out[m++] = ht[j].data;
break;
}
}
i = w;
}
printf ( "解碼結果是:\n" );
for ( i=0; i<m; i++ ) /*輸出結果*/
printf ( "%c",out[i] );
printf ( "\n" );
}
int main()
{
int select,index,i,k,len;
char str[10000];
printf ( "請輸入一篇文章以便編碼:\n" );
gets (str);
for ( index=0; index<=200; index++ ){//初始化
a[index].data = '#';
a[index].weight = 0;
}
len = strlen(str);
k = 27;
for ( index=0; index<len; index++ ){//賦值
if ( str[index]>='A' && str[index]<='Z' ){
a[str[index]-'A'+1].data = str[index];
a[str[index]-'A'+1].weight++;
}
else{
a[k].data = str[index];
a[k].weight++;
k++;
}
}
k = 1;
for ( i=0; i<200; i++ )
if ( a[i].data != '#' ){
ht[k].data = a[i].data;
ht[k].weight = a[i].weight;
k++;
}
ht[0].weight = k-1;
hfmtree (ht); //建樹
output (ht);
do
{
printf ( "*************\n" );
printf ( "0.退出\n" );
printf ( "1.編碼\n" );
printf ( "2.解碼\n" );
printf ( "3.遍歷\n" );
printf ( "請輸入你的選擇:" );
scanf ( "%d",&select );
if ( select == 0 )
{
printf ( "感謝使用!\n" );
return 0;
}
if ( select == 1 )
coding ( hcd,ht );
else if ( select == 2 )
decoding ( hcd,ht );
}while(1);
return 0;
}
㈢ 用c語言完成：1.哈夫曼編碼/解碼器2.內部排序演算法的性能分析
我把網上的程序修改了一下，並整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//結點權值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//動態分配數組存儲哈夫曼編碼表
typedef struct
{
int key; /*關鍵字*/
}RecordNode; /*排序節點的類型*/
typedef struct
{
RecordNode *record;
int n; /*排序對象的大小*/
}SortObject; //待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//構建哈夫曼樹
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼樹中各結點的數據，沒初始值的賦值為0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循環從森林中選擇最小的兩棵樹組建成一顆新樹
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
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(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*從葉子結點到根結點求逆向編碼*/
if(ht[father].lchild==child)
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);//釋放工作空間
for(i=1;i<=n;++i)
{
printf("\n%c的編碼:",str[i]);
printf("%s\n",hc[i]);
}
}
void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);
printf("\n請輸入字元(一次性連續輸入所求的字元):");/*如:abcjhjg不要輸成ab cj hig,即字元間不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n請輸入%c的權值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}
void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("請輸入待排序的隨機數個數：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比較如下");
for(j=0;j<5;j++)
{
printf("\n\n對%d個數進行排序，結果為：\n",k);
printf("1.插入排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.選擇排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希爾排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回車繼續\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n對%d個隨機數進行5次排序，平均比較次數和平均移動次數為：\n",k);
printf("1.插入排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.選擇排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希爾排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}
void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("請選擇要運行的功能：\n");
printf("1.哈夫曼編碼解碼器\n");
printf("2.內部排序性能分析\n");
printf("3.退出該程序\n\n");
printf("你的選擇為：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
㈣ 清華大學出版社《c語言從入門到精通實例版》 和《 c語言從入門到精通》 內容上有什麼區別
實例版注重從實例中總結編程經驗，後者則強調編程原理的理解
《C語言從入門到精通》以零基礎講解為宗旨，用實例引導讀者深入學習，採取「基礎知識→核心技術→趣味題解→項目實戰」的講解模式，深入淺出地講解C語言的各項技術及實戰技能。《C語言從入門到精通》第1篇【基礎知識】主要講解步入C的世界、常量與變數、數據類型、運算符和表達式、程序控制結構和語句、輸入和輸出、數組與字元串、演算法與流程圖等；第2篇【核心技術】主要講解C語言中的函數、函數中的變數、指針、指針進階、文件、編譯與預處理指令、庫函數、位運算、結構體和聯合體、數據結構等；第3篇【趣味題解】主要講解哥德巴赫猜想、猴子選大王游戲、迷宮求解、背包問題求解、火車車廂重排、哈夫曼編碼的實現、8皇後問題的實現、商人過河游戲、K階斐波那契序列的實現、最短路徑的實現等經典數據結構問題的解決；第4篇【項目實戰】主要講解實戰前的項目規劃以及5個項目的實戰開發，包括通訊錄、圖書管理系統、簡易網路通信系統、學生成績管理系統、酒店管理系統等；第5篇【王牌資源】在DVD光碟中贈送了豐富的資源，諸如C語言標准庫函數查詢手冊、C語言常用查詢手冊、C源碼大放送、《C語言從入門到精通》【練一練】答案、C程序員職業規劃、全國計算機等級考試二級C考試大綱及應試技巧、C程序員面試技巧、C常見面試題、C常見錯誤及解決方案、C開發經驗及技巧大匯總等。
另外光碟中還包含37小時的全程同步視頻教學錄像及7小時的指導錄像（包括《C語言從入門到精通)》各章上機指導錄像及所有範例運行指導錄像）。
《C語言從入門到精通》適合任何想學習C語言的人員，無論您是否從事計算機相關行業、是否接觸過C語言，通過學習，均可快速掌握C語言的開發方法和技巧。《C語言從入門到精通（實例版）》從初學者的角度出發，通過通俗易懂的語言，豐富多彩的實例，詳細介紹了使用Visual C++ 6.0（部分使用Turbo C）進行C語言應用程序開發應該掌握的各方面技術。全書共分14章，包括初識C語言、C語言基礎、順序與選擇結構程序設計、循環控制、數組、函數、指針、結構體與共用體、演算法、位運算、預處理、文件、圖形圖像、商品信息管理系統。書中所有知識都結合具體實例進行介紹，涉及的程序代碼給出了詳細的注釋，可以使讀者輕松領會C語言應用程序開發的精髓，快速提高開發技能。另外，本書除了紙質內容之外，配書光碟中還給出了海量開發資源庫，主要內容如下：
語音視頻講解：總時長17小時，共193段 實例資源庫：881個實例及源碼詳細分析
模塊資源庫：15個經典模塊開發過程完整展現 項目案例資源庫：15個企業項目開發過程完整展現
測試題庫系統：616道能力測試題目 面試資源庫：371個企業面試真題
PPT電子教案
㈤ 數據結構中哈夫曼樹的應用（C語言）
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;
struct worder
{
char words; /*字元*/
}word[100];
struct weighted
{
int weighter; /*轉換權值有利於文件的存儲*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉樹*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}
void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼樹*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*將每個權值賦值給二維數組a[][],利用這個二維數組可以進行建立二叉樹*/
a[i+1][2]=haffTree[n+i].weight;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*對已經建立好的哈夫曼樹進行編碼*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}
void PrintBiTree(BiTreeNode *bt ,int n) /*將哈夫曼樹轉換成的二叉樹進行列印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}
int search(int a[][3],int m) /*查找和a[][2]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失敗返回數字0 查找成功返回和a[][2]相等的數的行數 i*/
else return i;
}
int searcher(int a[][3],int m) /*查找和a[][1]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失敗返回數字0 查找成功返回和a[][1]相等的數的行數 i*/
i++;
if(i==m) return 0;
else return i;
}
void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼樹*/（利用遞歸）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]為左子樹*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]為右子樹*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等則只要進行一個的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}
void code(Code myHaffCode[],int n ) /*編碼*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存儲編碼的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*讀取存儲字元的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*輸出每個權值的編碼*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字元找到對應的編碼*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*輸出相應的編碼*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}
fclose(fp2);
}
void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存儲權值個數的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存儲字元的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存儲權值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;
printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}
void menu() /*界面*/
{
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*編碼*/
printf("\t\t\t2. Decoding:\n\n"); /*解碼*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*列印哈夫曼樹*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}
void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;
HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;
case 5:exit(0);
}
}
}
getch();
}