-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPowerSet.c
More file actions
174 lines (143 loc) · 3.45 KB
/
PowerSet.c
File metadata and controls
174 lines (143 loc) · 3.45 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define ElemType int
#define Status int
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct LNode
{
ElemType data; // 存储的数据
struct LNode *next; // 后继的结点指针
}LNode,*LinkList;
void InitList(LinkList *L)
{
// InitList_L即CreateList_L
// 顺序(头插法)n个元素的值,建立带表头结点的单链线性表L
// int i;
(*L) = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL; // 先建立一个带头结点的单链表
} // InitList
int ListLength(LinkList L)
{
// 计算链表长度
int i=0;
LinkList p = L->next;
while(p)
{
i++; // 存在加1
p = p->next; // 指向下一个结点
}
return i;
} // ListLength
Status GetElem(LinkList L,int i,ElemType *e)
{
LNode *p;
int j;
// L为带头结点的单链表的头指针
// 当第i个元素存在时，其值赋给e并返回OK,否则返回false
p = L->next; j = 1; // 初始化,p指向第一个结点,j为计数器
while(p && j < i)
{
p = p->next; ++j;
}
if(!p || j>i)
return ERROR; // 第i个元素不存在
*e = p->data; // 取第i个元素
return OK;
} // GetElem
Status ListInsert(LinkList *L,int i,ElemType e)
{
LinkList p; int j;
LinkList s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
// 在带头结点的单链线性表L中第i个位置之前插入元素e
p = (*L); j = 0;
while(p && j < i-1)
{
p = p->next; ++j; // 寻找第i-1个结点
}
if(!p||j>i-1)
return ERROR; // i小于1或者大于表长+1
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return OK;
} // ListInsert
Status ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList p,q; int j;
// 在带头结点的单链线性表L中,删除第i个元素，并由e返回其值
p = (*L); j = 0;
while(p->next && j<i-1)
{
// 寻找第i个结点,并令p指向其前趋
p = p->next; ++j;
}
if((!p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
*e = q->data; free(q);
return OK;
} // ListDelete
void Output(LinkList L){
int e,i = 1;
int length = ListLength(L);
for( i;i<=length;++i)
{
GetElem(L,i,&e);
printf("%d ",e);
}
// 输出空集
if (!length)
{
printf("Empty");
}
printf("\n");
return;
}
// 算法6.15 P150
// 线性表A表示集合A，线性表B表示幂集ρ(A)的一个元素。
// 局部量k为进入函数时表B的当前长度。
// 第一次调用本函数时，B为空表，i＝1。
void GetPowerSet(int i, LinkList A, LinkList *B) {
ElemType x;
int k;
if (i > ListLength(A))
Output(*B); // 输出当前B值，即ρ(A)的一个元素
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);
}
}
int main(){
int n,i;
ElemType e;
LinkList a,b;
printf("请输入集合A的元素个数:\n");
scanf("%d",&n);
InitList(&a);
printf("请输入集合中的元素:\n");
for(i=1;i<=n;i++){
scanf("%d",&e);
ListInsert(&a,i,e);
}
InitList(&b);
printf("进行冥集合运算!\n");
GetPowerSet(1, a, &b);
return 0;
}
/*
请输入集合A的元素个数：
3
请输入集合A的元素：(空格区分)
1 2 3
*/