《面向对象课程设计集合类的设计与实现.doc》由会员分享，可在线阅读，更多相关《面向对象课程设计集合类的设计与实现.doc（22页珍藏版）》请在三一办公上搜索。
1、课 程 设 计 任 务 书学院信息科学与工程专业通信工程学生姓名学号设计题目集合类的设计与实现内容及要求：本课程设计主要是集合的交、并和差运算的研究与实现，用有序单链表表示集合，实现集合的交、并和差运算。研究表明，采用有序存储的运算简单、方便。通过类与对象的设计，编制一个能演示执行集合的并、交和差运算的程序，要求如下：（1）集合的元素限定为小写字母字符a,z。（2）演示程序以用户和计算机的对话方式执行。（3）以有序链表表示集合。（4）可进一步实现集合的元素判定和子集判定运算。进度安排：第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测
2、试与分析，撰写课程设计报告，进行答辩验收。指导教师（签字）：年 月 日学院院长（签字）年 月 日目 录1 需求分析- 1 -2 算法基本原理- 1 -图2-1单链表流程图- 2 -3 类设计- 3 -4 详细设计- 3 -4.1 类的设计和实现- 3 -4.2 主函数设计- 9 -5 DOS界面程序运行结果及分析- 10 -5.1 程序运行结果- 10 -5.2运行结果分析- 11 -6 基于MFC的图形界面程序开发- 12 -6.1 基于MFC的图形界面程序设计- 12 -6.2 程序测试- 15 -6.3 MFC程序编写总结- 19 -7 参考文献- 20 -1 需求分析（1）本演示程序中
3、，集合的元素限定为小写字母字符a.z，集合的大小n27。集合输入的形式为一个以“#”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符及非法字符，程序应能自动滤去。输出的运行结果字符串将不含重复字符及非法字符。（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。（3）程序执行的命令包括： 1).构造集合1；2).构造集合2；3).求并集；4).求交集；5).求差集；6).结束。 “构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。（4）测试数据
4、 1).head1=”merry”,head2=”Christmas”,head1head2=”acehimrsty”,head1head2=”mr”,head1-head2=”ey”； 2).head1=”012abcde”,head2=”123cdefg”,head1head2=”abcdefg”,head1head2=”cde”,head1-head2=”ab”。2 算法基本原理本课题采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素节点，有序链表，有序集和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。建立集合类，在类的
5、成员函数中，通过尾插法生成一个有N个结点的单链表。单链表是集合存储的基础，单链表建立算法需要一个计数循环语句，为每个元素建立一个结点，插入头结点之后。算法流程图如下2-1所示。开始初始化一个单链表输入字符为# 否建立一个插入头结点后的结点是结束图2-1单链表流程图开始集合运算系统，是将两单链表进行交、并和差的集合运算，其流程图如图2-2所示。输入提示任意输入两组字符串y/Y 继续其他 退出差集运算交集运算并集运算输出运行结果结束图2-2 集合运算系统流程图3 类设计从上面的算法分析可以看到，本设计面临的计算问题的关键是集合运算。可以定义一个线性表类Linklist作为基类，从问题的需要来看，在
6、线性表类应包括对两单链表的操作的成员函数。在集合的求解过程中，在线性表类Linklist的成员函数initLinklist(LinkList Head)中需要初始化类Linklist的数据成员，再利用成员函数 LinkList Merge(LinkList Head1,LinkList Head2)，LinkList Insection(LinkList Head1,LinkList Head2)，LinkList Deprive(LinkList Head1,LinkList Head2)分别求得两集合的并，交，差运算结果。4 详细设计整个程序分为两个独立的文档，Linklist.cpp包含
7、了单链表的定义和对两集合运算的成员函数；main.cpp文件包括程序的主函数，主函数中定义了一个类Linklist的对象，通过这个对象求解两集合的交，并，差运算结果。4.1 类的设计和实现#include using namespace std; typedef struct Node char data; Node *next; Node,*LinkList; #define SIZE sizeof(Node) #define FALSE 0 #define TRUE 1 class Linklistpublic:initLinklist(LinkList Head) char ch; No
8、de *p=Head; Head-next=NULL; Head-data=0; cinch; while(ch!=#) Node *newNode=(Node*)malloc(SIZE); newNode-data=ch; p-next=newNode; p=p-next; cinch; p-next=NULL; int Check(char ch,LinkList Head) Node *temp=Head-next; int flag=TRUE; while(temp!=NULL) if(temp-data=ch) flag=FALSE; return flag; temp=temp-n
9、ext; return flag; /合并两个集合 LinkList Merge(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Head-data=0;Head-next=NULL; Node *p1=Head1-next; Node *p2=Head2-next; Node *p=Head; while(p1!=NULL&p2!=NULL) if(p1-data=p2-data) if(Check(p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; p-
10、next=newNode; p=newNode; p-next=NULL; else if(Check(p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; if(Check(p2-data,Head)=TRUE)&(p2-data=97&p2-datadata=p2-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; p2=p2-next; while(p1!=NULL) if(Check(p1-d
11、ata,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; while(p2!=NULL) if(Check(p2-data,Head)=TRUE)&(p2-data=97&p2-datadata=p2-data; p-next=newNode; p=newNode; p-next=NULL; p2=p2-next; return Head; /集合A中的元素，B中是否存在 int IsExist(char data,LinkList Head) Nod
12、e *p=Head-next; int flag=FALSE; while(p!=NULL) if(p-data=data) return flag=TRUE; p=p-next; return flag; int IsExist2(char data,LinkList Head) Node *p=Head-next; int flag=FALSE; while(p!=NULL) if(p-data=data) return flag; p=p-next; return flag=TRUE; /两个集合的差集 LinkList Deprive(LinkList Head1,LinkList H
13、ead2) LinkList Head=(Node*)malloc(SIZE); Node *p=Head; Node *p1=Head1-next; while(p1!=NULL) if(IsExist2(p1-data,Head2)=1)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; return Head; /两个集合交集 LinkList Insection(LinkList Head1,LinkList Head2) Node *p1=Head1-next; L
14、inkList Head=(Node*)malloc(SIZE); Head-data=0; Head-next=NULL; Node *p=Head; while(p1!=NULL) if(IsExist(p1-data,Head2)=1)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; return Head; /打印集合元素 void PrintLinkList(LinkList Head) Node *p=Head-next; while(p!=NULL) cout
15、data; p=p-next; coutn; ;在程序的类声明部分，先由类的成员函数initLinklist(LinkList Head)生成单链表，然后由各成员函数对其进行集合的并，交，差运算。4.2 主函数设计int main() char cmd; Linklist List; do cout*n;cout*集合运算系统*n; cout*n;cout输入两个集合的元素，输完一个集合的元素,按#结束n; LinkList head1=(Node*)malloc(SIZE); LinkList head2=(Node*)malloc(SIZE); List.initLinklist(head
16、1);List.initLinklist(head2); Node *Head1=List.Merge(head1,head2); cout两个集合并集为n; List.PrintLinkList(Head1); Node *Head2=List.Insection(head1,head2); cout两个集合交集为n; List.PrintLinkList(Head2); Node *Head3=List.Deprive(head1,head2); cout两个集合差集为n; List.PrintLinkList(Head3); coutcmd; while(cmd=y|cmd=Y); re
17、turn 0; 在程序的主函数部分，先由类生成一个对象，再由此对象调用类的各成员函数，求出集合的并，交，差运算结果并输出。5 DOS界面程序运行结果及分析5.1 程序运行结果测试数据一运行结果如图5-1所示。图5-1 程序运行结果测试数据二运行结果如图5-2所示。图5-2 程序运行结果5.2运行结果分析整个程序中的集合存储采用的是动态内存分配方式。由Linklist类生成一个对象用来存放集合，然后由此对象调用成员函数，对集合进行各种并，交，差运算。并运算，是生成一个新的单链表，然后利用尾插法将两个集合的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。交运算，是生成一个新的单
18、链表，然后利用尾插法将两个集合的相同元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。差运算，是生成一个新的单链表，然后利用尾插法将集合一中不同于集合二的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。在主函数中对两集合进行测试，运算完成后，设置一个循环，若输入y/Y则继续运算，否则结束程序。6 基于MFC的图形界面程序开发MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I
19、/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。6.1 基于MFC的图形界面程序设计（1）界面设计首先在VC中建立MFC AppWizard（exe）工程，名称为MFC，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如下图6-1所示。图6-1 建立MFC AppWizard（exe）工程图6-2 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6-3所示。 图6-3 集合运算程序界面设计图6-3所示的界面
20、中包含了3个Static Text控件，4个Button控件，和1个Edit Box控件，控件的基本信息列表如下表1所示。表1 控件基本信息控件类别控件ID控件Caption说明Static TextIDC_STATIC输入操作记录功能BottonIDC_BUTTON_Def确定IDC_BUTTON_Jiao交集IDC_BUTTON_Bing并集IDC_BUTTON_Cha差集Edit BoxIDC_EDIT_A00 IDC_EDIT_A100集合的元素（2）代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为1个Edit Box控件建立Member Variables，按Ctrl+
21、w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设置界面，如图6-4所示。图6-4 成员变量设置界面通过该界面设置与1个Edit Box控件对应的成员变量，具体如表2所示。表2 控件基本信息控件ID成员变量类型成员变量名称IDC_EDIT_A00 IDC_EDIT_A100charm_A00m_A100下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。将Linklist.h文件和Linklist.cpp文件合并成一个文件，重新命名为Linklist.h，并将其加入MF
22、C工程。修改Linklist.h文件。在对话框类的实现文件MFCDlg.cpp中加入#include ，以实现在该文件中可使用Linklist类。在MFCDlg.cpp文件中加入全局变量的定义，以实现MFCDlg类和Linklist类之间的通信。编写读入元素按钮的消息处理函数，实现将集合的元素刷新到界面上。编写集合交，并，差及确定按钮的消息处理函数，6.2 程序测试运行程序后，首先出现的界面如图6-5所示。图6-5 程序初始运行界面输入集合一的元素后单击确定按钮后，可将集合一的元素在界面上显示出来，同理，可现示集合二的元素，如图6-6所示。图6-6 输入集合元素后的界面单击交集求解按钮，实现操
23、作并将操作结果显示出来，如图6-7所示。图6-7 实现交运算后的界面同理可实现并集，差集运算，如图6-8所示。图6-8实现并，差运算后的界面6.3 MFC程序编写总结MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上，而这些问题在DOS界面程序中是不存在的，因此，初学MFC的编程者会对此感到困难，然而，当你编写出一个基于Windows界面的程序时，所获得的满足程度远远大于简单的DOS界面程序，况且基于Windows的图形界面的程序设计已成为主流，作为程序员而言，是非学会不可的。本次课程设计作为编写Windows程序
24、的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，本此编写的MFC程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，主要包括以下几个方面。（1）功能不完全，可增进集合的元素判定和子集判定运算（2）将类的定义与实现放在同一个头文件Linklist.h中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件。（3）图6-8所示的界面中没有退出程序按钮，显得程序不够规范。7 参考文献1 李爱华，程磊. 面向对象程序设计（C+语言）. 北京:清华大学出版社,20102 严蔚敏，吴伟民. 数据结构（C语言版） . 北京:清华大学出版社,20113 严蔚敏，吴伟民，米宁. 数据结构题集（C语言版）. 北京:清华大学出版社,20114 徐士良. C常用算法程序集. 北京:清华大学出版社,19955 钱能. C+程序设计教程（第二版）. 北京:清华大学出版社,2007
