数据结构课程设计-集合运算(完整)

电子与信息工程学院数据结构实验报告实验名称：集合得运算实验类型：设计（验证、设计、创新)班级:2013级电信三班学号:2姓名：陆杰实验时间：2015年6月16日指导教师:余先伦成绩:目录TOC\o”1—3”\h\z\u一课程设计目得与要求二问题描述及分析HYPERLINK\l”_Toc264820527”三算法思想与程序得实现概述HYPERLINK\l”_Toc264820528"3、1算法思想四程序流程图五程序得实现5、1主函数HYPERLINK\l”_Toc264820535”5、2链表得生成HYPERLINK\l”_Toc264820536”5、3集合得输出5、4并运算函数HYPERLINK\l”_Toc264820538”5、5交运算函数六运行结果分析6、1程序主界面HYPERLINK\l”_Toc264820542"6、2整数集合并运算HYPERLINK\l”_Toc264820543"6、3整数集合交运算6、7字母集合差运算HYPERLINK\l”_Toc264820548”6、8字母与数据集合并运算6、9字母与数据集合交运算HYPERLINK\l”_Toc264820550”6、10字母与数据集合差运算6、11退出程序为结束标志得字符,允许出现重复字符或非法字符,程序应能自动滤去。输出得运算结果字符串中将不含重复字符或非法字符。

问题描述:

有两个集合A、B，要求它得交集、并集与差集C.用两个链表p、q存储集合A、B，用链表r存储集合C.描述该问题得存储结构,算法,并通过编写程序来实现。

问题分析:

1、定义一个链表来存储集合元素;

2、链表L包括数据域与指针域,数据域中存储集合元素,指针域中存储下一个集合元素得位置;

3、创建若干个基本函数，通过函数调用对链表进行操作,实现集合得交、并、差运算。三算法思想与程序得实现概述3、1算法思想定义一个链表，链表有整型数据与一个指向链表得指针，程序包含定义一个新链表得函数，集合并函数，集合交函数,集合差函数。求两集合交集并集差集从两集合得头结点开始，比较两集合元素大小,进行对应得操作,直到读取到两集合得末尾元素。主程序先定义三个集合,创建集合A读入A数据，创建集合B读入B数据，然后输出集合A,B得元素,求出两集合并集并输出。求两集合得交集与差集得运算与求并集得步骤类似,只需按提示输入即可。3、2程序得实现概述

(1）输入得形式与输入值得范围：

输入就是从键盘输入得,输入得内容为整数。(2）输出得形式

从屏幕输出，显示用户输入集合得元素,并显示进行运算后得值。(3)存储结构在这次设计中开始我就是采用链式存储结构，使得集合得算法定义十分简洁。算法实现定义链表,创建链表，输出链表。利用链表得来存储集合。利用三个函数分别实现课程要求程序实现得求并、求交与差三中运算。现分述如下:并运算函数该函数采取了用新集合存储两集合并后得新集合,利用一个for循环来消除新集合中相同得元素,使其在屏幕上只显示一次.B）交运算函数该函数用于实现集合得并运算,利用for嵌套实现两链表中数据得比较，输出两链表中相同得元素.C）差函数该函数用于实现集合得差运算,利用链表中得数据域进行判断。输出不同于被减集合中不存在得元素.四程序流程图流程图：开始开始定义链表定义链表创建链表 创建链表输入数据输入数据求两集合得并集求两集合得并集输入数据输入数据求两集合得交集求两集合得交集输入数据输入数据求两集合得差集求两集合得差集五程序得实现改程序得实现步骤就是定义链表,创建链表,输出链表。利用链表得来存储集合。利用三个函数分别实现课程要求程序实现得求并、求交与差三中运算。现分述如下：5、1主函数voidbangzhu（）｛printf("\n\t\t\t＊*＊＊＊＊＊＊＊*＊＊*＊＊*＊*＊***＊*＊＊**＊*＊＊＊＊*”)；printf(”\n\t\t\t*求集合得交并差＊"）;printf（"\n\t\t\t*＊＊＊＊＊*＊＊＊＊＊**＊＊***＊*******＊*＊*＊*\n”);｝voidmain()/＊主函数*/{structset*p,*q，*r；intm，n,node；bangzhu（);for（;；){do｛printf（”请输入您要选择操作得代码:\n”）；printf("1：求两集合得并A∪B\n”)；printf(”2：求两集合得交A∩B\n”)；printf（"3:求两集合得差A—B\n”）；printf(”0：退出该程序\n”);scanf("％d",&node); ｝while（node〈0||node>3）；if(node==0)exit（1)；printf（”\t\t\t/*请输入集合A中元素得个数:＊/\n");scanf(”％d"，＆m）；createlist_p（p,m）;/＊调用链表生成函数生成A链表＊/printf（"\t\t\t/*请输入集合B中元素得个数：*/\n"）；scanf（”%d”，&n)；/*调用链表生成函数生成B链表*/createlist_p(q,n）；printf("集合A中元素为:”);printlist_p(p);/＊调用集合输出函数输出集合A＊/printf（”集合B中元素为：")；printlist_p（q)；/*调用集合输出函数输出集合A＊/while(node〈0｜|node>3）;switch(node){case1：Addset（p,q,r)；printf（”A∪B:\n”）；printlist_p(r);break;case2：Subset（p,q,r）；printf("A∩B:\n”）；printlist_p(r）；break；case3：Intset(p,q,r)；printf(”A-B:\n”)；printlist_p(r）；break;}printf("\n”);}}5、2链表得生成voidcreatelist_p（structset＊&p,intn）{inti；structset＊L;p=(structset*)malloc（sizeof（set））；/*申请结点p＊/p—>next=NULL；/＊定义p得next指针为空＊/ for(i=n；i>0；i-—） {L=(structset*)malloc（sizeof（set））;/＊申请结点L*/printf（”请输入该集合中第%d个整数元素：”,n-i+1）；scanf（”%s"，&L->coef）；L-〉next=p->next;p—〉next=L； }}//生成新链表用于存放两集合中得元素5、3集合得输出voidprintlist_p(structset*＆p)｛structset＊L;inti；L=p—>next;if（！L)printf("该表为空！\n"）;while（L！=NULL）｛printf("%c",L—〉coef);L=L-〉next；i++；｝printf("\n");｝//打印输入得两集合中得元素5、4并运算函数voidAddset(structset*＆p，structset*＆q,structset*＆r）｛structset＊k，*m，*n；r=(structset＊)malloc（sizeof（set）);/*申请结点r*/r-〉next=NULL;/＊定义r得next指针为空*/k=p—>next;/*k指向p得下一个结点*/for（；k;){m=(structset＊）malloc(sizeof(set));/*申请结点m＊/m->next=r->next;r-〉next=m;m->coef=k-〉coef；k=k->next；｝/*把第一个集合中得元素放在新集合中＊/k=q-〉next；m=(structset＊）malloc(sizeof(set））;m—〉next=r—〉next;r->next=m;m-〉coef=k—>coef;k=k—〉next;for(；k；)｛for（n=r-〉next；(k—〉coef!=n—>coef)&＆n->next；） {n=n—>next； ｝/＊与新集合中得元素比较，如果不同则链入链表中＊/if(（k-〉coef!=n—〉coef)＆&!（n->next）） ｛m=（structset＊)malloc（sizeof（set));m->next=r->next;r->next=m；m—>coef=k->coef； }k=k—〉next;｝/*对第二个集合中得元素进行分析*/｝/*求A∪B＊/该函数采取了用新集合存储两集合并后得新集合,利用一个for循环来消除新集合中相同得元素，就是其在屏幕上只显示一次。5、5交运算函数voidSubset(structset*＆p，structset＊&q，structset＊&r)｛structset＊k,＊m，*n；r=(structset＊）malloc（sizeof（set））；/*申请结点r＊/r-〉next=NULL；n=q-〉next；for（;n;）/*比较p与q链表中得元素，相同得元素存入链表r中*/{m=p—〉next；for(；(m—〉coef！=n-〉coef)&＆m—〉next;） {m=m—>next; }if(m-〉coef==n-〉coef） ｛k=(structset*)malloc（sizeof(set））；k-〉next=r—〉next；r-〉next=k；k—〉coef=m->coef; ｝n=n-〉next；}}/＊求A∩B*/该函数用于实现集合得并运算，利用for嵌套实现两链表中数据得比较，输出两链表中相同得元素。5、6差函数voidIntset（structset*&p,structset*&q，structset*&r）{structset＊k,＊m，＊n;r=（structset*)malloc(sizeof(set））；r-〉next=NULL；m=p->next;for（；m；）｛n=q—〉next;for（；（m—〉coef!=n-〉coef)&&n-〉next;) ｛n=n—>next; }if（！n—〉next＆&（m—>coef！=n—〉coef）)/*比较链表p与q,找出p中不同于q得元素存入链表r中*/ ｛k=（structset*）malloc(sizeof(set));k—〉next=r->next;r—>next=k；k—>coef=m->coef； ｝m=m—>next；}}/*求A—B*/该函数用于实现集合得差运算，利用链表中得数据域进行判断。输出不同于被减集合中不存在得元素.六运行结果分析6、1程序主界面 图6、1程序主界面6、2整数集合并运算图6、2整数集合并运算6、3整数集合交运算图6、3整数集合交运算6、4整数集合差运算图6、4整数集合差运算6、5字母集合并运算图6、5字母集合并运算6、6字母集合交运算图6、6字母集合交运算6、7字母集合差运算图6、7字母集合差运算6、8字母与数据集合并运算图6、8字母与数据集合并运算6、9字母与数据集合交运算图6、9字母与数据集合交运算6、10字母与数据集合差运算图6、10字母与数据集合差运算6、11退出程序图6、11退出程七源代码＃include〈stdio、h〉#include<malloc、h〉＃include〈stdlib、h>structset{charcoef；structset*next；};//线性表得单链表存储结构voidcreatelist_p(structset*＆p，intn){inti;structset*L；p=(structset*）malloc(sizeof（set)）；p->next=NULL;//建立一个带头结点得单链表 for(i=n;i>0；i-—) {L=（structset＊)malloc(sizeof（set））；//生成新节点printf（”请输入该集合中第%d个整数元素："，n-i+1)；scanf（”%s”，&L->coef）;L—〉next=p-〉next；p—>next=L；//插入到表头 }}voidprintlist_p（structset*&p){structset*L;inti;L=p->next；if（！L）printf（"该表为空!\n"）；while（L！=NULL）｛printf（"％c",L-〉coef）；L=L-〉next；i++;｝printf（"\n”)；｝voidAddset(structset＊&p,structset*&q,structset＊&r）｛structset＊k,＊m，＊n；r=(structset＊)malloc(sizeof(set））；r->next=NULL；k=p->next;for（;k;)｛m=(structset＊）malloc（sizeof（set））；m-〉next=r—〉next;r->next=m;m—>coef=k—>coef；k=k->next;//r中存放p}k=q-〉next;m=（structset＊）malloc（sizeof(set））；m—>next=r-〉next;r->next=m;m—>coef=k-〉coef；k=k-〉next；for(;k；）｛for（n=r->next；（k—〉coef！=n-〉coef）&＆n->next;) {n=n—>next; }if(（k->coef!=n—〉coef)&&!（n->next)) {m=（structset＊)malloc（sizeof（set)）；m->next=r->next；r->next=m；m—>coef=k—〉coef; }k=k—>next;｝}//求A∪BvoidSubset（structset*＆p,structset＊&q,structset＊＆r）｛structset＊k,*m,＊n；r=（structset*)malloc（sizeof（set)）;r-〉next=NULL；n=q—〉next；for（;n；）｛m=p—>next；for(;(m—〉coef!=n—〉coef）＆&m-〉next;） ｛m=m->next; ｝if(m—>coef==n-〉coef） ｛k=（structset＊）malloc(sizeof（set)）；k-〉next=r->next；r—>next=k；k—〉coef=m-〉coef； }n=n—>next；｝｝//求A∩BvoidIntset（structset*＆p,structset*＆q，structset＊＆r){structset＊k,*m,*n；r=（structset＊)malloc（sizeof（set））;r—>next=NULL;m=p—>next；for（；m；){n=q-〉next；for（；（m—〉coef!=n—>coef)＆&n-〉next；） ｛n=n->next; }if（！n->next&＆（m—〉coef！=n—〉coef)） ｛k=(structset＊)malloc（sizeof(set））;k-〉next=r-〉next;r—>next=k;k->coef=m-〉coef; }m=m->next;｝}//求A—Bvoidbangzhu(){printf（"\n\t\t\t*＊＊＊＊*＊＊＊******＊＊＊＊＊*＊＊＊＊*******＊＊*”）;printf（"\n\t\t\t*求集合得交并差*”)；printf（”\n\t\t\t＊＊********＊＊＊*****＊*＊＊**＊＊＊＊＊＊*＊＊\n”);}voidmain（){structset＊p，＊q,*r;intm，n，node；bangzhu（）;for(;；）｛do｛printf(”请输入您要选择操作得代码：\n"）;printf（”1:求两集合得并A∪B\n”);printf（"2:求两集合得交A∩B\n”）;printf(”3：求两集合得差A-B\n”）；printf("0：退出该程序\n”)；