数据结构实验

实验报告实验课程:实验项目：实验一集合的并交差运算专业:计算机科学与技术班级:姓名：学号：指导教师一、问题定义及需求分析实验目的实验任务需求分析二、概要设计：抽象数据类型定义主程序流程模块关系三、详细设计数据类型及存储结构(2)模块设计四、调试分析调试分析算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1)源代码一、问题定义及需求分析实验目的设计一个能演示集合的并、交、差运算程序。实验任务采用顺序表或链表等数据结构。集合的元素限定为数字和小写英文字母。需求分析：输入形式为：外部输入字符串；输入值限定范围为：数字和小写英文字母；输出形式为：字符集；程序功能:计算两个集合的交、并、差以及重新输入集合功能;二、概要设计：(1)抽象数据类型定义:

线性表⑵主程序流程：调用主菜单函数初始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息另初始化"线性表创建选择功能菜单界面通过不同选项调用不同功能函数在每个功能函数里面加结束选择功能，实现循环调用功能菜单一'计算完毕退出程序；(3)模块关系：菜单并运算交运算差运算新建集合结束/返回结束三、详细设计抽象数据类型定义:

typedefstruct{ElemType*elem；intlength；intlistsize；}SqList；存储结构：顺序表；模块1-在顺序表的逻辑为i的位置插入新元素e的函数；算法如下：菜单并运算交运算差运算新建集合/**在顺序表的逻辑为i的位置插入新元素e的函数**/StatusListInsert_Sq(SqList&L,inti,ElemTypee){ElemType*newbase,*p,*q;if(i<1||i>L.length+1)return0;//i的合法值为(1<=i<=L.length_Sq(L)+1)if(L.length>=L.listsize){〃当前储存空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(-1);//储存分配失败L.elem=L.elem=newbase;//新基址L.listsize+=LISTINCREMENT；//增加储存容量}q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)(p+1)=p;//插入位置及之后的元素往右移q=e;//插入e++L.length;//表长加1return1;}模块二在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0算法如下：/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0**/intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){ElemType*p;inti;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)returni;//若i的大小小于表长，则满足条件返回ielsereturn0;//否则，i值不满足条件，返回0}模块三集合交运算算法如下：/**求集合的交集的函数**/voidMix_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;//将表Lc的长度设为0for(i=1;i<=La.length;i++)〃依次查看表La的所有元素elem=La.elem[i-1]；//将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal))//在表Lb中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem);//将表La与Lb中共同的元素放在Lc中}}模块四集合并运算算法如下：/**求集合的并集的函数**/voidUnion_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;//将表Lc的长度初设为0for(i=0;i<La.length;i++)//先将表La的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i];for(i=1;i<=Lb.length;i++)

elem=Lb.elem[iT]；//依次将表Lb的值赋给elemif(!LocateElem_Sq(La,elem,Equal))//判断表Laelem=Lb.elem[iT]；//依次将表LbListInsert_Sq(Lc,Lc.length+1,elem);//若有的话将elem放入表Lc中}}模块五集合的差运算算法如下：/**求集合的差集函数**/voidDiffer_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;for(i=1;i<=La.length;i++){elem=La.elem[i-1];//把表匚2中第i个元素赋值给elemif(!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.elem[iT];//把表Lb中第i个元素赋值给elemif(!LocateElem_Sq(La,elem,Equal))//判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem);//若有，则把elem放入表Lc中，否则，就不存放}}四、调试分析问题分析及解决：首先，在编写程序时没有设置线性表的初始长度，导致集合元素输入错误；然后通过#defineLIST_INIT_SIZE100和#defineLISTINCREMENT10解决；时空分析：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))时间复杂度为O(n)；StatusListInsert_Sq(SqList&L,inti,ElemTypee)时间复杂度为O(n);voidUnion_Sq(SqListLa,SqListLb,SqList&Lc)时间复杂度为O(m*n);voidMix_Sq(SqListLa,SqListLb,SqList&Lc)时间复杂度为O(m*n);voidDiffer_Sq(SqListLa,SqListLb,SqList&Lc)时间复杂度为O(2*m*n);改进设想：当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会：顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大量增添和删除元素；在内存中存储地址连续；五、使用说明第一步：点击运行按钮；第二步：根据提示输入集合A(可以连续输入，只限输入小写字母和数字)；第三步：程序自动显示输入结果；第四步：输入集合B(同第二步)；第五步：跳出主菜单界面；第六步：根据选项输入对应运算项的数字序号；第七步：显示运算结果，并可继续进行选择运算还是退出;第八步：若继续运算则返回主菜单，否则退出；第九步：循环第六、七、八步，直至选择退出；六、测试结果输入界面:»R'Ccd亦I。：心簌据斯宾捡一候台Lexm评:苗朴林怦米欢迎使用集合操作［云算j器粹冷*苗样:悴请输入集台艮：123abc真•合a为123abc此案刍口侠个数n-E请输A^-nB;345cde集台B为c45cd=U漂合中的个数n=6•wwsf请输入您的操作选项LA3、4.****1、制亍集合的并运算进彳亍集合的交运算5行集合的差运算4、重新建立两个集合并运算结果：

[■JFACD&Blcitkis整卖毁一\^合脆成一口X集合A与集合B的并集为：123abc45dE上集合■的今敦r.=10$蜷计算请输入L停止计算请输入。•回叭Cbd*&k或标辟熨瞪一'蔗台£我5-uX粹林杵本WA您的操作.无项lx2.3.4.外E啊L七一集会或#运算2、送厂隽•三节主话算3＞送亍集己的差运算4重新建立两个集合A交运算结果:，F：lC：_d囱口ck5激摇s+耳实慝当膈xe集合A与集合B的交集为：3c此集合中的个数n二走续计急请峋入1,停止汁算请输入口'■ifE而削凸匚旧臾瘁言市宾验一样令2.收e；：M.、**心请输入您的操柞选项1、2、3、虫心*送行集合的并讴算:鼻〒集合的交运算法行集刍竹差诅箕重新建立两个集合；：M.、■州3dMm屁■■戳据皓构堇捡一[栾台基睥□X是■含A与集合职：J差集为:12ab45deIt藁合中的个♦n二&件计算请输入L停止计算请输入口A—□X1、2、3.、4.卜洼行集台的并运算寸行集合N了仁宜逃行集吁臼差运真重新圭立两个集台

重新建立集合并运算：!■!F:\CodeEI—\SEo-2.exe—□X,集*为"8t9fgJ土宰白巾的个教n=&请输入芽合玫时备1*集上逐为0?cd91J」件含巾的个教n=6而卷毋请输人您的操作选项1一、2.3.土砰1、进行集合的并■算2、讪行亲盲的运百3、进行集合的差运算虹重sr岸亏仙个佞r七、附录#include<stdio.h>#include<stdlib.h>#defineLIST_INIT_SIZE100//初始表空间大小#defineLISTINCREMENT10//表长增量typedefintStatus;/**Status是函数类型**/typedefcharElemType;/*ElemType类型根据实际情况而定，这里假设为char*/typedefstruct{ElemType*elem;/**储存空间基地址**/intlength;/**当前长度**/intlistsize；/**当前分配的储存容量(以sizeof(Elemtype)为单位)**/}SqList;SqListLa,Lb,Lc,Ld;/**定义全局变量**//**构造一个空的线性表L**/StatusInitList_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;/**初始储存容量**/return1;}/**在顺序表的逻辑为i的位置插入新元素e的函数**/StatusListInsert_Sq(SqList&L,inti,ElemTypee){ElemType*newbase,*p,*q;if(i<1||i>L.length+1)return0;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.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)二*p;//插入位置及之后的元素往右移*q=e;//插入£++L.length;return1;}/**创建一个线性表，输入数据**/voidCreateList_Sq(SqList&L){ElemTypech='\0';intinlist=0,j;while((ch)!='\n'){scanf("%c”,&ch)；//输入数据for(j=0；j<L.length；j++)if(ch==L.elem[j])//判断表L中是否有与ch相等的元素{inlist=1;//若有，则inlist置1break;//跳出本轮循环}elseinlist=0;//否则inlist为0if(!inlist&&ch!=f\nf)//若inlist为0且ch不为”\n”ListInsert_Sq(L,L.length+1,ch);//则将ch存入表L中}}/*判断两元素是否相等，若相等则返回1;否则返回0*/StatusEqual(ElemTypea,ElemTypeb){if(a==b)return1;//相等，返回1elsereturn0;//否则，返回0/*在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0*/intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){ElemType*p;inti;i=1;p=L.elem;//p的初值为第1个元素的储存位置while(i<=L.length&&!(*compare)(*p++,e))//循环查找表L找出其中与e相等的元素的位置++i;if(i<=L.length)//若i小于表长returni;//则i满足条件，返回i的值elsereturn0;//否则返回0}/*销毁线性表的函数*/StatusClear_Sq(SqList&L){ElemTypeelem;free(L.elem)；L.elem二NULL；return1；}/*打印顺序表函数*/voidPrint_Sq(SqListL){inti;for(i=0;i<L.length;i++)printf("%2c”,L.elem[i]);//通过for循环将表元素全部输出if(L.length==0)printf("空集");//若表长为0，则输出空表printf("\n\t\t\t此集合中的个数n=%d\n\n”,L.length);}/*求集合的并集的函数*/voidUnion_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;//将表Lc的长度初设为0for(i=0;i<La.length;i++)//先将表La的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i]；for(i=1;i<=Lb.length;i++){elem=Lb.elem[i-1];//依次将表Lb的值赋给elemif(!LocateElem_Sq(La,elem,Equal))//判断表La中是否有与elem相同的值ListInsert_Sq(Lc,Lc.length+1,elem);//若有的话将elem放入表Lc中}}/*求集合的交集的函数*/voidMix_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;//将表Lc的长度设为0for(i=1;i<=La.length;i++){〃依次查看表La的所有元素elem=La.elem[i-1]；//将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal))//在表La中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem);//将表La与Lb中共同的元素放在Lc中}}/*求集合的差集函数*/voidDiffer_Sq(SqListLa,SqListLb,SqList&Lc){inti;ElemTypeelem;Lc.length=0;for(i=1;i<=La.length;i++){elem=La.elem[i-1];//把表La中第i个元素赋值给elemif(!LocateElem_Sq(Lb,elem,Equal))//判断elem在表Lb中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem);//若有，则把elem放入表囱中，否则，就不存放}for(i=1；i<=Lb.length；i++){elem=Lb.elem[i-1];//把表Lb中第i个元素赋值给elemif(!LocateElem_Sq(La,elem,Equal))//判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem);//若有，则把elem放入表Lc中，否则，就不存放}}voidIndex_Sq(){//主菜单函数chars;intl=1;InitList_Sq(La);//初始化表Laprintf("\n\t\t请输入集合A:");CreateList_Sq(La);//创建表Laprintf("\t\t\t集合A为")；

Print_Sq(La)；printf("\n\n")；InitList_Sq(Lb)；//初始化表Lbprintf("\t\t请输入集合B:");CreateList_Sq(Lb);//创建表Lbprintf("\t\t\t集合B为")；Print_Sq(Lb);printf("\n\n");InitList_Sq(Lc);//初始化表LcInitList_Sq(Ld);//初始化表Ldwhile(l){printf("\t\t*************\n\n");printf("\t\t\n");printf("\t\t\n");printf("\t\tprintf("\t\t*************\n\n");printf("\t\t\n");printf("\t\t\n");printf("\t\t\n");printf("\t\t1、进行集合的并