《C语言实现集合地交,并,差.docx》由会员分享，可在线阅读，更多相关《C语言实现集合地交,并,差.docx（12页珍藏版）》请在三一文库上搜索。
1、实用文案【问题描述】编制一个能演示执行集合的并、交和差运算的程序【根本要求】(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 /函数结
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).标准文档实用文案/ 初始化集合Is.head = (Link) malloc( sizeof(Link);Is.tail = (Link) malloc( siz
3、eof(Link);if(!ls.head | !ls.tail) exit(OVERFLOW); /ls.head-next = ls.tail-next = NULL; /15.1 en = 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 PriorInsertNode(LinkS
4、et &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).如果分配失败头、尾指针为空长度为0值设定 指向空if(h1-data data) & h2-data (link-data) )data = (link-data) | h2-data =(link-data)return NULL;/else/
5、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;15.1 en +;:前一节点,h2:前一节如果比第一个节点小,返回/如果h1 &如果重复,返回 NULL否那么,顺次往后挪一个节点标准文档实用文案return OK;)Status InsertNode(LinkSet &ls, Link &link)./向
6、集合中插入节点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)./ 返回集合中 该节点的前一节点,不存在返回NULLint j=0;Link pre,h = ls.head;while(h-next & jnext;
7、 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
8、;)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为线性链表的头节
9、点,删除表中的第一个节点,并以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的并集到ls3if( !InitSets(lsc
10、) ) 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 = NextP
11、os(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的交集到ls3if( !InitSets(lsc) ) return ERROR;L
12、ink 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);whi
13、le(!Empty(lsa).DelFirst(lsa,node);Append(lsc,node);return OK;Status DifferenceSets(LinkSet &lsa,LinkSet &lsb, LinkSet &lsc). / 集合ls1,ls2的元素按值非递减排列ls3 = ls1 - ls2if( !InitSets(lsc) ) return ERROR;Link node;Link ha = lsa.head, hb=lsb.head;Link pa = NextPos(ha), pb = NextPos(hb);/,pb2 = NextPos(pb1);wh
14、ile( !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 =
15、 lsb.head-next;while(la).Link node;CreateNode(node,la-data);lb=node;lsb.len+;la = la-next;lb = lb-next;标准文档实用文案Isb.tail = lb;return OK;)4.测试 test.cpp#include constValues.h /#include notes.h/常量头文件节点定义头文件集合操作函数头文件#include setsFun.h/*/*测试 */printf(* );void Initialization().*printf(*MakeSet1-1 MakeSet1-
16、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);/printf(集合 Set2:);PrintSets(set2);/printf(请键入操作代码fflush(stdin); / char oper = getchar(); char setsCont
17、ent200;:);清空缓冲区初始化集合打印集合setl打印集合setlswitch(oper)./请输入集合集合set1赋值Set1的内容：);case 1:printf( fflush(stdin);gets(setsContent);InitSets(set1);SetSets(set1,setsContent); break;标准文档实用文案case 2:/printf(请输入集合fflush(stdin); gets(setsContent); InitSets(set2);SetSets(set2,setsContent); break;case u:case U:/InitSet
18、s(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(s
19、et3); 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);Set1的内容:集合set1赋值 );求并由于求并的算法是添加一个节点,删除所以要复制一份下同求交求差标准文档实用文案break;)system(cls); /清屏)本文来自：中国自学编程网( zxbc ) 详细出处参考 :/ zxbc /html/20070424/7423.html标准文档