単方向リストにおける要素の集合の列挙

前提・実現したいこと

構造体を用いてテキストから要素を並べる単方向リストを作りました。
次は、再帰関数を用いて以下のように部分集合を出力するようにしたいです。
試行錯誤したのですが、うまくプログラムを組むことができません。
どうすればよいでしょうか？分かる方いましたら、回答をお願いします。
テキストの左は要素数　：以降が要素の数字となっています。
###期待する出力

{10 , 20 , 30}
{10 , 20}
{10 , 30}
{10}
{20 , 30}
{20}
{30}
{}

###test3.txt

3: 10 30 20

該当のソースコード

c
1#include<stdio.h>
2#include<stdlib.h>
3
4typedef struct LISTNODE
5{
6    int data;
7    int hantei;
8    struct LISTNODE *pNext;
9}ListNode;
10
11ListNode head;
12
13ListNode* getNode(int num){
14    int i;
15    ListNode *retNode=&head;
16
17    for(i=0;i<num;i++){
18        retNode=retNode->pNext;
19        if(retNode==NULL){
20            return 0;
21        }
22    }
23    return retNode;
24}
25
26int checkNode(int num){
27    ListNode *currentNode, *pCheckNode=getNode(num);
28
29    currentNode=head.pNext;
30
31    while(currentNode!=pCheckNode){
32        if(currentNode->data==pCheckNode->data)
33            return 1;
34        currentNode=currentNode->pNext;
35    }
36    return 0;
37}
38
39void deleteNode(int num){
40    ListNode *targetNode=getNode(num);
41    ListNode *pPrevNode=getNode(num-1);
42    pPrevNode -> pNext =targetNode -> pNext;
43    free(targetNode);
44}
45
46int swapNode(int num1, int num2){
47    ListNode *node1=getNode(num1), *node2=getNode(num2);
48    ListNode *Prenode1=getNode(num1-1), *Prenode2=getNode(num2-1);
49    ListNode *tmpNext;
50
51    if(node1->pNext!=node2){
52        tmpNext=node1->pNext;
53        node1->pNext=node2->pNext;
54        node2->pNext=tmpNext;
55        Prenode1->pNext=node2;
56        Prenode2->pNext=node1;
57    }else{
58        node1->pNext=node2->pNext;
59        node2->pNext=node1;
60        Prenode1->pNext=node2;
61    }
62    return 1;
63}
64
65void printNode(ListNode *currentNode){
66    if(currentNode!=NULL){
67        if(currentNode->hantei!=1){
68            printf("%d, ",currentNode->data);
69        }
70        printNode(currentNode->pNext);
71    }   
72}
73
74int addNode(){
75    ListNode *newNode, *pCheckNode, *pNextNode;
76
77    FILE *fp=fopen("test3.txt","r");
78    if(!fp) return 0;
79    int k,c=0;
80    if (fscanf(fp, "%d:", &k) != 1) return 0;
81    int a[100];
82    for (int i = 1; i <= k; i++) {
83        if (fscanf(fp, " %d", &a[i]) != 1) return 0;
84        //printf("a[%d] = %d\n", i, a[i]);
85        ListNode *pPrevNode=getNode(c);
86        newNode=(ListNode*)malloc(sizeof(ListNode));
87        newNode->data=a[i];
88        newNode->pNext=pPrevNode->pNext;
89        pPrevNode->pNext=newNode;
90        //printf("%d\n",checkNode(c+1));
91        if(checkNode(c+1)==1){
92            deleteNode(c+1);
93            continue;
94        }
95        c++;
96        //printf("c=%d\n",c);
97    }
98
99    fclose(fp);
100
101    int nodeNum, num=0;
102    ListNode *pEndNode=getNode(c);
103    while(num!=c){
104        pCheckNode=head.pNext;
105        nodeNum=0;
106        while(pCheckNode->pNext!=NULL){
107            pNextNode=pCheckNode->pNext;
108            nodeNum++;
109            if(pCheckNode->data>pNextNode->data)
110                swapNode(nodeNum, nodeNum+1);
111            else
112                pCheckNode=pCheckNode->pNext;
113        }
114        num++;
115    }
116    
117    ListNode *currentNode=&head;
118    for(int i=c;i>0;i--){
119        currentNode->hantei=0;
120        currentNode=currentNode->pNext;
121        for(int j=1;j<=2;j++){
122            if(j==2)
123                currentNode->hantei=1;
124            printf("<");
125            printNode(head.pNext);
126            printf(">\n");
127        }
128    }
129    return 1;
130}
131
132int main(void){
133    addNode();
134    return 0;
135}

episteme

2021/02/06 16:59

期待する出力は?

katkey

2021/02/06 17:02

情報追加しました。

episteme

2021/02/06 17:03

実際の出力は?

katkey

2021/02/06 17:06

このプログラムを動かしてみてください

行動規範の内容に同意します

回答2件

ベストアンサー

diff
1     if (fscanf(fp, "%d:", &k) != 1) return 0;
2-    int a[100];
3     for (int i = 1; i <= k; i++) {
4-        if (fscanf(fp, " %d", &a[i]) != 1) return 0;
5         //printf("a[%d] = %d\n", i, a[i]);
6         ListNode *pPrevNode=getNode(c);
7         newNode=(ListNode*)malloc(sizeof(ListNode));
8-        newNode->data=a[i];
9+        if (fscanf(fp, "%d", &newNode->data) != 1) return 0;
10         newNode->pNext=pPrevNode->pNext;
11 
12-    int nodeNum, num=0;
13-    ListNode *pEndNode=getNode(c);
14-    while(num!=c){
15-        pCheckNode=head.pNext;
16-        nodeNum=0;
17-        while(pCheckNode->pNext!=NULL){
18-            pNextNode=pCheckNode->pNext;
19-            nodeNum++;
20-            if(pCheckNode->data>pNextNode->data)
21-                swapNode(nodeNum, nodeNum+1);
22-            else
23-                pCheckNode=pCheckNode->pNext;
24-        }
25-        num++;
26-    }
27-
28-    ListNode *currentNode=&head;
29-    for(int i=c;i>0;i--){
30-        currentNode->hantei=0;
31-        currentNode=currentNode->pNext;
32-        for(int j=1;j<=2;j++){
33-            if(j==2)
34-                currentNode->hantei=1;
35-            printf("<");
36-            printNode(head.pNext);
37-            printf(">\n");
38-        }
39-    }
40+	for (int i = 1 << c; --i >= 0; ) {
41+        pCheckNode = head.pNext;
42+		printf("{");
43+		const char *sep = "";
44+		for (int j = c; --j >= 0; ) {
45+			if (i >> j & 1) {
46+				printf("%s%d", sep, pCheckNode->data);
47+				sep = " , ";
48+			}
49+			pCheckNode = pCheckNode->pNext;
50+		}
51+		printf("}\n");
52+	}
53     return 1;

追記

C
1#include<stdio.h>
2#include<stdlib.h>
3
4typedef struct LISTNODE
5{
6    int data;
7    int hantei;
8    struct LISTNODE *pNext;
9}ListNode;
10
11ListNode head;
12
13ListNode* getNode(int num){
14    int i;
15    ListNode *retNode=&head;
16
17    for(i=0;i<num;i++){
18        retNode=retNode->pNext;
19        if(retNode==NULL){
20            return 0;
21        }
22    }
23    return retNode;
24}
25
26int checkNode(int num){
27    ListNode *currentNode, *pCheckNode=getNode(num);
28
29    currentNode=head.pNext;
30
31    while(currentNode!=pCheckNode){
32        if(currentNode->data==pCheckNode->data)
33            return 1;
34        currentNode=currentNode->pNext;
35    }
36    return 0;
37}
38
39void deleteNode(int num){
40    ListNode *targetNode=getNode(num);
41    ListNode *pPrevNode=getNode(num-1);
42    pPrevNode -> pNext =targetNode -> pNext;
43    free(targetNode);
44}
45
46int swapNode(int num1, int num2){
47    ListNode *node1=getNode(num1), *node2=getNode(num2);
48    ListNode *Prenode1=getNode(num1-1), *Prenode2=getNode(num2-1);
49    ListNode *tmpNext;
50
51    if(node1->pNext!=node2){
52        tmpNext=node1->pNext;
53        node1->pNext=node2->pNext;
54        node2->pNext=tmpNext;
55        Prenode1->pNext=node2;
56        Prenode2->pNext=node1;
57    }else{
58        node1->pNext=node2->pNext;
59        node2->pNext=node1;
60        Prenode1->pNext=node2;
61    }
62    return 1;
63}
64
65void printNode(ListNode *currentNode){
66    if(currentNode!=NULL){
67        if(currentNode->hantei!=1){
68            printf("%d, ",currentNode->data);
69        }
70        printNode(currentNode->pNext);
71    }   
72}
73
74int addNode(){
75    ListNode *newNode, *pCheckNode, *pNextNode;
76
77    FILE *fp=fopen("test3.txt","r");
78    if(!fp) return 0;
79    int k,c=0;
80    if (fscanf(fp, "%d:", &k) != 1) return 0;
81    for (int i = 1; i <= k; i++) {
82        //printf("a[%d] = %d\n", i, a[i]);
83        ListNode *pPrevNode=getNode(c);
84        newNode=(ListNode*)malloc(sizeof(ListNode));
85        if (fscanf(fp, "%d", &newNode->data) != 1) return 0;
86        newNode->pNext=pPrevNode->pNext;
87        pPrevNode->pNext=newNode;
88        //printf("%d\n",checkNode(c+1));
89        if(checkNode(c+1)==1){
90            deleteNode(c+1);
91            continue;
92        }
93        c++;
94        //printf("c=%d\n",c);
95    }
96
97    fclose(fp);
98    for (int i = 1 << c; --i >= 0; ) {
99        pCheckNode = head.pNext;
100        printf("{");
101        const char *sep = "";
102        for (int j = c; --j >= 0; ) {
103            if (i >> j & 1) {
104                printf("%s%d", sep, pCheckNode->data);
105                sep = " , ";
106            }
107            pCheckNode = pCheckNode->pNext;
108        }
109        printf("}\n");
110    }
111    return 1;
112}
113
114int main(void){
115    addNode();
116    return 0;
117}

追記2

1つ質問ですが、変数 i は2進数として扱っているのですか？

text
1{10, 20, 30}   {1, 1, 1}   7
2{10, 20    }   {1, 1, 0}   6
3{10,     30}   {1, 0, 1}   5
4{10        }   {1, 0, 0}   4
5{    20, 30}   {0, 1, 1}   3
6{    20    }   {0, 1, 0}   2
7{        30}   {0, 0, 1}   1
8{          }   {0, 0, 0}   0

表示するものを 1、表示しないものを 0 とすると、
それは 2進数とみなして、7～0 の値になります。

投稿2021/02/06 23:56

編集2021/02/07 15:54

kazuma-s

総合スコア8224

katkey

2021/02/07 07:01

これって赤の部分は不要部ということですか？

kazuma-s

2021/02/07 07:17

そうです。なぜ試してみないんですか？

katkey

2021/02/07 07:37

試したのですが、表示されないからです。

kazuma-s

2021/02/07 08:00

今から、オンライン飲み会なので、しばらく返信できません。

katkey

2021/02/07 08:06

返信ありがとうございます。試してみます。

kazuma-s

2021/02/07 12:03

解決済みになっていますが、どのようにして解決したのですか？最初に試して表示されなかった原因は何ですか？

katkey

2021/02/07 12:40

追記にかかれているプログラムをコピペしたところ理想の表示結果が得られました。すみません、以前のプログラムを消してしまったのでわからないのですが、実行したところ{}のように表示されていました。コピーするときに行が少しずれてしまっていたので、その時にコードの一部を消してしまったのかもしれません。

kazuma-s

2021/02/07 12:50

以前のプログラムは質問の「該当のソースコード」にあります。もう一度確認をお願いします。理想の表示結果が得られたコードの意味を完全に理解していますか？理解していなければ解決とは言えないと思います。分からないところは、自分で調べるなり、また質問するなりしないといけないのではないでしょうか？

katkey

2021/02/07 13:02

おっしゃる通りです。確認ができたらここに解答をいたしますので、しばらくお待ちください。

katkey

2021/02/07 13:58

当該のソースコードには pPrevNode->pNext=newNode; がありません。そのため、単方向リストが正しく作成されていないことが原因でした。ビット演算を用いて、部分集合を生成していることは分かりました。 1つ質問ですが、変数 i は2進数として扱っているのですか？

katkey

2021/02/07 21:45

返信ありがとうございます。分かりました。

行動規範の内容に同意します

C
1    ListNode* currentNode = &head;
2    for (int i = c; i > 0; i--) {
3        currentNode->hantei = 0;
4        currentNode = currentNode->pNext;
5        for (int j = 1; j <= 2; j++) {
6            if (j == 2)
7                currentNode->hantei = 1;
8            printf("<");
9            printNode(head.pNext);
10            printf(">\n");
11        }
12    }

この↑コードはなにしたいんですか?

外側のloopはc(=3)回の繰り返しなので、出力されるとしたら6行。
期待する結果と明らかに違います。

printNode() は与えたListNodeから順に最後まで、hantei != 1 のものを出力するんよね?
ちゃんと書けてるしちゃんと動いてますよ。

投稿2021/02/06 17:18

編集2021/02/06 17:27

episteme

総合スコア16612

あなたの回答

tips

プレビュー

行動規範の内容に同意します

質問の解決につながる回答をしましょう。サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。また、読む側のことを考えた、分かりやすい文章を心がけましょう。

15分調べてもわからないことは
teratailで質問しよう！

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

『🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中！

＼teratail特別グッズやAmazonギフトカード最大2,000円分が当たる！／

単方向リストにおける要素の集合の列挙

前提・実現したいこと

該当のソースコード

関連した質問