數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--編制一個(gè)演示集合的并、交和差運(yùn)算的程序_第1頁(yè)
已閱讀1頁(yè),還剩14頁(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>  實(shí)習(xí)報(bào)告</b></p><p>  題目:編制一個(gè)演示集合的并、交和差運(yùn)算的程序</p><p><b>  一、需求分析</b></p><p>  1. 本程序中,集合的元素限定為小寫字母字符 ['a'..'z'],集合的大小n<27。集合輸入的形式

2、為一個(gè)以"回車符"為結(jié)束標(biāo)志的字符串,串中字符順序不限,且允許出現(xiàn)重復(fù)字符或非法字符,程序應(yīng)能自動(dòng)濾去。輸出的運(yùn)算結(jié)果字符串中將不含重復(fù)字符或非法字符。</p><p>  2. 演示程序以用戶與計(jì)算機(jī)交互方式執(zhí)行,即在計(jì)算機(jī)終端上顯示"提示信息"之后,由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令;相應(yīng)的輸入數(shù)據(jù)(濾去輸入中的非法字符)和運(yùn)算結(jié)果顯示在其后。</p>

3、;<p>  3. 程序執(zhí)行的命令包括:</p><p>  (1)構(gòu)造集合1;(2)構(gòu)造集合2;(3)求并集;(4)求交集;(5)求差集;(6)結(jié)束。</p><p>  構(gòu)造集合1和構(gòu)造集合2時(shí),需以字符串的形式鍵入集合元素。</p><p><b>  4. 測(cè)試數(shù)據(jù)</b></p><p>  (1

4、) Setl="magazine",Set2="paper",</p><p>  Setl Set2="egimnprz",</p><p>  Setl Set2="ae",Setl-Set2="gimnz"</p><p>  (2) Setl=&quo

5、t;0120per4a6tion89",Set2="error data",</p><p>  Setl Set2="deinoprt",Setl set2="aeort",Setl-Set2="inp"</p><p><b>  二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p&g

6、t;<p>  為實(shí)現(xiàn)上述程序功能,應(yīng)以有序鏈表表示集合。為此,需要兩個(gè)抽象數(shù)據(jù)類型:有序表和集合。</p><p>  1. 有序表的抽象數(shù)據(jù)類型定義為:</p><p>  ADT OrderedList</p><p><b>  {</b></p><p>  數(shù)據(jù)對(duì)象:D={ai|aiCharS

7、et,i=1,2,...,n, n 0}</p><p>  數(shù)據(jù)關(guān)系:Rl={<ai-1,ai>|ai-1,aiD,ai-1<ai,i=2,...,n}</p><p><b>  基本操作:</b></p><p>  InitList(&L)</p><p>  操作結(jié)果:構(gòu)造一個(gè)空的有

8、序表L。</p><p>  DestroyList(&L)</p><p>  初始條件:有序表L已存在。</p><p>  操作結(jié)果:銷毀有序表L。</p><p>  ListLength(L)</p><p>  初始條件:有序表L已存在。</p><p>  操作結(jié)果:返回有

9、序表L的長(zhǎng)度。</p><p>  ListEmpty(L)</p><p>  初始條件:有序表L已存在。</p><p>  操作結(jié)果:若有序表L為空表,則返回True,否則返回 False。</p><p>  GetElem(L ,pos)</p><p>  初始條件:有序表 L 已存在。</p>

10、<p>  操作結(jié)果:若 1posLength(L),則返回表中第pos個(gè)數(shù)據(jù)元素。</p><p>  LocateElem(L,e , &q)</p><p>  初始條件:有序表L已存在。</p><p>  操作結(jié)果:若有序表L中存在元素e,則q指示L中第一個(gè)值為e的元素的位置,并返回函數(shù)值TRUE,否則q指示第一個(gè)大于 e 的元素的前

11、驅(qū)的位置 , 并返回函數(shù)值 FALSE。</p><p>  Append (&L,e)</p><p>  初始條件:有序表L已存在。</p><p>  操作結(jié)果:在有序表L的未尾插入元素e。</p><p>  InsertAfter(&L,q,e)</p><p>  初始條件:有序表L已存在,

12、q指示L中一個(gè)元素。</p><p>  操作結(jié)果:在有序表L中q指示的元素之后插入元素e。</p><p>  ListTraverse(q,visit())</p><p>  初始條件:有序表L已存在,q指示L中一個(gè)元素。</p><p>  操作結(jié)果:依次對(duì)L中q指示的元素開(kāi)始的每個(gè)元素調(diào)用函數(shù)visit()。</p>

13、<p>  }ADT OrderedList</p><p>  2. 集合的抽象數(shù)據(jù)類型定義為:</p><p><b>  ADT Set{</b></p><p>  數(shù)據(jù)對(duì)象:D={ai|ai為小寫英文字母且互不相同,i=l,2,...,n,0n26}</p><p>  數(shù)據(jù)關(guān)系:R1={}</

14、p><p>  基本操作:Createset(&T,Str)</p><p>  初始條件:Str為字符串。</p><p>  操作結(jié)果:生成一個(gè)由Str中小寫字母構(gòu)成的集合T。</p><p>  Destroyset(&T)</p><p>  初始條件:集合T已存在。</p><

15、p>  操作結(jié)果:銷毀集合T的結(jié)構(gòu)。</p><p>  Union(&T,SL S2)</p><p>  初始條件:集合S1和S2存在。</p><p>  操作結(jié)果:生成一個(gè)由Sl和S2的并集構(gòu)成的集合T。</p><p>  Intersection(&T,SL S2)</p><p> 

16、 初始條件:集合Sl和S2存在。</p><p>  操作結(jié)果:生成一個(gè)由Sl和S2的交集構(gòu)成的集合T。</p><p>  Difference(&T,S1,S2)</p><p>  初始條件:集合S1和S2存在。</p><p>  操作結(jié)果:生成一個(gè)由S1和S2的差集構(gòu)成的集合T。</p><p>  

17、Printset(T)</p><p>  初始條件:集合T已存在。</p><p>  操作結(jié)果:按字母次序順序顯示集合T的全部元素。</p><p><b>  }ADT Set</b></p><p><b>  三、概要設(shè)計(jì)</b></p><p>  1. 本程序包

18、含四個(gè)模塊</p><p><b>  1) 主程序模塊</b></p><p>  void main(){</p><p><b>  初始化:</b></p><p><b>  do{</b></p><p><b>  接受命令;&l

19、t;/b></p><p><b>  處理命令;</b></p><p>  }while("命令"!="退出")</p><p>  2) 集合單元模塊 實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型;</p><p>  3) 有序表單元模塊 實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型;</p>

20、<p>  4) 結(jié)點(diǎn)結(jié)構(gòu)單元模塊 定義有序表的結(jié)點(diǎn)結(jié)構(gòu)。</p><p>  各模塊之間的調(diào)用關(guān)系如下:</p><p><b>  四、詳細(xì)設(shè)計(jì)</b></p><p>  (一) 元素類型、結(jié)點(diǎn)類型和指針類型</p><p>  (1)typedef char ElemType; /*元素類型*/&

21、lt;/p><p> ?。?)typedef struct NodeType{</p><p>  ElemType data; </p><p>  NodeType *next;</p><p>  }NodeType,LinkType; /*結(jié)點(diǎn)類型,指針類型*/</p><p> ?。?)status Make

22、Node(LinkType &p,ElemType e)</p><p><b>  { </b></p><p>  /* 分配由p指向的數(shù)據(jù)元素為e、后繼為"空"的結(jié)點(diǎn),并返回 TRUE,擴(kuò)若分配失敗,則返回FALSE*/</p><p>  p=(LinkType)malloc(sizeof(NodeType)

23、;</p><p>  if(!p) return FALSE;</p><p>  p->data=e;</p><p>  p->next =NULL;</p><p>  return TRUE;</p><p><b>  }</b></p><p> 

24、?。?)void FreeNode(LinkType &p)</p><p><b>  {</b></p><p>  /* 釋放 p 所指結(jié)點(diǎn)*/</p><p><b>  }</b></p><p> ?。?)LinkType Copy(LinkType p)</p>

25、<p><b>  {</b></p><p>  /*復(fù)制生成和指針 p 所指結(jié)點(diǎn)有同值元素的新結(jié)點(diǎn)并返回,若分配空間失敗,則返回空指針。新結(jié)點(diǎn)的指針域?yàn)镹ULL */</p><p>  s=(LinkType)malloc(sizeof(NodeType))</p><p>  if(!s) return NULL;</p

26、><p>  s->data=p->data;</p><p>  s->next =NULL;</p><p><b>  return s;</b></p><p><b>  }</b></p><p> ?。?)ElemType Elem(LinkTyp

27、e p)</p><p><b>  {</b></p><p>  /*若指針p!=NULL,則返回p所指結(jié)點(diǎn)的數(shù)據(jù)元素,否則返回'#'*/</p><p><b>  }</b></p><p> ?。?)LinkType SuccNode(LinkType p)</p&g

28、t;<p><b>  {</b></p><p>  /*若指針p!=NULL,則返回指向p所指結(jié)點(diǎn)的后繼元素的指針,否則返回NULL*/</p><p><b>  }</b></p><p>  (二) 根據(jù)有序表的基本操作的特點(diǎn),有序表采用有序鏈表實(shí)現(xiàn)。鏈表設(shè)頭、尾兩個(gè)指針和表長(zhǎng)數(shù)據(jù)域,并附設(shè)頭結(jié)點(diǎn),

29、頭結(jié)點(diǎn)的數(shù)據(jù)域沒(méi)有實(shí)在意義。</p><p>  typedef struct</p><p><b>  {</b></p><p>  LinkType head,tail; /*分別指向線性鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)*/</p><p>  Int size; /*指示鏈表當(dāng)前的長(zhǎng)度*/</p><p

30、>  }OrderedList; /*有序鏈表類型*/</p><p>  1. 有序鏈表的基本操作定義如下:</p><p> ?。?)bool InitList(OrderedList &L);</p><p>  //構(gòu)造一個(gè)帶頭結(jié)點(diǎn)的空的有序鏈表L,并返回TRUE;</p><p>  //若分配空間失敗,則令L.he

31、ad為NULL,并返回FALSE;</p><p> ?。?)void DestroyList(OrderedList &L);</p><p>  // 擴(kuò)銷毀有序鏈表 L</p><p> ?。?)bool ListEmpty(OrderedList L);</p><p>  // 若L不存在或?yàn)?quot;空表"

32、,則返回TRUE,否則返回FALSE</p><p> ?。?)int ListLength(OrderedList L);</p><p>  // 返回鏈表的長(zhǎng)度</p><p> ?。?)LinkType GetElemPos(OrderedList L,tnt pos);</p><p>  // 若L存在且0<pos&l

33、t;L.size+1,則返回指向第pos個(gè)元素的指針,否則返回 NULL</p><p> ?。?)bool LocateElem(OrderedList L ,ElemType e ,LinkType &q);</p><p>  //若有序鏈表L存在且表中存在元素e,則q指示L中第一個(gè)值為 e的結(jié)點(diǎn)的位置,并返回TRUE;否則q指示第一個(gè)大于e的元素的前驅(qū)的位置,并返回FAL

34、SE</p><p> ?。?)void Append(OrderedList &L, LinkType s);</p><p>  //在已存在的有序鏈表L的末尾插入指針s所指結(jié)點(diǎn)</p><p> ?。?)void InsertAfter(OrderList &L, LinkType q, LinkType s);</p>&l

35、t;p>  //已存在的有序鏈表L中q所指示的結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)</p><p> ?。?)void ListTraverse(LinkType p,status(* visit)(LinkType q));</p><p>  //從p(p!=NULL)指示的結(jié)點(diǎn)開(kāi)始,依次對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit</p><p>  2. 其中部分操作的偽碼算

36、法如下:</p><p> ?。?)bool InitiList(OrderedList &L)</p><p><b>  {</b></p><p>  if(MakeNode(head,"))</p><p>  { //頭結(jié)點(diǎn)的虛設(shè)元素為空格符"</p><p&

37、gt;  L.tail =L.head; L.size =0; return TRUE;</p><p><b>  }</b></p><p><b>  else</b></p><p>  { L.head =NULL ;return FALSE ;}</p><p>  }//Init

38、List</p><p> ?。?)void DestroyList(OrderedList &L)</p><p><b>  {</b></p><p><b>  p=L.head;</b></p><p>  while(p){q=p; p=SuccNode(p); FreeNode

39、(q);}</p><p>  L.head =L.tail =NULL ;</p><p>  }//DestroyList</p><p> ?。?)LinkType GetElemPos(OrderedList L, int pos)</p><p><b>  {</b></p><p>

40、  if(!L.head||pos<1||pos>L.size) return NULL;</p><p>  else if(pos==L.size) return L.tail;</p><p><b>  else{</b></p><p>  p=L.head->next;</p><p>&

41、lt;b>  k=1;</b></p><p>  while(p&&k<pos){ p=SuccNode(p); k++;}</p><p><b>  return p;</b></p><p><b>  }</b></p><p>  }//GetEl

42、emPos;</p><p> ?。?)status LocateElem(OrderedList L, ElemType e,LinkType &p)</p><p><b>  {</b></p><p>  if(L.head)</p><p><b>  {</b></p&g

43、t;<p>  pre=L.head; p=pre->next;</p><p>  //pre指向*p的前驅(qū),p指向第一個(gè)元素結(jié)點(diǎn)</p><p>  white( p&&P->data<e)</p><p><b>  {</b></p><p>  pre=p; p=

44、SuccNode( p);</p><p><b>  }</b></p><p>  if(p&&p->data==e) return TRUE;</p><p>  else{p=pre; return FALSE;}</p><p><b>  }</b></p&g

45、t;<p>  else return FALSE;</p><p>  }//LocateElem</p><p>  (5)void Append(OrderedList &L, LinkType s)</p><p><b>  {</b></p><p>  if(L.head &

46、;&s)</p><p><b>  {</b></p><p>  if(L.tail!=L.head) L.tail->next =s;</p><p>  else L.head->next=s;</p><p>  L.tail =s; L.size++;</p><p&

47、gt;<b>  }</b></p><p>  } //Append</p><p> ?。?)void InsertAfter(OrderList &L,LinkType q,LinkType s)</p><p><b>  {</b></p><p>  if(L.head&am

48、p;&q&&s)</p><p><b>  {</b></p><p>  s->next=q->next; q->next =s;</p><p>  if(L.tail ==q) L.tail =s;</p><p><b>  L.size++;</b&g

49、t;</p><p><b>  }</b></p><p>  }//InsertAfter</p><p> ?。?)void ListTraverse(LinkType p, status (*visit)(LinkType q))</p><p><b>  {</b></p>

50、<p>  while(p){ visit(p); p=SuccNode(p);}</p><p>  }//ListTraverse</p><p> ?。ㄈ┘蟂et利用有序鏈表類型OrderedList來(lái)實(shí)現(xiàn),定義為有序集 OrderedSet;</p><p>  typedef OrderedList OrderedSet;</p>

51、;<p>  集合類型的基本操作的類C偽碼描述如下:</p><p> ?。?)void Createset(OderedSet &T,char *s)</p><p>  {//生成由串s中小寫字母構(gòu)成的集合T,IsLower是小寫字母判別函數(shù)</p><p>  if(InitList(T); //構(gòu)造空集T</p>&

52、lt;p>  for(i=l; i<=length(s); i++)</p><p>  if(islower(s[I])&&!LocateElem(T,s[I],p))</p><p>  //過(guò)濾重復(fù)元素并按字母次序大小插入</p><p>  if(MakeNode(q,s[i]))InsertAfter(T,p,q);</

53、p><p>  }// Createset</p><p> ?。?)void Destroyset(OrderedSet &T)</p><p>  { //銷毀集合T的結(jié)構(gòu)</p><p>  DestroyList(T);</p><p>  }//DestroyList</p><p&

54、gt; ?。?)void Union(OrderedSet &T,OrderedSet S1, OrderedSet S2)</p><p>  {//求已建成的集合Sl和S2的并集T,即:S1.head!=NULL且S2.head!=NULL</p><p>  if(InitList(T){</p><p>  pl=GetEiemPos(Sl,1

55、);</p><p>  p2=GetElemPos(S2,l);</p><p>  while(pl&&p2)</p><p><b>  {</b></p><p>  cl=Elem(pl); c2=Elem(p2);</p><p>  if(cl<=c2)<

56、;/p><p><b>  {</b></p><p>  Append(T,Copy(pl);</p><p>  pl=SuccNode(pl);</p><p>  if(cl==c2) p2=SuccNode(p2);</p><p><b>  }</b></p&

57、gt;<p><b>  else</b></p><p>  { Append(T,Copy(p2)); p2=SuccNode(p2); }</p><p><b>  while(pl)</b></p><p>  { Append( T,Copy(pl)); pl=SuccNode(pl);}&

58、lt;/p><p><b>  while(p2)</b></p><p>  {Append(T,Copy(p2)); p2=SuccNode(p2);}</p><p><b>  }</b></p><p><b>  }//Union</b></p><

59、;p>  (4)votd Intersection(OrderedSet &T,OrderedSet S1; OrderedSet S2)</p><p><b>  {</b></p><p>  //求集合 Sl 和 S2 的交集 T</p><p>  if(!InitList(T)) T.head =NULL;<

60、/p><p><b>  else{</b></p><p>  pl=GetElemPos(S1,1);</p><p>  p2=GetElemPos(S2,l);</p><p>  while(pl&&p2){</p><p>  c1=Elem(p1);</p>

61、<p>  c2=Elem(p2);</p><p>  if(cl<c2) pl=SuccNode(pl);</p><p>  else if(cl>c2) p2=SuccNode(p2);</p><p>  else{ //cl==c2</p><p>  Append(T,Copy(pl));</p&

62、gt;<p>  pl=SuccNode(pl);</p><p>  p2=SuccNode(p2);</p><p><b>  }//else</b></p><p><b>  }//while</b></p><p><b>  }// else</b>

63、</p><p>  }//Intersection</p><p> ?。?)void Difference(OrderedSet &T,OrderedSet S1,OrderedSet S2)</p><p>  {//求集合Sl和S2的差集T</p><p>  if(!InitList(T)) T.head =NULL;<

64、;/p><p><b>  else {</b></p><p>  pl =GetElemPos(S1,l);p2=GetElemPos(S2,1);</p><p>  while(pl&&p2)</p><p><b>  {</b></p><p>  c

65、l=Elem(pl);c2=Elem(p2);</p><p>  if(cl<c2){</p><p>  Append(T,Copy(pl));</p><p>  pl=SuccNode(pl)</p><p>  else if(cl>c2) p2=SuccNode(p2);</p><p>  e

66、lse // Cl ==c2</p><p>  {pl =SuccNode(p1);p2=SuccNode(p2);}</p><p><b>  }//while</b></p><p><b>  while(pl)</b></p><p><b>  {</b><

67、/p><p>  Apend(T,Copy(pl));</p><p>  p =SuccNode(pl);</p><p><b>  }</b></p><p><b>  }//else</b></p><p>  }//Difference</p><

68、p> ?。?)void WriteSetElem(LinkType p)</p><p>  {//顯示集合的一個(gè)元素</p><p>  pramtk'Jh WriteElem(Elem(p));</p><p>  }//WriteSetElem</p><p> ?。?)votd Printset(OrderedSet T

69、)</p><p>  {//顯示集合的全部元素</p><p>  p=GetElemPos(T,1);</p><p>  printf('[']);</p><p><b>  if(p){</b></p><p>  WriteElem(Elem(p);</p>

70、<p>  p=SuccNode(p);</p><p><b>  }</b></p><p>  ListTraverse(p,WriteSetElem());</p><p>  Prtntf(')]');</p><p>  }//Printset</p><p&

71、gt; ?。ㄋ模?主函數(shù)和其他函數(shù)的偽碼算法</p><p> ?。?)void main()</p><p><b>  {// 主函數(shù)</b></p><p>  Initialization(); //初始化</p><p><b>  do{</b></p><p>

72、;  ReadCommand(cmd);//讀入一個(gè)操作命令符</p><p>  Interpret(cmd); //解釋執(zhí)行操作命令符</p><p>  }while(cmd!='q'&&cmd!='Q') ;</p><p><b>  }//main</b></p>&l

73、t;p> ?。?)void Initialization()</p><p><b>  {//系統(tǒng)初始化</b></p><p>  clrscr(); //清除在屏幕上方顯示操作命令清單</p><p>  //Makesetl--------l</p><p>  //Maltesed--------2&l

74、t;/p><p>  //Union-----------U</p><p>  //Intersaction-----I</p><p>  //Difference------d</p><p>  //Quit--------------q</p><p>  //在屏幕下方顯示操作命令提示框;</p>

75、<p>  Createset(Set1,"); Createset(Set2,");</p><p>  }//Initialization</p><p> ?。?)Printset(Set1); Printset(Setl);</p><p>  //構(gòu)造并顯示空集Set1和Set2空集</p><p>

76、 ?。?)void ReadCommand(char cmd)</p><p>  { //讀入操作命令符,顯示鍵入操作命令符的提示信息;</p><p>  do (cmd=getch())</p><p>  while (cmd['1','2','u', 'U', 'i', 

77、9;I','d','D,'q','Q']) ;</p><p><b>  }</b></p><p> ?。?)void Interpret (char cmd)</p><p>  {// 解釋執(zhí)行操作命令cmd</p><p>  switch(cmd

78、)</p><p><b>  {</b></p><p>  case 'l': //顯示以串的形式鍵入集合元素的提示信息;</p><p>  scanf('讀入集合元素到串變量',v);</p><p>  Createset(Set1,v);</p><p&g

79、t;  Printset(Setl); //構(gòu)造并顯示有序集Setl</p><p><b>  Break;</b></p><p>  case '2': //顯示以串的形式鍵入集合元素的提示信息;</p><p>  scanf('讀入集合元素到串變量',v);</p><p>

80、  Createset(Set2,v);</p><p>  Printset(Set2); //構(gòu)造并顯示有序集Set2</p><p><b>  Break;</b></p><p><b>  case 'U':</b></p><p><b>  case 

81、9;u':</b></p><p>  Union(Set3,Set1,Set2); //求有序集Set1和Set2的并集Set3</p><p>  Printset(Set3); //顯示并集 Set3</p><p>  DestroyList(Set3);//銷毀并集Set3</p><p><b>

82、  Break;</b></p><p><b>  case 'i':</b></p><p><b>  case 'I':</b></p><p>  Intersection(Set3,Set1,Set2); //求有序集Setl和Set2的交集Set3</p>

83、;<p>  Printset(Set3);</p><p>  Destroy(set3);</p><p><b>  break;</b></p><p><b>  case 'd':</b></p><p><b>  case 'D'

84、;:</b></p><p>  Difference(Set3,Set1,Set2);//求集合Setl和Set2的差集Set3</p><p>  Printset(Set3); DestroyList(Set3);</p><p><b>  }//switch</b></p><p>  }//Int

85、erpret</p><p>  5. 函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu) :</p><p><b>  五、程序調(diào)試與運(yùn)行</b></p><p>  1. 本程序的運(yùn)行環(huán)境為XP下的仿真DOS系統(tǒng),執(zhí)行文件為 SetDemo.exe</p><p>  2. 進(jìn)入演示程序后即顯示文本方式的用戶界面;</

86、p><p>  ************************</p><p>  * Makesetl--------------l *</p><p>  * Maltesed--------------2 *</p><p>  * Union-----------------U *</p><p>

87、  * Intersaction-----------I *</p><p>  * Difference------------d *</p><p>  * Quit--------------------q *</p><p>  ************************</p><p>  Enter a oper

88、ation code E 1,2,u ,J, d OR q:</p><p>  3. 進(jìn)入"構(gòu)造集合1<Makesetl>"和"構(gòu)造集合2<Makeset2>"的命令后,即提示鍵入集合元素串,結(jié)束符為"回車符"。</p><p>  4. 接受其他命令后即執(zhí)行相應(yīng)運(yùn)算和顯示相應(yīng)結(jié)果。</p>

89、<p><b>  六、測(cè)試結(jié)果</b></p><p><b>  執(zhí)行命令1</b></p><p>  鍵入magazine后,構(gòu)造集合Setl[a,e,g,i,m,z]</p><p><b>  執(zhí)行命令2</b></p><p>  鍵入paper后,構(gòu)

90、造集合Set2[a.e,p,r]</p><p><b>  執(zhí)行命令d</b></p><p>  構(gòu)造集合Setl和Set2的并集[a,e,g,i,m,p ,r,z]</p><p><b>  執(zhí)行命令I(lǐng)</b></p><p>  構(gòu)造集合 Setl 和 Set2 的交集 [a,e]<

91、/p><p><b>  執(zhí)行命令d</b></p><p>  構(gòu)造集合 Setl 和 Set2 的差集[gim];</p><p><b>  七、設(shè)計(jì)結(jié)果分析</b></p><p>  1. 由于對(duì)集合的三種運(yùn)算的算法推敲不足,在有序鏈表類型的早期版本未設(shè)置尾指針和Append操作,導(dǎo)致算法低效

92、。</p><p>  2. 剛開(kāi)始時(shí)曾忽略了一些變量參數(shù)的標(biāo)識(shí)"&",使調(diào)試程序時(shí)費(fèi)時(shí)不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識(shí)。</p><p>  3. 本程序的模塊劃分比較合理,且盡可能將指針的操作封裝在結(jié)點(diǎn)和鏈表的兩個(gè)模塊中,致使集合模塊的調(diào)試比較順利。反之,如此劃分的模塊并非完全合理,因?yàn)樵趯?shí)現(xiàn)集合操作的編碼中仍然需要判別指針是否為空。按理

93、,兩個(gè)鏈表的并、交和差的操作也應(yīng)封裝在鏈表的模塊中,而在集合的模塊中,只要進(jìn)行相應(yīng)的應(yīng)用即可。</p><p>  4. 算法的時(shí)空分析</p><p>  l)由于有序表采用帶頭結(jié)點(diǎn)的有序單鏈表,并增設(shè)尾指針和表的長(zhǎng)度兩個(gè)標(biāo)識(shí),各種操作的算法時(shí)間復(fù)雜度比較合理。InitList,ListEmpty,Listlength,Append和InsertAfter以及確定鏈表中第一個(gè)結(jié)點(diǎn)和之后一

94、個(gè)結(jié)點(diǎn)的位置都是O(l),DestroyList,LocateElem和TraverseList及確定鏈表中間結(jié)點(diǎn)的位置等則是O(n)的,n為鏈表長(zhǎng)度。</p><p>  2)基于有序鏈表實(shí)現(xiàn)的有序集的各種運(yùn)算和操作的時(shí)間復(fù)雜度分析如下:構(gòu)造有序集算法Createset 讀入n個(gè)元素,逐個(gè)用 LocateElem判定不在當(dāng)前集合中及確定插入位置后,才用InsertAfter 插入到有序集中,所以時(shí)間復(fù)雜度是O(

95、n2)。</p><p>  求并集算法Union利用集合的"有序性"將兩個(gè)集合的m+n個(gè)元素不重復(fù)地依次利用Append插入到當(dāng)前并集的末尾,故可在O(m+n) 時(shí)間內(nèi)完成。</p><p>  可對(duì)求交集算法Intersection和求差集算法Difference作類似地分析,它們也是O(m+n)。</p><p>  銷毀集合算法Destr

96、oyset和顯示集合算法Printset都是對(duì)每個(gè)元素調(diào)用一個(gè)O(1)的函數(shù),因此都是O(n)。</p><p>  除了構(gòu)造有序集算法CreateSet用一個(gè)串變量讀入n個(gè)元素,需要O(n)的輔助空間外,其余算法使用的輔助空間與元素個(gè)數(shù)無(wú)關(guān),即是O(0)。</p><p>  5. 本實(shí)習(xí)作業(yè)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法,將程序劃分為四個(gè)層次結(jié)構(gòu);元素結(jié)點(diǎn)、有序鏈表、有序集和主控模塊。使得

97、設(shè)計(jì)時(shí)思路清晰,實(shí)現(xiàn)時(shí)調(diào)試順利。各模塊具有較好的可重用性。確實(shí)得到了一次良好的程序設(shè)計(jì)訓(xùn)練。</p><p>  八、附錄 源程序文件名清單</p><p>  Node.H //元素結(jié)點(diǎn)實(shí)現(xiàn)單元。</p><p>  List.H //有序鏈表實(shí)現(xiàn)單元</p><p>  Orderset.H //有序集實(shí)現(xiàn)單元</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)論