C++集合类课件.doc

集合的概念 在数学中,我们把具有某些共同特征的元素构成的一个整体称为集合. 一个集合就是由同一种有序类型的一组数据元素所组成的,这一种有序类型称为该集合的基类型.课堂练习：设计一个集合类numSet，存放有序的整型数序，其中的元素按从小到大的顺序排列并且不包含相同的元素，要求：1）向数序中添加元素（过滤重复数据）并保持有序2）从数序中查找数据元素并删除分析：数据成员： int count; /数序中元素的个数 int aMAX; /存放数序的数组成员函数： void addnum(int n); /向有序数组中添加元素 v0id delenum(int n); /从有序数组中查找元素并删除 numSet( ) count=0; /构造函数 void disp ( ); /输出有序数组 测试数据：numSet set1,set2; set1.addnum(3); set1.addnum(2); set1.addnum(1); set1.disp( ); set1.delenum(2); set1.disp( ); 3）求两个整数数序的合并数序分析：增加友元函数： friend numSet unionset(numSet &s1, numSet &s2); 返回s1与s2合并的结果 即：S= s1,s2 s1: i=0 icount i+ s2: j=0 jcount j+ s1.ai 与 s2.aj 比较确定添加顺序例：set3=unionset(set1,set2)；set1: 1,2,3set2: 2,4,5,6set3: 1,2,3,4,5,6#include using namespace std;const int MAX=20;class Numsetfriend Numset unionset(Numset &s1,Numset &s2); /合并数序s1和s2 int count; int aMAX;public: Numset()count=0; void addnum(int n)int i=0,j;while(iai) i+;else break; /条件合并可简化逻辑 while(iai) i+;if(n=ai) return;for(j=count;ji;j-)aj=aj-1;ai=n;count+;void disp() for(int i=0;icount;i+) coutai ; coutendl; int geti(int i) return ai; Numset unionset(Numset &s1,Numset &s2) Numset s; int i=0,j=0; while(is1.count&js2.count) int v1=s1.ai; int v2=s2.aj; if(v1v2)s.addnum(v2);j+; else s.addnum(v1);i+;j+; while(is1.count) int v1=s1.ai; s.addnum(v1); i+; while(js2.count) int v2=s2.aj; s.addnum(v2); j+; return s;int main()Numset set1,set2,set3;set1.addnum(1);set1.addnum(3);set1.addnum(2);set1.addnum(6);cout数序一为：endl;set1.disp(); set2.addnum(3);set2.addnum(5);set2.addnum(7);set2.addnum(4);cout数序二为：endl;set2.disp();set3=unionset(set1,set2);cout数序一与数序二合并为：;set3.disp();return 0; 练习1、要求：定义一个集合类，要求： (1) 集合中的元素可用数组存放，也可用链表存放， 参考提示：用数组存放时，集合中数据成员元素个数数组(定义时用最大值) 用链表存放时，集合中数据成员元素个数指针(定义时指向结点类型) (2) 构造函数要求：能够通过从键盘上输入数据的形式，给集合中各元素赋值 (3) 要求能实现显示集合中元素个数 (4) 能显示集合中的元素 (5) 能向集合中增加元素 (6) 能从集合中删除元素 (7) 能实现两个集合的+(U)相并 (8) 能实现两个集合的( )相交 (8) 能实现两个集合的(差集) (9)在主函数中实现上述功能(创建对象，输入集合中元素，显示元素及个数，能增、删元素，实现集合并、交、差) 练习2要求：设计一个集合类Set，并重载运算符+、-以分别实现集合的并、差操作。另外设计一个主函数演示Set的使用。练习3：设计一个集合类Set，包括将集合置空、添加元素、判断元素是否在集合中、输出集合，以及将集合中元素逆置，另外还有一个拷贝构造函数，并使用一些数据进行测试。 解： Set类包括私有数据成员elems(存放集合元素)、pc(当前元素指针)，一个默认构造函数和拷贝构造函数Set(Set &s)，另有成员函数empty()(将集合置空)、isempty()(判断集合是否为空)、ismemberof()(判断元素是否在集合中)、add()(添加元素)、print()(输出集合)、reverse(将集合中元素置逆)。#include #define Max 100 class Set public: Set()pc=0; Set(Set &s); / 对象引用作为参数 void empty()pc=0; int isempty()return pc=0; int ismemberof(int n); int add(int n); void print(); void reverse(); private: int elemsMax; int pc; ; int Set:ismemberof(int n) for(int i=0;iMax) return 0; else elemspc+=n; return 1; Set:Set(Set &p) pc=p.pc; for(int i=0;ipc;i+) elemsi=p.elemsi; void Set:print() cout; for(int i=0;ipc-1;i+) coutelemsi0) coutelemspc-1; coutendl; void Set:reverse() int n=pc/2; for(int i=0;in;i+) int temp; temp=elemsi; elemsi=elemspc-i-1; elemspc-i-1=temp; void main() Set A; coutA是否为空：; coutA.isempty()endl; coutA:; A.print(); Set B; for(int i=1;i=8;i+) B.add(i); coutB:; B.print(); cout5是否在B中：; coutB.ismemberof(5)endl; B.empty(); for(int j=11;j20;j+) B.add(j); Set C(B); coutC:; C.print(); C.reverse(); coutC逆置endl; coutC:; C.print(); 练习4：要求：输入两个数组，并对元素过滤，实现交，并，差（还可以用混合运算） 1程序中，集合的元素限定为小写字母字符a.z,。集合输入的形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。 2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。 3.测试数据 (1) L1=”magazine”, L2= “paper”, L1L2=”aegimnprz”，L1L2=”ae”，L1-L2=”gimnz”； (2) L1=”012oper4a6tion89”，L2=”error data”， L1L2=”adeinoprt”，L1L2=”aeort”，L1-L2=”inp”。 程序1： struct SET /定义结构 char ch; SET * next; ; void display(SET * phead) /phead为链首指针 if(phead=NULL) cout 空集; else while(phead) cout ch; phead=phead-next; cout endl; ; /*建立链表*/ SET * build() SET * ps; /当前节点指针 SET * pend; /链尾指针 SET * pd; /中间指针 SET * head; char tem20; /输入存放变量 int i; ps=new SET; /开辟堆内存 cin.getline(tem,sizeof(tem); /接收字符串 head=NULL; pend=ps; for(i=0;i=A&temich=temi; if(head=NULL) /判断链首是否为空 head=ps; /为空则将元素做为链首 ps-next=NULL; goto onemore; pd=head; while(pd) if(pd-ch=ps-ch) goto again; /删除重复的元素，重复则进入下一次循环，不插入 pd=pd-next; if(head-chps-ch) /插入一个结点 /若结点比链首小，则该结点成为新链首 ps-next=head; head=ps; goto onemore; else if(pend-chch) /若结点比链尾大，则该结点成为新链尾 pend-next=ps