/***********************************************************************************\
 功    能：    求整数集合的子集 
 输入说明：    按提示输入数据
 输出说明：     以集合形式输出子集      
 
测试数据如下：
   
Enter the number of gather:4
Enter gather's each element:
1 2 3 4

The sub gather as followed:
{}
{1}
{2}
{3}
{4}
{2,1}
{3,1}
{4,1}
{3,2}
{4,2}
{4,3}
{3,2,1}
{4,2,1}
{4,3,1}
{4,3,2}
{4,3,2,1}
Press any key to continue
 
 算法说明： 对子集的寻找按照子集元素个数递增方式，用堆栈
  
 语    言：   非标准 C  编译环境：VC ++ 6.0            
 Author  ：   江南孤峰  Time ：2006--11--29   

 独学而无友，则孤陋而寡闻  编程爱好者群 : 28011342   
     
\************************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct meter{/* 堆栈结构 */
 int value;
 int i;
 struct meter *down;
 struct meter *up;
}STACK;

void TestMemoryOver(void *p){
 if(!p){
  fprintf(stderr,"Memory alloc failed !");
  exit(1);
 }
}

int* InputData(){/* 数据输入 */
 int *array,i,max;

 printf("Enter the number of gather:");
 scanf("%d",&max);
 printf("Enter gather's each element:\n");
 array = (int*)malloc(sizeof(int)*(max+2));
 TestMemoryOver(array);
 for(i = 1; i <= max; i ++)
  scanf("%d",array+i);
 *array = max;
 return array;
}

STACK* GetNewStackNode(){/* 分配一个新的堆栈节点 */
 STACK *newnode;
    newnode = (struct meter*)malloc(sizeof(struct meter));
 TestMemoryOver(newnode);
 newnode->i = 0;
 newnode->down = NULL;
 newnode->up = NULL;
 newnode->value = 0;
 return newnode;
}

int main(){
 int *array,i,j,k,max;
 STACK *temp,*bottom,*top;

 array = InputData();
 max = *array;
 temp = bottom = top = GetNewStackNode();
 
 printf("\nThe sub gather as followed:\n{}\n");
 for(j = 1; j <= max; j ++){ /* 控制子集元素数目 */  
 temp = GetNewStackNode();/* 增加一个堆栈节点 */
 temp->down = top;
 temp->up = NULL;
 top->up = temp;
 top = temp;
 for(temp = bottom->up,i = 1; i <= j; i ++){ /* 初始化堆栈 */
   temp->i = i;
   temp->value = *(array+i);
   temp = temp->up;
 }
 while(1){/* 打印一个子集 */
  printf("{");
  for(temp = top; temp != bottom; temp = temp->down)
   printf("%d,",temp->value);
  printf("\b}\n");
  for(temp = top,k = 0; (temp->i+k >= max) && (temp != bottom); k ++)
   temp = temp->down ;
  if(temp == bottom)
   break;
  for(k = temp->i+1; 1; k ++){/* 寻找下一个子集 */
   temp->i = k;
   temp->value = *(array+k);
   if(temp == top)
    break;
   temp = temp->up;
  }
 }
 }
 free(array);/* 释放内存 */
 for(temp = top; temp->down;){
  bottom = temp;
  temp = temp->down ;
  free(bottom);
 }
 return 0;
}

评论