集合类的设计与实现

1、1成绩评定表成绩评定表学生姓名钟城班级学号1503060334专 业通信工程课程设计题目集合类的设计与设计评语组长签字：成绩日期 20 年 月 日2课程设计任务书课程设计任务书学 院信息科学与工程学院专 业通信工程学生姓名钟城班级学号1503060334课程设计题目集合类的设计与实现实践教学要求与任务实践教学要求与任务本课程设计主要是集合的交、并和差运算的研究与实现，用有序单链表表示集合，实现集合的交、并和差运算。研究表明，采用有序存储的运算简单、方便。通过类与对象的设计，编制一个能演示执行集合的并、交和差运算的程序，要求如下：（1）集合的元素限定为小写字母字符a,z。（2）演示程序以用户和计

2、算机的对话方式执行。（3）以有序链表表示集合。(4）可进一步实现集合的元素判定和子集判定运算。工作计划与进度安排工作计划与进度安排第 2 周：分析题目，查阅课题相关资料，进行类设计、算法设计；第 3 周：程序的设计、调试与实现；第 4 周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日沈阳理工大学课程设计专用纸 3摘 要现实生活中许多数据的处理依赖于哈希表的应用，通过应用哈希表使复杂问题更加简单化。通过实用类模板，使用开放地址法和除留余数法来实现对哈希表的建立、插入、删除等功能，采用 Visual

3、C+ 6.0 的控制台工程和 MFC 工程分别实现了哈希表的应用。关键词：除留余数法；哈希表；开放地址法；MFC 工程沈阳理工大学课程设计专用纸 4目 录1需求分析.-1-2算法基本原理.-1-3类设计.-3-3.1 类的概述.-3-3.2 类的设计和实现.-3-4基于控制台的应用程序.-9-4.1 主函数设计.-9-4.2 运行结果及分析.-10-5基于 MFC 的应用程序 .-12-5.1 图形界面设计.-12-5.2 程序代码设计.-15-5.3 运行结果及分析.-16-结 论.-20-参考文献.-21-沈阳理工大学课程设计专用纸 01 需求分析 （1）本演示程序中，集合的元素限定为小写

4、字母字符a.z，集合的大小 n27。集合输入的形式为一个以“#”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符及非法字符，程序应能自动滤去。输出的运行结果字符串将不含重复字符及非法字符。（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。 (1)（3）程序执行的命令包括： 1).构造集合 1；2).构造集合 2；3).求并集；4).求交集；5).求差集；6).结束。 “构造集合 1”和“构造集合 2”时，需以字符串的形式键入集合元素。（4）测试数据 1

5、).head1=”merry”,head2=”Christmas”,head1head2=”acehimrsty”,head1head2=”mr”,head1-head2=”ey” ； 2).head1=”012abcde”,head2=”123cdefg”,head1head2=”abcdefg”,head1head2=”cde”,head1-head2=”ab” 。2 算法基本原理 本课题采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素节点，有序链表，有序集和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。建立集合类，在类

6、的成员函数中，通过尾插法生成一个有 N 个结点的单链表。单链表是集合存储的基础，单链表建立算法需要一个计数循环语句，为每个元素建立一个结点，插入头结点之后。算法流程图如下 2-1 所示。沈阳理工大学课程设计专用纸 1 否是图 2-1 单链表流程图集合运算系统，是将两单链表进行交、并和差的集合运算，其流程图如图 2-2 所示。开始初始化一个单链表输入字符为#建立一个插入头结点后的结点结束开始输入提示任意输入两组字符串并集运算交集运算差集运算y/Y 继续其他 退出输出运行结果结束沈阳理工大学课程设计专用纸 2图 2-2 集合运算系统流程图 3 类设计3.1 类的概述 从上面的算法分析可以看到，本设

7、计面临的计算问题的关键是集合运算。可以定义一个线性表类 Linklist 作为基类，从问题的需要来看，在线性表类应包括对两单链表的操作的成员函数。在集合的求解过程中，在线性表类 Linklist 的成员函数 initLinklist(LinkList Head)中需要初始化类 Linklist 的数据成员，再利用成员函数 LinkList Merge(LinkList Head1,LinkList Head2)，LinkList Insection(LinkList Head1,LinkList Head2)，LinkList Deprive(LinkList Head1,LinkList H

8、ead2)分别求得两集合的并，交，差运算结果。整个程序中的集合存储采用的是动态内存分配方式。由 Linklist 类生成一个对象用来存放集合，然后由此对象调用成员函数，对集合进行各种并，交，差运算。并运算，是生成一个新的单链表，然后利用尾插法将两个集合的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。交运算，是生成一个新的单链表，然后利用尾插法将两个集合的相同元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。差运算，是生成一个新的单链表，然后利用尾插法将集合一中不同于集合二的元素顺序插入到新表的表头之后。若待插字符串为非小写字母，则跳过不插。在主函数中对两

9、集合进行测试，运算完成后，设置一个循环，若输入 y/Y 则继续运算，否则结束程序。3.2 类的设计和实现#include using namespace std; typedef struct Node char data; Node *next; 沈阳理工大学课程设计专用纸 3Node,*LinkList; #define SIZE sizeof(Node) #define FALSE 0 #define TRUE 1 class Linklistpublic:initLinklist(LinkList Head) char ch; Node *p=Head; Head-next=NULL;

10、 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)沈阳理工大学课程设计专用纸 4 flag=FALSE; return flag; temp=temp-next; return

11、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

12、; p=newNode; p-next=NULL; else if(Check(p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; 沈阳理工大学课程设计专用纸 5 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(

13、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 He

14、ad) 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; /两个集合的差集 沈阳理工大学课程设计专用纸 7 LinkList Deprive(Li

15、nkList 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)

16、 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; 沈阳理工大学课程设计专用纸 8 p=newNode; p-next=NULL; p1=p1-next; return Head; /打印集合元素 void PrintLinkList(LinkList Head)

17、 Node *p=Head-next; while(p!=NULL) coutdata; p=p-next; coutn; ;在程序的类声明部分，先由类的成员函数 initLinklist(LinkList Head)生成单链表，然后由各成员函数对其进行集合的并，交，差运算。4 基于控制台的应用程序4.1 主函数设计int main() char cmd; Linklist List; do cout*n;cout*集合运算系统*n; cout*n;cout输入两个集合的元素，输完一个集合的元素,按#结束n; LinkList head1=(Node*)malloc(SIZE); 沈阳理工大学

18、课程设计专用纸 9 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

19、两个集合差集为n; List.PrintLinkList(Head3); coutcmd; while(cmd=y|cmd=Y); return 0; 在程序的主函数部分，先由类生成一个对象，再由此对象调用类的各成员函数，求出集合的并，交，差运算结果并输出。 整个程序分为两个独立的文档，Linklist.cpp 包含了单链表的定义和对两集合运算的成员函数；main.cpp 文件包括程序的主函数，主函数中定义了一个类 Linklist 的对象，通过这个对象求解两集合的交，并，差运算结果。4.2 程序运行结果及分析 通过下图可以看出求解两集合的交，并，差运算结果。测试数据一运行结果如图 5-1 所

20、示。沈阳理工大学课程设计专用纸 10图 5-1 程序运行结果测试数据二运行结果如图 5-2 所示。沈阳理工大学课程设计专用纸 11图 5-2 程序运行结果5 基于 MFC 的应用程序MFC 的图形界面程序设计可在上述类设计的基础上进行改造，MFC 的图形界面程序与 DOS 界面程序的主要不同点是：MFC 图形界面程序与 DOS 界面程序的输入输出方式不同，DOS 界面程序采用字符交互式实现数据输入输出，主要通过 cin，cout 等I/O 流实现，而 MFC 的图形程序界面采用标准 Windows 窗口和控件实现输入输出，因此必须在 MFC 类的框架下加入上面所设计的矩阵和方程组类，并通过图形

21、界面的输入输出改造来完成。5.1 图形界面设计首先在 VC 中建立 MFC AppWizard（exe）工程，名称为 MFC，并在向导的 Step1中选择 Dialog based，即建立基于对话框的应用程序，如下图 6-1 所示。沈阳理工大学课程设计专用纸 12图 6-1 建立 MFC AppWizard（exe）工程图 6-2 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 6-3 所示。沈阳理工大学课程设计专用纸 13 图 6-3 集合运算程序界面设计图 6-3 所示的界面中包含了 3 个 Static Text 控件，4 个 Button 控件，和 1

22、 个 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集合的元素沈阳理工大学课程设计专用纸 145.2 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为 1 个 Edit Box 控件建立 Member Variables，按 Ctrl+

23、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 文件合并成一个文件，重

24、新命名为 Linklist.h，并将其加入 MFC 工程。修改 Linklist.h 文件。在对话框类的实现文件 MFCDlg.cpp 中加入#include ，以实现在该文件中可使用 Linklist 类。在 MFCDlg.cpp 文件中加入全局变量的定义，以实现 MFCDlg 类和 Linklist 类之间的通信。沈阳理工大学课程设计专用纸 15编写读入元素按钮的消息处理函数，实现将集合的元素刷新到界面上。编写集合交，并，差及确定按钮的消息处理函数，5.3 运行结果及分析运行程序后，首先出现的界面如图 6-5 所示。图 6-5 程序初始运行界面沈阳理工大学课程设计专用纸 16输入集合一的元素后单击确定按钮后，可将集合一的元素在界面上显示出来，同理，可现示集合二的元素，如图 6-6 所示。图 6-6 输入集合元素后的界面沈阳理工大学课程设计专用