数据结构实验-集合的并交差运算实验报告

1、实 验 报 告 实验课程：数 据 结 构 实验项目：实验一集合的并交差运算 专 业：计算机科学与技术 班 级： 姓 名： 学 号： 指导教师： 目 录1、 问题定义及需求分析 （1）实验目的 （2）实验任务 （3）需求分析二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系3、 详细设计 (1)数据类型及存储结构 (2)模块设计4、 调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会5、 使用说明 (1)程序使用说明6、 测试结果 (1)运行测试结果截图7、 附录 (1)源代码1、 问题定义及需求分析（1）实验目的设计一个能演示集合的并、交、差运算程序。（2）实

2、验任务 1)采用顺序表或链表等数据结构。2)集合的元素限定为数字和小写英文字母。（3）需求分析：输入形式为:外部输入字符串；输入值限定范围为:数字和小写英文字母；输出形式为：字符集；程序功能:计算两个集合的交、并、差以及重新输入集合功能；2、 概要设计：(1)抽象数据类型定义： 线性表 (2) 主程序流程：调用主菜单函数 初始化两个线性表作为集合 给两个集合输入数据 输出集合数据元素信息 另初始化两个线性表 创建选择功能菜单界面 通过不同选 项调用不同功能函数 在每个功能函数里面加结束选择功能，实现循环调用功能菜单 计算完毕退出程序；（3） 模块关系： 主菜单 差运算 并运算 交运算 新建集合

3、 结束/返回 结束三、详细设计抽象数据类型定义：typedef struct ElemType *elem; int length; int listsize;SqList;存储结构：顺序表；模块1-在顺序表的逻辑为i的位置插入新元素e的函数；算法如下：/*在顺序表的逻辑为i的位置插入新元素e的函数*/Status ListInsert_Sq(SqList &L,int i,ElemType e)ElemType *newbase,*p,*q;if(i < 1 | i > L.length + 1) return 0; /i的合法值为(1 <= i <= L.l

4、ength_Sq(L) + 1)if(L.length >= L.listsize) /当前储存空间已满，增加分配 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

5、); 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; /

6、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 模块三集合交运算算法如下：/*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc) in

7、t i; ElemType elem; Lc.length = 0; /将表Lc的长度设为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中 模块四集合并运算算法如下：/*求集合的并集的函数*/void Union_Sq(SqList La,SqList

8、 Lb,SqList &Lc) int i; ElemType elem; Lc.length=0; /将表Lc的长度初设为0 for(i = 0; i < La.length; i+) /先将表La的元素全部复制到表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,e

9、lem); /若有的话将elem放入表Lc中 模块五集合的差运算算法如下：/*求集合的差集函数*/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); /

10、若有，则把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中，否则，就不存放 四、调试分析 问题分析及解决：首先，在编写程序时没有设置线性表的初始长度，导致集合元素输入错误；然后通过#define LIST_INIT_SIZE 100和#define LI

11、STINCREMENT 10解决；时空分析： int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)时间复杂度为O(n); Status ListInsert_Sq(SqList &L,int i,ElemType e) 时间复杂度为O(n); void Union_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n); void Mix_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);

12、void Differ_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(2*m*n);改进设想：当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会： 顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大量增添和删除元素；在内存中存储地址连续；五、使用说明第一步：点击运行按钮；第二步: 根据提示输入集合A(可以连续输入，只限输入小写字母和数字)；第三步：程序自动显示输入结果；第四步：输入集合B（同第二步）；第五步：跳出主菜单界面；第六步

13、：根据选项输入对应运算项的数字序号；第七步：显示运算结果，并可继续进行选择运算还是退出；第八步：若继续运算则返回主菜单，否则退出；第九步：循环第六、七、八步，直至选择退出；六、测试结果输入界面：并运算结果：交运算结果：差运算结果：重新建立集合并运算：七、附录#include<stdio.h>#include<stdlib.h>#define LIST_INIT_SIZE 100/初始表空间大小#define LISTINCREMENT 10/表长增量typedef int Status; /*Status是函数类型*/typedef char ElemType;/*El

14、emType类型根据实际情况而定，这里假设为char*/typedef struct ElemType *elem; /*储存空间基地址*/ int length; /*当前长度*/ int listsize;/*当前分配的储存容量（以sizeof(Elemtype)为单位）*/SqList;SqList La,Lb,Lc,Ld;/*定义全局变量*/*构造一个空的线性表L*/Status InitList_Sq(SqList &L) L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if(!L.elem) ex

15、it(-1); /*储存分配失败*/ L.length = 0; L.listsize = LIST_INIT_SIZE;/*初始储存容量*/ return 1;/*在顺序表的逻辑为i的位置插入新元素e的函数*/Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *newbase,*p,*q; if(i < 1 | i > L.length + 1) return 0; if(L.length >= L.listsize)/当前储存空间已满，增加分配 newbase=(ElemType*)realloc(

16、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;/*创建一个线性表，输入数据*/void C

17、reateList_Sq(SqList &L) ElemType ch='0' int inlist =0,j; while(ch) != 'n') scanf("%c",&ch);/输入数据 for(j = 0; j < L.length; j+) if(ch = L.elemj)/判断表L中是否有与ch相等的元素 inlist = 1; /若有，则inlist置1 break; /跳出本轮循环 else inlist =0; /否则inlist为0 if(!inlist && ch != 'n

18、')/若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,E

19、lemType) ElemType *p; int i; i = 1; p = L.elem;/p的初值为第1个元素的储存位置 while(i <= L.length && !(* compare)(*p+,e)/循环查找表L找出其中与e相等的元素的位置 +i; if(i <= L.length)/若i小于表长 return i;/则i满足条件，返回i的值 else return 0;/否则返回0/*销毁线性表的函数*/Status Clear_Sq(SqList &L) ElemType elem; free(L.elem); L.elem = NULL;

20、 return 1;/*打印顺序表函数*/void Print_Sq(SqList L) int i; for(i = 0; i < L.length; i+) printf("%2c",L.elemi);/通过for循环将表元素全部输出 if(L.length = 0) printf("空集");/若表长为0，则输出空表 printf("nttt此集合中的个数 n = %dnn",L.length);/*求集合的并集的函数*/void Union_Sq(SqList La,SqList Lb,SqList &Lc) i

21、nt i; ElemType elem; Lc.length=0; /将表Lc的长度初设为0 for(i = 0; i < La.length; i+) /先将表La的元素全部复制到表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

22、中 /*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc) int i; ElemType elem; Lc.length = 0; /将表Lc的长度设为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中共同

23、的元素放在Lc中 /*求集合的差集函数*/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

24、 = 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()/主菜单函数char s;int l=1;InitList_Sq(La);/初始化表Laprintf("ntt 请输入集合A:");CreateList_Sq(La);/创建表Lapri

25、ntf("ttt集合A为");Print_Sq(La);printf("nn");InitList_Sq(Lb);/初始化表Lbprintf("tt 请输入集合B:");CreateList_Sq(Lb);/创建表Lbprintf("ttt集合B为");Print_Sq(Lb);printf("nn");InitList_Sq(Lc);/初始化表LcInitList_Sq(Ld);/初始化表Ldwhile(l) printf("tt * 请输入您的操作选项 1、2、3、4. * nn&

26、quot;); printf("tt 1、进行集合的并运算 n"); printf("tt 2、进行集合的交运算 n"); printf("tt 3、进行集合的差运算 n"); printf("tt 4、重新建立两个集合 n"); printf("ttt"); scanf("%c",&s); switch(s) case '1' : system("cls"); Union_Sq(La,Lb,Lc);/调用集合的并运算函数 printf("t