递归求集合子集（两种方法实现（数组，链表））

方法一：

#include<stdio.h>

#define N 6

char b[]= {'a','b','c','d','e','f'};
int a[N+1];

void find(int t) {
    int i,j;
    if(t <=0) {
        printf( "\n < ");
        for( i=1; i <=N; i++) {
            if(a[i]!=0) {
                printf( "%c ",b[a[i]-1]);    //打印b数组中第a[i]个元素
            }
        }
        printf( "> ");
    } else
        for( j=0; j <=1; j++) {
            a[t]=t*j;
            find(t-1);     //递归
        }
}

int main() {
    find(N);
    return 0;
}

方法二：（线性表）

/*求集合子集（严蔚敏C语言版数据结构P150）*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef struct node{
    int data;
    node *next;
}Node,*List;

void getSonSet(int i, List A, List B);//求集合的所有子集
List createList();  //创建链表
int listLength(List list);   //返回链表长度
void addNode(List list, int val);   //添加节点
void insertNode(List list, int pos, int val);   //插入节点
void deleteNode(List list, int pos, int *val);  //删除节点
void printList(List list);  //遍历链表
void getList(List list, int pos, int *x);   //获得pos位的值

int main(){
    List A,B;
    int val;
    A = createList();
    B = createList();
    addNode(A,1); addNode(A,2); addNode(A,3); addNode(A,4); addNode(A,5);
    getSonSet(1,A,B);
    return 0;
}
/*线性表A表示集合A,线性表B表示A的一个子集
 *局部变量k；为进入函数时表B的当前长度。第一次调用本函数时，B为空表，i = 1。
 *进入函数时已对A中前i-1个元素做了取舍处理。
 */
void getSonSet(int i, List A, List B){
    int x, k;
    if(i>listLength(A)) printList(B);   //输出当前B值，即A的一个子集
    else{
        getList(A, i, &x);  k = listLength(B);
        insertNode(B,k+1,x);    //取第i个元素
        getSonSet(i+1,A,B);
        deleteNode(B,k+1,&x);   //舍去第i个元素
        getSonSet(i+1,A,B);
    }
}

//创建链表
List createList(){
    Node *list = new Node; list->next = NULL;
    return list;
}

//返回链表长度
int listLength(List list){
    int i=0;
    for(Node *current = list->next; current!=NULL; i++, current = current->next)
        ;
    return i;
}

//添加节点
void addNode(List list, int val){
    Node *current = list;
    while(current->next) current = current->next;

    Node *newnode = new Node;
    newnode->data = val; newnode->next = NULL; current->next = newnode;
}

//插入节点
void insertNode(List list, int pos, int val){
    Node *current=list;
    int i;
    for(i=0; i<pos-1 && current; i++, current = current->next)
        ;
    if(!current || i>pos-1) return;

    Node *newnode = new Node;
    newnode->data = val; newnode->next = current->next; current->next = newnode;
}

//删除节点
void deleteNode(List list, int pos, int *val){
    Node *current=list;
    int i;
    for(i=0; i<pos-1 && current->next; i++, current = current->next)
        ;
    if(!(current->next) || i>pos-1) return;

    Node *current_next = current->next;
    current->next = current_next->next;
    *val = current_next->data; free(current_next);
}

//遍历链表
void printList(List list){
    Node *current = list->next;
    while(current){
        printf("%d\t",current->data);
        current = current->next;
    }
    printf("\n");
}

//获得pos位的值
void getList(List list, int pos, int *x){
    Node *current = list;
    int i;
    for(i=0; i<pos && current; i++, current = current->next)
        ;
    if(!current && i>pos-1) return ;

    *x = current->data;
}