数据结构C课程设计--集合的并交和差运算.doc

数据结构C+课程设计题目: 集合的并、交和差运算 1、 设计题目 集合的并、交和差运算2、 小组成员分工说明 一个人3、 需求分析1） 运行环境（软、硬件环境）软件环境：Microsoft Vista操作系统，Visual C+ 6.0硬件环境：2.0GB内存2） 输入的形式和输入值的范围运行所给的测试数据，集合的元素限定为小写字符a. .z： 第一组： Set1magazine ，Set2paper 第二组： Set10120per4a6tion89，Set2error data 输出的形式描述程序运行并、交和差运算后得到数据，输出字符。3） 功能描述 能演示执行集合的并、交和差运算。4） 测试数据 (1) Set1magazine ，Set2paper， Set1Set2aeginmprz，Set1Set2ae，Set1Set2gimnz。 (2) Set10120per4a6tion89，Set2error data， Set1Set2=adeinoprt，Set1Set2=aeort，Set1Set2inp。四、概要设计1）抽象数据类型定义描述（顺序表的抽象数据类型描述）ADT Seqlist is Data线性表的长度OperationSeqlist初始化值：无动作：置顺序表的长度为0Length 输入：无 前置条件：表已存在 功能：求表的长度 输出：返回表的长度，即表中数据元素的个数 后置条件：表不变Get 输入：元素的序号i 前置条件：表已存在，i合法 功能：在表中取序号为i的数据元素 输出：若i合法，返回序号为i的元素值，否则抛出异常 后置条件：表不变Locate 输入：数据元素item 前置条件：表已存在 功能：在线性表中查找值等于item的元素 输出：若查找成功，返回x在表中的序号，否则返回0 后置条件：表不变Insert 输入：插入位置i；待插元素item 前置条件：表已存在,i合法 功能：在表的第i个位置处插入一个新元素x 输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素Delete 输入：删除位置i 前置条件：表已存在 功能：删除表中的第i个元素 输出：若删除成功，返回被删元素，否则抛出异常后置条件：若删除成功，表中减少一个元素Empty 输入：无 前置条件：表已存在 功能：判断表是否为空 输出：若是空表，返回1，否则返回0后置条件：表不变Clear 输入：无 前置条件：无 功能：清空顺序表 输出：无 后置条件：表的长度是0end ADT seqList2）功能模块设计（如主程序模块设计）集合的并、交和差运算集合的并运算集合的交运算集合的差运算3）模块层次调用关系图mainbinjiaocha五、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。1、顺序表存储结构的定义。2、成员函数类的定义。3、并、交和差三个操作函数的实现。1）并运算：将B中的元素插到A后面后形成新的集合，定义字符i在a到z之间，并将新的集合中的个元素与i进行比较，若相同则将此时i的值插入C中作为输出值，若不同则i+继续比较。template SeqList bin(SeqList A,SeqList B)SeqList C;int m=1;int a=A.Length();for (int b=0;b=B.Length();b+)A.Insert(a+b+1,B.Get(b);/将B的元素插到的A的后面成组合for(char i=a;i=z;i+)/定义字符i在a到z之间for (int d=0;d=A.Length();d+)if (A.Get(d)=i)/取组合后元素将元素与i进行比较C.Insert(m,i);/相同的插入Cm+;/不相同继续 break;return C;2）交运算：定义定义字符i在a到z之间，先将i与A中数据元素进行比较，再将i与B中元素进行比较，如果两次比较都有与i相同的元素，则将该i值插入C中作为输出。template SeqList jiao(SeqList A,SeqList B)SeqList C;int m=1;int flag=0;for(char i=a;i=z;i+,flag=0)/定义字符i在a到z之间for (int a=0;a=A.Length();a+)if (A.Get(a)=i)/将i与A中元素进行比较for (int b=0;b=B.Length();b+)if (B.Get(b)=i)/将i与B中元素进行比较C.Insert(m,i);/两次比较都有与i相同的元素，则将i插入Cm+;flag=1;break; if (flag=1)break;return C;3）差运算：定义字符i在a到z之间，先将i与A中数据元素进行比较，如果相同，再将i与B中元素进行比较，如果不同则将i插入C作为输出。 template SeqList cha(SeqList A,SeqList B)SeqList C;int m=1;int flag=0;for(char i=a;i=z;i+,flag=0)/定义字符i在a到z之间for (int a=0;a=A.Length();a+)if (A.Get(a)=i)/将i与A中元素进行比较for (int b=0;b=B.Length();b+)if (B.Get(b)=i)/如果i与A中元素相同，则将i与a中元素进行比较flag=m;if(flag=0)C.Insert(m,i);/如果不同则将i插入Cm+;break;return C;4、main函数。int main()char a50;char b50;coutSet1:;/输入set1数据cin.getline(b,/0); /所给数据中有空格，所以不能直接用cincoutendl;coutSet2:;/输入set2数据cin.getline(a,/0);coutendl;SeqList A(a,50),B(b,50),C,D,E;C=bin(A,B);/调用集合的并运算coutSet1Set2=;C.display();coutendl;D=jiao(A,B);/调用集合的交运算coutSet1Set2=;D.display();coutendl;E=cha(B,A);/调用集合的差运算coutSet1-Set2=;E.display();coutendl;return 0;六、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。七、 用户使用说明详细列出每一步的操作说明。1、 输入Set1的数据2、 输入Set2的数据 3、 分别输出 Set1Set2= Set1Set2= Set1-Set2=八、 测试结果九、附录：程序设计源代码#include using namespace std;const int MaxSize=200; /MaxSize是顺序表中最大项数template /定义模板类SeqList class SeqList public:SeqList( ); /无参构造函数 SeqList(T a, int n); /有参构造函数SeqList(const SeqList &A);/A中元素固定不变int Length(); /求线性表的长度 T Get(int i); /按位查找，取线性表的第i个元素 int Locate(T item);/查找元素item void Insert(int i, T item); /在第i个位置插入元素itemT Delete(int i); /删除线性表的第i个元素 void display(); /遍历线性表，按序号依次输出各元素 int empty(); /判断线性表是否为空表void clear(); /清空线性表private:T dataMaxSize; /存放数据元素的数组 int length; /线性表的长度 ;/存储结构定义templateSeqList:SeqList() length=0;/无参构造函数实现,初始化表，置表的长度为0template SeqList:SeqList(T a, int n) if (nMaxSize) throw 数组元素个数不合法;for (int i=0; in; i+) datai=ai;length=n;/有参构造函数实现template SeqList:SeqList(const SeqList &A) for (int i=0; iA.length; i+) datai=A.datai;length=A.length;/A的元素长度不变template int SeqList:Length() return length;/求线性表的长度template T SeqList:Get(int i) return datai;/取序号为i的数据元素,返回序号为i的元素值template int SeqList:Locate(T item) for (int i=1;i=length;i+) if (datai=item) return i+1 ; /下标为i的元素等于item，返回其序号i+1 return 0; /查找失败/返回数据元素item在表中的位置template void SeqList:Insert(int i, T item) int j;if (length=MaxSize) throw 溢出;if (ilength+1) throw i不合法！;for (j=length; j=i; j-)dataj=dataj-1; datai-1=item;length+;/在线性表的第i个位置插入一个元素itemtemplate T SeqList:Delete(int i) int item,j;if (length=0) throw 表为空,无法删除元素!;if (ilength) throw i不合法!;item=datai-1;for (j=i; jlength; j+)dataj-1=dataj;length-;return item;/删除线性表的第i个位置上的元素itemtemplate void SeqList:display() for (int i=0;ilength;i+)coutdatai;/遍历线性表，按序号依次输出各元素template int SeqList:empty() if (length=0)return 1;return 0;/判断线性表是否为空表template void SeqList:clear() length=0;/清空线性表template SeqList bin(SeqList A,SeqList B) SeqList C;int m=1;int a=A.Length();for (int b=0;b=B.Length();b+)A.Insert(a+b+1,B.Get(b);/将B的元素插到的A的后面成组合for(char i=a;i=z;i+)/定义字符i在a到z之间for (int d=0;d=A.Length();d+)if (A.Get(d)=i)/取组合后元素将元素与i进行比较C.Insert(m,i);/相同的插入Cm+;/不相同继续 break;return C;/并运算template SeqList jiao(SeqList A,SeqList B)SeqList C;int m=1;int flag=0;for(char i=a;i=z;i+,flag=0)/定义字符i在a到z之间for (int a=0;a=A.Length();a+)if (A.Get(a)=i)/将i与A中元素进行比较for (int b=0;b=B.Length();b+)if (B.Get(b)=i)/将i与B中元素进行比较C.Insert(m,i);/两次比较都有与i相同的元素，则将i插入Cm+;flag=1;break; if (flag=1)break;return C;/交运算template SeqList cha(SeqList A,SeqList B)SeqList C;int m=1;int flag=0;for(char i=a;i=z;i+,flag=0)/定义字符i在a到z之间for (int a=0;a=A.Length();a+)if (A.Get(a)=i)/将i与A中元素进行比较for (int b=0;b=B.Length();b+)if (B.Get(b)=i)/如果i与A中元素相同，则将i与a中元素进行比较flag=m;if(flag=0)C.Insert(m,i);/如果不同则将i插入Cm+;break;return C;/减运算int main()char a50;char b50;coutSet1:;/输入set1数据cin.getline(b,/0)