实习报告集合的并、交和差运算

1集合的并、交和差运算一、需求分析1.本演示程序中，集合的元素限制在小写字母‘a’-‘z’之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。3.程序的执行命令有：1）选择操作2）任意键清屏4.数据测试（1）Set1=”magazine”,Set2=’paper”,Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”;(2)Set1=”012oper4a6tion89”,Set2=”errordata”,Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”,Set1-Set2=”inp”.二、概要设计为实现上述功能，需要顺序表这个抽象数据类型。1.顺序表抽象数据类型定义ADTsqlist{数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n}基本操作：InitList(&l)操作结果：构造一个空的顺序表l。ListLength(l)初始条件：顺序表l已存在。操作结果：返回l中的元素个数。ListInsert_Sq(&L,i,e)初始条件：顺序表l已存在。操作结果：在l中第i个元素前面插入元素e。CreatSqList(&l,a[],n)初始条件：顺序表l已存在。操作结果：将数组a[n]每个元素赋给顺序表l。GetElem(L,i,&e)初始条件：顺序表l已存在。操作结果：返回l中第i个元素的值LocateElem_Sq(L,e,Status(*compare)())初始条件：顺序表l已存在。操作结果：依次遍历l中每个元素带入函数。ListDelete(&L,i,&e)初始条件：顺序表l已存在。操作结果：删除顺序表中第i个元素。Outputlist(&L)初始条件：顺序表l已存在。2操作结果：输出顺序表的每个元素值。}ADTsqlist三、详细设计//程序的头文件#includestdio.h#includemalloc.h#includestdlib.h#includestring.h//函数返回值#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineINFEASIBLE-1#defineOVERFLOW-2#defineNULL0#defineLIST_INIT_SIZE100//顺序表的初始大小#defineLISTINCREMENT10//顺序表的递增大小typedefintStatus;//返回状态类型typedefcharElemType;//元素类型typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//结点类型指针类型StatusInitList(SqList&l){//初始化顺序表l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!l.elem)exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;returnOK;}intListLength(SqListl){//求顺序表的长度return(l.length);3}StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}ElemType*q=&L.elem[i-1],*p=&L.elem[L.length-1];while(p=q){*(p+1)=*p;--p;}//插入位置后的元素右移*q=e;++L.length;returnOK;}StatusCreatSqList(SqList&l,ElemTypea[],intn){//创建顺序表intlen=ListLength(l);for(inti=0;in;i++){if(a[i]='a'&&a[i]='z')ListInsert_Sq(l,++len,a[i]);}returnOK;}StatusGetElem(SqListL,inti,ElemType&e){//返回顺序表中元素if(i=0||iL.length)returnERROR;elsee=*(L.elem+i-1);returnOK;4}Statusequal(ElemTypee1,ElemTypee2){if(e1==e2)returnTRUE;elsereturnFALSE;}intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){ElemType*p=L.elem;//p指向第一个元素inti=1;//i始终为p所指向元素的位序while(i=L.length&&!(*compare)(*p++,e))++i;if(i=L.length)return(i);elsereturn0;}StatusListDelete(SqList&L,inti,ElemType&e){//在顺序表Ｌ中删除第ｉ个元素，用ｅ返回其值．if(i1||iL.length)returnERROR;//删除位置不合理ElemType*p=&L.elem[i-1],*q=L.elem+L.length-1;e=*p;while(pq){*p=*(p+1);++p;}//删除位置后的元素左移--L.length;returnOK;}voidUnion(SqList&La,SqListLb){//将所有在线性表Lb中而不在La中的元素插入Laintla_len,lb_len;ElemTypee;la_len=ListLength(La);lb_len=ListLength(Lb);for(inti=1;i=lb_len;++i){GetElem(Lb,i,e);5if(LocateElem_Sq(La,e,equal)==0)ListInsert_Sq(La,++la_len,e);}}StatusJiaoJi(SqListl1,SqListl2,SqList&l3){//求集合的交集intl1_len,l2_len,l3_len,i=1,j=1;ElemTypee,u;l1_len=ListLength(l1);l2_len=ListLength(l2);l3_len=ListLength(l3);for(i=1;i=l1_len;i++){GetElem(l1,i,e);for(j=l2_len;j=1;j--){GetElem(l2,j,u);if(e==u){ListInsert_Sq(l3,++l3_len,u);break;}elsecontinue;}}returnOK;}StatusChaJi(SqList&l1,SqListl2){//求顺序表的差集SqListlc;intcount=0,lc_len,l1_len,l2_len;ElemTypee,u,f;InitList(lc);JiaoJi(l1,l2,lc);lc_len=ListLength(lc);6l1_len=ListLength(l1);l2_len=ListLength(l2);for(inti=1;i=lc_len;i++){GetElem(lc,i,e);for(intj=1;j=l1_len;j++){GetElem(l1,j,u);if(u==e){ListDelete(l1,j,f);}}}returnOK;}voidOutputlist(SqList&L){if(0==L.length)printf(空集!);elsefor(inti=0;iL.length;++i){printf(%c,*(L.elem+i));}}//程序的主函数voidmain(){system(@title集合的并交叉运算);for(1;;){system(colora1);intc;printf(****************************************************************\n);printf(########执行程序:1########退出程序:2\n);printf(****************************************************************\n);printf(请按键选择:);scanf(%d,&c);getchar();printf(\n);7if(c==1){SqListl1,l2,l3,la;intn1,n2,i,j;chara1[30],a2[30];InitList(l1);InitList(l2);InitList(l3);InitList(la);printf(请输入第一个集合:);gets(a1);n1=strlen(a1);for(i=n1-1;i=0;i--)//从最后一个开始依次与前面的比较重复赋值为0{for(j=0;ji;j++){if(a1[j]==a1[i])a1[i]=0;}}CreatSqList(l1,a1,n1);la=l1;printf(请输入第二个集合:);gets(a2);n2=strlen(a2);for(i=n2-1;i=0;i--)//同上{for(j=0;ji;j++){if(a1[j]==a1[i])a1[i]=0;}}CreatSqList(l2,a2,n2);printf(集合的交集是:);JiaoJi(l1,l2,l3);Outputlist(l3);printf(\n);printf(集合的并集是:);Union(l1,l2);Outputlist(l1);printf(\n);printf(集合的差集是:);ChaJi(la,l2);Outputlist(la);8printf(\n\n*****************按*任*意*键*清*屏!********************);system(pausenull);system(cls);}elseexit(0);}}四、调试分析1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。五、用户手册1.本程序的运行环境为DOS操作系统，可执行文件为：集合的并交差运算.exe2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。3.进入演示程序后即显示文本形式的用户界面：六、测试结果执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2执行命令“2”：退出程序运行魔王语言翻译实习