teratail
回答率
85.48%
質問するログイン新規登録

質問をすることでしか得られない、回答やアドバイスがある。

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

新規登録して質問してみよう
ただいま回答率
85.48%
トップCに関する質問
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

1929閲覧

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

katkey
katkey

総合スコア15

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2021/02/06 15:31

編集2021/02/06 17:02

0

0

前提・実現したいこと

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

{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}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme
episteme

2021/02/06 16:59

期待する出力は?
katkey
katkey

2021/02/06 17:02

情報追加しました。
episteme
episteme

2021/02/06 17:03

実際の出力は?
katkey
katkey

2021/02/06 17:06

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

回答2件

0

ベストアンサー

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
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

katkey
katkey

2021/02/07 07:01

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

2021/02/07 07:17

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

2021/02/07 07:37

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

2021/02/07 08:00

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

2021/02/07 08:06

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

2021/02/07 12:03

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

2021/02/07 12:40

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

2021/02/07 12:50

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

2021/02/07 13:02

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

2021/02/07 13:58

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

2021/02/07 21:45

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

0

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
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問

トップCに関する質問

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