はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

ALDS1_7_A Rooted Trees

問題
Rooted Trees | Aizu Online Judge

最近は相変わらずjavaをやっております。今回は木の実装です。
ノードというクラスを作り、その配列に情報を詰め込む、という感じです。

import java.util.Scanner;

class Node {
	private int parent;
	private int depth;
	private String type;
	private int childnum;
	private int[] child;
	
	Node(int d,int p){
		depth=d; parent=p; 
	}
	
	void setChildnum(int childnum){
		this.childnum=childnum;
		child=new int[childnum];
	}
	
	int getChildnum(){ return childnum; }
	
	void setChild(int x,int idx){
		child[idx]=x;
	}
	
	int getChild(int idx){ return child[idx]; }
	
	void setType(){
		if(parent==-1)
			type="root";
		else if(childnum==0)
			type="leaf";
		else 
			type="internal node";
	}
	
	int getParent(){ return parent; }
	
	void setParent(int p){ parent=p; }
	
	int getDepth(){ return depth; }
	
	void setDepth(int d){ depth=d; }
	
	String getType(){ setType(); return type; }
	
	void printChild(){
		
		System.out.print("[");
		
		for(int i=0;i<childnum;i++){
			if(i==childnum-1)
				System.out.print(child[i]);
			else 
				System.out.print(child[i] +", ");
		}
		
		System.out.println("]");
		
	}

}

class alds_7_a {
	
	static int getRoot(Node[] a,int n){
		for(int i=0;i<n;i++){
			if(a[i].getParent() == -1)
				return i;
		}
		return 0;
	}
	
	static void setdepth(Node[] a,int root){
		int c=a[root].getChildnum();
		for(int i=0;i<c;i++){
			int t=a[root].getChild(i);
			a[t].setDepth( a[root].getDepth()+1 );
			setdepth(a,t);
		}
		return;
	}
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		Node[] a=new Node[n];
		
		for(int i=0;i<n;i++)
			a[i]=new Node(0,-1);
		
		for(int i=0;i<n;i++){
			int x=scan.nextInt(); int y=scan.nextInt();
			a[x].setChildnum(y);
			for(int j=0;j<y;j++){
				int z=scan.nextInt();
				a[x].setChild(z,j);
				a[z].setParent(x);
			}
		}
		
		int root=getRoot(a,n);
		setdepth(a,root);
		
		for(int i=0;i<n;i++){
			System.out.print("node "+i+": parent = "+a[i].getParent()+", "+"depth = "+a[i].getDepth()+", "+a[i].getType()+", ");
			a[i].printChild();
		}
			
		
	}
}

クラスの練習を兼ねて基本的にprivateを付けて、ゲッタセッタを利用しているのですが、まあ面倒くさいですね。
実際のシステム等で使うには良いのかもしれませんが、競技プログラミングとか、こういう問題の場合はprivateなど付けず、C言語の構造体みたいに適当にアクセスする方が良い気がします。

今回各ノードが持つ子供を

void setChildnum(int childnum){
	this.childnum=childnum;
	child=new int[childnum];
}

こんな感じで無駄なく配列を作って、ここに保存しました。こうやって動的に配列を確保できるのは良いですね。

とここまで書いて、C言語でも同じことできるんじゃね?と思いました。
仮にCの構造体で、ノードXに配列を持たせるなら

typedef struct Node {
    int *child;
}
void setChild(Node a[],int x,int num){
    a[x].child=malloc(sizeof(int)*num); /*numは配列の要素数*/
}

こんな感じになるのでしょうか。javaの方がすっきりしてる気はしますが、やってることはあまり変わらないですね。