/***********************************************************************************\ 功 能： 求整数集合的子集 输入说明： 按提示输入数据 输出说明： 以集合形式输出子集 测试数据如下： Enter the number of gather:4Enter 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;}
评论