2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩9頁(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>  2011-2012年數(shù)據(jù)結(jié)構(gòu)</p><p><b>  課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告</b></p><p><b>  學(xué)院:計(jì)算機(jī)學(xué)院</b></p><p><b>  班級(jí):</b></p><p><b>  姓名:</b></

2、p><p><b>  學(xué)號(hào):</b></p><p><b>  郵箱:</b></p><p><b>  年月日</b></p><p>  《課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告</p><p>  ◎?qū)嶒?yàn)題目: 字典序</p><p>  ◎

3、實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu),建立字典樹(shù),解決文件中單詞的搜索統(tǒng)計(jì)問(wèn)題。</p><p>  ◎?qū)嶒?yàn)內(nèi)容:現(xiàn)在有一個(gè)英文字典(每個(gè)單詞都是由小寫的'a'-'z'組成),單詞量很大,達(dá)到100多萬(wàn)的單詞,而且還有很多重復(fù)的單詞。</p><p>  此外,我們現(xiàn)在還有一些 Document,每個(gè)Document 包含一些英語(yǔ)單詞。 </p>&l

4、t;p>  針對(duì)這個(gè)問(wèn)題,請(qǐng)你選擇合適的數(shù)據(jù)結(jié)構(gòu),組織這些數(shù)據(jù),使時(shí)間復(fù)雜度和空間復(fù)雜度盡可能低,并且解決下面的問(wèn)題和分析自己算法的時(shí)間復(fù)雜度。 </p><p><b>  1)基本型問(wèn)題 </b></p><p> ?。?)選擇合適的數(shù)據(jù)結(jié)構(gòu),將所有的英文單詞生成一個(gè)字典Dictionary。 </p><p> ?。?)給定一個(gè)單詞

5、,判斷這個(gè)單詞是否在字典 Dictionary中。如果在單詞庫(kù)中,輸出這個(gè)單詞總共出現(xiàn)的次數(shù)。否則輸出NO。</p><p><b>  2)擴(kuò)展型問(wèn)題 </b></p><p> ?。?)給定一個(gè)單詞,按字典序輸出字典 Dictionary 中所有以這個(gè)單詞為前綴的單詞。例如,如果字典 T={a,aa, aaa, b, ba}, 如果你輸入 a,那么輸出應(yīng)該為{a,

6、 aa, aaa}。</p><p>  (4)給定一個(gè)單詞,輸出在Dictionary 中以這個(gè)單詞為前綴的單詞的出現(xiàn)頻率最高的10個(gè)單詞,對(duì)于具有相同出現(xiàn)次數(shù)的情況,按照最近(即最后)插入的單詞優(yōu)先級(jí)比較高的原則輸出。</p><p> ?。?)輸出Dictionary中出現(xiàn)次數(shù)最高的10個(gè)單詞。</p><p><b>  3)高級(jí)型問(wèn)題 </

7、b></p><p>  (6)現(xiàn)在我們有一些Document,每個(gè)Document 由一些單詞組成,現(xiàn)在的問(wèn)題就是給你一個(gè)word,檢索出哪些 Document包含這個(gè) word,輸出這些Document的DocumentID(就如同搜索引擎一樣,即輸入一些關(guān)鍵字,然后檢索出和這些關(guān)鍵字相關(guān)的文檔)。</p><p> ?。?)在第(6)問(wèn)中,我們只考慮了一個(gè)word 在哪些Doc

8、ument中的情況,我們進(jìn)一步考慮2個(gè)相鄰word的情況,檢索出同時(shí)包含這兩個(gè)相鄰word的DocumentID。</p><p><b>  4)挑戰(zhàn)型問(wèn)題 </b></p><p> ?。?) 現(xiàn)在我們?cè)賹?duì)(7)的問(wèn)題進(jìn)行擴(kuò)展,把(7)中的只檢索相鄰 2個(gè)word 推廣到可以檢索多個(gè)word(即連續(xù)的k個(gè)word,其中k>=2),檢索出同時(shí)包含k個(gè)連續(xù)wor

9、d 的DocumentID。</p><p>  我解決了前六個(gè)問(wèn)題。</p><p><b>  一、需求分析</b></p><p>  1.本程序演示中,程序自動(dòng)讀取目標(biāo)文件,生成需要的文件。</p><p>  2. 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行,即在計(jì)算機(jī)終端上顯示“提示信息”之后,由用戶在鍵盤上輸入相

10、應(yīng)數(shù)據(jù)。</p><p>  3.程序執(zhí)行的主要命令包括:</p><p> ?。?)構(gòu)建棧;(2)構(gòu)造字典樹(shù);(3)構(gòu)建文件數(shù);(4)樹(shù)的查找;(5)結(jié)束。</p><p><b>  二 概要設(shè)計(jì)</b></p><p>  為實(shí)現(xiàn)上述算法,選擇字典樹(shù)為本程序的存儲(chǔ)結(jié)構(gòu)。</p><p>  

11、1、本程序包括三個(gè)模塊:</p><p><b> ?。?)主程序模塊;</b></p><p><b> ?。?)構(gòu)建棧模塊;</b></p><p> ?。?)構(gòu)造字典樹(shù)模塊;</p><p> ?。?)構(gòu)建文件數(shù)模塊;</p><p> ?。?)樹(shù)的遍歷模塊;</

12、p><p><b>  2、模塊調(diào)用關(guān)系圖</b></p><p><b>  三 詳細(xì)設(shè)計(jì)</b></p><p>  1、定義存儲(chǔ)鏈表結(jié)構(gòu):</p><p> ?。?)定義字典樹(shù)與文件數(shù)結(jié)構(gòu):</p><p>  #include<stdio.h></p&g

13、t;<p>  #include<string.h></p><p>  #include<stdlib.h></p><p>  #include<malloc.h></p><p>  #define NULL 0</p><p>  #define ERROR -1</p>

14、<p>  #define stack_in_size 100</p><p>  #define stackincrement 10</p><p>  struct TreeNode /*樹(shù)結(jié)點(diǎn)*/</p><p>  { </p><p>  char ch;

15、 </p><p>  int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/</p><p>  struct TreeNode* pt[26]; /*指向后繼的字母的26個(gè)指針*/</p><p>  }; </p><p>  struct TreeNode *

16、root;</p><p>  typedef struct TreeNode *Link_TreeNode;</p><p>  struct MAX_TEN /*存放出現(xiàn)頻率最高的十個(gè)單詞數(shù)據(jù)結(jié)構(gòu)*/</p><p><b>  {</b></p><p>  char STRING[35];<

17、;/p><p>  int count; /*字符串出現(xiàn)的次數(shù)*/</p><p>  int xiabao; /*字符數(shù)組位置的下標(biāo)*/</p><p>  }; </p><p>  struct MAX_TEN MAX[10];&

18、lt;/p><p>  struct MAX_TEN MIN;</p><p>  struct DocumentNode /*文件結(jié)點(diǎn)*/</p><p><b>  {</b></p><p>  char ch; /*存放某個(gè)單詞的一個(gè)字符*/</p

19、><p>  int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/</p><p>  struct DocumentNode* pt[26]; /*指向后繼的字母的26個(gè)指針*/</p><p>  struct Locationn *next;/*連接以該字符為結(jié)束的單詞所在的位置*/</p><p

20、>  }; </p><p>  typedef struct DocumentNode *Link_DocumentNode;</p><p>  Link_DocumentNode ROOT[301]; /*300個(gè)根節(jié)點(diǎn)指針,零號(hào)單元不用*/ </p><p>  struct Lo

21、cationn /*單詞在文件中的位置*/</p><p><b>  {</b></p><p>  int num; </p><p>  struct Locationn *next; </p><p>  };

22、 </p><p>  struct WORD /*單詞鏈表結(jié)構(gòu)*/</p><p><b>  {</b></p><p>  char strr[35];</p><p>  struct WORD *next;</p><p>  };

23、 </p><p>  typedef struct </p><p><b>  {</b></p><p>  char *base;</p><p>  char *top;</p><p>  int stacksize;</p><p>

24、;<b>  }SQSTACK;</b></p><p>  SQSTACK S,T;</p><p>  2、每個(gè)模塊的分析:</p><p><b> ?。?)主程序模塊:</b></p><p>  void main()</p><p><b>  {<

25、;/b></p><p>  printf("*****************基本型問(wèn)題************************\n");</p><p>  CREAT_DicTree();/*第一題,讀入vocabulary文件,建立存放單詞的字典樹(shù)*/</p><p>  printf("The First pro

26、blem has been solved,a dictionary tree has been buildt\n");</p><p>  OPEN_SearchWordInVocabulary();/*第二題,生成SearchWordInVocabulary_Result.txt*/</p><p>  printf("The Second problem has b

27、een solved,SearchWordInVocabulary_Result.txt formed \n");</p><p>  printf("*****************擴(kuò)展型問(wèn)題************************\n");</p><p>  OPEN_TotPrefixWord();/*第三題,生成TotPrefixWord_

28、Result.txt*/</p><p>  printf("The Third problem has been solved,TotPrefixWord_Result.txt formed \n");</p><p>  OPEN_PrefixFrequence();/*第四題,生成PrefixFrequence_Result.txt*/</p>&l

29、t;p>  printf("The Forth problem has been solved,PrefixFrequence_Result.txt formed \n");</p><p>  OPEN_MostFrequenceWord();/*第五題,生成MostFrequenceWord.txt*/</p><p>  printf("The F

30、ifth problem has been solved,MostFrequenceWord.txt formde\n");</p><p>  printf("*****************高級(jí)型問(wèn)題************************\n");</p><p>  CREAT_DocumentTree();/*第六題,讀入Document文

31、件,建立存放文件的樹(shù)*/</p><p>  printf("The Sixth problem has been solved,WordInDocument_Result.txt formed\n");</p><p><b>  }</b></p><p><b> ?。?)構(gòu)建棧模塊:</b>&l

32、t;/p><p>  SQSTACK Creat() /*創(chuàng)建空棧*/</p><p><b>  {</b></p><p>  SQSTACK s;</p><p>  s.base=(char*)malloc(stack_in_size*sizeof(char));</p>

33、<p>  s.top=s.base;</p><p>  s.stacksize=stack_in_size;</p><p><b>  return s;</b></p><p>  } /*全局變量棧*/</p><p>  char pop(SQSTACK &

34、;s) /*出棧*/</p><p>  { </p><p><b>  char e;</b></p><p>  if(s.top==s.base)return ERROR;</p><p>  e=*(--s.top);</p><p><b>  return

35、 e;</b></p><p><b>  }</b></p><p>  void push(SQSTACK &s,char e) /*入棧*/</p><p><b>  {</b></p><p>  if(s.top-s.base>=s.stacksize)&l

36、t;/p><p>  {s.base=(char*)realloc(s.base,</p><p>  (s.stacksize+stackincrement )*sizeof(char));</p><p>  s.top=s.base+s.stacksize;</p><p>  s.stacksize+=stackincrement;&l

37、t;/p><p><b>  }</b></p><p><b>  *s.top=e;</b></p><p>  s.top=s.top+1;</p><p><b>  }</b></p><p>  int isempty(SQSTACK s)

38、 /*判斷棧是否為空*/</p><p><b>  {</b></p><p>  if(s.base==s.top)</p><p><b>  return 1;</b></p><p><b>  else </b></p><p>&l

39、t;b>  return 0;</b></p><p><b>  }</b></p><p> ?。?)構(gòu)造字典樹(shù)模塊:</p><p>  Link_TreeNode creat() /*創(chuàng)建樹(shù)結(jié)點(diǎn),并返回指向該節(jié)點(diǎn)的指針*/</p><p><b>  {</b&

40、gt;</p><p><b>  int i;</b></p><p>  Link_TreeNode pt;</p><p>  pt=(Link_TreeNode)malloc(sizeof(TreeNode));</p><p>  pt->number=0;</p><p>  f

41、or(i=0;i<26;i++)</p><p>  pt->pt[i]=NULL;</p><p>  return pt;</p><p><b>  }</b></p><p>  void CREAT_DicTree() /*創(chuàng)建字典樹(shù)*/</p><p>

42、<b>  {</b></p><p>  root=creat();</p><p>  Link_TreeNode q;</p><p><b>  FILE *fp;</b></p><p><b>  char *p;</b></p><p>&

43、lt;b>  int ctmp;</b></p><p>  int jieshu;</p><p>  char str[35]; /*存放從文件中讀入的單詞*/</p><p>  if((fp=fopen("vocabulary.txt","r"))==NULL)</p&g

44、t;<p>  printf("cannot open vocabulary.txt\n");</p><p><b>  while(1)</b></p><p><b>  { </b></p><p>  jieshu=fscanf(fp,"%s",str)

45、;/*從文件中讀入字符串*/</p><p>  q=root; </p><p>  if(jieshu==-1) </p><p>  break; </p><p><b>  else</b></p><

46、;p>  { </p><p><b>  p=str;</b></p><p>  while(*p!='\0')</p><p>  { </p><p>  ctmp=*p-97;</p>

47、<p>  if(q->pt[ctmp]!=NULL)</p><p>  q=q->pt[ctmp]; </p><p><b>  else</b></p><p>  { </p><p>  q->pt[ctmp]=creat();</p>

48、;<p>  q=q->pt[ctmp];</p><p><b>  q->ch=*p;</b></p><p><b>  }</b></p><p><b>  p++;</b></p><p>  if(*p=='\0')

49、 </p><p><b>  {</b></p><p>  q->number++;</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b>&

50、lt;/p><p><b>  }</b></p><p><b>  } </b></p><p><b>  }</b></p><p> ?。?)構(gòu)建文件數(shù)模塊:</p><p>  Link_DocumentNode CREAT()/*創(chuàng)建一個(gè)文件

51、型的數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn),并返回指向該節(jié)點(diǎn)的指針*/</p><p><b>  {</b></p><p><b>  int i;</b></p><p>  Link_DocumentNode p;</p><p>  p=(Link_DocumentNode)malloc(sizeof(struct

52、 DocumentNode));</p><p>  p->number=0;</p><p>  for(i=0;i<26;i++)</p><p><b>  {</b></p><p>  p->pt[i]=NULL;</p><p><b>  }</b&

53、gt;</p><p>  p->next=NULL; /*文件初始化*/</p><p><b>  return p;</b></p><p><b>  }</b></p><p>  void CREAT_DocumentTree() /

54、*讀入文件,創(chuàng)建文件樹(shù)*/</p><p><b>  {</b></p><p>  Link_DocumentNode q;</p><p>  struct Locationn *LL;</p><p><b>  FILE *fp;</b></p><p><b

55、>  char *p;</b></p><p><b>  int ctmp;</b></p><p>  int jieshu;</p><p>  int Location; /*定位單詞在文章中的位置*/</p><p>  int k;

56、 </p><p>  char str[35]; /*存放從文件中讀入的單詞*/</p><p>  if((fp=fopen("Document.txt","r"))==NULL)</p><p>  printf("cannot open Document.tx

57、t\n");</p><p><b>  while(1)</b></p><p><b>  { </b></p><p>  jieshu=fscanf(fp,"%s",str);</p><p>  if(jieshu==-1) <

58、/p><p>  break; /*文件中單詞已讀完*/</p><p>  if(!strcmp(str,"Document"))</p><p><b>  {</b></p><p>  fscanf(fp,"%d",&k);</p>

59、;<p>  ROOT[k]=CREAT();</p><p>  Location=1;</p><p>  fscanf(fp,"%s",str);</p><p><b>  }</b></p><p>  q=ROOT[k];</p><p><b&

60、gt;  p=str;</b></p><p>  while(*p!='\0') /*處理每個(gè)單詞*/</p><p><b>  {</b></p><p>  ctmp=*p-97;</p><p>  if(q->pt[ctmp]!=NULL)</p

61、><p>  q=q->pt[ctmp];</p><p><b>  else</b></p><p><b>  {</b></p><p>  q->pt[ctmp]=CREAT();</p><p>  q=q->pt[ctmp];</p>

62、<p><b>  q->ch=*p;</b></p><p><b>  }</b></p><p><b>  p++;</b></p><p>  if(*p=='\0')</p><p><b>  { </b>

63、;</p><p>  q->number++;</p><p>  if(q->next==NULL) </p><p><b>  {</b></p><p>  LL=(struct Locationn *)malloc(sizeof(struct Locationn));</p><

64、;p>  LL->num=Location;</p><p>  q->next=LL;</p><p>  LL->next=NULL;</p><p>  Location++;</p><p><b>  break;</b></p><p><b>  }

65、</b></p><p>  else </p><p><b>  { </b></p><p>  LL=q->next;</p><p>  while(LL->next!=NULL)</p><p>  LL=LL->next;<

66、;/p><p>  LL->next=(struct Locationn *)malloc(sizeof(struct Locationn));</p><p>  LL=LL->next;</p><p>  LL->next=NULL;</p><p>  LL->num=Location;</p>&l

67、t;p>  Location++;</p><p><b>  break;</b></p><p><b>  }</b></p><p>  } </p><p><b>  }</b></p><p>

68、<b>  } </b></p><p><b>  }</b></p><p> ?。?)程序使用的函數(shù):</p><p>  SQSTACK Creat()</p><p>  char pop(SQSTACK &s)</p><p>  void push(S

69、QSTACK &s,char e)</p><p>  int isempty(SQSTACK s)</p><p>  Link_TreeNode creat()</p><p>  void CREAT_DicTree()</p><p>  int Search(char str[],Link_TreeNode root)<

70、;/p><p>  Link_TreeNode Get_Last_Link(char str[])</p><p>  bool OutPrint(Link_TreeNode p,FILE *fp)</p><p>  void RECHANGE_MIN(char tepp[],int cunt)</p><p>  bool GOT_MAX_T

71、EN(Link_TreeNode p)</p><p>  Link_DocumentNode CREAT()</p><p>  void CREAT_DocumentTree()</p><p>  int Search_Doc(char str[],Link_DocumentNode root)</p><p>  void SORT_

72、MAX_Ten()</p><p>  struct WORD *Creat_two_word_link(char str1[],char str2[])</p><p>  struct WORD *Creat_multi_word_link(int length,FILE *fp)</p><p>  void Search_Match_Word(struct

73、WORD *head,int length,FILE *fp)</p><p>  void OPEN_SearchWordInVocabulary()</p><p>  void OPEN_TotPrefixWord()</p><p>  void OPEN_PrefixFrequence()</p><p>  void OPEN_M

74、ostFrequenceWord()</p><p>  void main()</p><p>  3、數(shù)據(jù)結(jié)構(gòu)示意圖:‘</p><p><b>  26個(gè)孩子</b></p><p><b>  。。。。。。</b></p><p>  每個(gè)樹(shù)結(jié)點(diǎn)有26個(gè)孩子</

75、p><p>  四 使用說(shuō)明、測(cè)試分析及結(jié)果</p><p><b>  1、程序使用說(shuō)明:</b></p><p> ?。?)本程序的運(yùn)行環(huán)境為VC6.0。</p><p> ?。?)進(jìn)入演示程序后即顯示的提示信息:</p><p><b>  輸出:</b></p>

76、;<p>  *****************基本型問(wèn)題************************</p><p>  The First problem has been solved,a dictionary tree has been buildt</p><p>  The Second problem has been solved,SearchWordIn

77、Vocabulary_Result.txt formed</p><p>  *****************擴(kuò)展型問(wèn)題************************</p><p>  The Third problem has been solved,TotPrefixWord_Result.txt formed</p><p>  The Forth pr

78、oblem has been solved,PrefixFrequence_Result.txt formed</p><p>  The Fifth problem has been solved,MostFrequenceWord.txt formed</p><p>  *****************高級(jí)型問(wèn)題************************</p>

79、<p>  The Sixth problem has been solved,WordInDocument_Result.txt formed</p><p><b>  2、運(yùn)行界面:</b></p><p><b>  五、實(shí)驗(yàn)總結(jié)</b></p><p>  這次實(shí)驗(yàn)題目涉及了數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的多種結(jié)構(gòu),

80、要求對(duì)各種數(shù)據(jù)的存儲(chǔ)與處理的方法比較熟悉。在實(shí)驗(yàn)中,由于這學(xué)期沒(méi)有很認(rèn)真的學(xué)習(xí)這門課,平常實(shí)驗(yàn)課寫程序也不是很認(rèn)真,以至于解決前兩個(gè)問(wèn)題還比較輕松,但是從三個(gè)問(wèn)題開(kāi)始我就遇到了很大困難,在數(shù)據(jù)的處理過(guò)程中遇到了不小的麻煩,導(dǎo)致后來(lái)調(diào)試的時(shí)候浪費(fèi)了很多時(shí)間。同時(shí),程序的時(shí)間復(fù)雜度耗時(shí),占用內(nèi)存較大,這說(shuō)明程序的結(jié)構(gòu)不夠靈巧,我會(huì)再次認(rèn)真的自己學(xué)習(xí)這門課程,希望在以后的學(xué)習(xí)中能把程序?qū)懙酶谩?lt;/p><p><

溫馨提示

  • 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ù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 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)論