集合的并,交和差運算數(shù)據(jù)結(jié)構(gòu)C課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)C+課程設(shè)計題 目:集合的并、交和差運算一、設(shè)計題目集合的并、交和差運算二、小組成員分工說明一個人三、需求分析1）運行環(huán)境（軟、硬件環(huán)境）軟件環(huán)境：Microsoft Vista操作系統(tǒng)，Visual C+ 6.0硬件環(huán)境：2.0GB內(nèi)存2）輸入的形式和輸入值的范圍運行所給的測試數(shù)據(jù)，集合的元素限定為小寫字符a. .z：第一組： Set1 = magazine , Set2 = paper第二組：Set1 = 0120per4a6tion89 , Set2 = error data輸出的形式描述程序運行并、交和差運算后得到數(shù)據(jù)，輸出字符。3）功能描述能演示執(zhí)行集合的并、交和差運算。4）

2、測試數(shù)據(jù) Set1 = magazine , Set2 = paper,Set1 U Set2 = aeginmprz , Set1 A Set2 = ae, Set1 Set2 = gimnz。（2） Set1= 0120per4a6tion89 , Set2 = error data ,Set1 U Set2=adeinoprt , Set1 A Set2 =aeort , Set1 Set2 = inp。四、概要設(shè)計1）抽象數(shù)據(jù)類型定義描述（順序表的抽象數(shù)據(jù)類型描述）ADT Seqlist isData線性表的長度Operati onSeqlist初始化值：無動作：置順序表的長度為0Le

3、n gth輸入：無前置條件：表已存在功能：求表的長度輸出：返回表的長度，即表中數(shù)據(jù)元素的個數(shù) 后置條件：表不變Get輸入：元素的序號 i 前置條件：表已存在， i 合法 功能：在表中取序號為 i 的數(shù)據(jù)元素 輸出：若 i 合法，返回序號為 i 的元素值，否則拋出異常 后置條件：表不變Locate 輸入：數(shù)據(jù)元素 item 前置條件：表已存在 功能：在線性表中查找值等于 item 的元素 輸出：若查找成功，返回 x 在表中的序號，否則返回 0 后置條件：表不變Insert 輸入：插入位置 i ；待插元素 item 前置條件：表已存在 ,i 合法 功能：在表的第 i 個位置處插入一個新元素 x 輸

4、出：若插入不成功，拋出異常 后置條件：若插入成功，表中增加一個新元素Delete 輸入：刪除位置 i 前置條件：表已存在 功能：刪除表中的第 i 個元素 輸出：若刪除成功，返回被刪元素，否則拋出異常 后置條件：若刪除成功，表中減少一個元素Empty 輸入：無 前置條件：表已存在 功能：判斷表是否為空 輸出：若是空表，返回 1，否則返回 0 后置條件：表不變Clear 輸入：無 前置條件：無 功能：清空順序表 輸出：無 后置條件：表的長度是 0end ADT seqList2）功能模塊設(shè)計（如主程序模塊設(shè)計）3)模塊層次調(diào)用關(guān)系圖mai nbinjiaocha五、詳細設(shè)計實現(xiàn)概要設(shè)計中定義的所有

5、的類的定義及類中成員函數(shù)，并對主要的模塊 寫出偽碼算法。1、順序表存儲結(jié)構(gòu)的定義。2、成員函數(shù)類的定義。3、并、交和差三個操作函數(shù)的實現(xiàn)。1)并運算：將B中的元素插到A后面后形成新的集合，定義字符i在a到 z之間，并將新的集合中的個元素與i進行比較，若相同則將此時i的值插入C 中作為輸出值，若不同則i+繼續(xù)比較。template vclass T>SeqList<T> bin(SeqList<T> A,SeqListvT> B)SeqList<T> C;int m=1;int a=A.Length();for (int b=0;b<=B.

6、Length();b+)Ansert(a+b+1,B.Get(b);將B的元素插到的 A的后面成組合for(char i='a'iv='z'i+) 定義字符 i 在 a 到 z 之間for (int d=0;dv=A.Length();d+)if (A.Get(d)=i)取組合后元素將元素與i進行比較 C. Insert(m,i);/ 相同的插入 Cm+;/ 不相同繼續(xù) break;return C;2)交運算：定義定義字符 i 在 a 到 z 之間，先將 i 與 A 中數(shù)據(jù)元素進行比 較，再將 i 與 B 中元素進行比較，如果兩次比較都有與i 相同的元素，則將

7、該 i值插入 C 中作為輸出。template <class T>SeqList<T> jiao(SeqList<T> A,SeqList<T> B)SeqList<T> C;int m=1;int flag=0;for(char i='a'iv='z'i+,flag=0) 定義字符 i 在 a 到 z 之間for (int a=0;av=A.Length();a+)if (A.Get(a)=i)將i與A中元素進行比較for (int b=0;bv=B.Length();b+)if (B.Get(b)=

8、i)將i與B中元素進行比較Cnsert(m,i);兩次比較都有與i相同的元素，則將i 插入 Cm+;flag=1;break;if (flag=1)break;return C;3) 差運算：定義字符i在a到z之間，先將i與A中數(shù)據(jù)元素進行比較， 如果相同，再將i與B中元素進行比較，如果不同則將i插入C作為輸出。template <class T>SeqList<T> cha(SeqList<T> A,SeqList<T> B)SeqList<T> C;int m=1;int flag=0;for(char i='a'

9、iv='z'i+,flag=0) 定義字符 i 在 a 到 z 之間for (int a=0;av=A.Length();a+)if (A.Get(a)=i)將i與A中元素進行比較for (int b=0;bv=B.Length();b+)if (B.Get(b)=i)如果i與A中元素相同，則將i與a中 元素進行比較flag=m;if(flag=0)Cnsert(m,i);如果不同則將i插入Cm+;break;return C;4、 main 函數(shù)。int main()char a50;char b50;coutvv"Set1:"輸入 set1 數(shù)據(jù)cin.

10、getline(b,'/0'); /所給數(shù)據(jù)中有空格，所以不能直接用cincoutvvendl;coutvv"Set2:"輸入 set2數(shù)據(jù)cin.getline(a,'/0');coutvvendl;SeqListvchar> A(a,50),B(b,50),C,D,E;C=bin(A,B);調(diào)用集合的并運算coutvv"Set1 U Set2="C. display();coutvvendl;D=jiao(A,B);調(diào)用集合的交運算coutvv"Set1 A Set2="D. display(

11、);coutvvendl;E=cha(B,A);調(diào)用集合的差運算coutvv"Set1-Set2="E. display(); coutvvendl; return 0;六、調(diào)試分析包括調(diào)試過程中遇到的問題及解決的方法、算法的時間空間復(fù)雜性分析、 經(jīng)驗體會。七、用戶使用說明詳細列出每一步的操作說明。1、輸入Set1的數(shù)據(jù)2、輸入Set2的數(shù)據(jù)3、分別輸出 SetlU Set2=Set1 A Set2=Set1-Set2=八、測試結(jié)果畫 *C:UsersuseiAD©slctopCPPl lDebugll.exe4I回i £2 rSetl：0120per4

12、aGtion89Set2：error dataSetl |JSet2=adeinoprtSetlR&aortSetl-Set2-inpPress any key to continue1九、附錄：程序設(shè)計源代碼#include <iostream>using namespace std;const int MaxSize=200; /MaxSize 是順序表中最大項數(shù) template <class T> /定義模板類 SeqList class SeqList public:SeqList( );/無參構(gòu)造函數(shù)SeqList(T a, int n); /有參構(gòu)

13、造函數(shù)SeqList(const SeqList &A);/A 中元素固定不變int Length(); / 求線性表的長度T Get(int i);/ 按位查找，取線性表的第 i 個元素int Locate(T item);/ 查找元素 itemvoid Insert(int i, T item); /在第 i 個位置插入元素 item T Delete(int i); / 刪除線性表的第 i 個元素 void display(); /遍歷線性表，按序號依次輸出各元素 int empty(); /判斷線性表是否為空表 void clear(); /清空線性表private:T dat

14、aMaxSize; / 存放數(shù)據(jù)元素的數(shù)組int length;/線性表的長度;/ 存儲結(jié)構(gòu)定義 template<class T> SeqList<T>:SeqList() length=0;/ 無參構(gòu)造函數(shù)實現(xiàn) ,初始化表，置表的長度為 0 template <class T>SeqList<T>:SeqList(T a, int n) if (n>MaxSize) throw " 數(shù)組元素個數(shù)不合法 "for (int i=0; i<n; i+)datai=ai;length=n;/ 有參構(gòu)造函數(shù)實現(xiàn) tem

15、plate <class T> SeqList<T>:SeqList(const SeqList &A) for (int i=0; i<A.length; i+)datai=A.datai;length=A.length;/A 的元素長度不變 template <class T> int SeqList<T>:Length() return length;/ 求線性表的長度 template <class T>T SeqList<T>:Get(int i) return datai;/取序號為 i 的數(shù)據(jù)元

16、素 ,返回序號為 i 的元素值 template <class T>int SeqList<T>:Locate(T item) for (int i=1;i<=length;i+)if (datai=item)return i+1 ; /下標(biāo)為i的元素等于item，返回其序號i+1 return 0; /查找失敗/返回數(shù)據(jù)元素 item 在表中的位置template <class T>void SeqList<T>:Insert(int i, T item) int j;if (length>=MaxSize) throw "

17、; 溢出"if (i<1 | i>length+1) throw "i 不合法！ "for (j=length; j>=i; j-) dataj=dataj-1;datai-1=item;length+;/ 在線性表的第 i 個位置插入一個元素 item template <class T>T SeqList<T>:Delete(int i) int item,j;if (length=0) throw "表為空,無法刪除元素 !"if (i<1 | i>length) throw &quo

18、t;i 不合法!"item=datai-1;for (j=i; j<length; j+)dataj-1=dataj;length-;return item;/刪除線性表的第 i 個位置上的元素 item template <class T> void SeqList<T>:display() for (int i=0;i<length;i+)cout<<datai;/遍歷線性表，按序號依次輸出各元素 template <class T> int SeqList<T>:empty() if (length=0)r

19、eturn 1; return 0;/判斷線性表是否為空表 template <class T>void SeqList<T>:clear() length=0;/ 清空線性表 template <class T> SeqList<T> bin(SeqList<T> A,SeqList<T> B) SeqList<T> C;int m=1;int a=A.Length();for (int b=0;b<=B.Length();b+)A.Insert(a+b+1,B.Get(b);將B的元素插到的 A的后面

20、成組合for(char i='a'i<='z'i+) 定義字符 i 在 a 到 z 之間for (int d=0;d<=A.Length();d+)if (A.Get(d)=i)/ 取組合后元素將元素與 i 進行比較C.Insert(m,i);相同的插入 Cm+;不相同繼續(xù) break;return C;/并運算template <class T>SeqList<T> jiao(SeqList<T> A,SeqList<T> B)SeqList<T> C;int m=1;int flag=0

21、;for(char i='a'i<='z'i+,flag=O) 定義字符 i 在 a 到 z 之間for (int a=O;a<=A.Length();a+)if (A.Get(a)=i)將i與A中元素進行比較for (int b=O;b<=B.Length();b+)if (B.Get(b)=i)/ 將 i 與 B 中元素進行比較C.Insert(m,i);兩次比較都有與i相同的元素，則將i插入Cm+f_agH_.一 break 八 if (f-agHHl) break-efum C八M滋應(yīng)wfemp-aCDAC-ass TVSeq 匚 satv cha(seq 匚 SATV A-seq 匚 SATV B)宀seqLisATV 0inf mHk八inf f-agHO 八fo(char 兀aA'HN-T+f-agH0)1Mx蘋 imawN2凹for (inf aHOQiAHALengfh()Qi