版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 集合的并、交和差運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--集合的并、交和差運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--集合的并、交和差運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)集合的交并差運(yùn)算
- 數(shù)據(jù)庫(kù)課程設(shè)計(jì)---集合交、并、差、對(duì)稱差運(yùn)算
- java語(yǔ)言課程設(shè)計(jì)--集合的并、交和差運(yùn)算
- 西安石油大學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告--設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器和集合的并,交和差運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(集合交集并集運(yùn)算)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--文章編輯集合運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)----集合運(yùn)算課程設(shè)計(jì)報(bào)告(c++)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---一個(gè)銀行業(yè)務(wù)模擬的程序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--- 數(shù)據(jù)結(jié)構(gòu)各章算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 稀疏矩陣的運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--大整數(shù)的運(yùn)算
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---以鄰接鏈表的方式確定一個(gè)無(wú)向網(wǎng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--內(nèi)部排序演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--廣義表運(yùn)算的驗(yàn)算設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論