集合的交、并和差運算的實現(xiàn).doc

《集合的交、并和差運算的實現(xiàn).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、班級：計算機11-3班學號：11034050333姓名：曲玉昆成績：_________實驗四集合的交、并和差運算的實現(xiàn)1.問題描述用有序單鏈表表示集合，實現(xiàn)集合的交、并和差運算。2.基本要求⑴對集合中的元素，用有序單鏈表進行存儲；⑵實現(xiàn)交、并、差運算時，不另外申請存儲空間；⑶充分利用單鏈表的有序性，算法有較好的時間性能。3.設(shè)計思想首先，建立兩個帶頭結(jié)點的有序單鏈表表示集合A和B。單鏈表的結(jié)點結(jié)構(gòu)和建立算法請參見教材，需要注意的是：利用頭插法建立有序單鏈表，實參數(shù)組應(yīng)該是降序排列。其次，根據(jù)集合的運算規(guī)則，利用單鏈表的有序性，設(shè)計交、并和差運算。⑴根據(jù)集合的運算規(guī)則，集合中包含所有既屬

2、于集合A又屬于集合B的元素。因此，需查找單鏈表A和B中的相同元素并保留在單鏈表A中。算法如下：voidInterest(Node*A,Node*B){//A、B分別是兩個單鏈表的頭指針，最后的結(jié)果在單鏈表A中pre=A;p=A->next;q=B->next;while(p&&q){if(p->datadata){pre->next=p->next;p=pre->next;}elseif(p->data>q->data)q=q->next;else{p=p->next;q=q->next;}}}求集合的交集算法⑵根據(jù)集合的運算規(guī)則，集合中包含所有或?qū)儆诩螦或?qū)儆诩螧的元素。

3、因此，對單鏈表B中的每個元素x，在單鏈表A中進行查找，若存在和x不相同的元素，則將該結(jié)點插入到單鏈表A中。算法請參照求集合的交集自行設(shè)計。⑶根據(jù)集合的運算規(guī)則，集合A-B中包含所有屬于集合A而不屬于集合B的元素。因此，對單鏈表B中的每個元素x，在單鏈表A中進行查找，若存在和x相同的結(jié)點，則將該結(jié)點從單鏈表A中刪除。算法請參照求集合的交集自行設(shè)計。templatestructNode{Tdata;Node*next;};templateclassLinkList{public:LinkList(Ta[],intn);//建立有n個元素的單鏈表~Lin

4、kList();voidInterest(Node*A,Node*B);//求交集voidSum(Node*A,Node*B);/voidSubtraction(Node*A,Node*B);voidPrintList();voidShow(inti);Node*first;};templateLinkList::LinkList(Ta[],intn){Node*s;first=newNode;first->next=NULL;for(inti=0;i;s->data=a

5、[i];s->next=first->next;first->next=s;}}templateLinkList::~LinkList(){Node*p,*q;p=first;//工作指針p初始化while(p)//釋放單鏈表的每一個結(jié)點的存儲空間{q=p;//暫存被釋放結(jié)點p=p->next;//工作指針p指向被釋放結(jié)點的下一個結(jié)點，使單鏈表不斷開deleteq;}}templatevoidLinkList::Interest(Node*A,Node*B){Node*pre,*p,*q;pre=A;p=A->next

6、;q=B->next;while(p&&q){if(p->datadata){pre->next=p->next;p=pre->next;}elseif(p->data>q->data){q=q->next;}else{pre=p;p=p->next;q=q->next;}}}//求并集templatevoidLinkList::Sum(Node*A,Node*B{Node*pre,*p,*q;pre=A;p=A->next;q=B->next;while(p&&q){if(p->datadata){pre=p;p=p->next

7、;}elseif(p->data>q->data){q=q->next;}else{pre->next=p->next;p=p->next;q=q->next;}}}templatevoidLinkList::Subtraction(Node*A,Node*B){Node*pre,*p,*q,*pra;pre=A;pra=B;p=A->next;q=B->next;while(p&&q){if(p->da