數(shù)據(jù)結(jié)構(gòu)課程設計--編制一個演示集合的并、交和差運算的程序

1、精品文檔數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設 計 說 明 書課題：編制一個演示集合的并、交和差運算的程序班級：11軟件二姓名：張三學號：時間：計算機信息工程學院歡迎下載精品文檔一、需求分析1. 本程序中，集合的元素限定為小寫字母字符 'a'.'z'，集合的大小n<27。集合輸入的形式為一個以"回車符"為結(jié)束標志的字符串，串中字符順序不限，且允許出現(xiàn)重復字符或非法字符，程序應能自動濾去。輸出的運算結(jié)果字符串中將不含重復字符或非法字符。2. 演示程序以用戶與計算機交互方式執(zhí)行，即在計算機終端上顯示"提示信息"之后，由用戶在鍵盤上輸

2、入演示程序中規(guī)定的運算命令；相應的輸入數(shù)據(jù)(濾去輸入中的非法字符)和運算結(jié)果顯示在其后。3. 程序執(zhí)行的命令包括：(1)構(gòu)造集合1；(2)構(gòu)造集合2；(3)求并集；(4)求交集；(5)求差集；(6)結(jié)束。構(gòu)造集合1和構(gòu)造集合2時，需以字符串的形式鍵入集合元素。4. 測試數(shù)據(jù)(1) Setl="magazine"，Set2="paper"，Setl È Set2="egimnprz"，Setl Ç Set2="ae"，Setl-Set2="gimnz"(2) Setl=&quo

3、t;0120per4a6tion89"，Set2="error data"，Setl È Set2="deinoprt"，Setl Ç set2="aeort"，Setl-Set2="inp"二、概要設計為實現(xiàn)上述程序功能，應以有序鏈表表示集合。為此，需要兩個抽象數(shù)據(jù)類型：有序表和集合。1. 有序表的抽象數(shù)據(jù)類型定義為：ADT OrderedList數(shù)據(jù)對象：D=ai|aiÎCharSet，i=1,2,.,n, n³ 0數(shù)據(jù)關系：Rl=<ai-1,ai>

4、|ai-1,aiÎD,ai-1<ai,i=2,.,n根本操作：InitList(&L)操作結(jié)果：構(gòu)造一個空的有序表L。DestroyList(&L)初始條件：有序表L已存在。操作結(jié)果：銷毀有序表L。ListLength(L)初始條件：有序表L已存在。操作結(jié)果：返回有序表L的長度。ListEmpty(L)初始條件：有序表L已存在。操作結(jié)果：假設有序表L為空表，那么返回True，否那么返回 False。GetElem(L ,pos)初始條件：有序表 L 已存在。操作結(jié)果：假設 1£pos£Length(L)，那么返回表中第pos個數(shù)據(jù)元素。Loc

5、ateElem(L,e , &q)初始條件：有序表L已存在。操作結(jié)果：假設有序表L中存在元素e，那么q指示L中第一個值為e的元素的位置，并返回函數(shù)值TRUE，否那么q指示第一個大于 e 的元素的前驅(qū)的位置 , 并返回函數(shù)值 FALSE。Append (&L,e)初始條件：有序表L已存在。操作結(jié)果：在有序表L的未尾插入元素e。InsertAfter(&L,q,e)初始條件：有序表L已存在，q指示L中一個元素。操作結(jié)果：在有序表L中q指示的元素之后插入元素e。ListTraverse(q,visit()初始條件：有序表L已存在，q指示L中一個元素。操作結(jié)果：依次對L中q指示

6、的元素開始的每個元素調(diào)用函數(shù)visit()。ADT OrderedList2. 集合的抽象數(shù)據(jù)類型定義為：ADT Set數(shù)據(jù)對象：D=ai|ai為小寫英文字母且互不相同，i=l,2,.,n,0£n£26數(shù)據(jù)關系：R1=根本操作：Createset(&T,Str)初始條件：Str為字符串。操作結(jié)果：生成一個由Str中小寫字母構(gòu)成的集合T。Destroyset(&T)初始條件：集合T已存在。操作結(jié)果：銷毀集合T的結(jié)構(gòu)。Union(&T,SL S2)初始條件：集合S1和S2存在。操作結(jié)果：生成一個由Sl和S2的并集構(gòu)成的集合T。Intersection(&

7、amp;T,SL S2)初始條件：集合Sl和S2存在。操作結(jié)果：生成一個由Sl和S2的交集構(gòu)成的集合T。Difference(&T,S1,S2)初始條件：集合S1和S2存在。操作結(jié)果：生成一個由S1和S2的差集構(gòu)成的集合T。Printset(T)初始條件：集合T已存在。操作結(jié)果：按字母次序順序顯示集合T的全部元素。ADT Set3. 本程序包含四個模塊1) 主程序模塊void main()初始化：do接受命令；處理命令；while("命令"!="退出")2) 集合單元模塊 實現(xiàn)集合的抽象數(shù)據(jù)類型；3) 有序表單元模塊 實現(xiàn)有序表的抽象數(shù)據(jù)類型；4

8、) 結(jié)點結(jié)構(gòu)單元模塊 定義有序表的結(jié)點結(jié)構(gòu)。各模塊之間的調(diào)用關系如下：三、詳細設計1. 元素類型、結(jié)點類型和指針類型typedef char ElemType; /*元素類型*/typedef struct NodeTypeElemType data; NodeType *next;NodeType,LinkType; /*結(jié)點類型,指針類型*/status MakeNode(LinkType &p,ElemType e) /* 分配由p指向的數(shù)據(jù)元素為e、后繼為"空"的結(jié)點,并返回 TRUE,假設分配失敗,那么返回FALSE*/p=(LinkType)malloc

9、(sizeof(NodeType);if(!p) return FALSE;p->data=e;p->next =NULL;return TRUE;void FreeNode(LinkType &p)/* 釋放 p 所指結(jié)點*/LinkType Copy(LinkType p)/*復制生成和指針 p 所指結(jié)點有同值元素的新結(jié)點并返回,假設分配空間失敗,那么返回空指針。新結(jié)點的指針域為NULL */s=(LinkType)malloc(sizeof(NodeType)if(!s) return NULL;s->data=p->data;s->next =NU

10、LL;return s;ElemType Elem(LinkType p)/*假設指針p!=NULL,那么返回p所指結(jié)點的數(shù)據(jù)元素,否那么返回'#'*/LinkType SuccNode(LinkType p)/*假設指針p!=NULL,那么返回指向p所指結(jié)點的后繼元素的指針,否那么返回NULL*/2. 有序表根本操作根據(jù)有序表的根本操作的特點，有序表采用有序鏈表實現(xiàn)。鏈表設頭、尾兩個指針和表長數(shù)據(jù)域，并附設頭結(jié)點，頭結(jié)點的數(shù)據(jù)域沒有實在意義。typedef struetLinkType head,tail; /*分別指向線性鏈表的頭結(jié)點和尾結(jié)點*/Int size; /*指示

11、鏈表當前的長度*/OrderedList; /*有序鏈表類型*/ 有序鏈表的根本操作定義如下：bool InitList(OrderedList &L);/構(gòu)造一個帶頭結(jié)點的空的有序鏈表L,并返回TRUE;/假設分配空間失敗,那么令L.head為NULL,并返回FALSE;void DestroyList(OrderedList &L);/ 擴銷毀有序鏈表 Lbool ListEmpty(OrderedList L);/ 假設L不存在或為"空表"，那么返回TRUE，否那么返回FALSEint ListLength(OrderedList L);/ 返回鏈表的

12、長度LinkType GetElemPos(OrderedList L，tnt pos);/ 假設L存在且0<pos<L.size+1，那么返回指向第pos個元素的指針，否那么返回 NULLbool LocateElem(OrderedList L ,ElemType e ,LinkType &q);/假設有序鏈表L存在且表中存在元素e,那么q指示L中第一個值為 e的結(jié)點的位置，并返回TRUE；否那么q指示第一個大于e的元素的前驅(qū)的位置，并返回FALSEvoid Append(OrderedList &L, LinkType s);/在已存在的有序鏈表L的末尾插入指

13、針s所指結(jié)點void InsertAfter(OrderList &L, LinkType q, LinkType s);/已存在的有序鏈表L中q所指示的結(jié)點之后插入指針s所指結(jié)點void ListTraverse(LinkType p,status(* visit)(LinkType q);/從p(p!=NULL)指示的結(jié)點開始，依次對每個結(jié)點調(diào)用函數(shù)visit其中局部操作的偽碼算法如下:bool InitiList(OrderedList &L)if(MakeNode(head,") /頭結(jié)點的虛設元素為空格符"L.tail =L.head; L.siz

14、e =0; return TRUE;else L.head =NULL ;return FALSE ;/InitList void DestroyList(OrderedList &L)p=L.head;while(p)q=p; p=SuccNode(p); FreeNode(q);L.head =L.tail =NULL ;/DestroyListLinkType GetElemPos(OrderedList L, int pos)if(!L.head|pos<1|pos>L.size) return NULL;else if(pos=L.size) return L.t

15、ail;elsep=L.head->next;k=1;while(p&&k<pos) p=SuccNode(p); k+;return p;/GetElemPos;status LocateElem(OrderedList L, ElemType e,LinkType &p)if(L.head)pre=L.head; p=pre->next;/pre指向*p的前驅(qū),p指向第一個元素結(jié)點white( p&&P->data<e)pre=p; p=SuccNode( p);if(p&&p->data=e) r

16、eturn TRUE;elsep=pre; return FALSE;else return FALSE;/LocateElemvoid Append(OrderedList &L, LinkType s)if(L.head &&s)if(L.tail!=L.head) L.tail->next =s;else L.head->next=s;L.tail =s; L.size+; /Appendvoid InsertAfter(OrderList &L,LinkType q,LinkType s)if(L.head&&q&&a

17、mp;s)s->next=q->next; q->next =s;if(L.tail =q) L.tail =s;L.size+;/InsertAftervoid ListTraverse(LinkType p, status (*visit)(LinkType q)while(p) visit(p); p=SuccNode(p);/ListTraverse3.集合的操作集合Set利用有序鏈表類型OrderedList來實現(xiàn),定義為有序集 OrderedSet;typedef OrderedList OrderedSet;集合類型的根本操作的類C偽碼描述如下:void Cre

18、ateset(OderedSet &T,char *s)/生成由串s中小寫字母構(gòu)成的集合T,IsLower是小寫字母判別函數(shù)if(InitList(T); /構(gòu)造空集Tfor(i=l; i<=length(s); i+)if(islower(sI)&&!LocateElem(T,sI,p)/過濾重復元素并按字母次序大小插入if(MakeNode(q,si)InsertAfter(T,p,q);/ Createsetvoid Destroyset(OrderedSet &T) /銷毀集合T的結(jié)構(gòu)DestroyList(T);/DestroyListvoid

19、Union(OrderedSet &T,OrderedSet S1, OrderedSet S2)/求已建成的集合Sl和S2的并集T,即:S1.head!=NULL且S2.head!=NULLif(InitList(T)pl=GetEiemPos(Sl,1);p2=GetElemPos(S2,l);while(pl&&p2)cl=Elem(pl); c2=Elem(p2);if(cl<=c2)Append(T,Copy(pl);pl=SuccNode(pl);if(cl=c2) p2=SuccNode(p2);else Append(T,Copy(p2); p2=

20、SuccNode(p2); while(pl) Append( T,Copy(pl); pl=SuccNode(pl);while(p2)Append(T,Copy(p2); p2=SuccNode(p2);/Unionvotd Intersection(OrderedSet &T,OrderedSet S1; OrderedSet S2)/求集合 Sl 和 S2 的交集 Tif(!InitList(T) T.head =NULL;elsepl=GetElemPos(S1,1);p2=GetElemPos(S2,l);while(pl&&p2)c1=Elem(p1);c

21、2=Elem(p2);if(cl<c2) pl=SuccNode(pl);else if(cl>c2) p2=SuccNode(p2);else /cl=c2Append(T,Copy(pl);pl=SuccNode(pl);p2=SuccNode(p2);/else/while/ else/Intersectionvoid Difference(OrderedSet &T,OrderedSet S1,OrderedSet S2)/求集合Sl和S2的差集Tif(!InitList(T) T.head =NULL;else pl =GetElemPos(S1,l);p2=Ge

22、tElemPos(S2,1);while(pl&&p2)cl=Elem(pl);c2=Elem(p2);if(cl<c2)Append(T,Copy(pl);pl=SuccNode(pl)else if(cl>c2) p2=SuccNode(p2);else / Cl =c2pl =SuccNode(p1);p2=SuccNode(p2);/whilewhile(pl)Apend(T,Copy(pl);p =SuccNode(pl);/else/Differencevoid WriteSetElem(LinkType p)/顯示集合的一個元素pramtk'J

23、h WriteElem(Elem(p);/WriteSetElemvotd Printset(OrderedSet T)/顯示集合的全部元素p=GetElemPos(T,1);printf('');if(p)WriteElem(Elem(p);p=SuccNode(p);ListTraverse(p,WriteSetElem();Prtntf(')');/Printset4. 主函數(shù)和其他函數(shù)的偽碼算法void main()/ 主函數(shù)Initialization(); /初始化doReadCommand(cmd);/讀入一個操作命令符Interpret(cmd)

24、; /解釋執(zhí)行操作命令符while(cmd!='q'&&cmd!='Q') ;/mainvoid Initialization()/系統(tǒng)初始化clrscr(); /去除在屏幕上方顯示操作命令清單/Makesetl-l/Maltesed-2/Union-U/Intersaction-I/Difference-d/Quit-q/在屏幕下方顯示操作命令提示框;Createset(Set1,"); Createset(Set2,");/InitializationPrintset(Set1); Printset(Setl);/構(gòu)造并顯

25、示空集Set1和Set2空集void ReadCommand(char cmd) /讀入操作命令符,顯示鍵入操作命令符的提示信息;do (cmd=getch()while (cmd'1','2','u', 'U', 'i', 'I','d','D,'q','Q') ;void Interpret (char cmd)/ 解釋執(zhí)行操作命令cmdswitch(cmd)case 'l': /顯示以串的形式鍵入集合元素的提示信息;sca

26、nf('讀入集合元素到串變量',v);Createset(Set1,v);Printset(Setl); /構(gòu)造并顯示有序集SetlBreak;case '2': /顯示以串的形式鍵入集合元素的提示信息;scanf('讀入集合元素到串變量',v);Createset(Set2,v);Printset(Set2); /構(gòu)造并顯示有序集Set2Break;case 'U':case 'u':Union(Set3,Set1,Set2); /求有序集Set1和Set2的并集Set3Printset(Set3); /顯示并集

27、 Set3DestroyList(Set3);/銷毀并集Set3Break;case 'i':case 'I':Intersection(Set3,Set1,Set2); /求有序集Setl和Set2的交集Set3Printset(Set3);Destroy(set3);break;case 'd':case 'D':Difference(Set3,Set1,Set2);/求集合Setl和Set2的差集Set3Printset(Set3); DestroyList(Set3);/switch/Interpret5. 函數(shù)的調(diào)用關系

28、圖函數(shù)的調(diào)用關系圖反映了演示程序的層次結(jié)構(gòu) :XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 四、調(diào)試分析1. 由于對集合的三種運算的算法推敲缺乏,在有序鏈表類型的早期版本未設置尾指針和Append操作,導致算法低效。2. 剛開始時曾忽略了一些變量參數(shù)的標識"&"，使調(diào)試程序時費時不少。今后應重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。3. 本程序的模塊劃分比擬合理,且盡可能將指針的操作封裝在結(jié)點和鏈表的兩個模塊中，致使集合模塊的調(diào)試比擬順利。反之，如此劃分的模塊并非完全合理，因為在實現(xiàn)集合操作的編碼中仍然需要判別指針是否為空。按理

29、，兩個鏈表的并、交和差的操作也應封裝在鏈表的模塊中，而在集合的模塊中，只要進行相應的應用即可。4. 算法的時空分析l)由于有序表采用帶頭結(jié)點的有序單鏈表，并增設尾指針和表的長度兩個標識，各種操作的算法時間復雜度比擬合理。InitList,ListEmpty,Listlength,Append和InsertAfter以及確定鏈表中第一個結(jié)點和之后一個結(jié)點的位置都是O(l)，DestroyList，LocateElem和TraverseList及確定鏈表中間結(jié)點的位置等那么是O(n)的，n為鏈表長度。2)基于有序鏈表實現(xiàn)的有序集的各種運算和操作的時間復雜度分析如下：構(gòu)造有序集算法Createset 讀入n個元素，逐個用 LocateElem判定不在當前集合中及確定插入位置后，才用Ins