面向对象课程设计集合类的设计与实现

课 程 设 计 任 务 书学院信息科学与工程专业通信工程学生姓名学号设计题目集合类的设计与实现内容及要求：本课程设计主要是集合的交、并和差运算的研究与实现，用有序单链表表示集合，实现集合的交、并和差运算。研究表明，采用有序存储的运算简单、方便。通过类与对象的设计，编制一个能演示执行集合的并、交和差运算的程序，要求如下：（1）集合的元素限定为小写字母字符a,z。（2）演示程序以用户和计算机的对话方式执行。（3）以有序链表表示集合。（4）可进一步实现集合的元素判定和子集判定运算。进度安排：第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计；第 18 周：程序的设计、调试与实现；第 19 周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师（签字）：年 月 日学院院长（签字）年 月 日目目 录录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）本演示程序中，集合的元素限定为小写字母字符a.z，集合的大小 n27。集合输入的形式为一个以“#”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符及非法字符，程序应能自动滤去。输出的运行结果字符串将不含重复字符及非法字符。（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。（3）程序执行的命令包括： 1).构造集合 1；2).构造集合 2；3).求并集；4).求交集；5).求差集；6).结束。 “构造集合 1”和“构造集合 2”时，需以字符串的形式键入集合元素。（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 算法基本原理算法基本原理本课题采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素节点，有序链表，有序集和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。建立集合类，在类的成员函数中，通过尾插法生成一个有 N 个结点的单链表。单链表是集合存储的基础，单链表建立算法需要一个计数循环语句，为每个元素建立一个结点，插入头结点之后。算法流程图如下 2-1 所示。 否是图 2-1 单链表流程图集合运算系统，是将两单链表进行交、并和差的集合运算，其流程图如图2-2 所示。图 2-2 集合运算系统流程图开始初始化一个单链表输入字符为#建立一个插入头结点后的结点结束开始输入提示任意输入两组字符串并集运算交集运算差集运算y/Y 继续其他 退出输出运行结果结束3 类设计类设计从上面的算法分析可以看到，本设计面临的计算问题的关键是集合运算。可以定义一个线性表类 Linklist 作为基类，从问题的需要来看，在线性表类应包括对两单链表的操作的成员函数。在集合的求解过程中，在线性表类 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 包含了单链表的定义和对两集合运算的成员函数；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; Node *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-next; 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-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-data,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) Node *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 Head2) 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; LinkList 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) coutdata; 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(head1);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); return 0; 在程序的主函数部分，先由类生成一个对象，再由此对象调用类的各成员函数，求出集合的并，交，差运算结果并输出。5 DOS 界面程序运行结果及分析界面程序运行结果及分析5.1 程序运行结果测试数据一运行结果如图 5-1 所示。图 5-1 程序运行结果测试数据二运行结果如图 5-2 所示。图 5-2 程序运行结果5.2 运行结果分析整个程序中的集合存储采用的是动态内存分配方式。由 Linklist 类生成一个对象用来存放集合，然后由此对象调用成员函数，对集合进行各种并，交，差运算。并运算，是生成一个新的单链表，然后利用尾插法将两个集合的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。交运算，是生成一个新的单链表，然后利用尾插法将两个集合的相同元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。差运算，是生成一个新的单链表，然后利用尾插法将集合一中不同于集合二的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。在主函数中对两集合进行测试，运算完成后，设置一个循环，若输入 y/Y则继续运算，否则结束程序。6 基于基于 MFC 的图形界面程序开发的图形界面程序开发MFC 的图形界面程序设计可在上述类设计的基础上进行改造，MFC 的图形界面程序与 DOS 界面程序的主要不同点是：MFC 图形界面程序与 DOS 界面程序的输入输出方式不同，DOS 界面程序采用字符交互式实现数据输入输出，主要通过 cin，cout 等 I/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 所示的界面中包含了 3 个 Static Text 控件，4 个 Button 控件，和 1个 Edit Box 控件，控件的基本信息列表如下表 1 所示。表 1 控件基本信息控件类别控件 ID控件 Caption说明输入操作记录Static TextIDC_STATIC功能IDC_BUTTON_Def确定IDC_BUTTON_Jiao交集IDC_BUTTON_Bing并集BottonIDC_BUTTON_Cha差集Edit BoxIDC_EDIT_A00 IDC_EDIT_A100集合的元素（2）代码设计）代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为 1 个 Edit Box 控件建立 Member Variables，按 Ctrl+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，并将其加入 MFC 工程。修改 Linklist.h 文件。在对话框类的实现文件 MFCDlg.cpp 中加入#include ，以实现在该文件中可使用 Linklist 类。在 MFCDlg.cpp 文件中加入全局变量的定义，以实现 MFCDlg 类和Linklist 类之间的通信。编写读入元素按钮的消息处理函数，实现将集合的元素刷新到界面上。编写集合交，并，差及确定按钮的消息处理函数，6.2 程序测试运行程序后，首先出现的界面如图 6-5 所示。图 6-5 程序初始运行界面输入集合一的元素后单击确定按钮后，可将集合一的元素在界面上显示出来，同理，可现示集合二的元素，如图 6-6 所示。图 6-6 输入集合元素后的界面单击交集求解按钮，实现操作并将操作结果显示出来，如图 6-7 所示。图 6-7 实现交运算后的界面同理可实现并集，差集运算，如图 6-8 所示。图 6-8 实现并，差运算后的界面6.3 MFC 程序编写总结MFC 程序与 DOS 界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上，而这些问题在 DOS 界面程序中是不存在的，因此，初学 MFC 的编程者会对此感到困难，然而，当你编写出一个基于 Windows 界面的程序时，所获得的满足程度远远大于简单的 DOS 界面程序，况且基于 Windows 的图形界面的程序设计已成为主流，作为程序员而言，是非学会不可的。本次课程设计作为编写 Windows 程序的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，本此编写的 MFC 程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，主要包括以下几个方面。（1）功能不完全，可增进集合的元素判定和子集判定运算（2）将类的定义与实现放在同一个头文件 Linklist.h 中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件。（3）图 6-8 所示的界面中没有退出程序按钮，显得程序不够规范。7 参考文献参考文献1 李爱华，程磊. 面向对象程序设计（C+语言）. 北京:清华大学出版社,20102 严蔚敏，吴伟民. 数据结构（C 语言版） . 北京:清华大学出版社,20113 严蔚敏，吴伟民，米宁. 数据结构题集（C 语言版）. 北京:清华大学出版社,20114 徐士良. C 常用算法程序集. 北京:清华大学出版社,19955 钱能. C+程序设计教程（第二版）. 北京:清华大学出版社,2007