回 帖 发 新 帖 刷新版面

主题:自已写的求子集的程序

根据严蔚敏课本P149写的,
输入一个N值,求出N的所有子集,已经做出来了,但还有一个小错误,请帮忙看一眼吧。

#include<stdio.h>
#include<stdlib.h>
#define ElemType int
typedef struct node{
    ElemType data;
    struct node *next;
}LinkList;
int ListInsert(LinkList *L,int n,ElemType &x){//含头结点
    int i;
    LinkList *p,*q,*r;
    p=L;
    for(i=1;i<=n&&p!=NULL;i++){
        q=p;
        p=p->next;
    }
    if(i<n) {printf("List INsert error\n");return 0;}
    r=(LinkList *)malloc(sizeof(LinkList));
    r->data=x;
    if(p==NULL){
        q->next=r;
        r->next=NULL;
    }
    else {
        q->next=r;
        r->next=p;
    }
    return 1;
}
int ListDelete(LinkList *L,int n,ElemType &x){
    int i;
    LinkList *p,*q;
    p=L;
    for(i=1;i<=n&&p;i++){
        q=p;
        p=p->next;
    }
    if(p==NULL){
        printf("Delete elem error p==NULL\n");
        return 0;
    }
    if(p->next)         
        q->next=p->next;    
    else q->next=NULL;
    x=p->data;
    free(p);
    return 1;
}
int GetElem(LinkList *L,int n,ElemType &x){
    int i;
    LinkList *p;
    p=L;
    for(i=1;i<=n&&p;i++)
        p=p->next;
    if(p==NULL) {
        printf("n too large in GetElem");
        return 0;
    }
    x=p->data;
    return 1;
}
int ListLength(LinkList *L){//忽略头结点长度
    int i=0;
    LinkList *p;
    p=L->next;
    while(p!=NULL){
        i++;
        p=p->next;
    }
    return i;

}
int OutPut(LinkList *L){
    LinkList *p;
    p=L->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return 1;
}
void GetPowerSet(int i,LinkList *A,LinkList *B){
    ElemType x;
    int k;
    if(i>ListLength(A)) OutPut(B);
    else{
        GetElem(A,i,x);
        k=ListLength(B);
        ListInsert(B,k+1,x);GetPowerSet(i+1,A,B);
        ListDelete(B,k+1,x);GetPowerSet(i+1,A,B);
    }
}
void main(){
    LinkList *A,*B;
    A=(LinkList *)malloc(sizeof(LinkList));A->next=NULL;
    B=(LinkList *)malloc(sizeof(LinkList));B->next=NULL;
    int n,j;
    printf("含N个元素的集合的幂集    输入N\n");
    scanf("%d",&n);
    for(j=1;j<=n;j++)
        ListInsert(A,j,j);
    GetPowerSet(1,A,B);
}

回复列表 (共3个回复)

沙发

复杂。佩服。

板凳

1,不用自己写数据结构的,那样写程序麻烦

2,求密集可以用二进制的方法,任何一个子集都和一个N为的2进制数对应,共2^N个子集

3,写的不错,支持一下!

3 楼

谢谢rickone的指点,
根据你的第二点,现写程序如下,调试运行结果完全成功。
#include<stdio.h>
#define max 100     //输入的最大的数
void Output(int a[],int n){
    int i;
    for(i=1;i<=n;i++)
        if(a[i]) printf("%d ",i);
        printf("\n");
}
void Produce(int n){//软计数器实现,1代表有该数,0代表无该数
    long i,j,tmp,m=1;        
    int flag[max];    //flag    1代表有该数,0代表无该数
    for(i=1;i<=n;i++) m=m*2;
    for(i=1;i<=m;i++){
        tmp=i;
        for(j=1;j<=n;j++){
            flag[j]=tmp%2;
            tmp=tmp/2;
        }
        Output(flag,n);
    }
}
void main(){
    int n;
    printf("求幂集输入的正整数\n");
    scanf("%d",&n);
    Produce(n);
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册