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

1、课 程 设 计 任 务 书 学院信息科学与工程专业通信工程 学生姓名学号 设计题目集合类的设计与实现 内容及要求： 本课程设计主要是集合的交、并和差运算的研究与实现，用有序单链表表 示集合，实现集合的交、并和差运算。研究表明，采用有序存储的运算简单、 方便。 通过类与对象的设计，编制一个能演示执行集合的并、交和差运算的程序， 要求如下： （1）集合的元素限定为小写字母字符a,z。 （2）演示程序以用户和计算机的对话方式执行。 （3）以有序链表表示集合。 （4）可进一步实现集合的元素判定和子集判定运算。 进度安排： 第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计； 第 18 周：

2、程序的设计、调试与实现； 第 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 运行结果分析运行

3、结果分析.- 11 - 6 基于基于 mfc 的图形界面程序开发的图形界面程序开发.- 12 - 6.1 基于基于 mfc 的图形界面程序设计的图形界面程序设计.- 12 - 6.2 程序测试程序测试.- 15 - 6.3 mfc 程序编写总结程序编写总结.- 19 - 7 参考文献参考文献 .- 20 - 1 需求分析需求分析 （1）本演示程序中，集合的元素限定为小写字母字符a.z，集合 的大小 n27。集合输入的形式为一个以“#”为结束标志的字符串，串中字符 顺序不限，且允许出现重复字符及非法字符，程序应能自动滤去。输出的运行 结果字符串将不含重复字符及非法字符。 （2）演示程序以用户和计

4、算机的对话方式执行，即在计算机终端上显示 “提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的 输入数据（滤去输入中的非法字符）和运算结果显示在其后。 （3）程序执行的命令包括： 1).构造集合 1；2).构造集合 2；3).求并集；4).求交集；5).求差集；6).结 束。 “构造集合 1”和“构造集合 2”时，需以字符串的形式键入集合元素。 （4）测试数据 1).head1=”merry”,head2=”christmas”,head1head2=”acehimrsty”,head1hea d2=”mr”,head1-head2=”ey” ； 2).head1=”012ab

5、cde”,head2=”123cdefg”,head1head2=”abcdefg”, head1head2=”cde”,head1-head2=”ab” 。 2 算法基本原理算法基本原理 本课题采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素 节点，有序链表，有序集和主控模块，使得设计时思路清晰，实现时调试顺利， 各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。 建立集合类，在类的成员函数中，通过尾插法生成一个有 n 个结点的单链 表。单链表是集合存储的基础，单链表建立算法需要一个计数循环语句，为每 个元素建立一个结点，插入头结点之后。算法流程图如下 2-1 所示。 否

6、 是 图 2-1 单链表流程图 集合运算系统，是将两单链表进行交、并和差的集合运算，其流程图如图 2-2 所示。 图 2-2 集合运算系统流程图 开始 初始化一个单链表 输入字符为 # 建立一个插入头 结点后的结点 结束 开始 输入提示 任意输入两组字符串 并集运算交集运算差集运算y/y 继续 其他 退出 输出运行结果 结束 3 类设计类设计 从上面的算法分析可以看到，本设计面临的计算问题的关键是集合运算。 可以定义一个线性表类 linklist 作为基类，从问题的需要来看，在线性表类应包 括对两单链表的操作的成员函数。 在集合的求解过程中，在线性表类 linklist 的成员函数 initl

7、inklist(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 文件包括程序的主函数，主函数

8、中定义了一个类 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 linklist public: initlinklist(linklist head) char ch; node *p=head; head-next=null; head-dat

9、a=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 m

10、erge(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 p-next=newnode; p=newnode; p-next=null; else if(check(p1-data,head)=true) p-next=newnode; p=newnode; p-next=null; if(check(p2-data

11、,head)=true) p-next=newnode; p=newnode; p-next=null; p1=p1-next; p2=p2-next; while(p1!=null) if(check(p1-data,head)=true) p-next=newnode; p=newnode; p-next=null; p1=p1-next; while(p2!=null) if(check(p2-data,head)=true) p-next=newnode; p=newnode; p-next=null; p2=p2-next; return head; /集合 a 中的元素，b 中是否

12、存在 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; /两个集合的差集

13、 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) p-next=newnode; p=newnode; p-next=null; p1=p1-next; return head; /两个集合交集 linklist insection(linklist head1,linklist head2) node *p1=hea

14、d1-next; linklist head=(node*)malloc(size); head-data=0; head-next=null; node *p=head; while(p1!=null) if(isexist(p1-data,head2)=1) 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;

15、; 在程序的类声明部分，先由类的成员函数 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.initlin

16、klist(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; 在程序的主函数

17、部分，先由类生成一个对象，再由此对象调用类的各成员函数， 求出集合的并，交，差运算结果并输出。 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 界

19、面 程序的输入输出方式不同，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 appwi

20、zard（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并集 botton idc

21、_button_cha差集 edit box idc_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成员变量类型成员变量名称 id

22、c_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 实