木構造的に続く計算を行いたい

[Rcampsy]

お初にお目にかかります

現在バニングとホールという、既約ピタゴラス数を無限に生み出す行列式の勉強をしているのですが、それをプログラムで動かそうとしています

やりたいことは、三つの三行三列の行列式　A,B,C　を左から別々に元となる三行一列の行列式　K　にかけます
その結果現れた三つの三行一列の行列式　AK,BK,CK　に、上記の計算を別々に再び行います
最終的に行列内の数値が一定の基準を超えたらプログラムをストップするというものです

三分木のようにデータが増えていくものです
リスト構造を使えばいいといわれたのですが、どうも上手くいきません
プログラム自体は少しかじった程度で四苦八苦しています
どなたか助言をいただけるとありがたいです

[usao]

やろうとしていることの内容はよくわかりませんが，
{k} -> { AK, BK, CK } -> { {AAK,BAK,CAK}, {ABK,BBK,CBK}, {ACK,BCK,CCK} } -> ...
のように増えてく過程の全データを保持する必要がある　ということなのでしょうか．
で，この形が三分木になるということですが，
であれば三分木を実装するのではいけないのでしょうか？　何が問題なのですか？

>どうも上手くいきません
というあいまいな言い方では実情がわからないので有用な助言を得るのは難しいのではないかと思います．
何に困っているのか具体的に示すとよいのではないでしょうか．

[Rcampsy]

usaoさん、ありがとうございます
とりあえず仮組みしたものを乗せてみます
環境はVisual C++ 2010 Expressです

リスト構造と各々を計算するだけの関数を別に作る
別々の関数で行った計算で出た行列をリストに入れる
リストのはじめからループ文の条件を満たすまで計算を行う
ループが終わったらそれを表示する

という感じで進めていきたいのです

そこで分からないことは
　別の関数で行列の計算をしたとき、どうやって元に返せばいいのか
　そもそもこれでちゃんとリストが作られているのか
という点です

コード:

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

struct list
{
	int data[3][1];
	struct list *next;
};

int DP(int,int,int);
int AP(int,int,int);
int UP(int,int,int);

struct list *add_list(int data,struct list *head);
void show_list(struct list *p);
void free_list(struct list *p);

int main(void)

{
	struct list *head;
	struct list *p;
	int a=3;
	int b=4;
	int c=5;
	int data[3][1]={{a},{b},{c}};
	int l[3][1];
	int	m[3][1];
	int	n[3][1];

	head=NULL;

	head=add_list(data[3][1],head);

	for( ;p!=NULL;p=p->next)
	{
		a=p->data[0][0];
		b=p->data[1][0];
		c=p->data[2][0];

		while(a<100,b<100)
		{
			l[3][1]=DP(a,b,c);
			m[3][1]=AP(a,b,c);
			n[3][1]=UP(a,b,c);

			data[3][1]=l[3][1];
			head=add_list(data[3][1],head);
			data[3][1]=m[3][1];
			head=add_list(data[3][1],head);
			data[3][1]=n[3][1];
			head=add_list(data[3][1],head);
		}
	}

	show_list(head);

	free_list(head);

	return 0;
}

struct list *add_list(int data[3][1], struct list *head)
{
	struct list *p;

	if((p=(struct list *) malloc(sizeof(struct list)))==NULL)
	{
		printf("malloc error\n");
		exit(EXIT_FAILURE);
	}


	p->data[3][1]=data[3][1];
	
	p->next=head;
	head=p;

	return head;
}

void show_list(struct list *p)
{
	while(p!=NULL)
	{
		int i,j;

		for(i=0;i<3;i++)
		{
			for(j=0;j<1;j++)
			{
				printf("%4d",p->data[i][j]);
			}
		}
		putchar('\n');

		p=p->next;
	}
}

void free_list(struct list *p)
{
	struct list *p2;
	while (p!=NULL)
	{
		p2 = p->next;
		free(p);
		p = p2;
	}
}

int DP(int a,int b,int c)
{
	int i,j,k;
	int l[3][3]={{-1,2,2},{-2,1,2},{-2,2,3}};
	int m[3][1]={{a},{b},{c}};
	int n1[3][1];
	for(i=0;i<3;i++)
	{
		for(j=0;j<1;j++)
		{
			n1[i][j]=0;
			for(k=0;k<3;k++)
			{
				n1[i][j]+=l[i][k]*m[k][j];
			}
		}
	}

	return n1[3][1];
}

int AP(int a,int b,int c)
{
	int i,j,k;
	int l[3][3]={{1,2,2},{2,1,2},{2,2,3}};
	int m[3][1]={{a},{b},{c}};
	int n2[3][1];
	for(i=0;i<3;i++)
	{
		for(j=0;j<1;j++)
		{
			n2[i][j]=0;
			for(k=0;k<3;k++)
			{
				n2[i][j]+=l[i][k]*m[k][j];
			}
		}
	}

	return n2[3][1];
}

int UP(int a,int b,int c)
{
	int i,j,k;
	int l[3][3]={{1,-2,2},{2,-1,2},{2,-2,3}};
	int m[3][1]={{a},{b},{c}};
	int n3[3][1];
	for(i=0;i<3;i++)
	{
		for(j=0;j<1;j++)
		{
			n3[i][j]=0;
			for(k=0;k<3;k++)
			{
				n3[i][j]+=l[i][k]*m[k][j];
			}
		}
	}

	return n3[3][1];
}

[usao]

提示されたコードを拝見するに，１本のリストでデータを保持しているように見受けます．
取り組んでいる問題の内容がわからないので，間違っているかもしれませんが，

>{k} -> { AK, BK, CK } -> { {AAK,BAK,CAK}, {ABK,BBK,CBK}, {ACK,BCK,CCK} } -> ...
>のように増えてく過程の全データを保持する必要がある　ということなのでしょうか．
>で，この形が三分木になる

ということをやろうとしているのだと思っているのですが，まず，この解釈は合っているでしょうか？

↓あってる場合

これを素直に表現するとしたら，木構造の個々のノードは，
・データ(AKだとかBBKだとかいうやつ)を１つ持ち
・次の階層のノード(x3)を指し示す手段を持つ
ような形とかになると思います．データがint型なのであれば，例えば

コード:

struct Node
{
   int Data;  //データ
   Node *pNext[3];   //次の階層のノードを指すためのポインタ．３分木なので子ノードは３つ
};

という感じでしょうか．
初期状態ではデータ値Kを持つノードが木のルートノードとして存在する形：

コード:

Node Root;
Root.Data = K;
Root.pNext[0] = Root.pNext[1] = Root.pNext[2] = NULL;

とし，その後，このデータ値Kから３つのデータ値{AK,BK,CK}が計算されたとしたら
３つの新しいノードを作成し，それらのノードのDataがそれぞれAK,BK,CKになるようにして，
Root.pNext[0～3]がそれら３つのノードを指す形にする……という感じ．
（ノードには親を指すポインタも持たせた方がいろいろと楽かも）

[追記]
>そもそもこれでちゃんとリストが作られているのか
これについては，せっかく出力する関数を用意されているので，ご自身で確認されると良いかと思います．
ただ，mainのfor文に入る時点で p の値が不定になっているような…
あと，配列の文法について，少し復習された方がよいかと思います．
期待通りの動作をする書き方にはなっていないと思います．

[Rcampsy]

何度もありがとうございます

>{k} -> { AK, BK, CK } -> { {AAK,BAK,CAK}, {ABK,BBK,CBK}, {ACK,BCK,CCK} } -> ...
>のように増えてく過程の全データを保持する必要がある　ということなのでしょうか．
>で，この形が三分木になる

ということであっています
助言を元にもう一度洗いなおしてみたいと思います

ただ、いかんせん勉強不足なので、気づいたことがあれば書いていただけると幸いです

[usao]

木のデータ構造とか操作については
「二分木　Ｃ」とかで検索すると，例えば↓のようなのが見つかるので参考にすると良いでしょう．
（ここの図がわかりやすいかと思います）
http://akita-nct.jp/yamamoto/lecture/20 ... node2.html

３分木にするのでも話はほぼ変わらないはずです．

とりあえず最初は（早期に終了基準を満たすような閾値でも設けて）
あまり深くない木を作ってみて，結果を表示して確かめてみると良いかと思います．

書き方はいろいろあると思いますが，

コード:

//データ値 DataValue を持つ新しいノードを作る
//ノードの破棄には ReleaseNode()関数を用いること
Node *CreateNode( int DataValue )
{
  Node *pNewNode = (Node*)(   malloc( sizeof(Node) )   );
  pNewNode->Data = DataValue;
  pNewNode->pNext[0] = pNewNode->pNext[1] = pNewNode->pNext[2] = NULL;
  return pNewNode;
}

//ノードの破棄
//CreateNode()で作ったノードはこの関数で破棄すること
void ReleaseNode( Node *pNode )
{
  free( pNode );
}

//pNodeの子ノード×３個　を作成，データ構造に追加する．
void Create3ChildNodes_of( struct Node *pNode )
{
  int a,b,c;
  pNode->Data の値を用いて，三つの新しいデータ値 a,b,cを計算する．
  //計算したデータ値を持つノードを生成し，pNodeの子とする．
  pNode->pNext[0] = CreateNode( a );
  pNode->pNext[1] = CreateNode( b );
  pNode->pNext[2] = CreateNode( c );
}

みたいな雰囲気の関数を用意すれば，あとは木構造の中を探索しながら
次々に新しいノードを追加していけばいいんじゃないかと思います．

コード:

int main()
{
  //ルートノードの準備
  Node *pRootNode = CreateNode( K );  //※Kは最初のデータ値

  //ルートの下の３つを計算し，データ構造に追加する
  //※実際は木の中をめぐりながら（深さ優先探索，幅優先探索，etc）やることになるかと．
  Create3ChildNodes_of( pRootNode );

  ...

  //最後に木の全てのノードを破棄する必要がある．
  //（この例では，個々のノードの破棄には ReleaseNode() 関数を使う）
  (略)
  ...
}

[non]

データ構造以前に
三行三列なのに　int data[3][1];　なのはなぜ？
int data[3][3];　ではいけないのでしょうか。

[usao]

>nonさん
「行列式」とのことだったので　データはスカラーなのかな，と思い込んでいました
（ [3][1] というのは要するに[3]で，この3というのは３つの分岐のことなのかなー，とか）
が，あらためて

>やりたいことは、三つの三行三列の行列式　A,B,C　を左から別々に元となる三行一列の行列式　K　にかけます
>その結果現れた三つの三行一列の行列式　AK,BK,CK　に、上記の計算を別々に再び行います
>最終的に行列内の数値が一定の基準を超えたらプログラムをストップするというものです

を読み返してみると，
>三行一列の行列式
とか書かれている！　ので違うのかも…
（どこが「行列」でどこが「行列式」なのかが謎ですね）

[non]

ほんとだ。行列式って書いてある。行列だとばっかり思ってました。

[non]

関数DPを読みました。
3行3列の行列に3行1列の行列を掛けています。求められるのは、3行1列の行列ですね。
だから、int data[3][1];　にしているみたい。
int data[3];　でいいですね。

[Rcampsy]

nonさん、usaoさんありがとうございます
ほしいのは、KにA,B,Cをかけて出るAK,BK,CKという別々の行列です
こんな初歩的なミスまでして申し訳ありません

[usao]

データは行列なんですね．なら int にしてたDataの型を

コード:

int d[3][3];
とか
struct Mat33{  int d[3][3];  };

みたいなのに変えればよいですね．

オフトピック

あと，一応断っておくと(?)，
三分木の構造を勧めているのは，
『問題が三分木な形になるのであれば　それをそのまま実直に表現するのが一番わかりやすい』と思うからで，
>リスト構造を使えばいい
という助言をされた方には　別の考えがあるのかもしれません．
その辺　確認できるのであればしてみると良いかと思います．

[non]

ノードの数は
1,3,9,27・・・と増えることを頭に入れれば、リスト構造でもいいけど、配列を動的に用意するだけでもいいかも。
ただし、
>最終的に行列内の数値が一定の基準を超えたらプログラムをストップするというものです
これが、全体をストップするのか、そのノードの子ノードを作るのを止めるのかわからないのですが。