集合类的设计与实现

1、封皮按学校要求手工填写课程设计任务书学院专业学生姓名学号设计题目集合类的设计与实现内容及要求:1.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计水平;2,初步掌握程序设计过程中的结构化程序设计的一般方法,及数据类型在设计中的应用.3,能够利用所学的根本知识和技能,解决简单的程序设计问题；通过类与对象的设计,编制一个能演示执行集合的并、交和差运算的程序,要求如下：(1)集合的元素限定为小写字母字符'a','z'.(2)演示程序以用户和计算机的对话方式执行.(3)以有序链表表示集合.(4)可进一步实现集合的元素判定和子集判定运算.进度安排：第17周：分

2、析题目,查阅课题相关资料,进行类设计、算法设计;第18周：程序的设计、调试与实现；第19周：程序测试与分析,撰写课程设计报告,进行辩论验收.指导教师(签字)：学院院长(签字)年月日年月日1需求分析-1-2算法根本原理-1-3类设计-1-4详细设计-1-4.1 类的接口设计-2-4.2 类的实现-2-4.3 主函数设计-4-5DO国面程序运行结果及分析-5-5.1 程序运行结果错误!未定义书签.5.2 运行结果分析-6-6基于MFC勺图形界面程序开发-6-6.1 基于MFC勺图形界面程序设计-6-6.2 程序测试-21-6.3 MFC1序编写总结-24-7参考文献-25-1需求分析1问题描述：用

3、有序单链表表示集合,实现集合的交、并、差运算,且空间复杂度为0(1)2根本功能：可快速的分别求出两个字符集合的交、并、差.3输入和输出：(1)输入：在C+环境下编写的程序,其输入是简单、方便的,即按提示分别输入两集合的元素.输入字符的范围：小写字母a,b,.,y,z,大写字母A,B,.Y,Z,和数字0,1,.8,9;输入形式：字符集合,按顺序大小排序输入,允许出现重复字符,程序能自动滤去；(2)输出：程序采用单链表的存储结构,使得运算快捷简便,显示的结果也明了.输出结果不含重复或非法字符；2算法根本原理Setl=a,b,x,w,Set2=a,b,y,z,SetlUSet2=a,b,x,y,z,

4、wSetlnSet2=a,bSetlSet2=x,w3类设计从上面的算法分析可以看到,本设计关键是集合的并,交,差运算.可以定义一个类int_set,然后由该类定义出私有和公有成员函数,为主函数的执行做好铺垫4详细设计整个程序分为三大块,先是类的接口,定义出基类后再在类中定义出相关成员函数：接着是累的实现局部,写出具体的函数代码,用以执行相关功能；最后那么是主函数,用一天调用各个函数并执行相应的输入输出功能4.1 类的接口设计#include<iostream.h>classint_set(private:intmax_size;intcur_size;char*p;public:

5、int_set(constint_set&a)/必须有拷贝构造函数,由于下面以对象为返回值max_size=a.max_size;cur_size=a.cur_size;p=newchara.max_size;for(inti=0;i<cur_size;i+)pi=a.pi;int_set(intx)cur_size=0;max_size=x;p=newcharx;int_set()deletep;4.2 类的实现intsearch(charx)/判断一个元素是否在集合中for(inti=0;i<max_size;i+)if(pi=x)return1;return0;voi

6、difsearch(charx)(if(search(x)cout<<x<<"在集合中！"<<endl;elsecout<<x<<"不在集合中！"<<endl;)voidadd(charx)/增加一个整数到集合中if(cur_size>=max_size)cout<<"集合已满,不可再添加元素！"<<endl;elseif(!search(x)pcur_size=x;cur_size+;)voiddec(charx)/从集合中去掉一个

7、元素for(inti=0;i<max_size;i+)if(pi=x)for(i;i<max_size-1;i+)pi=pi+1;cur_size-;)/输入friendistream&operator<<(istream&in,int_set&a)/注意在类内写友元的实现时不能直接使用类成员cout<<"请输入集合("<<a.max_size<<"个小写字母(az)：;for(inti=0;i<a.max_size;i+)cin>>a.pi;/不能直接写pia.

8、cur_size=a.max_size;returnin;/in可以换别的/输出friendostream&operator>>(ostream&out,int_set&a)for(inti=0;i<a.cur_size;i+)cout<<a.pi<<''cout<<endl;returnout;int_setjiao(int_set&b)/交集int_settemp(max_size);for(inti=0;i<b.cur_size;i+)Iif(search(b.pi)temp.pt

9、emp.cur_size=b.pi;temp.cur_size+;returntemp;int_setbing(int_set&b)/并集int_settemp(max_size+b.max_size);for(inti=0;i<max_size;i+)temp.pi=pi;temp.cur_size=cur_size;for(i=0;i<b.cur_size;i+)if(!search(b.pi)temp.ptemp.cur_size=b.pi;temp.cur_size+;returntemp;int_setcha(int_set&b)/求差int_settem

10、p(max_size);for(inti=0;i<max_size;i+)temp.pi=pi;temp.cur_size=cur_size;for(i=0;i<b.cur_size;i+)Iif(temp.search(b.pi)temp.dec(b.pi);returntemp;/*/;4.3 主函数设计voidmain()int_setobj1(8);int_setobj2(6);cin<<obj1;/输入集合cin<<obj2;obj1.dec(1);/删除一个元素cout>>obj1;obj1.add(7);cout>>ob

11、j1;obj1.add(8);/添加一个元素再添加一个元素判断元素是否在集合中obj1.ifsearch(3);/obj1.ifsearch(0);cout<<"交集为："cout>>obj1.jiao(obj2);/被提前释放了,输出大的随机数*/cout<<"并集为："cout>>obj1.bing(obj2);/cout<<"差为："cout>>obj1.cha(obj2);/求交集/*假设没拷贝构造函数,那么指针求并集差运算5DOS界面程序运行结果及分析5

12、.1 程序运行结果5.2 运行结果分析在程序运行过程中,前面的局部必须有拷贝构造函数,由于后续需要以对象为返回值,中间的局部那么需要注意在类内写友元的实现时不能直接使用类成员,最后的局部假设没拷贝构造函数,那么指针被提前释放了,会输出大的随机数,那么不符合题目要求.6基于MFC勺图形界面程序开发MFC勺图形界面程序设计可在上述类设计的根底上进行改造,MFC勺图形界面程序与DO以面程序的主要不同点是：MFCS形界面程序与DO鼾面程序的输入输出方式不同,DOS界面程序采用字符交互式实现数据输入输出,主要通过cin,cout等I/O流实现,而MFC勺图形程序界面采用标准Windows窗口和控件实现输

13、入输出,因此必须在MFCI的框架下参加上面所设计的矩阵和方程组类,并通过图形界面的输入输出改造来完成.6.1基于MFC勺图形界面程序设计(1)界面设计首先在VC中建立MFCAppWizard(exe)工程,名称为集合类,并在向导的Step1中选择Dialogbased,即建立基于对话框的应用程图4建立MFCAppWizard(exe)工程图5建立基于对话框的应用程序6所示.将对话框资源中的默认对话框利用工具箱改造成如下界面,如图图6方集合的并交差界面设计图6所示的界面中包含了3个Edit控件,6个Button控件,控件的根本信息列表如下表1所小.控件类别控件ID控件Caption说明EditB

14、oxIDC_EDIT1集合1IDC_EDIT2集合2IDC_EDIT3所求集合BottonIDC_BUTTON1计算交集IDC_BUTTON2计算并集IDC_BUTTON3计算差集A-BIDC_BUTTON4计算差集B-AIDC_BUTTON6验证集合关系表1控件根本信息(2)代码设计为了能够将对话框界面上的控件能够与代码联系起来,需要为3个EditBox控件建立MemberVariables,按Ctrl+w键进入MFCClassWizard界面,选择MemberVariables选项卡,可显示成员变量设置界面,如图7所示.图7成员变量设置界面通过该界面设置与3个EditBox控件对应的成员变

15、量,具体如表2所示表2控件根本信息控件ID成员变量类型成员变量名称IDC_EDIT1Stringm_1IDC_EDIT2Stringm_2IDC_EDIT3Stringm_3下面是编写代码的重要阶段,可以借鉴在设计基于DO阴面的限制台应用程序的代码,并将其作必要的改写,具体改写的步骤与内容如下.1将JIHE.h文件和JIHE.cpp文件合并成一个文件,重新命名为JIHE.h,并将其参加MFC：程.2在对话框类的实现文件JIHEDlg.cpp中参加#include"Jihe.h",以实现在该文件中可使用Jihe类.3在JIHEDlg.cpp文件中参加以下全局变量的定义,以实现

16、JIHEDlg类和JIHE类之间的通信,具体代码如下：CJIHEDlg:CJIHEDlg(CWnd*pParent/*=NULL*/):CDialog(CJIHEDlg:IDD,pParent)/AFX_DATA_INIT(CJIHEDlg)m_1=_T("");m_2=_T("");m_3=_T("");/AFX_DATA_INIT/NotethatLoadicondoesnotrequireasubsequentDestroylconinWin32m_hlcon=AfxGetApp()->LoadIcon(IDR_MAINF

17、RAME);voidCJIHEDIg二DoDataExchange(CDataExchange*pDX)(CDiaIog:DoDataExchange(pDX);/AFX_DATA_MAP(CJIHEDIg)DDX_Text(pDX,IDC_EDIT1,m_1);DDX_Text(pDX,IDC_EDIT2,m_2);DDX_Text(pDX,IDC_EDIT3,m_3);/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CJIHEDIg,CDialog)/AFX_MSG_MAP(CJIHEDIg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERY

18、DRAGICON()ON_BN_CLICKED(IDC_BUTTON1,Onjiao)ON_BN_CLICKED(IDC_BUTTON2,Onbing)ON_BN_CLICKED(IDC_BUTTON3,Onbu)ON_BN_CLICKED(IDC_BUTTON4,Oncha)ON_BN_CLICKED(IDC_BUTTON5,Onduichencha)ON_BN_CLICKED(IDC_BUTTON6,Onbaohan)/AFX_MSG_MAPEND_MESSAGE_MAP()4运行代码BOOLCJIHEDIg:OnInitDiaIog()CDialog:OnInitDialog();/Ad

19、d"About."menuitemtosystemmenu./IDM_ABOUTBOXmustbeinthesystemcommandrange.ASSERT(IDM_ABOUTBOX&0xFFF0)=IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX<0xF000);CMenu*pSysMenu=GetSystemMenu(FALSE);if(pSysMenu!=NULL)CStringstrAboutMenu;strAboutMenu.LoadString(IDS_ABOUTBOX);if(!strAboutMenu.IsEmpty()pS

20、ysMenu->AppendMenu(MF_SEPARATOR);pSysMenu->AppendMenu(MF_STRING,IDM_ABOUTBOX,strAboutMenu);/Settheiconforthisdialog.Theframeworkdoesthisautomatically/whentheapplication'smainwindowisnotadialogSetIcon(m_hIcon,TRUE);/SetbigiconSetIcon(m_hIcon,FALSE);/Setsmallicon/TODO:Addextrainitializationh

21、erereturnTRUE;/returnTRUEunlessyousetthefocustoacontrolvoidCJIHEDlg:OnSysCommand(UINTnID,LPARAMlParam)if(nID&0xFFF0)=IDM_ABOUTBOX)(CAboutDlgdlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID,lParam);/Ifyouaddaminimizebuttontoyourdialog,youwillneedthecodebelow/todrawtheicon.ForMFCapplicatio

22、nsusingthedocument/viewmodel,/thisisautomaticallydoneforyoubytheframework.voidCJIHEDlg:OnPaint()(if(IsIconic()(CPaintDCdc(this);/devicecontextforpaintingSendMessage(WM_ICONERASEBK%PARAMdc.GetSafeHdc(),0);/CentericoninclientrectangleintcxIcon=GetSystemMetrics(SM_CXICON);intcyIcon=GetSystemMetrics(SM_

23、CYICON);CRectrect;GetClientRect(&rect);intx=(rect.Width()-cxIcon+1)/2;inty=(rect.Height()-cyIcon+1)/2;/Drawtheicondc.DrawIcon(x,y,m_hIcon);)else(CDialog:OnPaint();)/Thesystemcallsthistoobtainthecursortodisplaywhiletheuserdrags/theminimizedwindow.HCURSORCJIHEDlg:OnQueryDragIcon()(return(HCURSOR)m

24、_hIcon;)intCJIHEDlg:panduanCF()(UpdateData(1);m_3.Empty();CStringm,n;for(inti=0;i<=m_1.GetLength()/2;i+)(AfxExtractSubString(m,(LPCTSTR)m_1,i,'');for(intj=i+1;j<=m_1.GetLength()/2;j+)(AfxExtractSubString(n,(LPCTSTR)m_1,j,'');if(m=n)AfxMessageBox("重复输入");m_1="0&qu

25、ot;m_2="0"UpdateData(0);return1;)for(i=0;i<=m_2.GetLength()/2;i+)(AfxExtractSubString(m,(LPCTSTR)m_2,i,'');for(intj=i+1;j<=m_2.GetLength()/2;j+)(AfxExtractSubString(n,(LPCTSTR)m_2,j,'');if(m=n)AfxMessageBox("重复输入！");m_1="0"m_2="0"UpdateDa

26、ta(0);return1;return0;5求相应集合的运算代码voidCJIHEDlg:Onjiao()UpdateData(1);m_3.Empty();if(panduanCF()return;CStringtem,dem;if(m_1="0"&&m_2="0")AfxMessageBox("交集为空,请输入元素");m_3="0"return;elseif(m_1="0"|m_2="0")m_3="空集"elsefor(inti=

27、0;i<=m_1.GetLength()/2;i+)for(intj=0;j<=m_2.GetLength()/2;j+)AfxExtractSubString(tem,(LPCTSTR)m_1,i,'');AfxExtractSubString(dem,(LPCTSTR)m_2,j,'');if(tem=dem)(if(m_3.GetLength()=0)m_3=tem;elsem_3=m_3+""+tem;)if(m_3="0")m_3="空集"；UpdateData(0);)voidC

28、JIHEDlg:Onbing()(UpdateData(1);m_3.Empty();UpdateData(0);if(m_1="0"&&m_2="0")AfxMessageBox("并集为空,请输入元素");return;if(panduanCF()return;if(m_1="0"|m_2="0")m_3=m_1+m_2;UpdateData(0);return;m_3=m_1;CStringtem;CStringdem;for(inti=0;i<m_2.GetLeng

29、th();i+)AfxExtractSubString(tem,(LPCTSTR)m_2,i,'');intflag=0;/没有一样的for(intj=0;j<m_1.GetLength();j+)(AfxExtractSubString(dem,(LPCTSTR)m_1,j,'');if(tem=dem)flag=1;break;if(flag=0)m_3=m_3+""+tem;UpdateData(0);voidCJIHEDlg:Onbu()UpdateData(1);m_3.Empty();UpdateData(0);if(m_1

30、="0"&&m_2="0")AfxMessageBox("差集为空,请输入元素)；return;if(panduanCF()return;if(m_2="0")m_3=m_1;UpdateData(0);return;if(m_1="0")m_3="空集"UpdateData(0);return;CStringtem;CStringdem;for(inti=0;i<=m_1.GetLength();i+)(intpd=1;for(intj=0;j<=m_2.

31、GetLength();j+)(AfxExtractSubString(tem,(LPCTSTR)m_1,i,'');AfxExtractSubString(dem,(LPCTSTR)m_2,j,'');if(tem=dem)pd=0;break;if(pd=1)m_3=m_3+tem+"UpdateData(0);voidCJIHEDlg:Oncha()UpdateData(1);m_3.Empty();UpdateData(0);if(m_1="0"&&m_2="0")AfxMessageBo

32、x("差集为空,请输入元素)；return;if(panduanCF()return;if(m_1="0")m_3=m_2;UpdateData(0);return;if(m_2="0")m_3="空集"UpdateData(0);return;CStringtem;CStringdem;for(inti=0;i<=m_2.GetLength();i+)intpd=1;for(intj=0;j<=m_1.GetLength();j+)(AfxExtractSubString(tem,(LPCTSTR)m_2,i,

33、'');AfxExtractSubString(dem,(LPCTSTR)m_1,j,'');if(tem=dem)pd=0;break;if(pd=1)m_3=m_3+tem+"UpdateData(0);voidCJIHEDlg二Onduichencha()UpdateData(1);m_3.Empty();UpdateData(0);if(m_1="0"&&m_2="0")AfxMessageBox("对称差为空,请输入元素)return;if(panduanCF()return;

34、if(m_1="0")m_3=m_2;UpdateData(0);return;if(m_2="0")m_3=m_1;UpdateData(0);return;CStringtem;CStringdem;for(inti=0;i<=m_1.GetLength();i+)intpd=1;for(intj=0;j<=m_2.GetLength();j+)AfxExtractSubString(tem,(LPCTSTR)m_1,i,'');AfxExtractSubString(dem,(LPCTSTR)m_2,j,'

35、9;);if(tem=dem)pd=0;break;if(pd=1)m_3=m_3+tem+"for(i=0;i<=m_2.GetLength();i+)intpd=1;for(intj=0;j<=m_1.GetLength();j+)AfxExtractSubString(tem,(LPCTSTR)m_2,i,'');AfxExtractSubString(dem,(LPCTSTR)m_1,j,'');if(tem=dem)pd=0;break;if(pd=1)m_3=m_3+tem+"UpdateData(0);voidCJI

36、HEDlg二Onbaohan()UpdateData(1);m_3.Empty();if(m_1="0"&&m_2="0")AfxMessageBox("AB为空集");return;if(panduanCF()return;if(m_1="0")AfxMessageBox("A为空集,B包含A");return;if(m_2="0")AfxMessageBox("B为空集,A包含B");return;if(m_1=m_2)AfxMessageBox("AB相等)return;/CStringm_4,tem,dem;/交for(inti=0;i<=m_1.GetLength()/2;i+)AfxExtractSubString(tem,(LPCTSTR)m_1,i,'');for(intj=0;j<=m_2.GetLength()/2;j+)AfxExtractSubString(dem,(LPCTSTR)m_2,j,'');if(tem=dem)if(