C語言實(shí)現(xiàn)集合的交,并,差

1、問題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序 【基本要求】（1）集合的元素限定為小寫字母字符 a.z （2）演示程序以用戶和計(jì)算機(jī)對(duì)話的方式執(zhí)行 【測(cè)試數(shù)據(jù)】【實(shí)現(xiàn)提示】 以有序鏈表表示集合【代碼過程】1。先定義 集合的數(shù)據(jù)類型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 #include

2、 /函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2#define ElemTypeint /存放數(shù)據(jù)的類型typedef int Status;/函數(shù)的返回值/3。集合實(shí)現(xiàn)函數(shù)setsFun.h/*/*函數(shù)定義*/Status InitSets(LinkSet &ls)./初始化 集合ls.head = (Link) malloc( sizeof(Link);ls.tail = (Link) malloc( sizeof(L

3、ink);if(!ls.head | !ls.tail) exit(OVERFLOW); /如果分配失敗ls.head-next = ls.tail-next = NULL; /頭、尾指針為空ls.len = 0; return OK;Status CreateNode(Link &link,ElemType e)./創(chuàng)建一節(jié)點(diǎn)，內(nèi)容為elink = (Link) malloc( sizeof(Link);if(!link) exit(OVERFLOW);link-data = e; /link-next = NULL; / return OK;Position PriorInsert

4、Node(LinkSet &ls,Link &link)./找出節(jié)點(diǎn)link要插入到ls的前一個(gè)節(jié)點(diǎn)if(!ls.head-next)return ls.head;Link h1 = ls.head-next, h2 = h1-next; /h1節(jié)點(diǎn)的后一節(jié)點(diǎn)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 =(li

5、nk-data) )return NULL; /else / h1=h2,h2=h1-next;return h1;Status Append(LinkSet &ls, Link &link)./向集合末尾追加節(jié)點(diǎn)if(ls.head-next = NULL) ls.head-next = link; elsels.tail-next-next = link;ls.tail-next = link;ls.len +;return OK;Status InsertNode(LinkSet &ls, Link &link)./向集合中插入節(jié)點(diǎn)Position p =

6、 PriorInsertNode(ls,link); if(!p) return ERROR; / link-next = p-next;if(!p-next) ls.tail-next = link; / tailp-next = link;/長(zhǎng)度為0值設(shè)定指向空：前一節(jié)點(diǎn),h2:前一如果比第一個(gè)節(jié)點(diǎn)小,返回/如果h1 &如果重復(fù),返回NULL否則,順次往后挪一個(gè)節(jié)點(diǎn)如果集合中已有相應(yīng)元素如果前一節(jié)點(diǎn)為尾節(jié)點(diǎn),修改ls.len+;return OK;Position PriorNode(LinkSet &ls, Link &link)./返回集合中 該節(jié)點(diǎn)的前一節(jié)點(diǎn),

7、不存在返回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)./獲得集合的頭節(jié)點(diǎn)return ls.head;Position NextPo

8、s(Link &link)./獲得當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)return link?link-next:link;Status Empty(LinkSet &ls)./空為真return ls.head-next=NULL;ElemType GetCurElem(Link &link)./獲得當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)return link-data;int Compare(Link &la, Link &lb)./判斷兩個(gè)節(jié)點(diǎn)的大小return la-data - lb-data;int Compare(ElemType e1, ElemType e2)./比較兩個(gè)數(shù)字

9、的大小return e1-e2;Status DelFirst(LinkSet &ls,Link &q)./已知h為線性鏈表的頭節(jié)點(diǎn),刪除表中的第一個(gè)節(jié)點(diǎn),并以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)./釋放節(jié)點(diǎn),有問題free(l);return OK;Status UnionSets(LinkSet lsa, LinkSet &lsb,

10、 LinkSet &lsc)./已知集合ls1,ls2的元素按值非遞減排列/將集合ls1，ls2的并集到ls3if( !InitSets(lsc) ) return ERROR;Link node;Link ha = lsa.head, hb=lsb.head; /找到兩節(jié)點(diǎn)的頭指針Link pa = NextPos(ha), pb = NextPos(hb);while( !Empty(lsa) & !Empty(lsb) ).int result = Compare(pa,pb);/比較兩節(jié)點(diǎn)大小if( result0)./向lsc插入lsb的相關(guān)節(jié)點(diǎn)DelFirst(ls

11、b,node);Append(lsc,node); pb = NextPos(hb);else.DelFirst(lsb,node); pb = NextPos(hb);/如果兩 節(jié)點(diǎn)相同，刪除lsb中 重復(fù)的節(jié)點(diǎn)，即以lsa為標(biāo)準(zhǔn)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

12、 &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.DelFir

13、st(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;

14、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)

15、;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。 測(cè)試test.cpp #includeconstValues.h #includenotes.h #includes

16、etsFun.h/*/*/測(cè)試常量頭 文件節(jié)點(diǎn)定義 頭文件集合操作函數(shù) 頭文件*/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);/pr

17、intf(集合Set2:);PrintSets(set2);/初始化集合打印集合set1打印集合set1printf(請(qǐng)鍵入操作代碼:); fflush(stdin); /清空緩沖區(qū)char oper = getchar();char setsContent200;switch(oper).case 1: / printf(請(qǐng)輸入集合fflush(stdin);gets(setsContent); InitSets(set1);SetSets(set1,setsContent); break;case 2: / printf(請(qǐng)輸入集合fflush(stdin);gets(setsConten

18、t); InitSets(set2);SetSets(set2,setsContent); break;case u:case U: / InitSets(set3);CopySets(set1,seta); / set1,set2中對(duì)應(yīng)的節(jié)點(diǎn)，CopySets(set2,setb); /UnionSets(seta,setb,set3); / printf(set1 Uset2=: ); 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;