javaによるジョセファス問題の実現方法

Question

現在javaを勉強中なのですがC言語で書かれた以下のコードをjavaで書いてみようとしています．

該当のソースコード

//リンクによるリスト
//Josephus problem
#include <stdlib.h>

typedef struct node *link;
struct node {
    int item;
    link next;
};

main(int argc, char *argv[]){
    int i, N = atoi(argv[1]), M = atoi(argv[2]);
    // N人の人がリーダーを選ぶのに環状に並んで適当な始点から数えてM番目の人を削除していく

    link t = malloc(sizeof *t), x = t;

    t -> item = 1;
    t -> next = t;

    for(i=2;i<=N;i++){
        x = (x->next = malloc(sizeof *x));
        x->item = i;
        x->next = t;
    }

    while(x != x->next){
        for(i=1;i<M;i++) x = x->next;
        
        //節点の削除
        t = x->next;
        x->next = t->next;

        N--;
    }

    printf("Leader is %dth\n", x->item);
}

試したこと

上記のCのコードに対して以下のようなjavaのコードを書いてみました．
###ソースコード

class Node{
  int item;
  Node next;
  Node(){
    item = 0;
    next = this;
  }
  Node(int item, Node next){
    this.item = item;
    this.next = next;
  }
}

public class Ex3{
  public static void main(String[] args){
    int i;
    int N = Integer.parseInt(args[0]);
    int M = Integer.parseInt(args[1]);
    Node t = null;
    Node x;
    x = t;
    t.item = 1;
    t.next = t;
    for(i=2;i<=N;i++){
      x = x.next;
      x.item = i;
      x.next = t;
    }
    while(x!=x.next){
      for(i=1;i<M;i++) x = x.next;
      x.next = (x.next).next;
      N--;
    }
    System.out.printf("%d/n", x.item);
  }
}

###試したこと
上のようにコードを書くとCのコードでいうmallocの部分が表現できていないためかException in thread "main" java.lang.NullPointerException
at Ex3.main(Ex3.java:24)
というエラーが出てしまいました．少し調べてみるとjavaにはmallocのようなものはないとありましたのでどうしようか行き詰ってしまいました．まだ勉強して間もないため基礎的な間違いや勘違いがありましたら申し訳ないのですがこの解決方法について教えてほしいです．

Comments

[y_waiwai]

このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[freeza]

ご返信ありがとうございます。質問を編集しました。始めてtaratailを利用したので不手際があって申し訳ございません。

[dodox86]

C言語のプログラムの方はご自身で書かれ、内容は理解している上で想定通り動作している完動品なのでしょうか。それをJavaの勉強の為に移植している、ということですか。

[freeza]

ご返信ありがとうございます。Cのコードはある参考書に載っていたコードで動くことは確認しており内容は少しは理解しているつもりです．そのコードをjavaの勉強のために移植している感じです．

Answer 1

javaにはmallocのようなものはない

メモリ管理は JVM が行いますので、"何かを入れる為の領域"をユーザが低レベルで確保して利用する必要はありません。

例えば、任意のタイミングで任意の型・長さの配列を確保・使用することが出来ます。

ex) int array[] = new int[N]; //C的 : int *array=(int*)malloc(sizeof(int)*N);

開放は、そのオブジェクト(配列もオブジェクトです)への参照が無くなれば自動で行われます。

C の構造体を java のクラスとして表現されるのでしたら、インスタンスの生成が malloc に相当します。

ex) Node node = new Node(); //C的 : Node *node = (Node*)malloc(sizeof(Node));

C では malloc した後にその領域を初期化したりがありますが、java ではコンストラクタのパラメータを使って初期化させるのが一般的かと思います。

Comments

[freeza]

ご返信ありがとうございます。ご指摘のとおり
Node t = new Node();
Node x = new Node();
x = x.next = new Node();
のように改変したら動くことができました！ありがとうございます！

Answer 2

そのアルゴリズムは存じませんが、今回のエラー原因について回答します。

まず、エラーメッセージを読みましょう。エラーメッセージにヒントが隠されています。

Exception in thread "main" java.lang.NullPointerException
at Ex3.main(Ex3.java:24)

[訳]
mainメソッドからjava.lang.NullPointerExceptionという例外が投げられています。
場所はEx3.javaの24行目です。 

ですね。今回はエラーではなく、例外ですね。

このNullPointerExceptionはいわゆるヌルポです。

インスタンス化していないオブジェクトを動かそうとしているときに飛んでくる例外です。

参考； 公式

で、今回のコードを見ると、ヌルポが飛んできそうな場面は、

    Node t = null;
    Node x;
    x = t;
    t.item = 1;
    t.next = t;
    for(i=2;i<=N;i++){
      x = x.next;
      x.item = i;
      x.next = t;
    }
    while(x!=x.next){
      for(i=1;i<M;i++) x = x.next;
      x.next = (x.next).next;
      N--;
    }

ですかね。

で、コードを読んでみましょう。

コードを読むコツは、一行レベルで、その行が何をしているかを考えながら読むですね。

で、読んでみると、

Node t に null として、Node x にその t を割り当てているようですね。

ですが、Javaとかでは、(動きから見るに)
参照型です。

まず、t = null となります。
で、そのnull というのは『有効でない範囲』です。

ヒント: 参考

Xにtが指しているnullを設定します。
そして、t をインスタンス化しています。

ですが、tが指し示す場所をxも指し示している…わけではありません。

ある意味、null用のアドレスが入っている状態です。

その状態で、xを動かそうとしていますから、今回の例外が飛んできているはずです。

おそらく、C/C++のポインタと混同しているのではないかと思いますが。

Comments

[dodox86]

ご回答が間違っている、という指摘ではないのですが、質問文中にある

> javaにはmallocのようなものはないとありましたのでどうしようか行き詰ってしまいました．

という文から、C言語構造体をmallocで割り当てる方法をJavaで代替するにはどうしたら良いのか？という疑問が元にあるのではないかと思います。Nodeクラスをnewでインスタンス化してあれやこれやする、ような。質問者さんのJavaの習熟状況は置いておいたとしても。

[freeza]

ご返信ありがとうございます。Node t　にnullを入れている部分に関して
Node t = new Node();　にして，　また
Node x = new Node(); x = x.next = new Node();
にすることで動くことができました！