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

下載本文檔

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

文檔簡(jiǎn)介

1、<p><b>  課程設(shè)計(jì)報(bào)告</b></p><p><b>  2012年12月</b></p><p> 課程名稱:數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p> 課程設(shè)計(jì)題目:哈夫曼編碼</p><p> 系:數(shù)學(xué)與計(jì)算科學(xué)系</p><p> 專 業(yè):信息與計(jì)

2、算科學(xué)</p><p> 年級(jí)、班:</p><p> 姓 名:</p><p> 學(xué) 號(hào):</p><p> 指導(dǎo)教師:</p><p> 職 稱:</p><p><b>  目錄</b></p><p>  問題描述 ----

3、----------------------------------------------------2</p><p>  基本要求 --------------------------------------------------------2</p><p>  測(cè)試結(jié)果 ------------------------------------------------------

4、--2</p><p>  算法思想 --------------------------------------------------------2</p><p>  模塊劃分 --------------------------------------------------------2</p><p>  數(shù)據(jù)結(jié)構(gòu) -------------------

5、-------------------------------------2</p><p>  源程序 --------------------------------------------------------3</p><p>  測(cè)試情況 --------------------------------------------------------14</p>

6、<p>  設(shè)計(jì)總結(jié) --------------------------------------------------------15</p><p>  參考資料 -------------------------------------------------------15</p><p><b>  1 問題描述</b></p>

7、<p>  利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率,縮短信息傳輸時(shí)間,降低傳輸成本,試設(shè)計(jì)一個(gè)哈夫曼編碼系統(tǒng)。對(duì)所給的報(bào)文可以進(jìn)行編碼,并進(jìn)行譯碼。</p><p><b>  2 基本要求</b></p><p>  從鍵盤輸入一段報(bào)文(如"what did you do that made you so happy")或從文檔

8、中讀取,輸出這段報(bào)文的哈夫曼編碼。</p><p><b>  3 測(cè)試數(shù)據(jù)</b></p><p>  what did you do that made you so happy</p><p><b>  4 算法分析</b></p><p> ?。簭奈募凶x取data.txt中的數(shù)據(jù)并賦值給

9、ch數(shù)組(保存文件中的所有內(nèi)容)后面的程序只對(duì)數(shù)組進(jìn)行操作。</p><p>  :對(duì)數(shù)組ch[]進(jìn)行操作,統(tǒng)計(jì)出報(bào)文中出現(xiàn)的字符種類存放在m[i].ch中,并比較統(tǒng)計(jì)出每個(gè)字符出現(xiàn)的頻數(shù)作為權(quán)值存放在m[i].weight中。</p><p> ?。豪脵?quán)值創(chuàng)建哈夫曼樹。</p><p>  :先序遍歷輸出哈夫曼樹,利用哈夫曼樹輸出哈夫曼編碼,Code d[i]中

10、存儲(chǔ)關(guān)于字符哈夫曼編碼的數(shù)據(jù)。d[i].ch存放字符,d[i].code存放字符的哈夫曼編碼。</p><p> ?。簩?duì)數(shù)組ch[]跟d[]進(jìn)行比較輸出整篇報(bào)文的哈夫曼編碼,并以輸出的形式寫入到文件date1中。</p><p>  :調(diào)用文件date1根據(jù)哈夫曼編碼譯出文件的內(nèi)容,把文件的內(nèi)容賦值給字符串,對(duì)字符串進(jìn)行操作。把str和d[i].code進(jìn)行比較輸出d[i].ch.<

11、/p><p><b>  5 模塊劃分</b></p><p> ?。篐uffmanTree CreateHuffman(Element *m,int size1);//創(chuàng)建哈夫曼樹</p><p> ?。篐uffmanTree UnitHuffmanTree(HuffmanTree &T1,HuffmanTree &T2); //

12、合并兩棵哈夫曼樹</p><p> ?。篿nt tongji(Element *m,char *ch);//統(tǒng)計(jì)權(quán)值</p><p>  :void GetCode(HuffmanTree T,Code *m,int &s,string code); //獲取各字符的編碼</p><p> ?。簐oid bianma(char ch[],Code *m,in

13、t size1);//對(duì)報(bào)文進(jìn)行哈夫曼編碼</p><p> ?。簐oid yima(Code *m,int size1);//對(duì)哈夫曼編碼譯出報(bào)文內(nèi)容</p><p><b>  6 數(shù)據(jù)結(jié)構(gòu)</b></p><p>  struct Code //編碼類型</p><p><b>  {</b&g

14、t;</p><p>  char ch; //字符</p><p>  string code; //編碼</p><p><b>  };</b></p><p>  typedef BiTree HuffmanTree; //定義哈夫曼樹類型</p><p>  struct

15、BiTNode</p><p><b>  {</b></p><p>  TElemType data;</p><p>  BiTNode *lchild,*rchild;</p><p><b>  };</b></p><p>  typedef BiTNode *B

16、iTree;//定義哈夫曼樹的結(jié)構(gòu)類型</p><p>  struct Element</p><p><b>  {</b></p><p><b>  char ch;</b></p><p>  double weight;</p><p><b>  };

17、</b></p><p>  typedef Element TElemType;//定義二叉樹的存儲(chǔ)類型</p><p>  struct BiTNode</p><p><b>  {</b></p><p>  TElemType data;</p><p>  BiTNode

18、*lchild,*rchild;</p><p><b>  };</b></p><p>  typedef BiTNode *BiTree;//定義二叉樹的類型</p><p>  struct LNode</p><p><b>  {</b></p><p>  El

19、emType data;</p><p>  LNode* next;</p><p><b>  };</b></p><p>  typedef LNode* LinkList;//定義鏈表的類型</p><p><b>  7源程序</b></p><p><b&

20、gt;  mian.cpp</b></p><p>  #include <iostream></p><p>  #include<fstream></p><p>  #include<cstdlib></p><p>  #include "huffman.h"<

21、/p><p>  #include"string.h"</p><p>  using namespace std;</p><p>  int main()</p><p><b>  {</b></p><p>  const int n=200;</p><

22、;p>  char ch[n]={0};</p><p>  char filename[10];</p><p>  Element m[n];</p><p>  cout<<"輸入數(shù)據(jù)文件名:";</p><p>  cin>>filename;</p><p>

23、  ifstream infile;</p><p>  infile.open(filename);//打開文件</p><p>  if(!infile)</p><p><b>  {</b></p><p>  cout<<"錯(cuò)誤:此文件不存在!"<<endl;<

24、/p><p><b>  }</b></p><p>  infile.seekg(0,ios::end);</p><p>  int size=infile.tellg();//獲取文件的大小</p><p>  cout<<"文件大小為:"<<size<<endl

25、;</p><p>  infile.seekg(0,ios::beg);</p><p>  for(int i=0; i<size; ++i)</p><p><b>  {</b></p><p>  infile.get(ch[i]);//把數(shù)據(jù)賦值ch[i]給數(shù)組</p><p>

26、<b>  }</b></p><p>  cout<<"此文件的內(nèi)容為"<<endl;</p><p>  for(int i=0; i<size; i++)//輸出文件的內(nèi)容</p><p><b>  {</b></p><p>  cout&

27、lt;<ch[i];</p><p><b>  }</b></p><p>  cout<<endl;</p><p>  int size1;</p><p>  cout<<"字符出現(xiàn)的頻率作為字符的權(quán)重:"<<endl;</p><

28、p>  size1=tongji(m,ch,size);//獲取m[i]的大小,并統(tǒng)計(jì)出出現(xiàn)的字符,并 </p><p>  把每個(gè)字符出現(xiàn)的頻數(shù)作為字符的權(quán)重</p><p>  BiTree T=CreateHuffman(m,size1);//根據(jù)權(quán)重創(chuàng)建哈夫曼樹</p><p>  cout<<"創(chuàng)建huffman樹并先序遍歷h

29、uffmanbitree"<<endl;</p><p>  preOrderTraverse(T,Print);//前序遍歷輸出哈夫曼樹</p><p>  cout<<endl;</p><p>  Code d[size1]; //定義字符的編碼數(shù)組</p><p>  string code=&quo

30、t;";</p><p>  int s=0; //已編碼的字符計(jì)數(shù)</p><p>  GetCode(T,d,s,code);//獲取每個(gè)字符的哈夫曼編碼</p><p>  cout<<"字符的huffman編碼為:"<<endl;</p><p>  for(int i=0; i

31、<size1; i++)</p><p>  cout<<"字符:"<<d[i].ch<<" "<<"編碼:"<<d[i].code<<endl;</p><p>  bianma(ch,d,size1,size);//對(duì)輸入的文件內(nèi)容進(jìn)行編碼<

32、;/p><p>  cout<<endl;</p><p>  cout<<"根據(jù)huffman編碼議譯出內(nèi)容為:" ;</p><p>  yima(d, size1);//對(duì)哈夫曼編碼進(jìn)行譯碼</p><p><b>  return 0;</b></p><

33、;p><b>  }</b></p><p><b>  Haffman.h</b></p><p>  #ifndef HUFFMAN_H_INCLUDED</p><p>  #define HUFFMAN_H_INCLUDED</p><p>  #include "bitre

34、e.h"</p><p>  #include "linklist.h"</p><p>  struct Code //編碼類型</p><p><b>  {</b></p><p>  char ch; //字符</p><p>  string c

35、ode; //編碼</p><p><b>  };</b></p><p>  typedef BiTree HuffmanTree; //定義哈夫曼樹類型</p><p>  HuffmanTree UnitHuffmanTree(HuffmanTree &T1,HuffmanTree &T2); //合并兩棵哈夫曼樹&

36、lt;/p><p>  HuffmanTree CreateHuffman(Element *m,int size1); //創(chuàng)建哈夫曼樹</p><p>  int compare(ElemType e1,ElemType e2); //查找插入點(diǎn)的比較函數(shù)</p><p>  void Print(TElemType e); //輸出二叉樹結(jié)點(diǎn)字符</p&

37、gt;<p>  void GetCode(HuffmanTree T,Code *m,int &s,string code); //獲取各字符的編碼</p><p>  int tongji(Element *m,char *ch,int size);//統(tǒng)計(jì)出現(xiàn)的字符,并統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻數(shù)</p><p>  void bianma(char ch[],Cod

38、e *m,int size1,int size);//對(duì)文件中的內(nèi)容依據(jù)各字符的編碼進(jìn)行譯碼</p><p>  void yima(Code *m,int size1);//依據(jù)哈夫曼編碼進(jìn)行譯碼</p><p>  #endif // HUFFMAN_H_INCLUDED</p><p>  Huffman.cpp</p><p>  #

39、include "huffman.h"</p><p>  #include"string.h"</p><p>  #include<fstream></p><p>  void Print(TElemType e)</p><p><b>  {</b></

40、p><p>  cout<<e.ch;</p><p><b>  }</b></p><p>  HuffmanTree UnitHuffmanTree(HuffmanTree &T1,HuffmanTree &T2)</p><p><b>  {</b></p&g

41、t;<p>  HuffmanTree T=new BiTNode; //新樹根結(jié)點(diǎn)</p><p>  T->data.ch='#'; //非葉子結(jié)點(diǎn)</p><p>  T->data.weight=T1->data.weight+T2->data.weight;//根結(jié)點(diǎn)的權(quán)重</p><p>  T-&g

42、t;lchild=T1; //T1為左子樹</p><p>  T->rchild=T2; //T2為右子樹</p><p><b>  return T;</b></p><p><b>  }</b></p><p>  int compare(ElemType e1,ElemType

43、 e2)</p><p><b>  {</b></p><p>  if((e1->data.weight)>(e2->data.weight))</p><p><b>  return 1;</b></p><p><b>  else</b></

44、p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  HuffmanTree CreateHuffman(Element *m,int size1)</p><p><b>  {</b></p><p&

45、gt;  LinkList L; //定義存放哈夫曼樹的鏈表</p><p>  initList(L);</p><p>  for(int i=0; i<size1; i++) //依據(jù)n個(gè)字符及其權(quán)重,建n棵哈夫曼樹加入鏈表</p><p><b>  {</b></p><p>  HuffmanTre

46、e t=new BiTNode;</p><p>  t->data.ch=m[i].ch;</p><p>  t->data.weight=m[i].weight;</p><p>  t->lchild=NULL;</p><p>  t->rchild=NULL;</p><p>  O

47、rderInsert(L,t,compare);</p><p><b>  }</b></p><p>  for(int i=0; i<size1-1; i++) //合并n-1次</p><p><b>  {</b></p><p>  HuffmanTree t,t1,t2;<

48、/p><p>  t1=DelReturn(L,1);</p><p>  t2=DelReturn(L,1);</p><p>  t=UnitHuffmanTree(t1,t2);</p><p>  OrderInsert(L,t,compare);</p><p><b>  }</b><

49、;/p><p>  HuffmanTree T=DelReturn(L,1); //獲取鏈表中唯一的一棵哈夫曼樹</p><p><b>  return T;</b></p><p><b>  }</b></p><p>  void GetCode(HuffmanTree T,Code *m,in

50、t &s,string code)</p><p><b>  {</b></p><p>  if(T)// T不空</p><p><b>  {</b></p><p>  if(T->data.ch!='#')// 先訪問根結(jié)點(diǎn)</p><p

51、><b>  {</b></p><p>  m[s].ch=T->data.ch;</p><p>  m[s].code=code;</p><p>  s++; //已編碼的字符計(jì)數(shù)</p><p><b>  }</b></p><p>  GetCod

52、e(T->lchild,m,s,code+"0"); // 再先序遍歷左子樹</p><p>  GetCode(T->rchild,m,s,code+"1"); // 最后先序遍歷右子樹</p><p><b>  }</b></p><p><b>  }</b>&l

53、t;/p><p>  int tongji(Element *m,char ch[],int size)</p><p>  /*文件的內(nèi)容儲(chǔ)存在數(shù)組ch[]中,ch[]的長(zhǎng)度為size,統(tǒng)計(jì)出出現(xiàn)的字符存放在m[i].ch中,再把數(shù)組ch[]跟m[i].ch進(jìn)行比較得出每個(gè)字符出現(xiàn)的頻數(shù)存放在m[i].weight中,并返回結(jié)構(gòu)體數(shù)組m[]的長(zhǎng)度*/</p><p>

54、<b>  {</b></p><p>  int j=0,k=1;</p><p>  for(int i=0;i<size;i++)//給m[i]賦初值</p><p><b>  {</b></p><p>  m[i].ch=ch[0];</p><p>  m

55、[i].weight=0;</p><p><b>  }</b></p><p>  for(int i=0;i<size;i++)</p><p><b>  {</b></p><p>  int cunzai=0;</p><p>  for(j=0;j<

56、k;++j)</p><p><b>  {</b></p><p>  if(m[j].ch==ch[i])</p><p><b>  {</b></p><p>  m[j].weight++;</p><p><b>  cunzai=1;</b>

57、;</p><p><b>  }</b></p><p><b>  }</b></p><p>  if(cunzai==0)</p><p><b>  {</b></p><p>  m[k].ch=ch[i];</p><p

58、>  m[k].weight=1;</p><p><b>  k++;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  for(int i=0;i<k;++i)</p><p> 

59、 cout<<"字符:"<<m[i].ch<<" "<<"頻數(shù):"<<m[i].weight<<endl;//輸出內(nèi)容中出現(xiàn)的字符,以及出現(xiàn)的頻數(shù)</p><p><b>  return k;</b></p><p><b&g

60、t;  }</b></p><p>  void bianma(char ch[],Code *m,int size1,int size)</p><p>  /* ch[]中為文件的內(nèi)容,長(zhǎng)度為size,m[i]中是出現(xiàn)了的字符以及每個(gè)字符出現(xiàn)的頻數(shù),m[]的長(zhǎng)度為size1*/</p><p><b>  {</b></p

61、><p>  cout<<"報(bào)文的huffman編碼為:";</p><p>  ofstream outfile("date1");//創(chuàng)建一個(gè)文件data1</p><p>  if(!outfile)</p><p><b>  {</b></p>&l

62、t;p>  cerr<<"open date1 error!"<<endl;</p><p><b>  exit(1);</b></p><p><b>  }</b></p><p>  for(int i=0;i<size;i++)//比較得出報(bào)文的哈夫曼編碼,

63、并以輸出的方式寫入文件date1</p><p><b>  {</b></p><p>  for(int j=0;j<size1;j++)</p><p>  if(ch[i]==m[j].ch)</p><p><b>  {</b></p><p>  outf

64、ile<<m[j].code<<" ";</p><p>  cout<<m[j].code<<" ";</p><p><b>  }</b></p><p><b>  }</b></p><p><b

65、>  }</b></p><p>  void yima(Code *m,int size1)//對(duì)文件date1中的哈夫曼編碼進(jìn)行譯碼</p><p><b>  {</b></p><p>  string str;</p><p>  ifstream infile;</p><

66、;p>  infile.open("date1");</p><p>  if(!infile.eof()==0)</p><p><b>  {</b></p><p>  cout<<"錯(cuò)誤:此文件為空!"<<endl;</p><p><b

67、>  }</b></p><p>  while(infile>>str)//把文件的內(nèi)容以字符串的形式調(diào)用</p><p><b>  {</b></p><p>  for(int i=0;i<size1;++i)</p><p><b>  {</b><

68、;/p><p>  if(str==m[i].code)</p><p>  cout<<m[i].ch;</p><p><b>  }</b></p><p><b>  }</b></p><p>  cout<<endl;</p>&

69、lt;p><b>  }</b></p><p><b>  Bitree.h</b></p><p>  #ifndef BITREE_H_INCLUDED</p><p>  #define BITREE_H_INCLUDED</p><p>  #include <iostream

70、></p><p>  #include <cstdlib></p><p>  using namespace std;</p><p>  struct Element</p><p><b>  {</b></p><p><b>  char ch;</b

71、></p><p>  double weight;</p><p><b>  };</b></p><p>  typedef Element TElemType;</p><p>  struct BiTNode</p><p><b>  {</b></p

72、><p>  TElemType data;</p><p>  BiTNode *lchild,*rchild;</p><p><b>  };</b></p><p>  typedef BiTNode *BiTree;</p><p>  void initBiTree(BiTree &

73、;T);//初始化樹</p><p>  void createBiTree(BiTree &T);//創(chuàng)建樹</p><p>  void preOrderTraverse(BiTree T,void (*visit)(TElemType)); </p><p><b>  //遞歸前序遍歷</b></p><p&

74、gt;<b>  #endif</b></p><p>  Bitree.cpp</p><p>  #include "bitree.h"</p><p>  void initBiTree(BiTree &T)//構(gòu)造空二叉樹T</p><p><b>  {</b>

75、</p><p><b>  T=NULL;</b></p><p><b>  }</b></p><p>  void createBiTree(BiTree &T)</p><p><b>  {</b></p><p>  //按先序次序

76、輸入二叉樹中結(jié)點(diǎn)的值('#'表示空格),構(gòu)造二叉鏈表表示的二叉樹T。</p><p><b>  char ch;</b></p><p><b>  cin>>ch;</b></p><p>  if(ch=='#') // 空</p><p><

77、b>  T=NULL;</b></p><p><b>  else</b></p><p><b>  {</b></p><p>  T=new BiTNode;</p><p><b>  if(!T)</b></p><p>&

78、lt;b>  exit(1);</b></p><p>  T->data.ch=ch; // 生成根結(jié)點(diǎn)</p><p>  createBiTree(T->lchild); // 構(gòu)造左子樹</p><p>  createBiTree(T->rchild); // 構(gòu)造右子樹</p><p><

79、b>  }</b></p><p><b>  }</b></p><p>  void preOrderTraverse(BiTree T,void (*visit)(TElemType))</p><p><b>  {</b></p><p>  // 先序遞歸遍歷T,對(duì)每個(gè)

80、結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次</p><p><b>  if(T)</b></p><p><b>  { // T不空</b></p><p>  visit(T->data); // 先訪問根結(jié)點(diǎn)</p><p>  preOrderTraverse(T->lchild,vi

81、sit); // 再先序遍歷左子樹</p><p>  preOrderTraverse(T->rchild,visit); // 最后先序遍歷右子樹</p><p><b>  }</b></p><p><b>  }</b></p><p>  Linklist.h</p>

82、<p>  #include <cstdlib></p><p>  #include "bitree.h"</p><p>  using namespace std;</p><p>  typedef BiTree ElemType;</p><p>  struct LNode</p&

83、gt;<p><b>  {</b></p><p>  ElemType data;//數(shù)據(jù)域</p><p>  LNode* next;//指向下一個(gè)結(jié)點(diǎn)</p><p><b>  };</b></p><p>  typedef LNode* LinkList;</p&

84、gt;<p>  void initList(LinkList& L);//初始單鏈表</p><p>  LinkList getRear(LinkList L);//獲取鏈尾指針</p><p>  void createList(LinkList& L,int n,void (*visit)(ElemType&));//創(chuàng)建單鏈表</p&g

85、t;<p>  void clearList(LinkList& L);//清空單鏈表</p><p>  int getSize(LinkList L);//獲取單鏈表長(zhǎng)度</p><p>  bool isEmpty(LinkList L);//判斷單鏈表是否為空</p><p>  void traverList(LinkList L,v

86、oid (*visit)(ElemType&));//遍歷單鏈表</p><p>  ElemType& getElem(LinkList L,int pos);//獲取指定位置的元素</p><p>  int locateElem(LinkList L,ElemType e,int (*compare)(ElemType,ElemType));//定位滿足條件的元素&l

87、t;/p><p>  bool insertElem(LinkList& L,ElemType e,int pos);//在指定位置插入元素</p><p>  bool deleteElem(LinkList& L,int pos);//刪除指定位置的元素</p><p>  void OrderInsert(LinkList& L,ElemT

88、ype e,int (*compare)(ElemType,ElemType));//按序插入元素</p><p>  ElemType DelReturn(LinkList& L,int pos);//刪除pos位序上的元素,并返回被刪除的元素</p><p>  #endif // LINKLIST_H_INCLUDED</p><p>  Linkli

89、st.cpp</p><p>  //帶頭結(jié)點(diǎn)的單鏈線性表的實(shí)現(xiàn)</p><p>  #include "linklist.h"</p><p>  void initList(LinkList& L)//初始單鏈表</p><p><b>  {</b></p><p&g

90、t;  L=new LNode;</p><p><b>  if (!L)</b></p><p>  exit(1); //存儲(chǔ)空間分配失敗</p><p>  L->next=NULL;</p><p><b>  }</b></p><p>  LinkLis

91、t getRear(LinkList L)//獲取鏈尾指針</p><p><b>  {</b></p><p>  LinkList p=L;</p><p>  while (p->next!=NULL)</p><p>  p=p->next;</p><p><b>

92、;  return p;</b></p><p><b>  }</b></p><p>  void createList(LinkList& L,int n,void (*visit)(ElemType&))//創(chuàng)建單鏈表</p><p><b>  {</b></p><

93、;p>  LinkList p;</p><p>  LinkList r=L;</p><p>  for (int i=1; i<=n; ++i)</p><p><b>  {</b></p><p>  p=new LNode;</p><p>  visit(p->da

94、ta);</p><p>  p->next=NULL;</p><p>  r->next=p;</p><p>  r=r->next;</p><p><b>  }</b></p><p><b>  }</b></p><p&g

95、t;  void traverList(LinkList L,void (*visit)(ElemType&))//遍歷單鏈表</p><p><b>  {</b></p><p>  LinkList p=L;</p><p>  if (p->next==NULL)</p><p>  cout<

96、;<"list is empty!"<<endl;</p><p><b>  else</b></p><p><b>  {</b></p><p>  while (p->next!=NULL)</p><p><b>  {</b&

97、gt;</p><p>  p=p->next;</p><p>  visit(p->data);</p><p><b>  }</b></p><p>  cout<<endl;</p><p><b>  }</b></p>&l

98、t;p><b>  }</b></p><p>  void clearList(LinkList& L)//清空單鏈表</p><p><b>  {</b></p><p>  LinkList r=L->next,p;</p><p>  L->next=NULL;&

99、lt;/p><p>  while (r!=NULL)</p><p><b>  {</b></p><p><b>  p=r;</b></p><p>  r=r->next;</p><p><b>  delete p;</b></p&

100、gt;<p><b>  }</b></p><p><b>  }</b></p><p>  bool isEmpty(LinkList L)//判斷單鏈表是否為空</p><p><b>  {</b></p><p>  if (L->next==N

101、ULL)</p><p>  return true;</p><p><b>  else</b></p><p>  return false;</p><p><b>  }</b></p><p>  int getSize(LinkList L)//獲取單鏈表長(zhǎng)度&

102、lt;/p><p><b>  {</b></p><p>  LinkList p=L;</p><p><b>  int n=-1;</b></p><p>  while (p!=NULL)</p><p><b>  {</b></p>

103、<p>  p=p->next;</p><p><b>  ++n;</b></p><p><b>  }</b></p><p><b>  return n;</b></p><p><b>  }</b></p>

104、<p>  ElemType& getElem(LinkList L,int pos)//獲取指定位置的元素</p><p><b>  {</b></p><p>  LinkList p=L;</p><p><b>  int i=0;</b></p><p>  if (

105、pos<1||pos>getSize(L))</p><p><b>  {</b></p><p>  cout<<"pos is out range!"<<endl;</p><p><b>  exit(1);</b></p><p>&

106、lt;b>  }</b></p><p>  while (i<pos)</p><p><b>  {</b></p><p>  p=p->next;</p><p><b>  ++i;</b></p><p><b>  }&l

107、t;/b></p><p>  return p->data;</p><p><b>  }</b></p><p>  int locateElem(LinkList L,ElemType e,int (*compare)(ElemType,ElemType))//定位滿足條件的元素</p><p>&l

108、t;b>  {</b></p><p>  LinkList p=L;</p><p><b>  int i=0;</b></p><p>  while (p->next!=NULL)</p><p><b>  {</b></p><p>  p

109、=p->next;</p><p><b>  ++i;</b></p><p>  if (compare(p->data,e)==1)</p><p><b>  return i;</b></p><p><b>  }</b></p><

110、p><b>  return 0;</b></p><p><b>  }</b></p><p>  bool insertElem(LinkList& L,ElemType e,int pos)//在指定位置插入元素</p><p><b>  {</b></p>&l

111、t;p>  LinkList p=L,s;</p><p><b>  int i=0;</b></p><p>  while (p!=NULL&&i<pos-1)</p><p><b>  {</b></p><p>  p=p->next;</p>

112、;<p><b>  ++i;</b></p><p><b>  }</b></p><p>  if (pos<1||p==NULL)</p><p>  return false;</p><p>  s=new LNode;</p><p>  s

113、->data=e;</p><p>  s->next=p->next;</p><p>  p->next=s;</p><p>  return true;</p><p><b>  }</b></p><p>  bool deleteElem(LinkList&a

114、mp; L,int pos)//刪除指定位置的元素</p><p><b>  {</b></p><p>  LinkList p=L,q;</p><p><b>  int i=0;</b></p><p>  while ((p->next)!=NULL&&i<p

115、os-1)</p><p>  { p=p->next;++i;}</p><p>  if (pos<1||(p->next)==NULL)</p><p>  return false;</p><p>  q=p->next;</p><p>  p->next=q->next

116、;</p><p><b>  delete q;</b></p><p>  return true;</p><p><b>  }</b></p><p>  VoidOrderInsert(LinkList&L,ElemTypee,</p><p>  int

117、(*compare)(ElemType,ElemType))//順序插入</p><p><b>  {</b></p><p>  int pos=locateElem(L,e,compare);//獲取插入位置</p><p>  if(pos==0)//如沒找到插入位置,則插在最后</p><p>  pos=ge

118、tSize(L)+1;</p><p>  insertElem(L,e,pos);</p><p><b>  }</b></p><p>  ElemType DelReturn(LinkList& L,int pos)</p><p><b>  {</b></p>&l

119、t;p>  ElemType e=getElem(L,pos);</p><p>  deleteElem(L,pos);</p><p><b>  return e;</b></p><p><b>  }</b></p><p><b>  8 測(cè)試情況</b>&l

120、t;/p><p><b>  程序運(yùn)行的結(jié)果:</b></p><p>  該程序的運(yùn)行良好,對(duì)文件能正確操作,能達(dá)到題目的要求對(duì)文件里面的報(bào)文能精確的統(tǒng)計(jì),并進(jìn)行編碼,并能依據(jù)存入文件的哈夫曼編碼進(jìn)行準(zhǔn)確譯碼,滿足題目的要求。</p><p><b>  9 設(shè)計(jì)總結(jié)</b></p><p>  通過

121、這次的課程設(shè)計(jì)我深刻認(rèn)識(shí)到基礎(chǔ)知識(shí)的重要性,對(duì)復(fù)雜的程序可以分塊實(shí)行功能,能夠讓整個(gè)思路變得清晰,讓程序變得容易理解,編程的過程中可以把各個(gè)模塊封裝起來,先實(shí)行單個(gè)的功能,在沒有錯(cuò)誤的情況下在實(shí)行整體的連接使用,可以清楚的發(fā)現(xiàn)錯(cuò)誤點(diǎn),并快速解決,提高了編程的效率。</p><p><b>  參考資料</b></p><p> ?、?嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu). 清

溫馨提示

  • 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)論