集合的并交差运算数据结构课程设计

1、集合的并、交和差运算实习报告题目：编制一个演示集合的并、交和差运算的程序班级：10092711姓名：魏洲学号：10927128完成日期：2012.4一、需求分析 1.本演示程序中，集合的元素限制在小写字母a-z之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏 4.数据测

2、试 （1） set1=”magazine”, set2=paper”, set1set2=”aegimnprz”,set1set2=”ae”,set1-set2=”gimnz”; (2) set1=”012oper4a6tion89”,set2=”error data”,set1set2=”adeinoprt”,set1set2=”aeort”, set1-set2=”inp”.二、概要设计为实现上述功能，需要顺序表这个抽象数据类型。1.顺序表抽象数据类型定义adt sqlist 数据对象：d=ai|aielemset,i=1,2,3,n,n=0 数据关系：r1=|ai-1,aid,i=2,

3、n 基本操作： initlist(&l) 操作结果：构造一个空的顺序表l。 listlength(l) 初始条件：顺序表l已存在。 操作结果：返回l中的元素个数。 listinsert_sq(&l, i, e) 初始条件：顺序表l已存在。 操作结果：在l中第i个元素前面插入元素e。 creatsqlist(&l, a,n) 初始条件：顺序表l已存在。 操作结果：将数组an每个元素赋给顺序表l。 getelem(l, i, &e) 初始条件：顺序表l已存在。操作结果：返回l中第i个元素的值 locateelem_sq(l, e, status (*compare)() 初始条件：顺序表l已存在。

4、 操作结果：依次遍历l中每个元素带入函数。 listdelete(&l,i, &e) 初始条件：顺序表l已存在。 操作结果：删除顺序表中第i个元素。 outputlist(&l)初始条件：顺序表l已存在。 操作结果：输出顺序表的每个元素值。adt sqlist三、详细设计/ 程序的头文件#include#include#include#include/ 函数返回值#define ok 1#define error 0#define true 1#define false 0#define infeasible -1#define overflow -2#define null 0#define

5、 list_init_size 100 /顺序表的初始大小#define listincrement 10 /顺序表的递增大小typedef int status; /返回状态类型typedef char elemtype; /元素类型 typedef structelemtype *elem;int length;int listsize;sqlist;status initlist(sqlist &l)l.elem=(elemtype *)malloc(list_init_size *sizeof(elemtype);if(!l.elem) exit(overflow);l.length=

6、0;l.listsize=list_init_size;return ok;int listlength(sqlist &l)return l.length;status listinsert(sqlist &l,int i, elemtype e)if(il.length+1)return error;if(l.length=l.listsize)elemtype *newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*sizeof(elemtype);if(!newbase)exit(overflow);l.elem

7、 = newbase;l.listsize+=listincrement;elemtype *q=&(l.elemi-1);for(elemtype *p = &(l.eleml.length-1);p=q;-p)*(p+1)=*p;*q=e;+l.length;return ok;status creatsqlist(sqlist &l,elemtype a,int n)int len=listlength(l);for(int i=0;i=a&ai=0&ai=9)listinsert(l,+len,ai);return ok;status getelem(sqlist l,int i,el

8、emtype &e)if(il.length)return error;elsee=*(l.elem+i-1);return ok;status listdelete(sqlist &l,int i,elemtype &e)if(il.length) return error;elemtype *p = &(l.elemi-1);e=*p;elemtype *q=l.elem+l.length-1;for(+p;p=q;+p) *(p-1)=*p;-l.length;return ok;void paichu(sqlist &l) int i,j,l;l=listlength(l);elemt

9、ype e,u;for(i=1;i=l-1;i+)getelem(l,i,e);for(j=1;j=l;j+)getelem(l,j,u);if(i=j)continue;elseif(u=e)listdelete(l,j,u);j=1;int locateelem(sqlist &l,elemtype e,status(*compare)(elemtype,elemtype)int i=1;elemtype *p=l.elem;while(i=l.length&!(*compare)(*p+,e) +i;if(i=l.length) return i;else return 0;status

10、 jiaoji(sqlist l1,sqlist l2, sqlist &l3)int l1_len, l2_len,l3_len,i=1,j=1;elemtype e,u;l1_len=listlength(l1);l2_len=listlength(l2);l3_len=listlength(l3);for(i=1;i=1;j-)getelem(l2,j,u);if(e=u) listinsert(l3,+l3_len,u); break;elsecontinue;return ok;status chaji(sqlist l1,sqlist l2,sqlist &ld)sqlist lc

11、;int count=0,lc_len,l1_len,l2_len,k=1,flag;elemtype e,u,f;initlist(lc);jiaoji(l1,l2,lc);lc_len=listlength(lc);l1_len=listlength(l1);l2_len=listlength(l2);for(int i=1;i=l1_len;i+)flag=0;getelem(l1,i,e);for(int j=1;j=lc_len;j+) getelem(lc,j,u);if(u=e)flag=1;if(flag=0)listinsert(ld,k,e);k+;return ok;vo

12、id union(sqlist &la,sqlist lb,sqlist &lc)sqlist l1;initlist(l1);jiaoji(la,lb,l1);int la_len , lb_len,l1_len,flag;elemtype e,u;int i,j; la_len=listlength(la); lb_len=listlength(lb);l1_len=listlength(l1);for(i=1;i=la_len;+i)getelem(la,i,e); listinsert(lc,i,e); for(i=1;i=lb_len;+i)flag=0;getelem(lb,i,e

13、);for(j=1;j=l1_len;j+)getelem(l1,j,u);if(u=e)flag=1;if(flag=0)la_len+;listinsert(lc,la_len,e);void outputlist(sqlist &l)paichu(l);if(0=l.length)printf(空集!);else for(int i=0;i=0;i-) /从最后一个开始依次与前面的比较 重复赋值为0 for(j=0;j=0;i-) /同上 for(j=0;jnull); system(cls);elseexit(0);四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元