C语言实现集合的交,并,差

1、问题描述】编制一个能演示执行集合的并、交和差运算的程序 【基本要求】（1）集合的元素限定为小写字母字符 a.z （2）演示程序以用户和计算机对话的方式执行 【测试数据】【实现提示】 以有序链表表示集合【代码过程】1。先定义 集合的数据类型notes.h /notes.h typedef struct LNode.ElemType data;LNode *next;*Link, *Position;typedef struct.Link head,tail;int len; LinkSet;/2。以后要用的一些常量放在constValues.h #include#include #include

2、 /函数结果状态代码#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2#define ElemTypeint /存放数据的类型typedef int Status;/函数的返回值/3。集合实现函数setsFun.h/*/*函数定义*/Status InitSets(LinkSet &ls)./初始化 集合ls.head = (Link) malloc( sizeof(Link);ls.tail = (Link) malloc( sizeof(L

3、ink);if(!ls.head | !ls.tail) exit(OVERFLOW); /如果分配失败ls.head-next = ls.tail-next = NULL; /头、尾指针为空ls.len = 0; return OK;Status CreateNode(Link &link,ElemType e)./创建一节点，内容为elink = (Link) malloc( sizeof(Link);if(!link) exit(OVERFLOW);link-data = e; /link-next = NULL; / return OK;Position PriorInsert

4、Node(LinkSet &ls,Link &link)./找出节点link要插入到ls的前一个节点if(!ls.head-next)return ls.head;Link h1 = ls.head-next, h2 = h1-next; /h1节点的后一节点if(link-data data) return ls.head; /头指针while(h1 & h2).if(h1-data data) & h2-data (link-data) ) vh2,说明找到插入的地方了break;if(h1-data = (link-data) | h2-data =(li

5、nk-data) )return NULL; /else / h1=h2,h2=h1-next;return h1;Status Append(LinkSet &ls, Link &link)./向集合末尾追加节点if(ls.head-next = NULL) ls.head-next = link; elsels.tail-next-next = link;ls.tail-next = link;ls.len +;return OK;Status InsertNode(LinkSet &ls, Link &link)./向集合中插入节点Position p =

6、 PriorInsertNode(ls,link); if(!p) return ERROR; / link-next = p-next;if(!p-next) ls.tail-next = link; / tailp-next = link;/长度为0值设定指向空：前一节点,h2:前一如果比第一个节点小,返回/如果h1 &如果重复,返回NULL否则,顺次往后挪一个节点如果集合中已有相应元素如果前一节点为尾节点,修改ls.len+;return OK;Position PriorNode(LinkSet &ls, Link &link)./返回集合中 该节点的前一节点,

7、不存在返回NULL int j=0;Link pre,h = ls.head;while(h-next & jnext; j+;if(j=0) return NULL;return pre;Status PrintSets(LinkSet &ls)./打印集合Link h=ls.head-next;printf( );while(h).printf(%c ,h-data);h = h-next;printf( );return OK;Position GetHead(LinkSet &ls)./获得集合的头节点return ls.head;Position NextPo

8、s(Link &link)./获得当前节点的下一个节点return link?link-next:link;Status Empty(LinkSet &ls)./空为真return ls.head-next=NULL;ElemType GetCurElem(Link &link)./获得当前节点的数据return link-data;int Compare(Link &la, Link &lb)./判断两个节点的大小return la-data - lb-data;int Compare(ElemType e1, ElemType e2)./比较两个数字

9、的大小return e1-e2;Status DelFirst(LinkSet &ls,Link &q)./已知h为线性链表的头节点,删除表中的第一个节点,并以q返回Link h = ls.head; if(!h-next) return ERROR; q = h-next;h-next = h-next-next;q-next=NULL;ls.len-;return OK;Status FreeNode(Link &l)./释放节点,有问题free(l);return OK;Status UnionSets(LinkSet lsa, LinkSet &lsb,

10、 LinkSet &lsc)./已知集合ls1,ls2的元素按值非递减排列/将集合ls1，ls2的并集到ls3if( !InitSets(lsc) ) return ERROR;Link node;Link ha = lsa.head, hb=lsb.head; /找到两节点的头指针Link pa = NextPos(ha), pb = NextPos(hb);while( !Empty(lsa) & !Empty(lsb) ).int result = Compare(pa,pb);/比较两节点大小if( result0)./向lsc插入lsb的相关节点DelFirst(ls

11、b,node);Append(lsc,node); pb = NextPos(hb);else.DelFirst(lsb,node); pb = NextPos(hb);/如果两 节点相同，删除lsb中 重复的节点，即以lsa为标准while(!Empty(lsa).DelFirst(lsa,node);Append(lsc,node);while(!Empty(lsb).DelFirst(lsb,node);Append(lsc,node);return OK;Status IntersectionSets(LinkSet &lsa,LinkSet &lsb, LinkSet

12、 &lsc). /已知集合ls1,ls2的元素按值非递减排列/将集合ls1，ls2的交集到ls3 if( !InitSets(lsc) ) return ERROR;Link node;Link ha = lsa.head, hb=lsb.head;Link pa = NextPos(ha), pb = NextPos(hb);while( !Empty(lsa) & !Empty(lsb) ). int result = Compare(pa,pb); if( result0).DelFirst(lsb,node); pb = NextPos(hb); else.DelFir

13、st(lsb,node); Append(lsc,node);pb = NextPos(hb); DelFirst(lsa,node);pa = NextPos(ha); while(!Empty(lsa).DelFirst(lsa,node);Append(lsc,node); return OK;Status DifferenceSets(LinkSet &lsa,LinkSet &lsb, LinkSet &lsc). /已知集合ls1,ls2的元素按值非递减排列/ls3 = ls1 - ls2 if( !InitSets(lsc) ) return ERROR;

14、Link node;Link ha = lsa.head, hb=lsb.head;Link pa = NextPos(ha), pb = NextPos(hb);/,pb2 = NextPos(pb1); while( !Empty(lsa) & !Empty(lsb) ).int result = Compare(pa,pb);if( result0). DelFirst(lsb,node); pb = NextPos(hb);else.DelFirst(lsa,node); pa = NextPos(ha);DelFirst(lsb,node); pb = NextPos(hb)

15、;return OK;Status CopySets(LinkSet lsa, LinkSet lsb)./将集合lsa拷贝到lsb中InitSets(lsb);Link la = lsa.head-next, lb = lsb.head-next;while(la).Link node;CreateNode(node,la-data);lb=node;lsb.len+;la = la-next;lb = lb-next;lsb.tail = lb;return OK;/ 4。 测试test.cpp #includeconstValues.h #includenotes.h #includes

16、etsFun.h/*/*/测试常量头 文件节点定义 头文件集合操作函数 头文件*/void Initialization().printf(f* H);printf(*MakeSet1-1MakeSet1-2 Union-u Intersection-i Difference-dQuit-q * );printf( * Hvoid main().LinkSet set1,set2,set3,seta,setb;InitSets(set1),InitSets(set2); /while(1).Initialization();printf(集合Set1:);PrintSets(set1);/pr

17、intf(集合Set2:);PrintSets(set2);/初始化集合打印集合set1打印集合set1printf(请键入操作代码:); fflush(stdin); /清空缓冲区char oper = getchar();char setsContent200;switch(oper).case 1: / printf(请输入集合fflush(stdin);gets(setsContent); InitSets(set1);SetSets(set1,setsContent); break;case 2: / printf(请输入集合fflush(stdin);gets(setsConten

18、t); InitSets(set2);SetSets(set2,setsContent); break;case u:case U: / InitSets(set3);CopySets(set1,seta); / set1,set2中对应的节点，CopySets(set2,setb); /UnionSets(seta,setb,set3); / printf(set1 Uset2=: ); PrintSets(set3); fflush(stdin); getchar();break;case i:case I: / InitSets(set3);CopySets(set1,seta);CopySets(set2,setb);IntersectionSets(seta,setb,set3);printf(set1交set2=: ); PrintSets(set3);fflush(stdin); getchar(); break;