【问题描述】
编制一个能演示执行集合的并、交和差运算的程序
【基本要求】
（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<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;}//~#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()...{