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

下載本文檔

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

文檔簡介

1、<p>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗</p><p>  樹的遍歷,文件目錄結(jié)構(gòu)的顯示</p><p><b>  實驗報告</b></p><p><b>  一、簡介</b></p><p>  樹型結(jié)構(gòu)是一類十分重要的非線性結(jié)構(gòu),它可以很好地描述客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦?/p>

2、的對象,如操作系統(tǒng)的文件構(gòu)成、人工智能搜索算法的模型表示以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等。</p><p>  文件的目錄結(jié)構(gòu)是樹型結(jié)構(gòu)在計算機操作系統(tǒng)的典型應(yīng)用。通過樹型結(jié)構(gòu)可以直觀且清晰的表明操作系統(tǒng)中的文件組織結(jié)構(gòu)。用戶可通過樹型結(jié)構(gòu)顯示的文件目錄列表找到自己想訪問的內(nèi)容。</p><p>  本實驗的要求在給出Unix下目錄和文件信息的前提下,編程實現(xiàn)將其排列成一棵具有一定縮進的樹。

3、具體要求如下:</p><p><b>  輸入要求</b></p><p>  輸入數(shù)據(jù)包含幾個測試案例。每一個案例由幾行組成,每以行都代表了目錄樹的層次結(jié)構(gòu)。第一行代表目錄的根節(jié)點。若是目錄節(jié)點,那么它的孩子節(jié)點將在第二行中被輸出,同時用一對圓括號“()”界定。同樣,如果這些孩子節(jié)點中某一個也是目錄的話,那么這個目錄所包含的內(nèi)容將在隨后的一行中列出,由一對圓括號將

4、首尾界定。目錄的輸入格式為:*nams size,文件的輸入格式為:name size,其中*代表當前節(jié)點是目錄,name代表文件或目錄的名稱,由一串長度不大于10的字符組成,并且name字符串中不能含有‘(’,‘)’,‘[’,‘]’和‘*’。size是該文件/目錄的大小,為一個大于0的整數(shù)。每一個案例中最多只能包含10層,每一層最多有10個文件/目錄。</p><p><b>  輸出要求</b

5、></p><p>  對每一個測試案例,輸出時要求:第d層的文件/目錄名前面需要插入8*d個空格,兄弟節(jié)點之間要在同一列上。不要使用Tab(制表符)來統(tǒng)一輸出的縮進。每一個目錄的大?。╯ize)是它所包含的所有子目錄和文件大小以及它自身大小的總和。</p><p>  有輸入/輸出樣例如下:</p><p><b>  輸入樣例:</b>

6、;</p><p><b>  */usr 1</b></p><p>  (*mark 1 *alex 1)</p><p>  (hw.c 3 *course 1)(hw.c 5)</p><p>  (aa.txt 12)</p><p><b>  */usr 1</b&g

7、t;</p><p><b>  ()</b></p><p><b>  輸出樣例:</b></p><p>  |_*/usr[24]</p><p>  |_*mark[17]</p><p>  | |_hw.c[3]</p><p>  

8、| |_*course[13]</p><p>  |_aa.txt[12]</p><p>  |_*alex[6]</p><p><b>  |_hw.c[5]</b></p><p><b>  |_*usr[1]</b></p><p>  因此,實驗任務(wù)如下:

9、</p><p>  (1)讀入給定的Unix目錄和文件信息。</p><p> ?。?)建立樹型鏈表以表示目錄和文件結(jié)構(gòu),同時重新計算目錄大小</p><p>  (3)以樹型結(jié)構(gòu)輸出文件信息。</p><p><b>  二、設(shè)計說明</b></p><p>  2.1、數(shù)據(jù)結(jié)構(gòu)實現(xiàn)</

10、p><p>  目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu),可以選擇孩子兄弟雙親鏈表來儲存樹的結(jié)構(gòu)。</p><p>  孩子兄弟雙親鏈表是一種典型的樹的存儲結(jié)構(gòu)。在該表示方法中,鏈表中節(jié)點的三個指針域分別指向該節(jié)點的父親、第一個孩子節(jié)點和下一個兄弟節(jié)點,分別命名為Parent域,F(xiàn)irstChild域和NextSibling域。</p><p>  在孩子兄弟雙親鏈表表示法中,節(jié)點

11、形式統(tǒng)一,節(jié)點間的聯(lián)系比較簡潔。同時,在這種存儲結(jié)構(gòu)上容易實現(xiàn)樹數(shù)據(jù)結(jié)構(gòu)的大多數(shù)運算。因此,孩子兄弟雙親鏈表表示是樹的一種實用的儲存結(jié)構(gòu)。其節(jié)點形式如下:</p><p>  本題中采用面向?qū)ο蟮姆绞綄崿F(xiàn)樹型結(jié)構(gòu)。構(gòu)建Tree類,將所有的目錄作為Tree類的對象。Tree類定義如下:</p><p>  class Tree{</p><p>  string Na

12、me; //樹的根節(jié)點名稱</p><p>  int Size;//樹的大小,用于統(tǒng)計樹本身及其子數(shù)大小的總和</p><p>  Tree* FirstChild;//指向他的第一個孩子節(jié)點</p><p>  Tree* NextSibling;//指向下一個兄弟節(jié)點</p><p>  Tree* Parent;

13、//指向父節(jié)點</p><p><b>  public:</b></p><p>  Tree (string Name=””,int Size=0);//構(gòu)造函數(shù)</p><p>  void parse();//根據(jù)輸入數(shù)據(jù)建立樹型結(jié)構(gòu)</p><p>  void reSize();//重新統(tǒng)計樹

14、節(jié)點的大小</p><p>  void outPut();//輸出函數(shù)</p><p>  ~Tree();//析構(gòu)函數(shù)</p><p><b>  };</b></p><p>  2.2、主要函數(shù)的實現(xiàn)</p><p>  在Tree類中共定義了5個函數(shù),即構(gòu)造樹(Tree()構(gòu)

15、造函數(shù)),銷毀樹(~Tree()析構(gòu)函數(shù)),目錄大小計算(reSize()函數(shù)),建立樹型鏈表結(jié)構(gòu)(parse()函數(shù))和樹型結(jié)構(gòu)輸出(outPut()函數(shù))。下面分別說明如下:</p><p><b>  2.2.1構(gòu)造函數(shù)</b></p><p>  構(gòu)造函數(shù)的作用是建立一個只有一個節(jié)點的樹,其三個指針域均為空,以方便接下來目錄結(jié)構(gòu)的讀入和樹型鏈表的構(gòu)建。<

16、/p><p><b>  函數(shù)實現(xiàn)如下:</b></p><p>  Tree::Tree(string Name, int Size){</p><p>  this->Name = Name;</p><p>  this->Size = Size;</p><p>  FirstCh

17、ild = NULL;//FirstChild域置空</p><p>  NextSibling = NULL;//NextSibling域置空</p><p>  parent = NULL;//Parent域置空</p><p><b>  }</b></p><p><b>  2.2

18、.2析構(gòu)函數(shù)</b></p><p>  析構(gòu)函數(shù)的作用是刪除同一個根節(jié)點下的各個子節(jié)點,以釋放空間。</p><p><b>  函數(shù)實現(xiàn)如下:</b></p><p>  Tree::~Tree()</p><p><b>  {</b></p><p>  

19、Tree* temp;</p><p>  Tree* temp1;</p><p>  temp = FirstChild;</p><p>  while(temp != NULL)</p><p><b>  {</b></p><p>  temp1 = temp;</p>

20、<p>  temp = temp->NextSibling;</p><p>  delete temp1;</p><p><b>  }</b></p><p><b>  }</b></p><p>  2.2.3建立樹型鏈表結(jié)構(gòu)(parse()函數(shù))</p>

21、<p>  根據(jù)輸入來確定樹型關(guān)系時,首先讀取根節(jié)點目錄/文件名和大小值,并根據(jù)這些節(jié)點信息建立一個新的節(jié)點;然后讀入后面各行的信息,對于同一括號中的內(nèi)容,即具有相同父節(jié)點(在同一目錄中的)接點建立兄弟關(guān)聯(lián)。這個函數(shù)實際上是采用層次遍歷建立樹型鏈表結(jié)構(gòu)。</p><p>  這里定義一個Tree*類型的數(shù)組treeArray[],此數(shù)組存放目錄的節(jié)點信息。整形變量head和rear用來標記當前節(jié)點的父節(jié)

22、點位置。每處理完一對括號(即同一目錄中的所有目錄/文件已被處理完),head值加1,下一對待處理括號的父節(jié)點在treeArray[]數(shù)組中應(yīng)當后移一個位置。若當前處理節(jié)點是目錄類型,則放置在treeArray[]數(shù)組中,rear作為數(shù)組的下標變量,加入一個目錄節(jié)點信息rear便加1。若是文件類型,則需按照Name和Size建立一個數(shù)的節(jié)點,并和head所指的父節(jié)點建立關(guān)聯(lián)(即表明此文件所存儲的目錄),但不用放進treeArray[]數(shù)組

23、中。</p><p>  此函數(shù)可形成如下的數(shù)據(jù)結(jié)構(gòu):</p><p><b>  若有</b></p><p><b>  */admin 1</b></p><p>  (*usr1 1 *usr2 1)</p><p>  (file1.c 3 *folder 1)(

24、file2.c 5)</p><p><b>  則有下圖:</b></p><p>  treeArray[]</p><p>  treeArray[]中存儲的為目錄列表。</p><p><b>  該函數(shù)實現(xiàn)如下:</b></p><p>  void Tree::p

25、arse()</p><p><b>  {</b></p><p>  Tree* temp;</p><p>  string line;</p><p>  string name;</p><p><b>  int size;</b></p><

26、p>  while(getline(infile,line,'\n'))//讀入行</p><p><b>  {</b></p><p>  startPos = 0;</p><p><b>  while(1)</b></p><p><b>  {<

27、/b></p><p>  s = getSubDir(line, &startPos);//獲取一對()間字符串</p><p>  int i = 1;</p><p>  skipWhiteSpace(s, &i);//跳過字符串s中多余的空格</p><p>  if(s[i] != ')')

28、</p><p><b>  {</b></p><p>  skipWhiteSpace(s,&i);</p><p>  name = getName(s,&i);//獲取目錄/文件名稱</p><p>  skipWhiteSpace(s,&i);</p><p>

29、  size = getSize(s,&i);//獲取目錄/文件大小</p><p>  temp = treeArray[head%100]->FirstChild = new Tree(name,size);//獲取第一個孩子節(jié)點</p><p>  temp->parent = treeArray[head%100];</p><p&

30、gt;  if(name[0] == '*')</p><p>  treeArray[(rear++)%100] = temp;//目錄則rear+1</p><p>  skipWhiteSpace(s,&i);</p><p><b>  }</b></p><p>  while(s[i

31、] != ')')</p><p><b>  {</b></p><p>  skipWhiteSpace(s,&i);</p><p>  name = getName(s,&i);</p><p>  skipWhiteSpace(s,&i);</p><

32、p>  size = getSize(s,&i);</p><p>  temp->NextSibling = new Tree(name,size); </p><p>  //獲取下一個兄弟節(jié)點</p><p>  skipWhiteSpace(s,&i);</p><p>  temp = temp->

33、NextSibling;</p><p>  temp->parent = treeArray[head%100];</p><p>  if(name[0] == '*')</p><p>  treeArray[(rear++)%100] = temp; //目錄則rear+1</p><p><b> 

34、 }</b></p><p>  head ++;//一對()掃描完畢</p><p>  if((unsigned int)startPos >= line.length())</p><p><b>  break;</b></p><p><b>  }</b></p

35、><p>  if(head == rear)//只有一個根節(jié)點時,head=rear</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  2.2.4目錄大小

36、計算(reSize()函數(shù))</p><p>  輸入數(shù)據(jù)中,目錄大小的初始化值一般為1,而目錄真正的大小為其自身大小與包含的所有子目錄/文件大小的和。因此在計算目錄大小時,應(yīng)當遍歷下面所有的文件和子目錄。在此采用遞歸的后根遍歷方法。此外需注意的是,在采用孩子兄弟雙親鏈表表示樹時,父目錄下所有的子目錄和自文件都在其左子樹上,因此遍歷的時候只需遍歷其左子樹即可。</p><p><b&

37、gt;  例如有</b></p><p><b>  */admin 1</b></p><p>  (*usr1 1 *usr2 1)</p><p>  */admin2 1</p><p><b>  則樹型結(jié)構(gòu)如圖:</b></p><p>  顯然其ad

38、min所有子目錄都在其左子樹上,其右子樹上為與之平級的目錄(兄弟節(jié)點)。</p><p><b>  該函數(shù)實現(xiàn)如圖:</b></p><p>  void Tree::reSize()</p><p><b>  {</b></p><p>  Tree* temp = this;</p&g

39、t;<p>  if(temp->FirstChild != 0){//后根遍歷左子樹</p><p>  temp = temp->FirstChild;</p><p>  while(temp != 0){</p><p>  temp->reSize();</p><p>  Size += tem

40、p->Size;</p><p>  temp = temp->NextSibling;</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  2.2.5樹

41、型結(jié)構(gòu)輸出(outPut()函數(shù))</p><p>  很顯然,輸出是對樹的先根遍歷過程。為了完成對于目錄的樹型輸出,兄弟目錄之間需要相同的縮進,用‘|’上下相連,而父子目錄或父目錄和子文件間需要設(shè)置正確的縮進,子目錄或子文件比父目錄右縮進8個空格。設(shè)置一個標志數(shù)組flag[11](題目規(guī)定每個目錄下最大層次數(shù)為10),當前Tree* temp指針所指向的節(jié)點如果有兄弟節(jié)點,則置flag為1,否則為0;并由此節(jié)點

42、反復(fù)查詢它的祖先節(jié)點;遇到flag[]=0則輸出” “,flag[]=1則輸出”| “,表明是兄弟節(jié)點。這樣可以保證兄弟節(jié)點間有相同縮進,而子節(jié)點比父節(jié)點向右縮進8個字符。</p><p><b>  該函數(shù)實現(xiàn)如下:</b></p><p>  void Tree::outPut()</p><p><b>  {<

43、/b></p><p>  Tree* temp; //用來指向當前結(jié)點的祖先結(jié)點</p><p>  Tree* temp1;</p><p>  bool flag[11];</p><p><b>  int i;</b></p><p>  outfile.

44、open("output.txt",ios::app);//結(jié)果保存至output.txt中</p><p>  if(!outfile){</p><p>  cout<<"cannot append the output file.\n";</p><p><b>  exit(0);</b&

45、gt;</p><p><b>  }</b></p><p>  if(!checkName(Name)){</p><p>  cout<<"input error!--"<<Name<<endl;</p><p><b>  exit(0);<

46、/b></p><p><b>  }</b></p><p>  outfile<<"|_"<<Name<<"["<<Size<<"]\n";</p><p>  outfile.close();</p>

47、<p>  temp1= FirstChild; //用來指向當前結(jié)點的子結(jié)點</p><p>  while(temp1 != NULL)</p><p><b>  {</b></p><p>  outfile.open("output.txt",ios::app);&

48、lt;/p><p>  if(!outfile){</p><p>  cout<<"cannot append the output file.\n";</p><p><b>  exit(0);</b></p><p><b>  }</b></p>

49、<p><b>  i = 0;</b></p><p>  temp = temp1;</p><p>  while(temp->parent != NULL)</p><p><b>  {</b></p><p>  if(i>=10){</p><

50、p>  cout<<"input error!--dictionary contains more than 10 levels."<<endl;</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p>  temp =

51、 temp->parent;</p><p>  if(temp->NextSibling != NULL)</p><p>  flag[i++] = true;//即flag[]為1,兄弟節(jié)點</p><p><b>  else</b></p><p>  flag[i++] = false;/

52、/即flag[]為0,父節(jié)點</p><p><b>  }</b></p><p>  while(i--)</p><p><b>  {</b></p><p>  if(flag[i] == true)</p><p>  outfile<<"|

53、 ";//兄弟節(jié)點輸出</p><p><b>  else</b></p><p>  outfile<<" ";//父節(jié)點輸出</p><p><b>  }</b></p><p>  outfile.close();

54、//關(guān)閉文件</p><p>  temp1->outPut();</p><p>  temp1 = temp1->NextSibling;</p><p><b>  }</b></p><p><b>  }</b></p><p><b> 

55、 三、測試結(jié)果</b></p><p>  本試驗提供了四組輸入樣例,其中一組為只有根節(jié)點,以測試在極端情況下算法的穩(wěn)定性,一組為有兩個目錄,每個目錄下有不超過5個目錄/文件,測試算法在一般情況下的運行情況,一組為有3個目錄,其中部分目錄名為長度為10的整數(shù),部分目錄下嵌套10層子目錄/文件,以測試在樣本容量較大情況下的算法穩(wěn)定性,最后一組為錯誤的數(shù)據(jù),以測試程序的健壯性。</p>&l

56、t;p><b>  測試結(jié)果如下:</b></p><p>  測試結(jié)果表明,程序基本符合設(shè)計要求,可以實現(xiàn)將提供的Unix下目錄和文件信息用樹形結(jié)構(gòu)表示出來。</p><p><b>  四、分析與探討</b></p><p>  本程序應(yīng)用了面向?qū)ο蟮脑O(shè)計思想,將每個目錄作為Tree類的對象加以實現(xiàn),使所有對于目

57、錄的操作具有較好的通用性和可移植性。</p><p>  同時,對于反復(fù)使用的checkName()、skipWhiteSpace()、getSubDir()等函數(shù),程序?qū)⑵鋯为毬暶饕员阌谠诟鱾€函數(shù)中調(diào)用執(zhí)行。最大限度的減少了編程工作量,符合模塊化、結(jié)構(gòu)化的程序設(shè)計思想。在寫作過程中對相應(yīng)語句標明了語句注釋,方便閱讀。</p><p>  此外,在程序中大量應(yīng)用了樹數(shù)據(jù)結(jié)構(gòu)的基本操作,如函

58、數(shù)parse()中用到了樹的層序遍歷:</p><p>  while(s[i] != ')')</p><p><b>  {</b></p><p>  skipWhiteSpace(s,&i);</p><p>  name = getName(s,&i);</p>&

59、lt;p>  skipWhiteSpace(s,&i);</p><p>  size = getSize(s,&i);</p><p>  temp->NextSibling = new Tree(name,size);</p><p>  skipWhiteSpace(s,&i);</p><p>  

60、temp = temp->NextSibling;</p><p>  temp->parent = treeArray[head%100];</p><p>  if(name[0] == '*')</p><p>  treeArray[(rear++)%100] = temp;</p><p><b&g

61、t;  }</b></p><p>  在函數(shù)reSize()中應(yīng)用到了遞歸的后序遍歷:</p><p>  while(temp != 0){</p><p>  temp->reSize();</p><p>  Size += temp->Size;</p><p>  temp = te

62、mp->NextSibling;</p><p><b>  }</b></p><p>  在函數(shù)outPut()中應(yīng)用到了樹的先序遍歷:</p><p>  while(temp->parent != NULL)</p><p><b>  {</b></p><

63、p>  if(i>=10){</p><p>  cout<<"input error!--dictionary contains more than 10 levels."<<endl;</p><p><b>  exit(0);</b></p><p><b>  }<

64、;/b></p><p>  temp = temp->parent;</p><p>  if(temp->NextSibling != NULL)</p><p>  flag[i++] = true;</p><p><b>  else</b></p><p>  fla

65、g[i++] = false;</p><p><b>  }</b></p><p>  這樣可以在樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)基礎(chǔ)算法的基礎(chǔ)上稍加改進即可實現(xiàn)實驗所需求的功能。</p><p>  很顯然,程序仍有許多不完善的地方。例如程序只可識別10層嵌套的目錄/文件,對于超過十層的目錄/文件程序便無法識別。此外,對于文件名超過10的文件處理不夠完善,

66、會出現(xiàn)下列的錯誤:</p><p><b>  輸入:</b></p><p><b>  */usr 1</b></p><p>  (*admin 1 *s1 1)</p><p>  (hw6232423.exe 3 *course 1) (hw.c 5)</p><p&g

67、t;  (aa.txt 12)</p><p><b>  輸出:</b></p><p>  The result is as follows:</p><p>  |_*/usr[24]</p><p>  |_*admin[17]</p><p><b>  | <

68、;/b></p><p>  即程序在執(zhí)行到讀取串”hw6232423.exe”時自動終止,無法輸出正確的目錄/文件結(jié)構(gòu)。</p><p>  此外,對于可能出現(xiàn)的輸入錯誤,程序并未有告警。雖不會導(dǎo)致程序崩潰,但是與用戶的交互性不強。</p><p>  本程序在Dev C++ 4.9.9.2版本和Visual C++ 6.0版本上調(diào)試通過。</p>

69、;<p><b>  附錄 源代碼</b></p><p><b>  Tree.cpp</b></p><p>  #include <string></p><p>  #include <iostream></p><p>  #include <

70、fstream></p><p>  using namespace std;</p><p>  string s = "";</p><p>  int startPos = 0;</p><p>  ofstream outfile;</p><p>  ifstream infile;

71、</p><p>  class Tree{</p><p>  string Name; //樹的根結(jié)點名稱 </p><p>  int Size; //樹的大小,用于統(tǒng)計這棵樹本身及其包含的所以子樹大小的總和</p><p>  Tree* FirstChild; //指向它的第一

72、個孩子結(jié)點 </p><p>  Tree* NextSibling; //指向它的下一個兄弟結(jié)點</p><p>  Tree* parent; //指向雙親結(jié)點</p><p><b>  public:</b></p><p>  Tree(string Name = "&quo

73、t;, int Size = 0); //構(gòu)造函數(shù)</p><p>  void parse(); //根據(jù)輸入數(shù)據(jù)來建立樹形結(jié)構(gòu)</p><p>  void reSize(); //重新統(tǒng)計樹結(jié)點的大小</p><p&g

74、t;  void outPut(); //輸出樹形結(jié)構(gòu)</p><p>  ~Tree(); //析構(gòu)函數(shù)</p><p><b>  };</b></p><p>  Tree* treeArray[100];&

75、lt;/p><p>  int head = 0, rear = 0;</p><p>  Tree::Tree(string Name, int Size){</p><p>  this->Name = Name;</p><p>  this->Size = Size;</p><p>  FirstCh

76、ild = NULL;</p><p>  NextSibling = NULL;</p><p>  parent = NULL;</p><p><b>  }</b></p><p>  Tree::~Tree()</p><p><b>  {</b></p&g

77、t;<p>  Tree* temp;</p><p>  Tree* temp1;</p><p>  temp = FirstChild;</p><p>  while(temp != NULL)</p><p><b>  {</b></p><p>  temp1 = te

78、mp;</p><p>  temp = temp->NextSibling;</p><p>  delete temp1;</p><p><b>  }</b></p><p><b>  }</b></p><p>  void Tree::reSize()&l

79、t;/p><p><b>  {</b></p><p>  Tree* temp = this;</p><p>  if(temp->FirstChild != 0){</p><p>  temp = temp->FirstChild;</p><p>  while(temp !=

80、 0){</p><p>  temp->reSize();</p><p>  Size += temp->Size;</p><p>  temp = temp->NextSibling;</p><p><b>  }</b></p><p><b>  }<

81、;/b></p><p><b>  }</b></p><p>  bool checkName(string s)</p><p><b>  {</b></p><p>  if(s[0]!='*' && s.length() > 10)</p

82、><p>  return false;</p><p>  if(s[0]=='*' && s.length() > 11)</p><p>  return false;</p><p>  if(s[0]!='*' && (s[0]=='(' || s[0

83、]==')' || s[0]=='[' || s[0]==']'))</p><p>  return false;</p><p>  for(int i=1;i<s.length();i++){</p><p>  if(s[i]=='*' || s[i]=='(' || s[

84、i]==')' || s[i]=='[' || s[i]==']')</p><p>  return false;</p><p><b>  }</b></p><p>  return true;</p><p><b>  }</b></

85、p><p>  void Tree::outPut()</p><p><b>  {</b></p><p>  Tree* temp; //用來指向當前結(jié)點的祖先結(jié)點</p><p>  Tree* temp1;</p><p>  bool flag[11];

86、 //用來標志輸出縮進、層次情況的數(shù)組</p><p><b>  int i;</b></p><p>  outfile.open("output.txt",ios::app);</p><p>  if(!outfile){</p><p>  cout<&l

87、t;"cannot append the output file.\n";</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p>  if(!checkName(Name)){</p><p>  cout<<&

88、quot;input error!--"<<Name<<endl;</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p>  outfile<<"|_"<<Name<<"

89、;["<<Size<<"]\n";</p><p>  outfile.close();</p><p>  temp1= FirstChild; //用來指向當前結(jié)點的子結(jié)點</p><p>  while(temp1 != NULL)</p><p&g

90、t;<b>  {</b></p><p>  outfile.open("output.txt",ios::app);</p><p>  if(!outfile){</p><p>  cout<<"cannot append the output file.\n";</p>

91、<p><b>  exit(0);</b></p><p><b>  }</b></p><p><b>  i = 0;</b></p><p>  temp = temp1;</p><p>  while(temp->parent != NULL)&

92、lt;/p><p><b>  {</b></p><p>  if(i>=10){</p><p>  cout<<"input error!--dictionary contains more than 10 levels."<<endl;</p><p><b&g

93、t;  exit(0);</b></p><p><b>  }</b></p><p>  temp = temp->parent;</p><p>  if(temp->NextSibling != NULL)</p><p>  flag[i++] = true;</p>&l

94、t;p><b>  else</b></p><p>  flag[i++] = false;</p><p><b>  }</b></p><p>  while(i--)</p><p><b>  {</b></p><p>  if(fl

95、ag[i] == true)</p><p>  outfile<<"| ";</p><p><b>  else</b></p><p>  outfile<<" "; </p><p><b>  }&

96、lt;/b></p><p>  outfile.close();</p><p>  temp1->outPut();</p><p>  temp1 = temp1->NextSibling;</p><p><b>  }</b></p><p><b>  }&

97、lt;/b></p><p>  void skipWhiteSpace(string& s, int* i)</p><p><b>  {</b></p><p>  while(s[*i] == '\t' || s[*i] == ' ')</p><p><b&g

98、t;  (*i)++;</b></p><p><b>  }</b></p><p>  string getSubDir(string& line, int* startPos)</p><p><b>  {</b></p><p>  string res = "

99、;";</p><p>  skipWhiteSpace(line,startPos);</p><p>  while(line[*startPos] != ')')</p><p>  res += line[(*startPos)++];</p><p>  res += line[(*startPos)++]

100、;</p><p>  skipWhiteSpace(line, startPos);</p><p>  return res;</p><p><b>  }</b></p><p>  int stringToNum(string s)</p><p><b>  {</b&

101、gt;</p><p>  int num = 0;</p><p>  unsigned int i = 0;</p><p>  while(i < s.length())</p><p><b>  {</b></p><p>  num *= 10;</p><p

102、>  num += s[i++] - '0';</p><p><b>  }</b></p><p>  return num;</p><p><b>  }</b></p><p>  string getName(string& s, int* i)</p

103、><p><b>  {</b></p><p>  string name = "";</p><p>  while(s[*i] != ' ' && s[*i] != '\t')</p><p>  name += s[(*i)++];</p>

104、;<p>  return name;</p><p><b>  }</b></p><p>  int getSize(string&s, int* i)</p><p><b>  {</b></p><p>  string size = "";&l

105、t;/p><p>  while((unsigned int)(*i) < s.length() && s[*i] != ' ' && s[*i] != '\t' && s [*i] != ')')</p><p>  size += s[(*i)++];</p><p&g

106、t;  return stringToNum(size);</p><p><b>  }</b></p><p>  void Tree::parse()</p><p><b>  {</b></p><p>  Tree* temp;</p><p>  string

107、line;</p><p>  string name;</p><p><b>  int size;</b></p><p>  while(getline(infile,line,'\n'))</p><p><b>  {</b></p><p>  

108、startPos = 0;</p><p><b>  while(1)</b></p><p><b>  {</b></p><p>  s = getSubDir(line, &startPos);</p><p>  int i = 1;</p><p>  

109、skipWhiteSpace(s, &i);</p><p>  if(s[i] != ')')</p><p><b>  {</b></p><p>  skipWhiteSpace(s,&i);</p><p>  name = getName(s,&i);</p>

110、;<p>  skipWhiteSpace(s,&i);</p><p>  size = getSize(s,&i);</p><p>  temp = treeArray[head%100]->FirstChild = new Tree(name,size);</p><p>  temp->parent = tree

111、Array[head%100];</p><p>  if(name[0] == '*')</p><p>  treeArray[(rear++)%100] = temp;</p><p>  skipWhiteSpace(s,&i);</p><p><b>  }</b></p>

112、<p>  while(s[i] != ')')</p><p><b>  {</b></p><p>  skipWhiteSpace(s,&i);</p><p>  name = getName(s,&i);</p><p>  skipWhiteSpace(s,&a

113、mp;i);</p><p>  size = getSize(s,&i);</p><p>  temp->NextSibling = new Tree(name,size);</p><p>  skipWhiteSpace(s,&i);</p><p>  temp = temp->NextSibling;&

114、lt;/p><p>  temp->parent = treeArray[head%100];</p><p>  if(name[0] == '*')</p><p>  treeArray[(rear++)%100] = temp;</p><p><b>  }</b></p>&l

115、t;p><b>  head ++;</b></p><p>  if((unsigned int)startPos >= line.length())</p><p><b>  break;</b></p><p><b>  }</b></p><p>  i

116、f(head == rear)</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  int main()</p><p><b>  {</

117、b></p><p>  Tree* fileTree;</p><p><b>  string s;</b></p><p>  string name;</p><p><b>  int size;</b></p><p>  outfile.open(&quo

118、t;output.txt");</p><p>  if(!outfile){</p><p>  cout<<"cannot open the output file!\n";</p><p><b>  exit(0);</b></p><p><b>  }<

119、;/b></p><p>  outfile<<"The result is as follows:\n";</p><p>  outfile.close();</p><p>  infile.open("input.txt",ios::out);</p><p>  if(!in

120、file){</p><p>  cout<<"cannot open the input file!\n";</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p>  while(getline(infile,

121、s,'\n'))</p><p><b>  {</b></p><p>  int i = 0;</p><p>  skipWhiteSpace(s, &i);</p><p>  name = getName(s,&i);</p><p>  skipWhi

122、teSpace(s,&i);</p><p>  size = getSize(s,&i);</p><p>  fileTree = new Tree(name, size);</p><p>  if(name[0] == '*')</p><p><b>  {</b></p&

123、gt;<p>  treeArray[rear++] = fileTree;</p><p>  fileTree->parse();</p><p><b>  }</b></p><p>  fileTree->reSize();</p><p>  fileTree->outPut(

124、);</p><p>  delete fileTree;</p><p><b>  }</b></p><p>  infile.close();</p><p><b>  return 0;</b></p><p><b>  }</b><

溫馨提示

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

最新文檔

評論

0/150

提交評論