線形リストにおいて差集合を求める関数を作りたいのですが

Question

上の問題において
（ア）は
tail->next = new(a->elm, NULL);
a = a->next;
tail = tail->next;
であってますでしょうか？

(２)は

でいいでしょうか？
各変数が保持する線形リストを図示せよと記載されているのですが、どこからリストを描けばいいか理解できませんでした。

(３）最悪の場合は差集合A-B＝A、つまり、A∩B＝０であることから、（ア）の文とb=b->nextの文を繰り返すことから
O(|A|+|B|)と考えました

(4)

struct node *diff(struct node *a, struct node *b) {
struct node *head = new(0, NULL), *tail = head;
if(a==NULL || b== NULL) {
 tail->next = a;
 return head->next
}
if(a->elm < b->elm) {
 return diff(a->next, b);
}
else if(a->elm == b->elm) {
return diff(a->next, b->next);
}
else {
return diff(a, b->next);
}
}

と考えましたが、冒頭の
struct node *head = new(0, NULL), *tail = head;
が邪魔でうまく再起できません。

(5)(6)はできませんでした。

ご教示願います。

＊追記＊

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

struct node {
  int elm;
  struct node *next;
};

struct node *new(int e, struct node *n) {
  struct node *p;
  p = malloc(sizeof(struct node));
  p->elm = e;
  p->next = n;
  return p;
}

struct node *diff(struct node *a, struct node *b) {
  struct node *head = new(0, NULL), *tail = head;
  if(a==NULL || b== NULL) {
    return a;
  }
  if(a->elm < b->elm) {
    tail->next = new(a->elm, NULL);
    tail= tail->next;
  return tail->next = diff(a->next, b);
  }
  else if(a->elm == b->elm) {
    return tail->next = diff(a->next, b->next);
  }
  else {
    return tail->next = diff(a, b->next);
  }
}

int main(void) {
  struct node *a = new(1, new(3, new(6, new(10, NULL))));
  struct node *b = new(3, new(7, NULL));
  struct node *c = diff(a,b);
  while(c!=NULL) {
    printf("%d\n",c->elm);
    c = c->next;
  }
  return 0;
}

Comments

[coco_bauer]

夏休みの宿題ですか？　自分でがんばりましょう。

[apeirogon0813]

宿題じゃないです。過去問で答えがないので、合ってるか教えていただきたいです。

[Zuishin]

できなかったなら合ってないのでは？
正解を教えてもらったのでは過去問をする意味はありませんよ。その問題は二度と出ませんから。
必要なのはその問題が解けるだけの力です。
自分で考えて作れなければ力はつきません。

[apeirogon0813]

研究ではなく勉強なので、ある程度考えても分からなかったら、答えを見て、次の問題に取り組むべきだと思います。分からないものをずっと考えても効率悪いと思わないのでしょうか？

[Zuishin]

答えを見ずに次へ行くほうが効率がいいのでは？

[Zuishin]

このような問題を解く人は、線形リストなんて自分で作れて当たり前なので、そのレベルに無い人が答えだけ見てわかったつもりになってもただの時間の無駄です。

[apeirogon0813]

わかりました！

Answer 1

1～3はあってると思います

4について
最初と最後だけ書いておきます

Node *ret = NULL;

(中略)

Node *node = diff(?, ?);
return ret == NULL ? node : new new(ret->elm, node);

5,6は、要は二分木をつくれという課題です
多分どっかに書いてあるので、そのソースを丸ごと写してからスタートです

Comments

[apeirogon0813]

ありがとうございます。
参考にさせてもらったところ４番は
struct node *diff(struct node *a, struct node *b) {
struct node *head = new(0, NULL), *tail = head;
if(a==NULL || b== NULL) {
return a;
}
if(a->elm < b->elm) {
tai->next = new(a->elm, NULL);
tail= tail->next
return tail->next = diff(a->next, b);
}
else if(a->elm == b->elm) {
return tail->next = diff(a->next, b->next);
}
else {
return tail->next = diff(a, b->next);
}
}
完成しました。

[izmktr]

それバグってます
head ＝ new... とありますが、newしたものはdeleteしなければならないルールは知っていますか？
headはローカル変数ですからどこかに渡さないとdeleteできないし、
headをコピーしたtailもtail->nextで上書きしてますから、deleteする機会がありませんね

というか、この問題自体おかしいですね
Φ＝{}ではなく、Φ={0} なんですか？

[apeirogon0813]

deleteを入れるなら最初のコードもバグってますよね。
おそらくこの線形リストは先頭にダミーノードをおいた手法だと思います。

[izmktr]

ほんとだ、最初のコードからしてまずいですね
その本読むのやめたほうがいいと思います

さて、deleteの件を調査する過程で見つかると思ったので追記します
再帰コードを簡略化すると、return diff(???); になっているわけです
ということは、最後のdiffですべての差分集合を作り上げないと駄目なのにそういうコードになってないんです
これ本当にテストした上で完成とみなしていますか？

[apeirogon0813]

追記したコードで実行したところ、10とだけ出力されて繋がっていませんでした。
返り値をtail->nextに代入しているので繋がっていると思ったのですが、
どうして繋がっていないのかわかりません。もう少しヒントを教えていただけないでしょうか？

[izmktr]

最初と最後だけ書いておきます、って私は回答しましたよね
それを完全無視して自分のやりたいようにやるのなら勝手にやってください、としか言えません

Answer 2

自己解決！できました！！