集合的运算，交集，并集，差集都可以，幂集怎么做，求指教，谢谢 - 数据结构与算法

问题点数：0 回复次数：2

集合的运算，交集，并集，差集都可以，幂集怎么做，求指教，谢谢

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<time.h>

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void CreateLinkList(LinkList &L,int n){             //尾插法建立单向链表,头结点不用

    LinkList cur,pNew;
    int i,x;
    L=cur=NULL;
    for(i=0;i<=n;i++){
        pNew=(LinkList)malloc(sizeof(LNode));
        cin>>x;
        pNew->data=x;
        if(i==0){
            L=cur=pNew;
            L->data=-1;
        }
        else{
            cur->next=pNew;
            cur=pNew;
        }
    }
    cur->next=NULL;

}

int QuickSort(LinkList &L,LinkList tail){
    LinkList mid,p,q,m;
    int key;

    if (L->next==tail || L->next->next==tail)
        return -1;

    mid=L->next;
    p=L;
    q=mid;
    key=mid->data;
    m=mid->next;

    while (m!=tail){
        if (m->data<key)
            p=p->next=m;
        else
            q=q->next=m;
        m=m->next;
    }

    p->next = mid;
    q->next = tail;

    QuickSort(L,mid);
    QuickSort(mid,tail);

    return 0;
}

void Print(LinkList L){
    LinkList p;
    p=L->next;
    cout<<"{";
    while(p){
        cout<<p->data;
        if(p->next!=NULL)
            cout<<",";
        p=p->next;
    }
    cout<<"}"<<endl;

}

void AddList(LinkList La,LinkList Lb){
    LinkList Lc;
    LinkList cur,la,lb,ln;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;

    while(la && lb){
        if(la->data<lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
        }
        else if(la->data==lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
            lb=lb->next;
        }
        else{
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=lb->data;
            cur->next=ln;
            cur=ln;
            lb=lb->next;
        }
    }
    while(la){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=la->data;
        cur->next=ln;
        cur=ln;
        la=la->next;
    }
    while(lb){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=lb->data;
        cur->next=ln;
        cur=ln;
        lb=lb->next;
    }
    cur->next=NULL;

    Print(Lc);
}

void JiaoList(LinkList La,LinkList Lb){
    LinkList Lc,la,lb,ln,cur;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;
    while(la && lb){
        if(la->data<lb->data)
            la=la->next;
        else if(la->data==lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
            lb=lb->next;
        }
        else
            lb=lb->next;
    }
        cur->next=NULL;
        Print(Lc);
}

void ChaList(LinkList La,LinkList Lb){
    LinkList Lc,la,lb,cur,ln;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;

    while(la && lb){
        if(la->data<lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
        }
        else if(la->data==lb->data){
            la=la->next;
            lb=lb->next;
        }
        else
            lb=lb->next;
    }
    while(la){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=la->data;
        cur->next=ln;
        cur=ln;
        la=la->next;
    }
    cur->next=NULL;
    Print(Lc);
}

int main(){
    LinkList La,Lb;
    int na,nb;
    cout<<"请输入第一个集合的元素数目:"<<endl;
    cin>>na;
    cout<<"请输入集合元素<头结点不用!>"<<endl;
    CreateLinkList(La,na);
    cout<<"请输入第二个集合的元素数目:"<<endl;
    cin>>nb;
    cout<<"请输入集合元素<头结点不用!>"<<endl;
    CreateLinkList(Lb,nb);
    QuickSort(La,NULL);
    QuickSort(Lb,NULL);
    cout<<"集合LA:";
    Print(La);
    cout<<"集合LB:";
    Print(Lb);
    cout<<"LA和LB的并集为:";
    AddList(La,Lb);
    cout<<"LA和LB的交集为:";
    JiaoList(La,Lb);
    cout<<"LA和LB的差集为:";
    ChaList(La,Lb);

    return 0;
}

搜索更多相关主题的帖子: include　

第 2 楼

得分:0

程序代码：

// 集合幂集
void PowerLink(LinkList L, LinkList rear, LinkList result)
{
    // 遍历到尾部
    if (NULL == L)
    {
        Print(result);
        return;
    }
    // 第一次递归，此时L指向头结点
    if (NULL == result)
    {
        result = (LinkList) malloc(sizeof(LNode));
        result->data = -1;
        result->next = NULL;
        PowerLink(L->next, result, result);
        free(result);
    }
    else
    {
        // 当前节点加入幂集
        rear->next = (LinkList) malloc(sizeof(LNode));
        rear->next->data = L->data;
        rear->next->next = NULL;
        PowerLink(L->next, rear->next, result);

        free(rear->next);
        rear->next = NULL;  // 还原上层递归改变的next值

        // 当前节点不加入幂集
        PowerLink(L->next, rear, result);
    }
}

int main()
{
    LinkList L;
    cout << "输入集合的元素:";
    CreateLinkList(L, 5);
    PowerLink(L, NULL, NULL);
    return 0;
}

[此贴子已经被作者于2016-7-11 11:08编辑过]

[fly]存在即是合理[/fly]

第 3 楼

得分:0

ps:以下回答搬运自，  http://www.   我承诺未对其内容进行过任何编辑。
=========================================================================================
集合的幂集

集合A的幂集是由集合A的所有子集所组成的的集合。

如：A={1，2，3}，则A的幂集P（A）={{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }}。

求一个集合的幂集就是求一个集合的所有的子集，方法有穷举法，分治法，回溯等，这里主要介绍一下回溯法。

回溯法是设计递归过程的一种重要的方法，它的求解过实质上是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中的。

幂集中的每个元素是一个集合，它或是空集，或含集合A中一个元素，或含集合A中两个元素…… 或等于集合A。反之，从集合A 的每个元素来看，它只有两种状态：它或属幂集的无素集，或不属幂集的元素集。则求幂集p(A)的元素的过程可看成是依次对集合A中元素进行“取”或“舍”的过程，并且可以用一棵二叉树来表示过程中幂集元素的状态变化过程，树中的根结点表示幂集元素的初始状态（空集）；叶子结点表示它的终结状态，而第i层的分支结点，则表示已对集合A中前i-1个元素进行了取舍处理的当前状态（左分支表示取，右分支表示舍）。因此求幂集元素的过程即为先序遍历这棵状态树的过程。

具体算法如下：

C/C++描述：

#include <iostream>
#include <cstring>
#include <ctype.h>
#include <stdlib.h>
#include <string>
using namespace std;

char a[100];
char b[100];

void GetPowerSet(int i, char a[])
{
char x;
int k;
int len = strlen(a);
if(i >= len)
{
  if(b[0])
   cout << b <<  endl;
  else
   cout << "XX" << endl;  // 表示空集
}
else
{
  x = a[i];
  k = strlen(b);
  b[k] = x;
  GetPowerSet(i+1, a);
  b[k] = 0;
  GetPowerSet(i+1, a);
}
}

int main()
{
while(scanf("%s", a) != EOF)
{
  printf("%s的幂集是:\n", a);
  printf("------------\n");
  GetPowerSet(0, a);
  printf("------------\n");
}
}

φ(゜▽゜*)♪