C语言实现集合的交-并-差.doc

【问题描述】 编制一个能演示执行集合的并、交和差运算的程序【基本要求】 （1）集合的元素限定为小写字母字符 a.z （2 ）演示程序以用户和计算机对话的方式执行【测试数据】【实现提示】 以有序链表表示集合【代码过程】 1。先定义 集合的数据类型 notes.h /notes.htypedef struct LNode. ElemType data; LNode *next;*Link, *Position;typedef struct. Link head,tail; int len;LinkSet; / 2。以后要用的一些常量放在 constValues.h #include#include #include /函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 #define ElemType int /存放数据的类型typedef int Status; /函数的返回值 / 3。集合实现函数 setsFun.h/*/* 函数定义 */Status InitSets(LinkSet &ls). /初始化 集合 ls.head = (Link) malloc( sizeof(Link); ls.tail = (Link) malloc( sizeof(Link); if(!ls.head | !ls.tail) exit(OVERFLOW); /如果分配失败 ls.head-next = ls.tail-next = NULL; /头、尾指针为空 ls.len = 0; /长度为0 return OK;Status CreateNode(Link &link,ElemType e). /创建一节点，内容为e link = (Link) malloc( sizeof(Link); if(!link) exit(OVERFLOW); link-data = e; /值设定 link-next = NULL; /指向空 return OK;Position PriorInsertNode(LinkSet &ls,Link &link). /找出节点link要插入到ls的前一个节点 if(!ls.head-next) return ls.head; Link h1 = ls.head-next, h2 = h1-next; /h1：前一节点，h2:前一节点的后一节点 if(link-data data) return ls.head; /如果比第一个节点小，返回头指针 while(h1 & h2). if(h1-data data) & h2-data (link-data) ) /如果h1 & data = (link-data) | h2-data =(link-data) ) return NULL; /如果重复，返回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). /向集合中插入节点 Position p = PriorInsertNode(ls,link); if(!p) return ERROR; /如果集合中已有相应元素 link-next = p-next; if(!p-next) ls.tail-next = link; /如果前一节点为尾节点，修改tail p-next = link; ls.len+; return OK;Position PriorNode(LinkSet &ls, Link &link). /返回集合中 该节点的前一节点,不存在返回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 NextPos(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). /比较两个数字的大小 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, LinkSet &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). /向lsc插入lsb的相关节点 DelFirst(lsb,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 &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. DelFirst(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; 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); 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#include constValues.h /常量头 文件#include notes.h /节点定义 头文件#include setsFun.h /集合操作函数 头文件/*/* 测试 */void Initialization(). printf(* ); printf(*MakeSet1-1 MakeSet1-2 Union-u Intersection-i Difference-d Quit-q * ); printf(* );void main(). LinkSet set1,set2,set3,seta,setb; InitSets(set1),InitSets(set2); /初始化集合 while(1). Initialization(); printf(集合Set1:); PrintSets(set1); /打印集合set1 printf(集合Set2:); PrintSets(set2); /打印集合set1 printf(请键入操作代码:); fflush(stdin); /清空缓冲区 char oper = getchar(); char setsContent200; switch(oper) . case 1: /集合set1 赋值 printf(请输入集合Set1的内容：); fflush(stdin); gets(setsContent); InitSets(set1); SetSets(set1,setsContent); break; case 2: /集合set1 赋值 printf(请输入集合Set1的内容：); fflush(stdin); gets(setsContent); 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 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