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

1、問題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序 【基本要求】（1）集合的元素限定為小寫字母字符 az （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 #inc

2、lude / 函數(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( size

3、of(Link);if(!ls.head | !ls.tail) exit(OVERFLOW); / 如果分配失敗ls.head-next = ls.tail-next = NULL; / 頭、尾指針為空/長度為 0ls.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 P

4、riorInsertNode(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 =

5、(link-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; else ls.tail-next-next = link;ls.tail-next = link;ls.len +;return OK;Status InsertNode(LinkSet &ls, Link &link)./ 向集合中插入節(jié)點(diǎn)值設(shè)定指向空：前一節(jié)點(diǎn), h2: 前一如

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

7、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 NextPos(Link &link)./ 獲得當(dāng)前節(jié)點(diǎn)的下一個(gè)

8、節(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ù)字的大小return e1-e2;Status DelFirst(LinkSet &

9、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, LinkSet &lsc)./ 已知集合 ls1,ls2 的元素按值非遞減排列/ 將集合

10、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(lsb,node);Append(lsc,node); pb = NextPos(

11、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 &lsc). / 已知集合 ls1,ls2 的元素按值非遞減排列 / 將集合 ls

12、1 ， 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 = Next

13、Pos(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 p

14、a = 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

15、)./ 將集合 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 #include constValues.h #include notes.h #include setsFun.h /*/*/測(cè)試常量頭 文件節(jié)點(diǎn)定義 頭文件集合操作函數(shù) 頭文件

16、*/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);/printf(集合 Set2:);PrintSets(set2);/初始化集

17、合打印集合 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(setsContent); InitSets(set2); S

18、etSets(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 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: