2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩34頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、<p><b>  哈夫曼編碼與譯碼</b></p><p>  學(xué)生姓名: 指導(dǎo)老師:</p><p>  摘 要 本課程設(shè)計(jì)主要解決的是利用哈夫曼樹生成的哈夫曼編碼進(jìn)行字符串的加密和解密,并將加密的編碼寫入文件。在此課程設(shè)計(jì)中,系統(tǒng)開發(fā)平臺(tái)為Windows XP,程序設(shè)計(jì)語(yǔ)言采用面向過程的高級(jí)語(yǔ)言C和面向?qū)ο蟮母呒?jí)語(yǔ)言C++,程序運(yùn)行平臺(tái)為Vis

2、ual C++ 6.0。在程序設(shè)計(jì)中,采用了結(jié)構(gòu)化與面向過程兩種解決問題的方法。程序通過調(diào)試運(yùn)行,初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo),并且經(jīng)過適當(dāng)完善后,將可以應(yīng)用在商業(yè)中解決實(shí)際問題。</p><p>  關(guān)鍵詞 哈夫曼樹,編碼,譯碼,文件操作,C,C++; </p><p><b>  1 引 言</b></p><p><b>  1.1 課

3、題背景</b></p><p>  隨著信息時(shí)代的到來(lái),各種信息日益豐富,信息迅速膨脹,對(duì)信息管理的工作量也日益增大。在信息化未到來(lái)之前,信息的存儲(chǔ)編碼也變得尤為重要,公司之間的信息需要編碼,用戶個(gè)人數(shù)據(jù)需要編碼,都需要占用很大的空間,所以一個(gè)好的、高效的編碼譯碼算法是十分重要的。好的加密算法不僅可以降低管理方的工作量和存儲(chǔ)量,還可以對(duì)用戶的信息進(jìn)行高效的管理,同時(shí)使在用中可以避免不必要的麻煩。 &l

4、t;/p><p>  數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同,數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)(logical structure)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。所謂邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同,數(shù)據(jù)結(jié)構(gòu)分為四類:集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖,是面向問題的,反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式。為了區(qū)別于數(shù)據(jù)的

5、存儲(chǔ)結(jié)構(gòu),常常將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storage structure)又稱為物理結(jié)構(gòu),是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示,換言之,存儲(chǔ)結(jié)構(gòu)除了數(shù)據(jù)元素之外,必須隱式或顯示地存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。通常有兩種存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。</p><p>  樹是一種在實(shí)際應(yīng)用中被廣泛使用的數(shù)據(jù)結(jié)構(gòu)。它是由同一類型的記錄構(gòu)成的集合。哈夫曼樹是樹的一種子類型,又稱最優(yōu)樹,是一類帶

6、權(quán)路徑最短的樹,利用哈夫曼樹可以得到合適的字符編碼,這樣我們既可以對(duì)數(shù)據(jù)加密,也可以實(shí)現(xiàn)高效的存儲(chǔ)信息。因此哈夫曼編碼是一種常用的編碼方式。</p><p>  1.2 課程設(shè)計(jì)目的</p><p>  哈夫曼編碼與譯碼系統(tǒng)是為了實(shí)現(xiàn)信息的高效存儲(chǔ)與管理、加密、解密而設(shè)計(jì)的。通過建立一個(gè)有效,低存儲(chǔ)量,易于管理的編碼譯碼系統(tǒng),使得企業(yè)對(duì)信息管理更加高效、準(zhǔn)確,更加科學(xué)化和正規(guī)化,降低企業(yè)對(duì)

7、信息管理的難度。</p><p>  本課程設(shè)計(jì)主要是用數(shù)據(jù)結(jié)構(gòu)和文件實(shí)現(xiàn)的,通過程序的編寫、調(diào)試和運(yùn)行可以進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。理解對(duì)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)及應(yīng)用,同時(shí)加深對(duì)哈夫曼樹的運(yùn)用及理解。本課程設(shè)計(jì)是利用哈夫曼編碼實(shí)現(xiàn)對(duì)字符串的加密、解密和低存儲(chǔ)量存儲(chǔ),程序?qū)崿F(xiàn)哈夫曼樹的建立和哈夫曼編碼的生成,實(shí)現(xiàn)字符串的快速編碼、解密和保存。掌握哈夫曼編碼的工作原理,熟悉建立哈夫曼樹、利用哈夫曼編

8、碼進(jìn)行實(shí)際編碼、解碼等功能的實(shí)現(xiàn),同時(shí)加深對(duì)文件的操作原理。 </p><p><b>  1.3課程設(shè)計(jì)內(nèi)容</b></p><p>  本課程設(shè)計(jì)主要是采用哈夫曼編碼對(duì)字符串的編碼、解碼,同時(shí)實(shí)現(xiàn)地存儲(chǔ)量要求。在設(shè)計(jì)的過程中,共用到兩種數(shù)據(jù)元素,第一種是哈夫曼樹建立是用到樹的結(jié)構(gòu),樹節(jié)點(diǎn)信息包括父節(jié)點(diǎn)、左

9、子樹節(jié)點(diǎn)、右子樹節(jié)點(diǎn)以及該節(jié)點(diǎn)的權(quán)值其信息如圖1-1所示,第二種是在存儲(chǔ)個(gè)字符對(duì)應(yīng)編碼時(shí)用到的結(jié)構(gòu),其中包括字符、字符密文以及其長(zhǎng)度,如圖1-2所示:</p><p>  圖1-1 樹節(jié)點(diǎn)數(shù)據(jù)元素</p><p>  圖1-2 每個(gè)字符密文數(shù)據(jù)元素</p><p>  程序功能是實(shí)現(xiàn)對(duì)用戶輸入信息的編碼與解碼,并存入文件中,具體如圖1-3所示:</p>

10、<p>  圖1-3 功能模塊圖</p><p><b>  2 設(shè)計(jì)思路與方案</b></p><p><b>  2.1 設(shè)計(jì)思路</b></p><p>  C語(yǔ)言是結(jié)構(gòu)化和模塊化的語(yǔ)言,它是面向過程的。在處理較小規(guī)模的程序時(shí),程序員用C語(yǔ)言還比較得心應(yīng)手。</p><p>  C

11、++是由C語(yǔ)言發(fā)展而來(lái)的,與C語(yǔ)言兼容。用C語(yǔ)言編寫的程序基本上可以不加修改地用于C++。從C++的名字可以看出它是C的超集。C++既可以用于面向過程的結(jié)構(gòu)化程序設(shè)計(jì),又可用于面向?qū)ο蟮某绦蛟O(shè)計(jì),是一種功能強(qiáng)大的混合型的程序設(shè)計(jì)語(yǔ)言。</p><p>  C++對(duì)C的“增強(qiáng)”,表現(xiàn)在兩個(gè)方面:</p><p> ?。?)在原來(lái)面向過程的機(jī)制基礎(chǔ)上,對(duì)C語(yǔ)言的功能做了不少擴(kuò)充。</p&

12、gt;<p>  (2)增加了面向?qū)ο蟮臋C(jī)制。</p><p>  作為一種編程約定,C++程序員傾向于只有當(dāng)所有的成員均為公共時(shí)才使用結(jié)構(gòu)。結(jié)構(gòu)(struct)是一種特殊的類,它的特殊之處在于其成員都是公共的(除非另作聲明)。C++程序員只有在所有成員都是公共的時(shí)候才會(huì)使用結(jié)構(gòu)。</p><p>  在計(jì)算機(jī)中進(jìn)行編碼的方法有很多種,此文選擇哈弗曼編碼。哈弗曼編碼由哈弗曼樹

13、得到,所以我們要選擇存儲(chǔ)樹的數(shù)據(jù)結(jié)構(gòu),為了高效的產(chǎn)生哈弗曼編碼,樹的存儲(chǔ)采用三叉鏈表的方式,同時(shí)增加一個(gè)選項(xiàng)以存儲(chǔ)各個(gè)樹結(jié)點(diǎn)的權(quán)值。同時(shí)將得到的密文存儲(chǔ)到文件中,以便我們進(jìn)行查看。</p><p><b>  2.2 設(shè)計(jì)方案</b></p><p>  通過分析可知,本課程設(shè)計(jì)主要功能是通過哈弗曼樹得到哈弗曼編碼,利用得到的哈弗曼編碼對(duì)字符串進(jìn)行編碼與譯碼,并存入文

14、件便于查看。由于構(gòu)造哈弗曼樹和根據(jù)哈弗曼樹得到編碼時(shí)要經(jīng)常對(duì)節(jié)點(diǎn)的父結(jié)點(diǎn),左右子樹結(jié)點(diǎn)進(jìn)行訪問,所以采用三叉鏈表的方式存儲(chǔ)樹結(jié)點(diǎn),同時(shí)在該結(jié)點(diǎn)信息中還需要增加一個(gè)選項(xiàng)存儲(chǔ)結(jié)點(diǎn)的權(quán)值。其次,為了解決得到的哈弗曼編碼的存儲(chǔ)問題,再建立一個(gè)結(jié)構(gòu)體,用于存儲(chǔ)每個(gè)字符所對(duì)應(yīng)編碼及編碼長(zhǎng)度,編碼的存儲(chǔ)簡(jiǎn)化了編碼與譯碼的操作。同時(shí),將得到的密文存儲(chǔ)到文件中,便于我們查看。</p><p>  定義一個(gè)結(jié)構(gòu)體HTNode將樹結(jié)點(diǎn)

15、,父結(jié)點(diǎn),左右子樹結(jié)點(diǎn)及該結(jié)點(diǎn)的權(quán)值聯(lián)系在一起,便于操作。具體定義如下:</p><p>  typedef struct//建立樹結(jié)點(diǎn)</p><p><b>  { </b></p><p>  int weight;</p><p>  int parent,lchild,rchild;</p>

16、<p><b>  }HTNode; </b></p><p>  定義一個(gè)結(jié)構(gòu)體CodeNode將各個(gè)字符對(duì)應(yīng)編碼及編碼的長(zhǎng)度聯(lián)系在一起,便于操作。具體定義如下:</p><p>  typedef struct//建立每個(gè)編碼的結(jié)構(gòu)體</p><p><b>  {</b></p>&l

17、t;p><b>  char ch;</b></p><p>  char bits[10];</p><p><b>  int len;</b></p><p>  }CodeNode;</p><p>  同時(shí),為了操作的方便,我們做如下處理:</p><p> 

18、 typedef HTNode HafumanTree[m+1];//重命名HTNode</p><p>  typedef CodeNode HafumanCode[n+1];//重命名CodeNode</p><p><b>  3 詳細(xì)設(shè)計(jì)</b></p><p>  3.1 menu菜單功能</p><p&

19、gt;  Menu菜單主要用于讓用戶選擇何種方式構(gòu)造哈弗曼樹,此時(shí)需要用戶輸入0或者1來(lái)進(jìn)行控制。該段代碼位于viod main()函數(shù)中。其代碼如下:</p><p>  printf(" -------------------------------------------------------------------------- \n");</p><p&

20、gt;  printf(" 歡迎使用編碼譯碼系統(tǒng)\n");</p><p>  printf(" -------------------------------------------------------------------------- \n");</p><p>  printf("請(qǐng)

21、輸入獲得權(quán)值的方法,輸入1表示自己輸入每個(gè)節(jié)點(diǎn)的權(quán)值,輸入0表示將每個(gè)字符在輸入字符串中出現(xiàn)的次數(shù)作為其權(quán)值:");</p><p>  scanf("%d",&method); //通過用戶的輸入來(lái)判斷使用何種方式</p><p>  其流程圖如圖3-1所示:</p><p>  圖3-1 menu菜單</p&

22、gt;<p>  3.2 int counttotal(char *s,int quan[],char str[])函數(shù)</p><p>  當(dāng)用戶選擇通過輸入的字符串自動(dòng)獲取權(quán)值(統(tǒng)計(jì)出現(xiàn)的字符種數(shù)以及每種字符出現(xiàn)的次數(shù), 將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值)時(shí),main函數(shù)將會(huì)調(diào)用該函數(shù)計(jì)算各個(gè)節(jié)點(diǎn)的權(quán)值,將相應(yīng)的字符存入str[]字符數(shù)組,同時(shí)該字符對(duì)應(yīng)的權(quán)值存入quan[]數(shù)組中。算法流程圖

23、如圖3-1:</p><p>  圖3-1計(jì)算字符權(quán)值及字符種類算</p><p>  說(shuō)明:counttotal()函數(shù)代碼見附錄。</p><p>  3.3 void selectmin()函數(shù) </p><p>  該函數(shù)的作用是在所有給定權(quán)值的結(jié)點(diǎn)中選出權(quán)值最小的兩個(gè)結(jié)點(diǎn)并返回,用于構(gòu)造哈弗曼樹。代碼如下:</p>

24、<p>  void selectmin(HafumanTree HT,int k,int *s1,int*s2)</p><p>  //選擇權(quán)值最小的兩個(gè)</p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  int m

25、in=9999;//聲明一個(gè)int類型的數(shù)值min,賦個(gè)較大的輸給它</p><p>  for(i=1;i<=k;i++)//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)(且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn))</p><p><b>  {</b></p><p>  if((HT[i].weight<min)&&(HT[i].parent==0

26、))</p><p><b>  {</b></p><p><b>  j=i;</b></p><p>  min=HT[i].weight;</p><p><b>  }</b></p><p><b>  }</b><

27、;/p><p><b>  *s1=j;</b></p><p><b>  min=9999;</b></p><p>  for(i=1;i<=k;i++)</p><p><b>  {</b></p><p>  if((HT[i].weigh

28、t<min)&&(HT[i].parent==0)&&(i!=*s1))</p><p>  //選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)(且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn))</p><p><b>  { j=i;</b></p><p>  min=HT[i].weight;</p><p><b&

29、gt;  }</b></p><p><b>  }</b></p><p><b>  *s2=j;</b></p><p><b>  }</b></p><p>  說(shuō)明:本函數(shù)返回兩個(gè)權(quán)值最小的結(jié)點(diǎn)信息分別存儲(chǔ)在s1和s2中,為下一步構(gòu)造哈弗曼樹做準(zhǔn)備。&l

30、t;/p><p>  3.4 void creathafumantree( )函數(shù)</p><p>  Creathafumantree()函數(shù)用于構(gòu)造一棵哈夫曼樹,構(gòu)造哈弗曼樹的步驟為:</p><p>  根據(jù)給定n個(gè)權(quán)值構(gòu)成n棵二叉樹的集合F,其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn),其左右字?jǐn)?shù)均為空。</p><p>  在F中選取

31、兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左、右子樹構(gòu)造一棵新的二叉樹,且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)權(quán)值之和。</p><p>  在F中刪除這兩棵樹,同時(shí)將新得到的二叉樹加入F中。</p><p>  重復(fù)步驟(2)和(3),直到F只含一棵樹為止,得到的樹便是哈夫曼樹。</p><p>  其算法流程圖如圖3-3所示:</p>&l

32、t;p>  圖 3-3 函數(shù)creathafumantree( )的算法流程圖</p><p>  說(shuō)明:其源代碼見附錄</p><p>  3.5 void Hafumanencode( )函數(shù)</p><p>  Hafumanencode( )函數(shù)是根據(jù)creathafumantree( )函數(shù)構(gòu)造的哈弗曼樹得到哈弗曼編碼。根據(jù)每個(gè)字符在哈夫曼樹中的位置

33、來(lái)編譯每個(gè)字符的0、1密文代碼,從葉節(jié)點(diǎn)判斷該葉節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右字左字為‘0’,右子為‘1’,在判斷父節(jié)點(diǎn)是上級(jí)父節(jié)點(diǎn)的左右子直至根節(jié)點(diǎn),將生成的0、1字符串按所表示的字符倒序存入HC相應(yīng)的字符的bins[]數(shù)組,代碼如下:</p><p>  void Hafumanencode(HafumanTree HT,HafumanCode HC)</p><p><b>  {&

34、lt;/b></p><p>  int c,p,i;</p><p>  char cd[n];//臨時(shí)數(shù)組用于記錄字符在哈夫曼樹的位置</p><p>  int start;</p><p>  cd[num]='\0';//給cd賦個(gè)結(jié)束符</p><p>  for

35、(i=1;i<=num;i++)</p><p><b>  {</b></p><p>  start=num;</p><p><b>  c=i;</b></p><p>  while((p=HT[c].parent)>0)</p><p>  //根據(jù)

36、節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右子來(lái)記錄它的位置</p><p><b>  {</b></p><p>  cd[--start]=(HT[p].lchild==c)?'0':'1';</p><p>  c=p;//將父節(jié)點(diǎn)轉(zhuǎn)為子節(jié)點(diǎn)</p><p><b>  }<

37、/b></p><p>  strcpy(HC[i].bits,&cd[start]);//將得到的0、1字串存入結(jié)構(gòu)體HC</p><p>  printf("%c:%s\n",HC[i].ch,HC[i].bits);</p><p>  HC[i].len=num-start;//求每個(gè)字符0、1編碼長(zhǎng)度<

38、;/p><p><b>  }</b></p><p><b>  }</b></p><p>  3.6 void codenum( )函數(shù)</p><p>  codenum()函數(shù)主要用于對(duì)輸入字符串進(jìn)行編碼。根據(jù)Hafumanencode( )函數(shù)得到的編碼,將字符串轉(zhuǎn)化為密文,為了方便查看,最

39、后會(huì)將得到的密文存入文件code.txt中。該函數(shù)由于要涉及到文件操作,故定義了文件流指針fp。該函數(shù)的算法流程圖如圖3-4所示:</p><p>  3.7 char *decode( )函數(shù)</p><p>  decode()函數(shù)用于將已加密的密文進(jìn)行譯碼翻譯為原字符串。解碼時(shí)從code.txt</p><p>  文件夾中,一個(gè)一個(gè)字符的讀出那串0、1代碼賦

40、給一個(gè)臨時(shí)字符串cd[],用該字符串與每個(gè)字符的HC[i].bins密文比較,直到與一個(gè)字符的密文相同時(shí),譯出該字符,將字符存放在臨時(shí)字符數(shù)組tempstr[]中,清空臨時(shí)字符串繼續(xù)讀取0、1代碼進(jìn)行翻譯,直至文件密文結(jié)束為止。于是就得到了原先被加密的那串字符串。該函數(shù)的算法流程圖如圖3-5所示:</p><p><b>  4 運(yùn)行結(jié)果</b></p><p>  

41、(1) 運(yùn)行程序,菜單如圖4-1:</p><p>  圖 4-1 功能菜單</p><p>  (2) 若要自己輸入每個(gè)字符的權(quán)值,輸入1后回車,如圖4-2:</p><p>  圖4-2 菜單狀態(tài)輸入1(選擇自己輸入權(quán)值)</p><p>  (3) 在(2)之后需要輸入字符的種類數(shù),這里假定有三種,輸入3回車,</p>&

42、lt;p><b>  圖4-3:</b></p><p>  圖4-3 輸入字符出現(xiàn)的種類數(shù)</p><p>  (4) 在(3)之后需要輸入第一個(gè)字符和該字符的權(quán)值,假定輸入字符a和權(quán)值3,回車會(huì)提示輸入第二字符和其權(quán)值,輸入字符b和權(quán)值5,回車,繼續(xù)提示輸入第三字符和其權(quán)值,輸入字符c和權(quán)值7,確認(rèn)回車,如圖4-3:</p><p>

43、  圖4-4 輸入字符和字符的權(quán)值</p><p>  (5) 在(4)確認(rèn)之后哈夫曼樹已經(jīng)構(gòu)造好,并且編碼已經(jīng)得到,這時(shí)會(huì)輸出各個(gè)字符、相應(yīng)權(quán)值及該字符的哈夫曼編碼,同時(shí)會(huì)提示輸入要按照得到的哈夫曼編碼進(jìn)行編碼的字符串,如圖4-5:</p><p>  圖4-5 各字符的哈夫曼編碼</p><p>  (6) 在(5)之后需要輸入要進(jìn)行編碼的字符串,假定輸入字符串

44、abcbcbaa,如圖4-6:</p><p>  圖4-6 輸入要編碼的字符串 </p><p>  (7) 在(6)之后確認(rèn)輸入,程序會(huì)將得到的編碼輸出,并將編碼寫入文件code.txt(當(dāng)前工程工作路徑下),寫入后會(huì)提示寫入文件成功,同時(shí)程序會(huì)根據(jù)每個(gè)字符的哈夫曼編碼和code.txt文件中的字符串編碼譯碼,并輸出,最后會(huì)提示是否要繼續(xù)運(yùn)行該程序。如圖4-7:</p>

45、<p>  圖4-7 編碼譯碼及寫入文件</p><p>  (8) 在(7)之后輸入1后回車,繼續(xù)運(yùn)行該編碼譯碼程序,同時(shí)演示第二種編碼譯碼方式(即不主動(dòng)輸入權(quán)值,將該種字符出現(xiàn)的次數(shù)作為它的權(quán)值),輸入0回車,如圖4-8:</p><p>  圖4-8 繼續(xù)運(yùn)行并選擇第二種方式</p><p>  (9) 在(8)之后確認(rèn)回車,系統(tǒng)會(huì)提示輸入將要編碼的

46、字符串,假定這里輸入字符串a(chǎn)sddcxxsad,如圖4-9:</p><p>  圖4-9 輸入要進(jìn)行編碼的字符串</p><p>  (10) 在(9)之后確認(rèn)回車,系統(tǒng)將對(duì)輸入的字符串進(jìn)行統(tǒng)計(jì),得到輸入字符的種類并計(jì)算出各字符的權(quán)值,同時(shí)根據(jù)得到的權(quán)值構(gòu)造哈夫曼樹并得到哈夫曼編碼,最后會(huì)根據(jù)哈夫曼編碼對(duì)字符串進(jìn)行編碼,同時(shí)會(huì)將編碼寫入文件,譯碼輸出。如圖4-10:</p>

47、<p>  圖4-10 編碼譯碼及寫入文件</p><p>  (11) 在程序運(yùn)行后系統(tǒng)會(huì)提示輸入0或1選擇編碼方式,若輸入其它的數(shù)值,系統(tǒng)會(huì)提示錯(cuò)誤輸入,如圖4-11:</p><p>  圖4-11 錯(cuò)誤輸入</p><p>  (12) 在程序運(yùn)行后系統(tǒng)會(huì)提示是否需要繼續(xù)進(jìn)行編碼譯碼,輸入0則推出系統(tǒng),如圖4-12:</p><

48、;p>  圖4-12 退出系統(tǒng)</p><p><b>  5 結(jié)束語(yǔ)</b></p><p>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)和現(xiàn)代計(jì)算機(jī)技術(shù)的實(shí)際應(yīng)用相結(jié)合,是我們?cè)诒緦W(xué)期學(xué)完理論課程之后對(duì)自己學(xué)習(xí)能力的一次很好的檢驗(yàn),從開始的算法思路到運(yùn)行調(diào)試后的可執(zhí)行程序,都是一個(gè)很好的學(xué)習(xí)和鍛煉的過程。既可以使我們鞏固了原有的理論知識(shí),培養(yǎng)了我們靈活運(yùn)用和組合集成所學(xué)過知識(shí)及技能

49、來(lái)分析、解決實(shí)際問題的能力,也可以使我們體會(huì)到自身知識(shí)和能力能在實(shí)際中的應(yīng)用和發(fā)揮。不但可以激發(fā)創(chuàng)新意識(shí),還可以開發(fā)創(chuàng)造能力、培養(yǎng)溝通能力。這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的時(shí)間里雖然時(shí)間有限,但確實(shí)使我受益非淺。通過實(shí)踐課程設(shè)計(jì)我豐富了編譯工具操作經(jīng)驗(yàn),更加深了對(duì)C和C++語(yǔ)言的了解,熟悉了其環(huán)境,更增強(qiáng)了對(duì)哈夫曼樹的理解與運(yùn)用。</p><p>  而且,在完成本課程設(shè)計(jì)的過程中,也充滿磨練了我的意志,鍛煉了我的耐心、認(rèn)

50、真。在實(shí)踐的過程中,需要不倦的查閱資料,甚至需要求助于老師、同學(xué)。要善于思考,多動(dòng)手。我深知,獨(dú)立完成這樣一項(xiàng)任務(wù)需要克服許多困難。</p><p>  總之,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讓我受益良多,我會(huì)好好珍惜像這種難得的機(jī)會(huì),努力學(xué)習(xí)知識(shí)。也感謝幫助了我的老師、同學(xué)。</p><p><b>  參考文獻(xiàn)</b></p><p>  [1] 嚴(yán)蔚敏,

51、吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社,2011.5 </p><p>  [2] 汪潔,數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)現(xiàn)與習(xí)題解答.人民郵電出版社,2004.1</p><p>  [3] 譚浩強(qiáng),C++程序設(shè)計(jì)(第一版).北京:清華大學(xué)出版社,2010.6</p><p>  [4] 譚浩強(qiáng),C程序設(shè)計(jì)(第三版).北京:清華大學(xué)出版社,2005.7</p>

52、<p><b>  附 錄 :源程序</b></p><p>  // 程序名稱:哈夫曼編碼與譯碼</p><p><b>  // 程序作者:</b></p><p>  // 最后修改日期:2012-6-27</p><p>  #include <iostream>&

53、lt;/p><p>  #include <stdlib.h></p><p>  #include <string.h></p><p>  using namespace std;</p><p>  #define n 100//葉節(jié)點(diǎn)的個(gè)數(shù)小等于n</p><p>  #def

54、ine m 2*n-1//總結(jié)點(diǎn)的個(gè)數(shù)為m=2*n-1</p><p>  int num;//定義一個(gè)全局變量用于存放字符種類個(gè)數(shù)</p><p>  typedef struct </p><p>  //結(jié)構(gòu)體用于存放樹節(jié)點(diǎn)包括節(jié)點(diǎn)的父節(jié)點(diǎn)、左子、右子以及權(quán)值</p><p><b>  { <

55、;/b></p><p>  int weight;</p><p>  int parent,lchild,rchild;</p><p><b>  }HTNode;</b></p><p>  typedef HTNode HafumanTree[m+1];//重命名HTNode HT</p

56、><p>  typedef struct//結(jié)構(gòu)體由于存放每個(gè)字符的密文和長(zhǎng)度</p><p><b>  {</b></p><p><b>  char ch;</b></p><p>  char bits[10];</p><p><b>  in

57、t len;</b></p><p>  }CodeNode;</p><p>  typedef CodeNode HafumanCode[n+1];//重命名CodeNode HC</p><p>  int main(int argc, char* argv[])</p><p><b>  {<

58、/b></p><p>  int quan[27],k=1,length,count=1,total,method;</p><p>  //聲明一個(gè)數(shù)組用以存放26字符的權(quán)</p><p>  值,length表示要加密字符串的長(zhǎng)度</p><p>  //count用于控制輸入字符和權(quán)值的次數(shù),total</p>

59、<p>  用于循環(huán)控制,k用于控制解密,加密的次數(shù)</p><p>  //method用于控制使用何種方法進(jìn)行輸入權(quán)值</p><p>  char getstr[300],str[27];</p><p>  //聲明兩個(gè)字符串?dāng)?shù)組一個(gè)用于存輸入,一個(gè)由于存放</p><p><b>  輸入中含有的字符<

60、;/b></p><p>  char *s; //聲明一個(gè)char型指針用于指向字符HafumanTree HT;</p><p>  HafumanCode HC; //聲明m+1個(gè)樹節(jié)點(diǎn)</p><p>  HafumanTree HT; //聲明n+1個(gè)code</p><p>  int c

61、ounttotal(char *s,int quan[],char str[]);//聲明需要調(diào)用的函數(shù)</p><p>  void creathafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]);</p><p>  void Hafumanencode(HafumanTree HT,HafumanCo

62、de HC);</p><p>  void codenum(HafumanCode HC,char *str);</p><p>  char *decode(HafumanCode HC);</p><p><b>  while(k)</b></p><p><b>  {</b></p

63、><p>  printf(" --------------------------------------------------------------------- \n");</p><p>  printf(" 歡迎使用編碼譯碼系統(tǒng)\n");</p><p>  printf(

64、" --------------------------------------------------------------------- \n");</p><p>  printf("請(qǐng)輸入獲得權(quán)值的方法,輸入1表示自己輸入每個(gè)節(jié)點(diǎn)的權(quán)值,輸入0表示將每個(gè)字符在輸入字符串中出現(xiàn)的次數(shù)作為其權(quán)值:");</p><p>  scanf(

65、"%d",&method);</p><p>  if(method==0) </p><p><b>  {</b></p><p>  printf("請(qǐng)輸入要編碼的字符串(請(qǐng)輸入小寫字母):");</p><p>  gets(getstr); //

66、</p><p>  scanf("%s",&getstr); //獲得輸入的字符串</p><p>  num=counttotal(getstr,quan,str);//統(tǒng)計(jì)字符串中含有字符種類個(gè)數(shù)</p><p>  creathafumantree(HT,HC,quan,str); //根據(jù)字符權(quán)值構(gòu)建哈夫曼樹&

67、lt;/p><p>  Hafumanencode(HT,HC);//根據(jù)哈夫曼樹確定每個(gè)字符的code</p><p>  codenum(HC,getstr);//將字符串譯碼存入文件夾</p><p>  s=decode(HC);//將暗文解碼</p><p>  printf("解密為:\n"

68、);</p><p>  printf("%s\n",s);</p><p>  printf("是否想繼續(xù)編碼、解碼,是輸入1回車,否輸入0回車:");</p><p>  scanf("%d",&k);</p><p><b>  }</b><

69、/p><p>  else if(method==1)</p><p><b>  {</b></p><p>  total=1; //每次都要將其清零,以達(dá)到控制循環(huán)的效果</p><p>  printf("請(qǐng)輸入要編碼字符所出現(xiàn)的種類數(shù):");</p><p>  s

70、canf("%d",&length);</p><p>  for(count=1;count<=length;count++)</p><p><b>  {</b></p><p>  printf("請(qǐng)輸入第%d個(gè)字符和該字符的權(quán)值(中間留一個(gè)空格):",count);</p&g

71、t;<p>  cin>>str[total]>>quan[total];</p><p><b>  total++;</b></p><p><b>  }</b></p><p>  num=length;</p><p>  creathafumantr

72、ee(HT,HC,quan,str);//根據(jù)字符權(quán)值構(gòu)建哈夫曼樹</p><p>  Hafumanencode(HT,HC);//根據(jù)哈夫曼樹確定每個(gè)字符的code</p><p>  printf("請(qǐng)輸入要編碼的字符串:");</p><p>  cin>>getstr;</p><p>  co

73、denum(HC,getstr);//將字符串譯碼存入文件夾</p><p>  s=decode(HC);//將暗文解碼</p><p>  printf("解密為:\n");</p><p>  printf("%s\n",s);</p><p>  printf(&q

74、uot;是否想繼續(xù)編碼、解碼,是輸入1回車,否輸入0回車:\n");</p><p>  scanf("%d",&k);</p><p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b&

75、gt;</p><p>  printf("錯(cuò)誤輸入!\n");</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  system(

76、"pause");</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  int counttotal(char *s,int quan[],char str[])//計(jì)算字符串中字符權(quán)值</p><p><

77、;b>  {</b></p><p><b>  char *p;</b></p><p>  int i,j,k,quantemp[27];</p><p>  for(i=1;i<27;i++)//將所有字符的權(quán)值賦成0</p><p>  quantemp[i]=0;<

78、/p><p>  for(p=s;*p!='\0';p++)//判斷字符串是否結(jié)束</p><p>  if(*p>='a'&&*p<='z')//判斷字符是否為26字母</p><p><b>  {</b></p><p&g

79、t;  k=*p-96;//看是26個(gè)字符中的哪個(gè)字符</p><p>  quantemp[k]++;//字符權(quán)值加1</p><p><b>  }</b></p><p><b>  j=0;</b></p><p>  for(i=1,j=0;i<27;i++)&

80、lt;/p><p><b>  {</b></p><p>  if(quantemp[i]!=0)</p><p><b>  {</b></p><p>  j++;//用于統(tǒng)計(jì)字符種類個(gè)數(shù)</p><p>  str[j]=i+96;//str按字母表順序存

81、儲(chǔ)出現(xiàn)過的字符</p><p>  quan[j]=quantemp[i];</p><p><b>  }</b></p><p><b>  }</b></p><p>  return j; //返回該數(shù)據(jù)給num賦值</p><p>&l

82、t;b>  }</b></p><p>  void selectmin(HafumanTree HT,int k,int *s1,int*s2)//選擇權(quán)值最小的兩個(gè)</p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>

83、  int min=9999;//聲明一個(gè)int類型的數(shù)值min,賦個(gè)較大的輸給它</p><p>  for(i=1;i<=k;i++)//選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)(且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn))</p><p><b>  {</b></p><p>  if((HT[i].weight<min)&&(HT[i].

84、parent==0))</p><p><b>  {</b></p><p><b>  j=i;</b></p><p>  min=HT[i].weight;</p><p><b>  }</b></p><p><b>  }<

85、/b></p><p><b>  *s1=j;</b></p><p><b>  min=9999;</b></p><p>  for(i=1;i<=k;i++)</p><p><b>  {</b></p><p>  if((HT

86、[i].weight<min)&&(HT[i].parent==0)&&(i!=*s1))</p><p>  //選擇權(quán)值最小的一個(gè)節(jié)點(diǎn)(且該節(jié)點(diǎn)無(wú)父節(jié)點(diǎn))</p><p><b>  {</b></p><p><b>  j=i;</b></p><p&

87、gt;  min=HT[i].weight;</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  *s2=j;</b></p><p><b>  }</b></p><p>

88、<b>  //構(gòu)建哈夫曼樹</b></p><p>  void creathafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]) </p><p><b>  {</b></p><p>  int i,s1,s2;</p>&l

89、t;p>  for(i=1;i<2*num-1;i++)//將所有的節(jié)點(diǎn)賦空</p><p><b>  {</b></p><p>  HT[i].lchild=0;HT[i].rchild=0;</p><p>  HT[i].parent=0;HT[i].weight=0;</p><p>

90、;<b>  }</b></p><p>  for(i=1;i<=num;i++)//將num個(gè)字符的權(quán)值賦給num葉節(jié)點(diǎn)</p><p><b>  {</b></p><p>  HT[i].weight=quan[i];</p><p><b>  }</b&

91、gt;</p><p>  for(i=1;i<=num;i++)//將num個(gè)字符賦給codenode</p><p><b>  {</b></p><p>  HC[i].ch=str[i];</p><p><b>  }</b></p><p>&

92、lt;b>  i=1;</b></p><p>  while(i<=num)</p><p><b>  { </b></p><p>  printf("字符為%c,權(quán)值為%d\n",HC[i].ch,quan[i]);</p><p><b>  i++;<

93、;/b></p><p>  }//輸出每個(gè)字符的及其權(quán)值</p><p>  for(i=num+1;i<=2*num-1;i++)</p><p><b>  {</b></p><p>  selectmin(HT,i-1,&s1,&s2);</p><p>

94、;  //選擇兩個(gè)權(quán)值最小的葉節(jié)點(diǎn),分別存放于s1和s2</p><p>  HT[s1].parent=i;</p><p>  HT[s2].parent=i;//兩個(gè)節(jié)點(diǎn)指向同一父節(jié)點(diǎn)</p><p>  HT[i].lchild=s1;HT[i].rchild=s2;</p><p>  HT[i].weight=HT[s1

95、].weight+HT[s2].weight;</p><p>  //父節(jié)點(diǎn)的權(quán)值為子節(jié)點(diǎn)相加(父節(jié)點(diǎn)繼續(xù)放入選擇區(qū))</p><p><b>  }</b></p><p><b>  }</b></p><p>  void Hafumanencode(HafumanTree HT,H

96、afumanCode HC)</p><p><b>  {</b></p><p>  int c,p,i;</p><p>  char cd[n];//臨時(shí)數(shù)組用于記錄字符在哈夫曼樹的位置</p><p>  int start;</p><p>  cd[num]='\0

97、';//給cd賦個(gè)結(jié)束符</p><p>  for(i=1;i<=num;i++)</p><p><b>  {</b></p><p>  start=num;</p><p><b>  c=i;</b></p><p>  while(

98、(p=HT[c].parent)>0)</p><p>  //根據(jù)節(jié)點(diǎn)是其父節(jié)點(diǎn)的左右子來(lái)記錄它的位置</p><p><b>  {</b></p><p>  cd[--start]=(HT[p].lchild==c)?'0':'1';</p><p>  c=p;

99、//將父節(jié)點(diǎn)轉(zhuǎn)為子節(jié)點(diǎn)</p><p><b>  }</b></p><p>  strcpy(HC[i].bits,&cd[start]);//將得到的0、1字串存入結(jié)構(gòu)體HC</p><p>  printf("%c:%s\n",HC[i].ch,HC[i].bits);</p><

100、;p>  HC[i].len=num-start;//求每個(gè)字符0、1編碼長(zhǎng)度</p><p><b>  }</b></p><p><b>  }</b></p><p>  //根據(jù)哈夫曼樹確定每個(gè)字符的0、1代碼code</p><p>  void codenum(Hafu

101、manCode HC,char *str) </p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  FILE *fp;//聲明一個(gè)文件夾指針</p><p>  fp=fopen("code.txt",

102、"w");//打開文件夾codefile</p><p>  printf("密文為:\n");</p><p>  while(*str)//字符串未結(jié)束時(shí)</p><p><b>  {</b></p><p>  for(i=1;i<=n

103、um;i++)</p><p><b>  {</b></p><p>  if(HC[i].ch==*str)//判斷字符是否在Codenode中存在</p><p><b>  {</b></p><p>  for(j=0;j<HC[i].len;j++)</p&

104、gt;<p>  //將codenode中該字符的1、0代碼存入文件夾</p><p><b>  {</b></p><p>  fputc(HC[i].bits[j],fp);</p><p><b>  }</b></p><p>  printf("%s",

105、HC[i].bits);</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  str++;//字符后移</p><p><b>

106、  }</b></p><p>  printf("\n");</p><p>  printf("編碼寫入文件--code.txt成功!!!"); //提示寫入文件成功</p><p>  printf("\n");</p><p>  fclose(fp

107、);</p><p><b>  }</b></p><p>  char *decode(HafumanCode HC)</p><p><b>  {</b></p><p><b>  FILE *fp;</b></p><p>  char te

108、mpstr[9999];</p><p><b>  char *p;</b></p><p>  static char cd[n+1];//char型數(shù)組用于存放從文件夾中讀取的1、0代碼</p><p>  int i,j,k=0,end;</p><p>  fp=fopen("code.txt&q

109、uot;,"r");</p><p>  while(!feof(fp))//當(dāng)文件夾讀取沒有結(jié)束</p><p><b>  {</b></p><p>  end=0;//判讀一個(gè)字符是否譯碼結(jié)束</p><p>  for(i=0;(i<num)&

110、&(end==0)&&(!feof(fp));i++)</p><p>  //當(dāng)一個(gè)字符未譯完并且文件未讀取結(jié)束</p><p><b>  { </b></p><p>  cd[i]=' ';cd[i+1]='\0';//讓cd[]賦成空格</p><

111、;p>  cd[i]=fgetc(fp);//讀取文件夾中的一個(gè)字符</p><p>  for(j=1;j<=num;j++)</p><p><b>  {</b></p><p>  if(strcmp(HC[j].bits,cd)==0)</p><p>  //看cd

112、[]的字符串是否等于Codenode中的某個(gè)密文</p><p><b>  {</b></p><p>  tempstr[k]=HC[j].ch;</p><p><b>  end=1;</b></p><p>  printf("=%s=",HC[j].bits);<

113、;/p><p><b>  k++;</b></p><p><b>  break;</b></p><p><b>  }</b></p><p>  //將譯出的字符賦給臨時(shí)字符串tempstr[],標(biāo)記一個(gè)字符譯碼結(jié)束jsjs賦1,跳出循環(huán)</p><

114、;p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  printf("\n");</p><p>  tempstr[k]='\0';//賦給臨

溫馨提示

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

評(píng)論

0/150

提交評(píng)論