數(shù)據(jù)結(jié)構(gòu)實驗-集合的并交差運算實驗報告

實 驗 報 告 實驗課程：數(shù) 據(jù) 結(jié) 構(gòu) 實驗項目：實驗一集合的并交差運算 專 業(yè)：計算機科學(xué)與技術(shù) 班 級： 姓 名： 學(xué) 號： 指導(dǎo)教師： 目 錄1、 問題定義及需求分析 （1）實驗?zāi)康?（2）實驗任務(wù) （3）需求分析二、概要設(shè)計： (1)抽象數(shù)據(jù)類型定義 (2)主程序流程 (3) 模塊關(guān)系3、 詳細設(shè)計 (1)數(shù)據(jù)類型及存儲結(jié)構(gòu) (2)模塊設(shè)計4、 調(diào)試分析 (1)調(diào)試分析 (2)算法時空分析 (3)經(jīng)驗體會5、 使用說明 (1)程序使用說明6、 測試結(jié)果 (1)運行測試結(jié)果截圖7、 附錄 (1)源代碼1、 問題定義及需求分析（1）實驗?zāi)康脑O(shè)計一個能演示集合的并、交、差運算程序。（2）實驗任務(wù) 1)采用順序表或鏈表等數(shù)據(jù)結(jié)構(gòu)。2)集合的元素限定為數(shù)字和小寫英文字母。（3）需求分析：輸入形式為:外部輸入字符串；輸入值限定范圍為:數(shù)字和小寫英文字母；輸出形式為：字符集；程序功能:計算兩個集合的交、并、差以及重新輸入集合功能；2、 概要設(shè)計：(1)抽象數(shù)據(jù)類型定義： 線性表 (2) 主程序流程：調(diào)用主菜單函數(shù) 初始化兩個線性表作為集合 給兩個集合輸入數(shù)據(jù) 輸出集合數(shù)據(jù)元素信息 另初始化兩個線性表 創(chuàng)建選擇功能菜單界面 通過不同選 項調(diào)用不同功能函數(shù) 在每個功能函數(shù)里面加結(jié)束選擇功能，實現(xiàn)循環(huán)調(diào)用功能菜單 計算完畢退出程序；（3） 模塊關(guān)系： 主菜單 差運算 并運算 交運算 新建集合 結(jié)束/返回 結(jié)束三、詳細設(shè)計抽象數(shù)據(jù)類型定義：typedef struct ElemType *elem; int length; int listsize;SqList;存儲結(jié)構(gòu)：順序表；模塊1-在順序表的邏輯為i的位置插入新元素e的函數(shù)；算法如下：/*在順序表的邏輯為i的位置插入新元素e的函數(shù)*/Status ListInsert_Sq(SqList &L,int i,ElemType e)ElemType *newbase,*p,*q;if(i L.length + 1) return 0; /i的合法值為(1 = i = L.listsize) /當(dāng)前儲存空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType); if(!newbase) exit(-1); /儲存分配失敗 L.elem = newbase; /新基址 L.listsize += LISTINCREMENT; /增加儲存容量q = &(L.elemi - 1); /q為插入位置for(p = &(L.elemL.length - 1); p = q; -p) (p + 1) = p; /插入位置及之后的元素往右移q = e; /插入e+L.length; /表長加1return 1;模塊二在順序線性表L中查找第1個與e滿足compare()的元素位序，若找到，則返回其在L中的位序，否則返回0算法如下：/*在順序線性表L中查找第1個與e滿足compare()的元素位序，若找到，則返回其在L中的位序，否則返回0*/int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType) ElemType *p; int i; i = 1; /i的初值為第1個元素的位序 p = L.elem; /p的初值為第1個元素的儲存位置 while(i = L.length & !(* compare)(*p+,e) +i; /從表L中的第一個元素開始與e比較，直到找到L中與e相等的元素時返回該元素的位置 if(i = L.length) return i; /若i的大小小于表長，則滿足條件返回i else return 0; /否則，i值不滿足條件，返回0 模塊三集合交運算算法如下：/*求集合的交集的函數(shù)*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length = 0; /將表Lc的長度設(shè)為0 for(i = 1; i = La.length; i+) /依次查看表La的所有元素 elem = La.elemi-1; /將表La中i位置的元素賦值給elem if(LocateElem_Sq(Lb,elem,Equal) /在表Lb中查找是否有與elem相等的元素 ListInsert_Sq(Lc,Lc.length+1,elem); /將表La與Lb中共同的元素放在Lc中 模塊四集合并運算算法如下：/*求集合的并集的函數(shù)*/void Union_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length=0; /將表Lc的長度初設(shè)為0 for(i = 0; i La.length; i+) /先將表La的元素全部復(fù)制到表Lc中 Lc.elemLc.length+=La.elemi; for(i = 1; i = Lb.length; i+) elem = Lb.elemi-1; /依次將表Lb的值賦給elem if(!LocateElem_Sq(La,elem,Equal) /判斷表La中是否有與elem相同的值 ListInsert_Sq(Lc,Lc.length+1,elem); /若有的話將elem放入表Lc中 模塊五集合的差運算算法如下：/*求集合的差集函數(shù)*/void Differ_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length = 0; for(i = 1; i = La.length; i+) elem = La.elemi-1; /把表La中第i個元素賦值給elem if(!LocateElem_Sq(Lb,elem,Equal) /判斷elem在表Lb中是否有相同的元素 ListInsert_Sq(Lc,Lc.length+1,elem); /若有，則把elem放入表Lc中，否則，就不存放 for(i = 1; i = Lb.length; i+) elem = Lb.elemi-1; /把表Lb中第i個元素賦值給elem if(!LocateElem_Sq(La,elem,Equal) /判斷elem在表La中是否有相同的元素 ListInsert_Sq(Lc,Lc.length+1,elem); /若有，則把elem放入表Lc中，否則，就不存放 四、調(diào)試分析 問題分析及解決：首先，在編寫程序時沒有設(shè)置線性表的初始長度，導(dǎo)致集合元素輸入錯誤；然后通過#define LIST_INIT_SIZE 100和#define LISTINCREMENT 10解決；時空分析： int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)時間復(fù)雜度為O(n); Status ListInsert_Sq(SqList &L,int i,ElemType e) 時間復(fù)雜度為O(n); void Union_Sq(SqList La,SqList Lb,SqList &Lc) 時間復(fù)雜度為O(m*n); void Mix_Sq(SqList La,SqList Lb,SqList &Lc) 時間復(fù)雜度為O(m*n); void Differ_Sq(SqList La,SqList Lb,SqList &Lc) 時間復(fù)雜度為O(2*m*n);改進設(shè)想：當(dāng)同時求兩個以上的結(jié)合間的運算是需要先進性兩個集合間的運算，然后在于另外的集合進行運算；若要同事進行多個集合的運算需要建立多個順序表；經(jīng)驗體會： 順序表使用起來比較簡單，但長度不可隨意變化，適用于大量訪問元素，而不適用于大量增添和刪除元素；在內(nèi)存中存儲地址連續(xù)；五、使用說明第一步：點擊運行按鈕；第二步: 根據(jù)提示輸入集合A(可以連續(xù)輸入，只限輸入小寫字母和數(shù)字)；第三步：程序自動顯示輸入結(jié)果；第四步：輸入集合B（同第二步）；第五步：跳出主菜單界面；第六步：根據(jù)選項輸入對應(yīng)運算項的數(shù)字序號；第七步：顯示運算結(jié)果，并可繼續(xù)進行選擇運算還是退出；第八步：若繼續(xù)運算則返回主菜單，否則退出；第九步：循環(huán)第六、七、八步，直至選擇退出；六、測試結(jié)果輸入界面：并運算結(jié)果：交運算結(jié)果：差運算結(jié)果：重新建立集合并運算：七、附錄#include#include#define LIST_INIT_SIZE 100/初始表空間大小#define LISTINCREMENT 10/表長增量typedef int Status; /*Status是函數(shù)類型*/typedef char ElemType;/*ElemType類型根據(jù)實際情況而定，這里假設(shè)為char*/typedef struct ElemType *elem; /*儲存空間基地址*/ int length; /*當(dāng)前長度*/ int listsize;/*當(dāng)前分配的儲存容量（以sizeof(Elemtype)為單位）*/SqList;SqList La,Lb,Lc,Ld;/*定義全局變量*/*構(gòu)造一個空的線性表L*/Status InitList_Sq(SqList &L) L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if(!L.elem) exit(-1); /*儲存分配失敗*/ L.length = 0; L.listsize = LIST_INIT_SIZE;/*初始儲存容量*/ return 1;/*在順序表的邏輯為i的位置插入新元素e的函數(shù)*/Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *newbase,*p,*q; if(i L.length + 1) return 0; if(L.length = L.listsize)/當(dāng)前儲存空間已滿，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(-1);/儲存分配失敗 L.elem = newbase; L.listsize += LISTINCREMENT;/增加儲存容量 q = &(L.elemi - 1);/q為插入位置 for(p = &(L.elemL.length - 1); p = q; -p) *(p + 1) = *p;/插入位置及之后的元素往右移 *q = e;/插入e +L.length; return 1;/*創(chuàng)建一個線性表，輸入數(shù)據(jù)*/void CreateList_Sq(SqList &L) ElemType ch=0; int inlist =0,j; while(ch) != n) scanf(%c,&ch);/輸入數(shù)據(jù) for(j = 0; j L.length; j+) if(ch = L.elemj)/判斷表L中是否有與ch相等的元素 inlist = 1; /若有，則inlist置1 break; /跳出本輪循環(huán) else inlist =0; /否則inlist為0 if(!inlist & ch != n)/若inlist為0且ch不為”n” ListInsert_Sq(L,L.length+1,ch);/則將ch存入表L中 /*判斷兩元素是否相等,若相等則返回1;否則返回0*/Status Equal(ElemType a,ElemType b) if(a = b) return 1;/相等，返回1 else return 0;/否則，返回0/*在順序線性表L中查找第1個與e滿足compare()的元素位序，若找到，則返回其在L中的位序，否則返回0*/int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType) ElemType *p; int i; i = 1; p = L.elem;/p的初值為第1個元素的儲存位置 while(i = L.length & !(* compare)(*p+,e)/循環(huán)查找表L找出其中與e相等的元素的位置 +i; if(i = L.length)/若i小于表長 return i;/則i滿足條件，返回i的值 else return 0;/否則返回0/*銷毀線性表的函數(shù)*/Status Clear_Sq(SqList &L) ElemType elem; free(L.elem); L.elem = NULL; return 1;/*打印順序表函數(shù)*/void Print_Sq(SqList L) int i; for(i = 0; i L.length; i+) printf(%2c,L.elemi);/通過for循環(huán)將表元素全部輸出 if(L.length = 0) printf(空集);/若表長為0，則輸出空表 printf(nttt此集合中的個數(shù) n = %dnn,L.length);/*求集合的并集的函數(shù)*/void Union_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length=0; /將表Lc的長度初設(shè)為0 for(i = 0; i La.length; i+) /先將表La的元素全部復(fù)制到表Lc中 Lc.elemLc.length+=La.elemi; for(i = 1; i = Lb.length; i+) elem = Lb.elemi-1; /依次將表Lb的值賦給elem if(!LocateElem_Sq(La,elem,Equal) /判斷表La中是否有與elem相同的值 ListInsert_Sq(Lc,Lc.length+1,elem); /若有的話將elem放入表Lc中 /*求集合的交集的函數(shù)*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length = 0; /將表Lc的長度設(shè)為0 for(i = 1; i = La.length; i+) /依次查看表La的所有元素 elem = La.elemi-1; /將表La中i位置的元素賦值給elem if(LocateElem_Sq(Lb,elem,Equal) /在表La中查找是否有與elem相等的元素 ListInsert_Sq(Lc,Lc.length+1,elem); /將表La與Lb中共同的元素放在Lc中 /*求集合的差集函數(shù)*/void Differ_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length = 0; for(i = 1; i = La.length; i+) elem = La.elemi-1; /把表La中第i個元素賦值給elem if(!LocateElem_Sq(Lb,elem,Equal) /判斷elem在表Lb中是否有相同的元素 ListInsert_Sq(Lc,Lc.length+1,elem);/若有，則把elem放入表Lc中，否則，就不存放 for(i = 1; i = Lb.length; i+) elem = Lb.elemi-1; /把表Lb中第i個元素賦值給elem if(!LocateElem_Sq(La,elem,Equal) /判斷elem在表La中是否有相同的元素 ListInsert_Sq(Lc,Lc.length+1,elem); /若有，則把elem放入表Lc中，否則，就不存放 void Index_Sq()/主菜單函數(shù)char s;int l=1;InitList_Sq(La);/初始化表Laprintf(ntt 請輸入集合A:);CreateList_Sq(La);/創(chuàng)建表Laprintf(ttt集合A為);Print_Sq(La);printf(nn);InitList_Sq(Lb);/初始化表Lbprintf(tt 請輸入集合B:);CreateList_Sq(Lb);/創(chuàng)建表Lbprintf(ttt集合B為);Print_Sq(Lb);printf(nn);InitList_Sq(Lc);/初始化表LcInitList_Sq(Ld);/初始化表Ldwhile(l) printf(tt * 請輸入您的操作選項 1、2、3、4. * nn); printf(tt 1、進行集合的并運算 n); printf(tt 2、進行集合的交運算