數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn)_第1頁(yè)
已閱讀1頁(yè),還剩16頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、<p>  課程設(shè)計(jì)說(shuō)明書(shū)(論文)</p><p>  題 目 哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn) </p><p>  課 程 名 稱(chēng) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>  院(系、部、中心) </p><p>

2、  專(zhuān) 業(yè) </p><p>  班 級(jí) </p><p>  學(xué) 生 姓 名 </p><p>  學(xué) 號(hào)

3、 </p><p>  設(shè) 計(jì) 地 點(diǎn) </p><p>  指 導(dǎo) 教 師 </p><p>  設(shè)計(jì)起止時(shí)間:2008 年6月 2日至 2008 年 6月 6 日</p><p><b>  目錄</b></p>

4、;<p><b>  1問(wèn)題描述2</b></p><p>  1.1題目?jī)?nèi)容2</p><p>  1.2基本要求2</p><p>  1.3測(cè)試數(shù)據(jù)2</p><p><b>  2需求分析2</b></p><p>  2.1程序的

5、基本功能2</p><p>  2.2輸入值、輸出值以及輸入輸出形式2</p><p>  2.3各個(gè)模塊的功能要求3</p><p><b>  3概要設(shè)計(jì)4</b></p><p>  3.1所需的ADT,每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明(如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義)4</p>

6、;<p>  3.2主程序流程以及模塊調(diào)用關(guān)系4</p><p>  3.3各個(gè)模塊的算法設(shè)計(jì)說(shuō)明4</p><p><b>  4詳細(xì)設(shè)計(jì)7</b></p><p>  4.1數(shù)據(jù)類(lèi)型7</p><p>  4.2函數(shù)調(diào)用8</p><p>  5各個(gè)算法實(shí)現(xiàn)

7、的源程序8</p><p><b>  6調(diào)試分析11</b></p><p><b>  7使用說(shuō)明12</b></p><p><b>  8測(cè)試結(jié)果12</b></p><p><b>  9源程序12</b></p>

8、<p><b>  問(wèn)題描述</b></p><p><b>  題目?jī)?nèi)容</b></p><p>  哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn)</p><p>  輸入一個(gè)英文字符串,對(duì)該字符串中各字符個(gè)數(shù)進(jìn)行統(tǒng)計(jì)取得各字符的出現(xiàn)次數(shù);以其出現(xiàn)次數(shù)作為關(guān)鍵字建立哈夫曼樹(shù)并進(jìn)行編碼,最后輸出各個(gè)字符對(duì)應(yīng)的碼值。</p&

9、gt;<p><b>  基本要求</b></p><p>  要求:設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)、基本算法(主要采用程序流程圖體現(xiàn));完成基本算法的實(shí)現(xiàn)代碼;設(shè)計(jì)測(cè)試輸入數(shù)據(jù)對(duì)程序進(jìn)行測(cè)試,分析輸出結(jié)果數(shù)據(jù)、算法的時(shí)間復(fù)雜度分析,如有改進(jìn)算法則提出算法的改進(jìn)方法。</p><p><b>  測(cè)試數(shù)據(jù)</b></p><p&g

10、t;<b>  測(cè)試數(shù)據(jù)三組:</b></p><p>  AAAABBBCCD(判斷連續(xù)的字符串是否可行)</p><p>  AABBAABCDC(判斷間段的字符串是否可行)</p><p>  AAAA BBBCCD(判斷含空格的字符串是否可行)</p><p><b>  需求分析</b>&

11、lt;/p><p><b>  程序的基本功能</b></p><p>  該程序大體上有兩個(gè)功能:</p><p>  輸入任何一個(gè)字符串后,該程序能統(tǒng)計(jì)不同字符串的個(gè)數(shù),并以不同字符串的個(gè)數(shù)作為權(quán)值。</p><p>  已知不同字母的權(quán)值,以該權(quán)值作為葉結(jié)點(diǎn),構(gòu)造一棵帶權(quán)路徑最小的樹(shù),對(duì)該樹(shù)從葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支遍歷

12、,經(jīng)過(guò)一個(gè)分支就得到一位夫曼編碼值。(規(guī)定哈夫曼樹(shù)中的左分支為0,右分支為1,則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼)</p><p>  輸入值、輸出值以及輸入輸出形式</p><p>  輸入值 :AAAABBBCCD</p><p>  輸出值 :W =4 C=0</p><p>  W=3

13、 C=10</p><p>  W=2 C=111</p><p>  W=1 C=110</p><p>  輸入值 :AABBAABCDC</p><p>  輸出值 :W=4 C=0</p><p>  W=3 C=10</p><p>  W=2 C=111<

14、;/p><p>  W=1 C=110</p><p>  輸入值 :AAAA BBBCCD</p><p>  輸出值 :W=4 C=11</p><p>  W=1 C=010</p><p>  W=3 C=10</p><p>  W=2 C=00</p>

15、<p>  W=1 C=011</p><p><b>  各個(gè)模塊的功能要求</b></p><p><b>  統(tǒng)計(jì)模塊</b></p><p>  任意輸入一個(gè)字符串,不論字母是否相聯(lián),字符串中是否含空格都能統(tǒng)計(jì)出不同字母的個(gè)數(shù)。</p><p><b>  建立哈夫曼

16、樹(shù)模塊</b></p><p>  以統(tǒng)計(jì)的字符串個(gè)數(shù)作為權(quán)值,利用仿真存儲(chǔ)結(jié)構(gòu),建立帶權(quán)路徑最小的樹(shù)。</p><p>  其中對(duì)結(jié)點(diǎn)的存儲(chǔ)需要六個(gè)域,分別是 weight 域,flag域, parent域,leftChild 域,rightChild域。weight 域是對(duì)權(quán)值的存放,flag 域是一個(gè)標(biāo)志域,flag=0時(shí)表示該結(jié)點(diǎn)尚未加入到哈夫曼樹(shù)中,flag=1時(shí)表示

17、該結(jié)點(diǎn)已加入到哈夫曼樹(shù)中。</p><p><b>  哈夫曼編碼模塊</b></p><p>  從哈夫曼樹(shù)的葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支逐步遍歷,每經(jīng)過(guò)一個(gè)分支就得到一位哈夫曼編碼。哈夫曼編碼也利用仿真存儲(chǔ)結(jié)構(gòu)。</p><p><b>  主函數(shù)模塊</b></p><p>  從屏幕上輸入字符串,

18、調(diào)用函數(shù),輸出每個(gè)字母的權(quán)值與編碼。</p><p><b>  概要設(shè)計(jì)</b></p><p>  所需的ADT,每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明(如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義)</p><p>  抽象數(shù)據(jù)類(lèi)型集合:在該程序中未用到抽象數(shù)據(jù)類(lèi)型,主要用到的數(shù)據(jù)類(lèi)型為 :int ,char 。</p><p&g

19、t;  在哈夫曼樹(shù)的建立與哈夫曼樹(shù)的編碼中用到仿真存儲(chǔ)</p><p>  主程序流程以及模塊調(diào)用關(guān)系</p><p>  輸入字符串——〉調(diào)用count 函數(shù)——〉申請(qǐng)內(nèi)存空間——〉調(diào)用 Haffman</p><p>  ——〉調(diào)用 HaffmanCode——〉輸出權(quán)值與編碼。</p><p>  各個(gè)模塊的算法設(shè)計(jì)說(shuō)明</p>

20、;<p><b>  主函數(shù)模塊</b></p><p><b>  n</b></p><p><b>  y</b></p><p><b>  y</b></p><p><b>  n</b></p>

21、<p><b>  n</b></p><p><b>  y</b></p><p>  主函數(shù)中利用gets輸入一個(gè)字符串,調(diào)用count 函數(shù)統(tǒng)計(jì)不同字母的個(gè)數(shù),在調(diào)用</p><p>  Haffman 函數(shù)建立哈夫曼樹(shù),然后調(diào)用HaffmanCode函數(shù)進(jìn)行編碼,如果成功,輸出權(quán)</p>

22、<p>  值與編碼,否則退出。</p><p><b>  統(tǒng)計(jì)函數(shù)</b></p><p><b>  y</b></p><p><b>  N</b></p><p><b>  y</b></p><p>&

23、lt;b>  y</b></p><p><b>  N</b></p><p><b>  Y</b></p><p>  統(tǒng)計(jì)函數(shù)在統(tǒng)計(jì)不同字符個(gè)數(shù)時(shí)先利用一個(gè)for循環(huán)遍歷所有的字母,每遍歷一個(gè)不同字母前令temp=1,然后用一個(gè)for循環(huán)將其后的字母與之比較,若相等則temp++,且將該字母從字符

24、串中刪除,否則從下一個(gè)字母遍歷。如此循環(huán)直到字符串結(jié)束。</p><p>  Haffman 函數(shù)</p><p><b>  n</b></p><p><b>  yn</b></p><p><b>  n</b></p><p><b&

25、gt;  y </b></p><p><b>  n</b></p><p><b>  y</b></p><p><b>  n</b></p><p><b>  y</b></p><p><b> 

26、 y</b></p><p>  Haffman函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息,開(kāi)始對(duì)每個(gè)域開(kāi)始賦值,再根據(jù)不同的情況對(duì)每個(gè)域的值進(jìn)行修改,如此循環(huán)下去,直到每個(gè)域的值修改完全。</p><p>  HffmanCode 函數(shù)</p><p><b>  n</b></p><p><b>  y<

27、;/b></p><p><b>  n</b></p><p><b>  nny</b></p><p><b>  y</b></p><p>  HaffmanCode 函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息 ,由葉結(jié)點(diǎn)向根結(jié)點(diǎn)遍歷,從數(shù)據(jù)域start域開(kāi)始編碼,bit數(shù)

28、組存放編碼,其編碼為0,1序列.。</p><p><b>  詳細(xì)設(shè)計(jì)</b></p><p><b>  數(shù)據(jù)類(lèi)型</b></p><p>  typedef struct</p><p><b>  {</b></p><p>  int weig

29、ht; /*權(quán)值*/</p><p>  int flag; /*標(biāo)記*/</p><p>  int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/</p><p>  int leftChild; /*左孩子下標(biāo)*/</p><p>  int rightChild; /*右孩子下標(biāo)*/

30、</p><p>  }HaffNode; /*哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)*/</p><p>  typedef struct</p><p><b>  {</b></p><p>  int bit[MaxN]; /*數(shù)組*/</p><p>  int start;

31、 /*編碼的起始下標(biāo)*/</p><p>  int weight; /*字符的權(quán)值*/</p><p>  }Code; /*哈夫曼編碼結(jié)構(gòu)*/ </p><p>  int weight[16]; /*用于存放權(quán)值*/</p><p>  char s[30]; /* 存放

32、字符串*/</p><p><b>  函數(shù)調(diào)用</b></p><p>  各個(gè)算法實(shí)現(xiàn)的源程序</p><p>  1.字符串統(tǒng)計(jì)源程序:</p><p>  int count(char * s,int * weight,int n)</p><p><b>  {</b&g

33、t;</p><p>  int i,j,temp,k=0,p;</p><p>  for(i=0;i<n&&s[i]!='\0';i++)</p><p><b>  {</b></p><p><b>  temp=1;</b></p>&l

34、t;p>  for(j=0;j<n;j++) /*遍歷相同的字母*/</p><p><b>  {</b></p><p>  if(s[j]==s[i]&&i!=j)</p><p><b>  {</b></p><p><b>  temp

35、++;</b></p><p>  for(p=j;p<n;p++) /*刪除相同的字母*/</p><p>  s[p]=s[p+1];</p><p><b>  n--;</b></p><p><b>  j--;</b></p><p>

36、;<b>  }</b></p><p><b>  }</b></p><p>  weight[k++]=temp; /*temp 作為權(quán)值賦給weight數(shù)組*/</p><p><b>  }</b></p><p>  return i;

37、 /*返回權(quán)值個(gè)數(shù)*/</p><p><b>  }</b></p><p>  2.哈夫曼樹(shù)建立源程序</p><p>  void Haffman( int weight[],int n,HaffNode haffTree[])</p><p>  /*建立葉結(jié)點(diǎn)個(gè)數(shù)為n,權(quán)值數(shù)組為weig

38、ht的哈夫曼樹(shù)haffTree*/</p><p><b>  {</b></p><p>  int i,j,m1,m2,x1,x2;</p><p>  for(i=0;i<2*n-1;i++)</p><p><b>  {</b></p><p><b&g

39、t;  if(i<n)</b></p><p>  haffTree[i].weight=weight[i];</p><p><b>  else</b></p><p>  haffTree[i].weight=0;</p><p>  haffTree[i].parent=0;</p>

40、<p>  haffTree[i].flag=0;</p><p>  haffTree[i].leftChild=-1;</p><p>  haffTree[i].rightChild=-1;</p><p><b>  }</b></p><p>  /*構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉結(jié)點(diǎn)

41、*/</p><p>  for(i=0;i<n-1;i++)</p><p><b>  {</b></p><p>  m1=m2=MaxValue;</p><p><b>  x1=x2=0;</b></p><p>  for(j=0;j<n+i;j++

42、)</p><p><b>  {</b></p><p>  if(haffTree[j].weight<m1&&haffTree[j].flag==0)</p><p><b>  {</b></p><p><b>  m2=m1;</b></

43、p><p><b>  x2=x1;</b></p><p>  m1=haffTree[j].weight;</p><p><b>  x1=j;</b></p><p><b>  }</b></p><p><b>  else</b

44、></p><p>  if(haffTree[j].weight<m2&&haffTree[j].flag==0)</p><p><b>  {</b></p><p>  m2=haffTree[j].weight;</p><p><b>  x2=j;</b>&

45、lt;/p><p><b>  }</b></p><p><b>  }</b></p><p>  /*將找出的兩顆權(quán)值最小的子樹(shù)合并為一棵子樹(shù)*/</p><p>  haffTree[x1].parent=n+i;</p><p>  haffTree[x2].paren

46、t=n+i;</p><p>  haffTree[x1].flag=1;</p><p>  haffTree[x2].flag=1;</p><p>  haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;</p><p>  haffTree[n+i].leftChi

47、ld=x1;</p><p>  haffTree[n+i].rightChild=x2;</p><p><b>  }</b></p><p><b>  } </b></p><p>  3.哈夫曼樹(shù)編碼函數(shù)</p><p>  void HaffmanCode(Haf

48、fNode haffTree[],int n,Code haffCode[])</p><p>  /*由n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)haffTree構(gòu)造哈夫曼編碼haffCode*/ </p><p><b>  {</b></p><p>  Code *cd=(Code *)malloc(sizeof(Code));</p><

49、p>  int i,j,child,parent;</p><p>  /*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/</p><p>  for(i=0;i<n;i++)</p><p><b>  {</b></p><p>  cd->start=n-1;</p><p>  cd->

50、;weight=haffTree[i].weight;</p><p><b>  child=i;</b></p><p>  parent=haffTree[child].parent;</p><p>  /*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/</p><p>  while(parent!=0)</p>&

51、lt;p><b>  {</b></p><p>  if(haffTree[parent].leftChild==child)</p><p>  cd->bit[cd->start]=0; /*左孩子分支編碼0*/</p><p><b>  else</b></p><p&

52、gt;  cd->bit[cd->start]=1; /*左孩子分支編碼1*/</p><p>  cd->start--;</p><p>  child=parent;</p><p>  parent=haffTree[child].parent;</p><p><b>  }</b>&l

53、t;/p><p>  for(j=cd->start+1;j<n;j++)</p><p>  haffCode[i].bit[j]=cd->bit[j]; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/</p><p>  haffCode[i].start=cd->start; /*保存不等長(zhǎng)編碼的起始位置*/</p><p

54、>  haffCode[i].weight=cd->weight; /*保存相應(yīng)字符的權(quán)值*/</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  調(diào)試分析</b></p><p>  測(cè)試數(shù)據(jù)與輸出結(jié)果

55、與2.2結(jié)果相同。對(duì)過(guò)函數(shù)的分析:</p><p>  1.count 函數(shù):最壞情況下時(shí)間復(fù)雜度為O(n*n*n),調(diào)試時(shí)必須給定字符串的長(zhǎng)度,否則會(huì)輸出亂碼,這很不方便。只要在條件語(yǔ)句中加上”s[i]!='\0'” ,就能解決。同時(shí)對(duì)入含空格的字符串不能正確統(tǒng)計(jì),因?yàn)檩斎胱址且詓canf 的形式輸入,scanf 遇到空格自動(dòng)結(jié)束,將scanf 改為gets 即可,出現(xiàn)gets(s);<

56、;/p><p>  2.Haffman函數(shù)在最壞情況下計(jì)算的次數(shù)為2*n-1+(3*n-3)*n/2時(shí)間復(fù)雜度最壞情況下為O(n*n); Haffman函數(shù)在書(shū)寫(xiě)時(shí)要注意定義變量的位置。</p><p>  3.HaffmanCode函數(shù)在最壞情況下計(jì)算的次數(shù)為n*(3*n-1),時(shí)間復(fù)雜度為O(n*n); HaffmanCode函數(shù)在書(shū)寫(xiě)時(shí)要注意定義變量的位置。</p><

57、;p>  4.主函數(shù)的時(shí)間復(fù)雜度又輸入的字符串決定。曾在主函數(shù)中將printf("輸入:\n"); get(s),n=count(s,weight,30)放在Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode)前面,出現(xiàn)很多問(wèn)題,像“HaffNode undefine”,”see undeclear HaffNode”等, 調(diào)整后

58、沒(méi)有問(wèn)題。主函數(shù)的時(shí)間復(fù)雜度由輸入的字符串決定。</p><p>  算法改進(jìn)設(shè)想:由于統(tǒng)計(jì)函數(shù)時(shí)間復(fù)雜度較高,是否降低其時(shí)間復(fù)雜度?統(tǒng)計(jì)函數(shù)中用到三個(gè)循環(huán),一個(gè)用于遍歷所有字符,一個(gè)用于尋找相同字符,一個(gè)用于刪除相同字符。而且三個(gè)循環(huán)嵌套,如果能減少循環(huán)的次數(shù)或者是由較少的循環(huán)嵌套,就能降低時(shí)間復(fù)雜度了。</p><p><b>  使用說(shuō)明</b></p&g

59、t;<p>  在寫(xiě)源程序前先將所要用到的函數(shù)都寫(xiě)好,以“haffman.h”保存起來(lái)。再書(shū)寫(xiě)主函數(shù),保存到相同的位置。在vc環(huán)境下,用“Build”里面的“complie”,進(jìn)行編譯 ,運(yùn)行。利用Debug中的F5,F10,F9,F11設(shè)置斷點(diǎn)等進(jìn)行調(diào)試。</p><p><b>  測(cè)試結(jié)果</b></p><p><b>  源程序<

60、;/b></p><p>  包含哈夫曼樹(shù)和圖,以哈夫曼樹(shù)為主要。圖在壓縮文件中</p><p><b>  哈夫曼樹(shù)</b></p><p>  #include<stdio.h></p><p>  #include<stdlib.h></p><p>  #de

61、fine MaxValue 10000</p><p>  #define MaxBit 4</p><p>  #define MaxN 10</p><p>  typedef struct</p><p><b>  {</b></p><p>  int weight; /*

62、權(quán)值*/</p><p>  int flag; /*標(biāo)記*/</p><p>  int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/</p><p>  int leftChild; /*左孩子下標(biāo)*/</p><p>  int rightChild; /*右孩子下標(biāo)*/</p>&

63、lt;p>  }HaffNode; /*哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)*/</p><p>  typedef struct</p><p><b>  {</b></p><p>  int bit[MaxN]; /*數(shù)組*/</p><p>  int start; /*編碼的起

64、始下標(biāo)*/</p><p>  int weight; /*字符的權(quán)值*/</p><p>  }Code; /*哈夫曼編碼結(jié)構(gòu)*/</p><p>  void Haffman( int weight[],int n,HaffNode haffTree[])</p><p>  /*建立葉結(jié)點(diǎn)個(gè)數(shù)為n,權(quán)

65、值數(shù)組為weight的哈夫曼樹(shù)haffTree*/</p><p><b>  {</b></p><p>  int i,j,m1,m2,x1,x2;</p><p>  for(i=0;i<2*n-1;i++)</p><p><b>  {</b></p><p>

66、;<b>  if(i<n)</b></p><p>  haffTree[i].weight=weight[i];</p><p><b>  else</b></p><p>  haffTree[i].weight=0;</p><p>  haffTree[i].parent=0;&l

67、t;/p><p>  haffTree[i].flag=0;</p><p>  haffTree[i].leftChild=-1;</p><p>  haffTree[i].rightChild=-1;</p><p><b>  }</b></p><p>  /*構(gòu)造哈夫曼樹(shù)haffTree的

68、n-1個(gè)非葉結(jié)點(diǎn)*/</p><p>  for(i=0;i<n-1;i++)</p><p><b>  {</b></p><p>  m1=m2=MaxValue;</p><p><b>  x1=x2=0;</b></p><p>  for(j=0;j<

69、;n+i;j++)</p><p><b>  {</b></p><p>  if(haffTree[j].weight<m1&&haffTree[j].flag==0)</p><p><b>  {</b></p><p><b>  m2=m1;</b&

70、gt;</p><p><b>  x2=x1;</b></p><p>  m1=haffTree[j].weight;</p><p><b>  x1=j;</b></p><p><b>  }</b></p><p><b>  el

71、se</b></p><p>  if(haffTree[j].weight<m2&&haffTree[j].flag==0)</p><p><b>  {</b></p><p>  m2=haffTree[j].weight;</p><p><b>  x2=j;<

72、;/b></p><p><b>  }</b></p><p><b>  }</b></p><p>  /*將找出的兩顆權(quán)值最小的子樹(shù)合并為一棵子樹(shù)*/</p><p>  haffTree[x1].parent=n+i;</p><p>  haffTree[x

73、2].parent=n+i;</p><p>  haffTree[x1].flag=1;</p><p>  haffTree[x2].flag=1;</p><p>  haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;</p><p>  haffTree[n+i]

74、.leftChild=x1;</p><p>  haffTree[n+i].rightChild=x2;</p><p><b>  }</b></p><p><b>  }</b></p><p>  void HaffmanCode(HaffNode haffTree[],int n,Cod

75、e haffCode[])</p><p>  /*由n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)haffTree構(gòu)造哈夫曼編碼haffCode*/ </p><p><b>  {</b></p><p>  Code *cd=(Code *)malloc(sizeof(Code));</p><p>  int i,j,child,pare

76、nt;</p><p>  /*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/</p><p>  for(i=0;i<n;i++)</p><p><b>  {</b></p><p>  cd->start=n-1;</p><p>  cd->weight=haffTree[i].weigh

77、t;</p><p><b>  child=i;</b></p><p>  parent=haffTree[child].parent;</p><p>  /*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/</p><p>  while(parent!=0)</p><p><b>  {</

78、b></p><p>  if(haffTree[parent].leftChild==child)</p><p>  cd->bit[cd->start]=0; /*左孩子分支編碼0*/</p><p><b>  else</b></p><p>  cd->bit[cd->st

79、art]=1; /*左孩子分支編碼1*/</p><p>  cd->start--;</p><p>  child=parent;</p><p>  parent=haffTree[child].parent;</p><p><b>  }</b></p><p>  for(

80、j=cd->start+1;j<n;j++)</p><p>  haffCode[i].bit[j]=cd->bit[j]; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/</p><p>  haffCode[i].start=cd->start; /*保存不等長(zhǎng)編碼的起始位置*/</p><p>  haffCode[i].weight=

81、cd->weight; /*保存相應(yīng)字符的權(quán)值*/</p><p><b>  }</b></p><p><b>  }</b></p><p>  int count(char * s,int * weight,int n)</p><p><b>  {</b>

82、;</p><p>  int i,j,temp,k=0,p;</p><p>  for(i=0;i<n&&s[i]!='\0';i++)</p><p><b>  {</b></p><p><b>  temp=1;</b></p><

83、;p>  for(j=0;j<n;j++)</p><p><b>  {</b></p><p>  if(s[j]==s[i]&&i!=j)</p><p><b>  {</b></p><p><b>  temp++;</b></p&

84、gt;<p>  for(p=j;p<n;p++)</p><p>  s[p]=s[p+1];</p><p><b>  n--;</b></p><p><b>  j--;</b></p><p><b>  }</b></p><

85、;p><b>  }</b></p><p>  weight[k++]=temp;</p><p><b>  }</b></p><p><b>  return i;</b></p><p><b>  }</b></p><

86、;p>  void main()</p><p><b>  {</b></p><p>  int i,j,n;</p><p>  int weight[16];</p><p>  char s[30];</p><p>  HaffNode *myHaffTree;</p>

87、;<p>  Code *myHaffCode;</p><p>  printf(" ************輸入字符串************\n");</p><p><b>  gets(s);</b></p><p>  n=count(s,weight,30);</p&

88、gt;<p>  myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n+1));</p><p>  myHaffCode=(Code*)malloc(sizeof(Code)*n);</p><p>  if(n>MaxN)</p><p><b>  {</b></p

89、><p>  printf("給出的n越界,修改MaxN!\n");</p><p><b>  exit(1);</b></p><p><b>  }</b></p><p>  Haffman(weight,n,myHaffTree);</p><p>

90、  HaffmanCode(myHaffTree,n,myHaffCode);</p><p>  /*輸出每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼*/</p><p>  for(i=0;i<n;i++)</p><p><b>  {</b></p><p>  printf(" W=

91、%d C= ",myHaffCode[i].weight);</p><p>  for(j=myHaffCode[i].start+1;j<n;j++)</p><p>  printf("%d",myHaffCode[i].bit[j]);</p><p>  printf("\n"

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論