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

1、问题描述】编制一个能演示执行集合的并、交和差运算的程序 【基本要求】（1）集合的元素限定为小写字母字符 az （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 #inc

2、lude / 函数结果状态代码 #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( size

3、of(Link);if(!ls.head | !ls.tail) exit(OVERFLOW); / 如果分配失败ls.head-next = ls.tail-next = NULL; / 头、尾指针为空/长度为 0ls.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 P

4、riorInsertNode(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 =

5、(link-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; else ls.tail-next-next = link;ls.tail-next = link;ls.len +;return OK;Status InsertNode(LinkSet &ls, Link &link)./ 向集合中插入节点值设定指向空：前一节点, h2: 前一如

6、果比第一个节点小,返回/如果 h1 &如果重复,返回 NULL 否则,顺次往后挪一个节点Position p = PriorInsertNode(ls,link); if(!p) return ERROR; / link-next = p-next;如果集合中已有相应元素如果前一节点为尾节点,修改if(!p-next) ls.tail-next = link; / tailp-next = link;ls.len+;return OK;Position PriorNode(LinkSet &ls, Link &link)./ 返回集合中 该节点的前一节点 , 不存在返回 NULL int j=

7、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 NextPos(Link &link)./ 获得当前节点的下一个

8、节点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)./ 比较两个数字的大小return e1-e2;Status DelFirst(LinkSet &

9、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, LinkSet &lsc)./ 已知集合 ls1,ls2 的元素按值非递减排列/ 将集合

10、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(lsb,node);Append(lsc,node); pb = NextPos(

11、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 &lsc). / 已知集合 ls1,ls2 的元素按值非递减排列 / 将集合 ls

12、1 ， 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.DelFirst(lsb,node); Append(lsc,node);pb = Next

13、Pos(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;Link node;Link ha = lsa.head, hb=lsb.head;Link p

14、a = 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);return OK;Status CopySets(LinkSet lsa, LinkSet lsb

15、)./ 将集合 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 #include constValues.h #include notes.h #include setsFun.h /*/*/测试常量头 文件节点定义 头文件集合操作函数 头文件

16、*/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);/printf(集合 Set2:);PrintSets(set2);/初始化集

17、合打印集合 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(setsContent); InitSets(set2); S

18、etSets(set2,setsContent); break;case u:case U: / InitSets(set3); CopySets(set1,seta); / set1,set2 中对应的节点， CopySets(set2,setb); / UnionSets(seta,setb,set3); / printf(set1 U set2=: ); 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;case d:case D: