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

【问题描述】 编制一个能演示执行集合的并、交和差运算的程序【基本要求】 （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<stdio.h>#include <malloc.h>#include <stdlib.h>/函数结果状态代码#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 < h1->data) return ls.head; /如果比第一个节点小，返回头指针 while(h1 && h2). if(h1->data < (link->data) && h2->data > (link->data) ) /如果>h1 && <h2，说明找到插入的地方了 break; if(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 && j<=ls.len && h!=link). pre = h; h=h->next; 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( result<0) . DelFirst(lsa,node);Append(lsc,node); pa = NextPos(ha); /向lsc插入lsa的相关节点 else if(result>0). /向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( result<0) . DelFirst(lsa,node);pa = NextPos(ha); else if(result>0). 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( result<0) . DelFirst(lsa,node);Append(lsc,node);pa = NextPos(ha); else if(result>0). 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': /求差 InitSets(set3); CopySets(set1,seta); CopySets(set2,setb); DifferenceSets(seta,setb,set3); printf("set1 - set2=: "); PrintSets(set3); fflush(stdin); getchar(); break; case 'q': case 'Q': exit(0); break; system("cls"); /清屏 /本文来自: 中国自学编程网() 详细出处参考：