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

下載本文檔

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

文檔簡介

1、<p>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p><b>  院、 系:</b></p><p><b>  學(xué)科專業(yè):</b></p><p><b>  姓 名:</b></p><p><b>  學(xué) 號(hào):</b></p

2、><p><b>  指導(dǎo)教師:</b></p><p><b>  1課程設(shè)計(jì)的題目-</b></p><p>  ——赫夫曼編碼/譯碼器</p><p><b>  1. 問題描述</b></p><p>  利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率

3、,縮短信息傳輸時(shí)間,降低傳輸成本。這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)赫夫曼碼的編/譯碼系統(tǒng)。</p><p><b>  基本要求</b></p><p>  一個(gè)完整的系統(tǒng)應(yīng)具有以下功能:</p>

4、<p>  (1) I:初始化(Initialization)。從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值,建立赫夫曼樹,并將它存于文件hfmTree中。</p><p>  (2) E:編碼(Encoding)。利用已建好的赫夫曼樹(如不在內(nèi)存,則從文件hfmTree中讀入),對(duì)文件ToBeTran中的正文進(jìn)行編碼,然后將結(jié)果存入文件CodeFile中。</p><p>

5、;  (3) D:譯碼(Decoding)。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼,結(jié)果存入文件Textfile中。</p><p><b>  以下為選做:</b></p><p>  (4) P:印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上,每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。<

6、/p><p>  (5) T:印赫夫曼樹(Tree printing)。將已在內(nèi)存中的赫夫曼樹以直觀的方式(比如樹)顯示在終端上,同時(shí)將此字符形式的赫夫曼樹寫入文件TreePrint 中。</p><p><b>  測試要求</b></p><p>  (1) 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符,其頻率分別為0.05,0.29,0.07,

7、0.08,0.14,0.23,0.03,0.11,試設(shè)計(jì)赫夫曼編碼。</p><p>  (2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹,并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼:“THIS PROGRAME IS MY FAVORITE”。</p><p><b>  實(shí)現(xiàn)提示</b></p><p>  (1) 編碼結(jié)果以文本方式存儲(chǔ)在

8、文件Codefile中。</p><p>  (2) 用戶界面可以設(shè)計(jì)為“菜單”方式:顯示上述功能符號(hào),再加上“Q”,表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單,直至某次用戶選擇了“Q”為止。</p><p>  (3) 在程序的一次執(zhí)行過程中,第一次執(zhí)行I,D或C命令之后,赫夫曼樹已經(jīng)在內(nèi)存了,不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令,因?yàn)槲募fmTre

9、e可能早已建好。</p><p>  2課程設(shè)計(jì)的目的(設(shè)計(jì)要解決的問題)</p><p>  數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu),以及對(duì)數(shù)據(jù)的各種操作。因此,主要有三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu);數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu);對(duì)數(shù)據(jù)的操作(或算法)。通常,算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu),算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式,其目的是為了提高算法的效

10、率,它通常與一組算法的集合相對(duì)應(yīng),通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。</p><p>  在當(dāng)今信息時(shí)代,信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑,在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報(bào)名等,所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上,現(xiàn)實(shí)世界中的實(shí)體經(jīng)過抽象以后,就可以成為計(jì)算機(jī)上所處理的數(shù)據(jù)。</p><p> 

11、 數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程,它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ),廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>  學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思

12、維能力,促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的:</p><p>  了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法,具備初步的獨(dú)立分析和設(shè)計(jì)能力;</p><p>  初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能;</p><p>  提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力;</p>

13、<p>  訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā),培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>  3概要設(shè)計(jì)(函數(shù)劃分、總體設(shè)計(jì))</p><p>  問題分析哈夫曼樹的定義</p><p>  1.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為:</p><p>  typedef struct{

14、 //赫夫曼樹的結(jié)構(gòu)體</p><p><b>  char ch;</b></p><p>  int weight; //權(quán)值</p><p>  int parent,lchild,rchild;</p><p>  }htnode,*hfmtree;</p><p&g

15、t;  2)所實(shí)現(xiàn)的功能函數(shù)如下</p><p>  1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹,處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù),按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select()函數(shù)。</p><p>  2、void Select(hfmtree &HT

16、,int a,int *p1,int *p2) //Select函數(shù),選出HT樹到a為止,權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)</p><p>  2、 int main()</p><p>  主函數(shù): 利用已建好的哈夫曼樹(如不在內(nèi)存,則從文件hfmtree.txt中讀入)</p><p>  對(duì)文件中的正文進(jìn)行編碼,然后將結(jié)果存入文件code

17、file.txt中。如果正文中沒有要編碼的字符,則鍵盤讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容,將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。</p><p>  3、Encoding </p><p>  編碼功能:對(duì)輸入字符進(jìn)行編碼</p><p>  4、Decoding</p><p>  譯碼功能:

18、利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼,結(jié)果存入文件textfile.dat 中。</p><p>  Print() 打印功能函數(shù):輸出哈夫曼樹,字符,權(quán)值,以及它對(duì)應(yīng)的編碼。</p><p>  5.主函數(shù)的簡要說明,主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語句,讓用戶挑選所實(shí)現(xiàn)的功能。</p><p>  使用鏈樹存儲(chǔ),然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù),

19、排序函數(shù),建立哈夫曼函數(shù),編碼函數(shù),譯碼函數(shù)來實(shí)現(xiàn)功能。</p><p>  4詳細(xì)設(shè)計(jì)(流程圖、程序)</p><p><b>  程序說明</b></p><p>  .哈夫曼編碼/譯碼器源代碼</p><p>  #include<iostream.h></p><p>  #i

20、nclude<stdio.h></p><p>  #include<stdlib.h></p><p>  #include<string.h></p><p>  #include<fstream.h></p><p>  typedef struct{ //赫夫曼樹的結(jié)構(gòu)體

21、</p><p><b>  char ch;</b></p><p>  int weight; //權(quán)值</p><p>  int parent,lchild,rchild;</p><p>  }htnode,*hfmtree;</p><p>  typedef

22、 char **hfmcode;</p><p>  void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù),選出HT樹到a為止,權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)</p><p><b>  {</b></p><p>  int i,j,x,y;</p>&

23、lt;p>  for(j=1;j<=a;++j){</p><p>  if(HT[j].parent==0){</p><p><b>  x=j;</b></p><p><b>  break;</b></p><p><b>  }</b></p>

24、;<p><b>  }</b></p><p>  for(i=j+1;i<=a;++i){</p><p>  if(HT[i].weight<HT[x].weight&&HT[i].parent==0){</p><p>  x=i; //選出最小的節(jié)點(diǎn)</

25、p><p><b>  }</b></p><p><b>  }</b></p><p>  for(j=1;j<=a;++j){</p><p>  if(HT[j].parent==0&&x!=j)</p><p><b>  {</

26、b></p><p><b>  y=j;</b></p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  for(i=j+1;i&

27、lt;=a;++i)</p><p><b>  {</b></p><p>  if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)</p><p><b>  {</b></p><p>  y=i;

28、 //選出次小的節(jié)點(diǎn)</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  if(x>y){</b></p><p><b>  *p1=y;</b></p>

29、;<p><b>  *p2=x;</b></p><p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b></p><p><b>  *p1=x;</b>&

30、lt;/p><p><b>  *p2=y;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建赫夫曼樹HT

31、,并求出n個(gè)字符的赫夫曼編碼HC</p><p><b>  {</b></p><p>  int i,start,c,f,m,w;</p><p>  int p1,p2;</p><p>  char *cd,z;</p><p><b>  if(n<=1){</b&

32、gt;</p><p><b>  return;</b></p><p><b>  }</b></p><p><b>  m=2*n-1;</b></p><p>  HT=(hfmtree)malloc((m+1)*sizeof(htnode));</p>

33、<p>  for(i=1;i<=n;++i) //初始化n個(gè)葉子結(jié)點(diǎn)</p><p><b>  {</b></p><p>  printf("請(qǐng)輸入第%d字符信息和權(quán)值:",i);</p><p>  scanf("%c%d",&z,&w);&

34、lt;/p><p>  while(getchar()!='\n')</p><p><b>  {</b></p><p><b>  continue;</b></p><p><b>  }</b></p><p>  HT[i].ch

35、=z;</p><p>  HT[i].weight=w;</p><p>  HT[i].parent=0;</p><p>  HT[i].lchild=0;</p><p>  HT[i].rchild=0;</p><p><b>  }</b></p><p> 

36、 for(;i<=m;++i) //初始化其余的結(jié)點(diǎn)</p><p><b>  {</b></p><p>  HT[i].ch='0';</p><p>  HT[i].weight=0;</p><p>  HT[i].parent=0;</p><p>

37、  HT[i].lchild=0;</p><p>  HT[i].rchild=0;</p><p><b>  }</b></p><p>  for(i=n+1;i<=m;++i) //建立赫夫曼樹</p><p><b>  {</b></p><p&

38、gt;  Select(HT,i-1,&p1,&p2);</p><p>  HT[p1].parent=i;HT[p2].parent=i;</p><p>  HT[i].lchild=p1;HT[i].rchild=p2;</p><p>  HT[i].weight=HT[p1].weight+HT[p2].weight;</p>

39、<p><b>  }</b></p><p>  HC=(hfmcode)malloc((n+1)*sizeof(char *));</p><p>  cd=(char *)malloc(n*sizeof(char));</p><p>  cd[n-1]='\0';</p><p> 

40、 for(i=1;i<=n;++i) //給n個(gè)字符編碼</p><p><b>  {</b></p><p>  start=n-1;</p><p>  for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)</p><p><b>

41、  {</b></p><p>  if(HT[f].lchild==c)</p><p><b>  {</b></p><p>  cd[--start]='0';</p><p><b>  }</b></p><p><b>  

42、else</b></p><p><b>  {</b></p><p>  cd[--start]='1';</p><p><b>  }</b></p><p><b>  }</b></p><p>  HC[i]=(

43、char*)malloc((n-start)*sizeof(char));</p><p>  strcpy(HC[i],&cd[start]);</p><p><b>  }</b></p><p><b>  free(cd);</b></p><p><b>  }<

44、/b></p><p>  int main(){</p><p>  char code[100],h[100],hl[100];</p><p>  int n,i,j,k,l;</p><p>  ifstream input_file; //文件輸入輸出流</p><p>  ofstream ou

45、tput_file;</p><p>  char choice,str[100];</p><p>  hfmtree HT;</p><p>  hfmcode HC;</p><p>  cout<<"\n";</p><p>  cout<<"

46、 "<<"計(jì)算機(jī)(3)班"<<" "<<"Q07620307"<<" "<<"XXX\n";</p><p>  while(choice!='Q'&&choice!='q')

47、 //當(dāng)choice的值不為q且不為Q時(shí)循環(huán)</p><p><b>  {</b></p><p>  cout<<" "<<"*************************赫夫曼編碼/譯碼器*************************\n";</p&

48、gt;<p>  cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" &quo

49、t;<<"Q.Exit\n";</p><p>  cout<<"請(qǐng)輸入您要操作的步驟:";</p><p>  cin>>choice;</p><p>  if(choice=='I'||choice=='i') //初始化赫夫曼

50、樹</p><p><b>  {</b></p><p>  cout<<"請(qǐng)輸入字符個(gè)數(shù):";</p><p><b>  cin>>n;</b></p><p>  hfmcoding(HT,HC,n);</p><p>  

51、for(i=1;i<=n;++i)</p><p><b>  {</b></p><p>  cout<<HT[i].ch<<":"<<HC[i]<<endl;</p><p><b>  }</b></p><p>  o

52、utput_file.open("hfmTree.txt");</p><p>  if(!output_file){</p><p>  cout<<"can't oen file!"<<endl;</p><p><b>  return 1;</b></p>

53、;<p><b>  }</b></p><p>  for(i=1;i<=n;i++)</p><p><b>  {</b></p><p>  output_file<<"("<<HT[i].ch<<HC[i]<<")&

54、quot;;</p><p><b>  }</b></p><p>  output_file.close();</p><p>  cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢,并且已經(jīng)放入hfmTree.txt文件中!"<<endl;</p><p><b>  }<

55、;/b></p><p>  else if(choice=='E'||choice=='e') //進(jìn)行編碼,并將字符放入ToBeTran.txt,碼值放入CodeFile.txt中</p><p><b>  {</b></p><p>  printf("請(qǐng)輸入字符:&q

56、uot;);</p><p>  gets(str);</p><p>  output_file.open("ToBeTran.txt");</p><p>  if(!output_file)</p><p><b>  {</b></p><p>  cout<&l

57、t;"can't oen file!"<<endl;</p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  output_file<<str<<endl;</p><p> 

58、 output_file.close();</p><p>  output_file.open("CodeFile.txt");</p><p>  if(!output_file){</p><p>  cout<<"can't oen file!"<<endl;</p>&l

59、t;p><b>  return 1;</b></p><p><b>  }</b></p><p>  for(i=0;i<strlen(str);i++){</p><p>  for(j=0;j<=n;++j)</p><p><b>  {</b>&

60、lt;/p><p>  if(HT[j].ch==str[i])</p><p><b>  {</b></p><p>  output_file<<HC[j];</p><p><b>  break;</b></p><p><b>  }</b

61、></p><p><b>  }</b></p><p><b>  }</b></p><p>  output_file.close();</p><p>  cout<<"\n";</p><p>  cout<<&q

62、uot;編碼完畢,并且已經(jīng)存入CodeFile.txt文件!\n";</p><p>  input_file.open("CodeFile.txt"); //從CodeFile.txt中讀入編碼,輸出在終端</p><p>  if(!input_file)</p><p><b>  {</b>

63、</p><p>  cout<<"can't oen file!"<<endl;</p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  input_file>>code;&

64、lt;/p><p>  cout<<"編碼碼值為:"<<code<<endl;</p><p>  input_file.close();</p><p><b>  }</b></p><p>  else if(choice=='D'||choice

65、=='d') //讀入CodeFile.txt中的編碼進(jìn)行譯碼,將譯出來的字符放入Textfile.txt中</p><p><b>  {</b></p><p>  input_file.open("CodeFile.txt");</p><p>  if(!input_file){</p&

66、gt;<p>  cout<<"can't oen file!"<<endl;</p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  input_file>>h;</p>

67、<p>  input_file.close();</p><p>  output_file.open("Textfile.txt");</p><p>  if(!output_file)</p><p><b>  {</b></p><p>  cout<<"

68、can't oen file!"<<endl;</p><p><b>  return 1;</b></p><p><b>  }</b></p><p><b>  k=0;</b></p><p>  while(h[k]!='\0

69、') //先用編碼中的前幾個(gè)和字符的編碼相比較,然后往后移</p><p><b>  {</b></p><p>  for(i=1;i<=n;i++){</p><p><b>  l=k;</b></p><p>  for(j=0;j<strlen(H

70、C[i]);j++,l++){</p><p>  hl[j]=h[l];</p><p><b>  }</b></p><p>  hl[j]='\0';</p><p>  if(strcmp(HC[i],hl)==0)</p><p><b>  {</b&

71、gt;</p><p>  output_file<<HT[i].ch;</p><p>  k=k+strlen(HC[i]);</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }&

72、lt;/b></p><p><b>  }</b></p><p>  output_file.close();</p><p>  input_file.open("Textfile.txt");</p><p>  if(!input_file){</p><p>

73、  cout<<"can't oen file!"<<endl;</p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  input_file>>h; </p><p>  c

74、out<<h<<endl;</p><p>  input_file.close();</p><p>  cout<<"譯碼結(jié)束,字符已經(jīng)存入Textfile.txt文件中!"<<endl;</p><p><b>  }</b></p><p>  

75、else if(choice=='Q'||choice=='q') //退出程序</p><p><b>  { </b></p><p><b>  exit(0);</b></p><p><b>  }</b></p><

76、p>  else //如果選了選項(xiàng)之外的就讓用戶重新選擇</p><p><b>  {</b></p><p>  cout<<"您沒有輸入正確的步驟,請(qǐng)重新輸入!"<<endl;</p><p><b>  }</b></p>

77、<p>  cout<<endl;</p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  }</b></p><p><b>  5調(diào)試結(jié)果</b></p&g

78、t;<p><b>  編碼</b></p><p><b>  、譯碼</b></p><p><b>  、退出</b></p><p><b>  6課程設(shè)計(jì)總結(jié)</b></p><p>  通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì),我學(xué)習(xí)了很多在上

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(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)論