自己参照構造体(リスト構造)を使用した住所録の作成

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
わたねる

自己参照構造体(リスト構造)を使用した住所録の作成

#1

投稿記事 by わたねる » 17年前

はじめまして、ここを利用させていただくのは初めてとなります。
自身の持っている知識なのですが、基礎的なC言語の入門書は読み漁り、簡単なポインタ、構造体までは理解しているつもりです。
当方、C言語を覚え始めて1ヶ月の未熟者です。色々と至らない面があると思いますが、お手柔らかにお願い致します。

さて早速ですが質問に移りたいと思います。
現在、ポインタ、構造体の理解のために「住所録」の作成をしています。
仕様としましては、

「名前」「住所」「電話番号」を標準入力で入力させ、データの追加、参照、削除、検索を行えるようにする。
データの保存は配列ではなく自己参照構造体を使い、リスト構造として実現する。
fwrite、wreadを使用してファイルへの読み書きを行う。
データの追加、参照、削除、検索はそれぞれ別の関数で行えるようにする。
グローバルな構造体、変数は使わない。



以上を踏まえて製作しているのですが、手詰まりを起こしてしまいました。
まず、使用している構造体は

struct List:{char name[10] , char address[50] , char phone[15] , List *next_pointa}
これを踏まえて、*prev、*next、start_dmyの3つの構造体を作ります。
まず、データを入れないただのダミー構造体(start_dmy)を作ります。
このstart_dmyのnext_pointaが指しているアドレスから、リスト構造の読み込みを行います。
リスト構造の最後にはNULLを格納します。

[1000](start_dmy。データは空) ⇒ [1001](start_dmy.next_pointaの指すアドレス。ここからデータが入る) ⇒ [1002] ⇒ [1003] ⇒ [NUL[/url]

イメージとしては、上のようなリスト構造を考えています。
for(prev = start_dmy.next_pointa ; prev != NULL ; prev = prev->next_pointa); ←つまり、データ読み込みにはこのような命令を行う。



まず、以上を踏まえて(簡素化した)メイン関数とデータの追加の関数を書いてみると
main(){
  struct List *prev;
  struct List start_dmy;
  prev = &start_dmy;
  prev->next_pointa = NULL;
  for(;;){
  prev = add(prev);
  }
}

struct List *add(struct List prev){
  struct List *next;
  next = ( struct List * )malloc( sizeof ( struct List )); //データ領域の確保
  printf("\nデータの追加を行います。以下に従って入力してください。\n登録する人の名前?:");//とりあえず名前だけ
  scanf( "%s" , &next->name );
  prev->next_pointa = next;				
  next->next_pointa = NULL;
  prev = next;
  return prev;					
}
このような形でリスト構造を実現しようとしているのですが、初めにprevとstart_dmyを対応付けているので、
add関数内で、prev->next_pointaをnextで確保した領域のアドレスとしても、それはstart_dmyにも同期してしまいます。
つまり先ほどの例だと

[1000](start_dmy。データは空) ⇒ [1001] ⇒ [1002] ⇒ [1003](start_dmy.next_pointaの指すアドレス、prev->next_pointaの指すアドレス) ⇒ [NUL[/url]

となってしまいます。(start_dmy.next_pointaはあくまで1001番地を指していたい。)
更に削除の際に、先頭のデータを削除・・・つまりstart_dmy.next_pointaを書き換えないといけない場合でも、
returnで指定するのが、prevとstart_dmyの2つの構造体を戻さないといけないため、上手く実装できません。

長くなりましたが、コレに対する対応策、
もしくはこのような方法を取らなくても(なるべくダミー構造体は使いたくない)良い案がありましたら是非ご教授お願いいたします。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#2

投稿記事 by yuuki++ » 17年前

双方向リスト構造でいいんですよね?
一応、定石というかなんというか、「Headポインタ」「Tailポインタ」なんかを置くのが簡単ですね。
具体的には、構造体リストの先頭のアドレスを「Head」に、最後尾のアドレスを「Tail」に。
最初は両方ともNULLで初期化しておきます。

図を描くと分かりやすいですが、最後尾に追加するときには
・メモリ確保
・確保した構造体のprev、nextを更新(prev = pTail; next = NULL; とか)

削除するときには
・「prev」「next」があれば、それぞれつなぎかえる

というのが大体の手順なんですけど、この概念は掴めていますか?

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#3

投稿記事 by 御津凪 » 17年前

少し分かりにくいところがありますが、こういうことでしょうか。

まず始めに、提示していただいたコードではエラーが発生します。
add 関数にポインタを渡していませんが、関数内部ではデータをポインタとして記述しています。

あと、main 関数に戻り値がありません。

あと、ちゃんとした住所録を作る場合、
struct List {
	char name[10];
	char address[50];
	char phone[15];
	struct List *next_pointa;
	struct List *prev_pointa;
};
の、ように、前へのポインタも用意したほうが良いでしょう。

さて、本題ですが、

まず、ダミーはあったほうが処理がしやすいです。

リスト構造の最後の指す次のポインタをダミーとすることで、
リスト全体に何か施したりする時に、
struct List* list = start_dmy.next_pointa;
for(;list != &start_dmy;list = list->next_pointa){
	// 何らかの処理
}
上記のようにするだけで全てのリストに対して処理が出来ます。

次に問題としている部分ですが、
add 関数で渡している引数がポインタだとしたら、正しく動作していると思うのですが。

一応この手の書き方は、結構こんがらがりやすいので、
上記の(前後を指すデータ構造)方法での追加、削除などを下記に提示しておきます。
// リストの初期化。list:初期化するデータ
void initList(struct List* list){
	// 自身を指す。
	list->prev_pointa = list;
	list->next_pointa = list;
}
// リストに追加。top:リストの先頭(基本ダミー) addlist:追加するデータ
void addList(struct List* top,struct List* addlist){
	addlist->prev_pointa = top->prev_pointa;
	addlist->next_pointa = top;
	top->prev_pointa->next_pointa = addlist;
	top->prev_pointa-> = addlist;
}
// リストから除く。remlist:除くデータ
void remList(struct List* remlist){
	if(addlist->next_pointa == addlist){
		return;// 既にリストから外れている or リストが空
	}
	remlist->prev_pointa = remlist->next_pointa;
	remlist->next_pointa = remlist->prev_pointa;
	// 自身を指す。
	remlist->prev_pointa = list;
	remlist->next_pointa = list;
}
長くなりましたが、これを理解できれば解決できると思います。
(yuuki++さんと被りましたね)

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#4

投稿記事 by わたねる » 17年前

なるほど、双方向リストで実現するんですね。
単方向リストでしか実現することを考えていなかったので、以上のアドバイスを踏まえて一度製作してみます。
また行き詰ったところがあれば、質問させていただきますね。yuuki++さん、御津凪さん、分かりやすいご教授ありがとうございました。


・・・さて、御津凪さんのコードを理解しようと勤めているのですが、早速躓いてしまいました。
削除する関数のこの部分なのですが

remlist->prev_pointa = remlist->next_pointa;
remlist->next_pointa = remlist->prev_pointa;
// 自身を指す。
remlist->prev_pointa = list;
remlist->next_pointa = list;

仮に、
[1000]⇒[1001]⇒[1002](top) となっている構造体があるとします。(数字はアドレス番地)
ここから1001を削除する(remlistは1001に設定)と、
まず、remlist->prev_pointaは1000、remlist->next_pointaは1002を指していますよね。
1行目
remlist->prev_pointa = remlist->next_pointa;
により、
remlist->prev_pointaは1002、remlist->next_pointaは1002に変わりますよね。
そして2行目
remlist->next_pointa = remlist->prev_pointa;
により、remlist->prev_pointaは1002、remlist->next_pointaは1002と変わらない数字になります。

そして、3、4行目
remlist->prev_pointa = list;
remlist->next_pointa = list;
結局、先ほど変更したremlistのprev_pointaもnext_pointaもlistを指すようになったので、上記のように付け替えたのが無意味になってしまってならなく感じます。
そして、list構造体も、addlist構造体も、引数として削除関数に書かれていませんが、これはグローバルで宣言したものなのでしょうか。
お忙しいところ恐縮ですが、もう一度ご教授お願いいたします。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#5

投稿記事 by yuuki++ » 17年前

単方向と双方向について補足です。

単方向の場合、前か次かどちらか1つの情報を持つことになります。
すると、データを削除する際に、前後の構造体をつなぐことができなくなってしまいます。
…□⇒□⇒□⇒…
真ん中を削除したら、1つ前が自分の次を指すようにしなければならないのですが、「1つ前」にアクセスするのが難しいですね(構造体のサイズを使ったアドレス演算が必要)。
逆方向だとしても同様です。
ただし削除ができなくなるわけではなくて、先頭の構造体を削除することのみ可能です(図で確認すると分かるかな)。

とすると、
・データの削除は先頭に対してのみ(スタックに近い)→単方向
・どのデータを削除するかはランダム→双方向
という使い分けができそうですね。

ちなみにシューティングの敵とかをリストで管理するとすれば、以上の理由から双方向になります(ランダムに消えていくので)。

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#6

投稿記事 by わたねる » 17年前

・・・さて、御津凪さんのコードを理解しようと勤めているのですが、早速躓いてしまいました。
削除する関数のこの部分なのですが

remlist->prev_pointa = remlist->next_pointa;
remlist->next_pointa = remlist->prev_pointa;
// 自身を指す。
remlist->prev_pointa = list;
remlist->next_pointa = list;

仮に、
[1000]⇒[1001]⇒[1002](top) となっている構造体があるとします。(数字はアドレス番地)
ここから1001を削除する(remlistは1001に設定)と、
まず、remlist->prev_pointaは1000、remlist->next_pointaは1002を指していますよね。
1行目
remlist->prev_pointa = remlist->next_pointa;
により、
remlist->prev_pointaは1002、remlist->next_pointaは1002に変わりますよね。
そして2行目
remlist->next_pointa = remlist->prev_pointa;
により、remlist->prev_pointaは1002、remlist->next_pointaは1002と変わらない数字になります。

そして、3、4行目
remlist->prev_pointa = list;
remlist->next_pointa = list;
結局、先ほど変更したremlistのprev_pointaもnext_pointaもlistを指すようになったので、上記のように付け替えたのが無意味になってしまってならなく感じます。
そして、list構造体も、addlist構造体も、引数として削除関数に書かれていませんが、これはグローバルで宣言したものなのでしょうか。
お忙しいところ恐縮ですが、もう一度ご教授お願いいたします。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#7

投稿記事 by yuuki++ » 17年前

ちょっと作ってみました。
//適当な構造体
typedef struct LIST {
	struct LIST *pPrev, *pNext; //前と次の自己参照
	int i;
} LIST, *PLIST;

//リストの最後尾に追加(リストのポインタのポインタを渡します)
PLIST Add(PLIST *pList)
{
	int i = 0;
	PLIST p = (PLIST)malloc(sizeof(LIST)); //確保
	PLIST pcur = *pList; //カレントポジション

	if (pcur) {	//先頭が存在したら
		i = 1;
		while(pcur->pNext) {	//最後尾まで移動(ループ)して(最後尾を保存しておいてもいいです)
			pcur = pcur->pNext;
			i++;
		}
		pcur->pNext = p;	//新しい奴を追加
	} else {		//先頭がなかったら
		*pList = p;	//新しい奴を先頭に
	}

	//新しいデータを設定する
	p->pPrev = pcur;
	p->pNext = NULL;
	p->i = i;		//メンバiにはデータの個数を0から連番で入れるようしています
	return p;
}

//リストから一個消す(ここも引数が・・・汗)
void Del(PLIST *pList, PLIST p)
{
	//「自分(p)の次」があったら、「次の1つ前」を「自分の1つ前」に
	if (p->pNext)	p->pNext->pPrev = p->pPrev;

	//「自分の前」があったら、「前の1つ次」を「自分の次」に
	if (p->pPrev)	p->pPrev->pNext = p->pNext;
	else			*pList = p->pNext;		//なかったら自分の次を先頭にします

	free(p); //自分を消す
}
で、main内で
PLIST pList = NULL;
として取り合えずポインタだけ宣言しておいて、Add()でガンガン追加します。
Del()で消せます。引数にはAddの返値が使えますね。
この方法だと、構造体そのものをダミーとかで用意する必要がなくなります。

ちょっといろいろ適当に作ったので自信ないですが、試してみてください。ってか分からなかったらまた聞いてください><

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#8

投稿記事 by 御津凪 » 17年前

すいません。remList 関数は間違いがありました。
void remList(struct List* remlist){
	if(addlist->next_pointa == addlist){
		return;// 既にリストから外れている or リストが空
	}
	remlist->prev_pointa->next_pointa = remlist->next_pointa;
	remlist->next_pointa->prev_pointa = remlist->prev_pointa;
	// 自身を指す。
	remlist->prev_pointa = list;
	remlist->next_pointa = list;
}
こうでした。
赤色の部分は、remlistの前後のデータを抜いた後も属していたリストが正しく動作するようにするもので、
その下の部分は、どのリストにも属していないことを表します。
つまり、どちらか一つでも自分自身を指していれば、リストに追加していないということが分かります。

> list構造体も、addlist構造体も、引数として削除関数に書かれていませんが、これはグローバルで宣言したものなのでしょうか。
list 構造体ではなく、これは list という名前の変数です。
同じく addlist も変数です。
上記に書かれていた引数は全て List 構造体のポインタですよ。

struct List* が型の名前、その後に続く単語が変数名です。
お間違えの無いように。

あと、initList 関数と addList 関数は理解できたでしょうか?

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#9

投稿記事 by 御津凪 » 17年前

> yuuki++ さん
ダミーはあっても無くてもこのリスト構造は作れます。
しかし、ゲームなどで使用するタイプのリストだと、
ダミーを用意したほうが早くなります。
ダミーがないと、リストが空なのかを確認する処理や、追加時や削除時に空かを確認する処理が入るため、
どうしても処理が増えてしまいます。

もちろん、一つのデータが大きい場合はダミーを用意しないほうがメモリの節約にはなります。
処理時間を優先しなければ(住所録のように)ダミーが無いほうが良いと思います。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#10

投稿記事 by yuuki++ » 17年前

>御津凪さん
実際にどれほどの遅延が発生しましたか?
おそらくループ移動とかでしょうが、あれはTailを保存すれば解消できますね。
>ダミーがないと、リストが空なのかを確認する処理や、追加時や削除時に空かを確認する処理が入るため、
>どうしても処理が増えてしまいます。
まさかこういう形で突っ込まれるとは思いませんでしたが笑

確かに、ポインタがNULLであるかのステップが入りますね。
では、
>void initList(struct List* list){
>	// 自身を指す。
>	list->prev_pointa = list;
>	list->next_pointa = list;
>}
この直後にこの構造体にアクセスしてしまったらどうしますか?新たにカウンタ変数を持ちますか?
リストがダミーのみのときにアクセスしてしまったらどうしますか?

おそらく、実際に遅延を計測したのでしょうが、最近のマシンでは気になるほどではないと思います。
この速度差が気になる状況下ですと、リスト構造そのものが使えなくなりますね。
特に頻繁にデータを作る必要がある場合、動的なメモリ確保はむしろボトルネックになります。

特にポインタ関連のコーディングに関しては保守点検がしやすいことを重視すべきです。

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#11

投稿記事 by わたねる » 17年前

>>yuuki++さん、御津凪さん

うーん・・・紙に書いて追ってみたのですが、どうもいまいち理解が出来かねます・・・。
yuuki++さんのソースも拝見しましたが、main関数に何をさせればいいのか手を付けられません・・・。
もしお暇でしたら、>>1で書いたような仕様でmain関数も含めて書いてくださいませんか。
後これは、単方向リストでは実現不能ですかね・・・?

>>御津凪さん
initList 関数と addList 関数、理解できました。ありがとうございます。
初期化用の関数として用意したり、初めはダミーではなくて自身を指すことを思いつかなかったので驚きです。
構造体の件も、勘違いしていたことが改めて頭に入りました。構造体ではなく変数なのですね。
後、このaddlist、list変数は引数として持ってきていませんが、動作するのでしょうか。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#12

投稿記事 by 御津凪 » 17年前

> 実際にどれほどの遅延が発生しましたか?
確認を取ってはいませんが、シューティングゲームなどに使用した場合、
毎フレームにNULLかどうかの確認処理が入るので、沢山弾を出している時に微妙に遅くなるタイミングが変わると思います。
yuuki++ さんのおっしゃる通り、その差は微々たるものですが、
処理の高速化はこのようなところまで気を配らないといけないような気がします。

> この直後にこの構造体にアクセスしてしまったらどうしますか?新たにカウンタ変数を持ちますか?
> リストがダミーのみのときにアクセスしてしまったらどうしますか?
たとえば、ゲームに使用した場合、
struct List{
	struct List *next;
	struct List *prev;
	// 何らかのデータ
};
// 移動処理 list:対象となるリストのデータ(ダミー)
void move(struct List* list){
	struct List* cur = list->next;
	while(cur != list){ // 一周するまで。ダミーしかなかったらループされない
		// cur について処理
		cur = cur->next;
	}
}
このようになり、関数に渡されたリスト構造は、
初期化直後であれば何もせずに返ってきますし、
リストを持っているならダミーを除く全てのリストを処理します。
initList 関数は、ただ前後のポインタのみを初期化しているので、
他の初期化を入れるならここに追記するなり後で初期化するようにすれば良いでしょう。

> 特にポインタ関連のコーディングに関しては保守点検がしやすいことを重視すべきです。

データの最大数が決まっていれば、あらかじめ一度に確保するのも一つの手ですし、
(別の話になりますが)スマートポインタのような参照カウンタを持つのもありだと思います。

ゲームならば、前者の方が多いかと思いますが。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#13

投稿記事 by yuuki++ » 17年前

>わたねるさん
では、例えばさっきのコードに追加でこれをためして見てください。
int main(void)
{
	int i, j;
	char str[64];
	PLIST pList = NULL, p, pNext;
	
	printf("データ数:");
	gets(str);
	i = atoi(str);
	
	for (j = 0; j < i; j++) {  //リスト作成と表示
		p = Add(&pList);
		printf("データ:%d\n", p->i);
	}
	printf("確保\n");
	
	p = pList;
	while (p) {  //リストを使うときの常套手段
		printf("データ:%d\n", p->i);
		p = p->pNext;
	}
	
	p = pList;
	while (p) {  //消すときも同様ですが、pNextを先に取っておきましょう
		pNext = p->pNext;
		Del(&pList, p);
		p = pNext;
	}
	printf("解放\n");  //要素の数だけ数字が表示され、ここまでくれば成功
	
	return 0;
}
かなりやっつけ仕事ですが、単純に
・リストの個数を入力
・リストを作る
・表示と削除
をやっています。

単方向でも似たような処理になります(今回のは単方向でも可)
「途中の要素を消す」とかが必要なときには双方向ですね。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#14

投稿記事 by yuuki++ » 17年前

>御津凪さん
>確認を取ってはいませんが、シューティングゲームなどに使用した場合、
>毎フレームにNULLかどうかの確認処理が入るので、沢山弾を出している時に微妙に遅くなるタイミングが変わると思います。
>yuuki++ さんのおっしゃる通り、その差は微々たるものですが、
>処理の高速化はこのようなところまで気を配らないといけないような気がします。

確認を取っていないのに、なぜそう言えるのですか?
ちなみに実際にやってみましたが、2000発やそこらの弾幕では全然差はありませんでしたよ。

>初期化直後のアクセス云々
これはなるほど、いい方法です。ただし、これは「循環リスト」という線形リストとは別の構造をもっています。

配列やスマートポインタ、ハッシュなどに関してはその通りです。
しかし、これを気にせず行える環境というのは、すなわちリスト構造の処理数云々が気にならない程度になるということです。
コンパイラの最適化もだいぶ賢くなっているので、多少の論理演算ではビクともしません。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#15

投稿記事 by 御津凪 » 17年前

> ちなみに実際にやってみましたが、2000発やそこらの弾幕では全然差はありませんでしたよ。
それは当然だと思います。
移動処理で一度だけしかその差となる処理を行っていないのですから。

一度に2000発の弾を出したり消したりした時に遅延が起こるのではないでしょうか?
(起こるかどうかはPC環境にもよりますが)
単純に考えれば2000回の判定処理が行われると思います。
(全消しなどの場合は専用の関数を用意すれば問題ないですが)

> ただし、これは「循環リスト」という線形リストとは別の構造をもっています。
循環リスト構造を使った線形リストの処理と思えばいいのではないでしょうか。
(いい加減かもしれませんが)

> コンパイラの最適化もだいぶ賢くなっているので、多少の論理演算ではビクともしません。
その通りです。
趣味で作るゲームなどはその辺はほとんど気にしなくてもいいのですが、
私はゲームプログラマ(ポータブル系)である以上、どうしても気になってしまうのです。

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#16

投稿記事 by わたねる » 17年前

>>yuuki++さん
初歩的な質問で申し訳ないのですが、(typedefに慣れていないからなのか?)

typedef struct LIST {
struct LIST *pPrev, *pNext; //前と次の自己参照
int i;
} LIST, *PLIST;
LIST , *PLISTと、2つつなげて宣言?(意味が良く分かっていません

main関数の
PLIST pList = NULL, p, pNext;

add関数の
PLIST pcur = *pList; //カレントポジション

について、何をやっているのかいまいち分からないので、ここを詳しく説明お願いします。。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#17

投稿記事 by 御津凪 » 17年前

> LIST , *PLISTと、2つつなげて宣言?(意味が良く分かっていません
これは、 struct LIST という構造体の名前を別名で扱えるようにするものです。

前者の LIST は struct LIST の別名で、
*PLIST は struct LIST* の別名です。

これにより、いちいち struct を前につけなくても使用することが出来るようになります。
つまり、
PLIST pList = NULL, p, pNext;
は、別名で行わないようにすると、
struct LIST *pList = NULL, *p, *pNext;
となります。

後の説明は yuuki++ さんに任せます。(コードを良く見ていないので…)

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#18

投稿記事 by わたねる » 17年前

なるほど、LIST,*PLISTとすると、2タイプ宣言できるんですね。また一つ知識が増えました。
ただ、add関数の
PLIST pcur = *pList; //カレントポジション
の部分は理解できましたが、


struct LIST *pList = NULL, *p, *pNext;


のような命令は初めて見ました。
例えば
struct decoy List = {5 , "言葉" , 30.5};
のように{}で結ぶような使い方は分かるのですが・・・。
これは何を意味しているのでしょうか。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#19

投稿記事 by 御津凪 » 17年前

> struct LIST *pList = NULL, *p, *pNext;
これは、
typedef struct LIST{
} LIST,*PLIST;
と同じように、一行で変数を複数宣言する記述です。
よく見ると分かるとおり、
pList には初期値(NULL)を、それ以外(p,pNext)の変数はそのままの状態で定義しています。
つまり、
int a,b,c,d,e,f,g,h,i,j,k,l,m,n;
こういうことも可能です。
ただし、ポインタ型の変数を複数定義する場合は、
int *a,*b,*c,*d,*e,*f,*g,*h,*i,*j,*k,*l,*m,*n;
と、変数の前に"*"をつけなければならない決まりのため、記述が面倒です。
(場合によっては見づらい)

この時に別名を定義しておけば見やすくなりますね。
typedef int *PINT; // int *型を PINT として定義
PINT a,b,c,d,e,f,g,h,i,j,k,l,m,n;
このように。

> struct decoy List = {5 , "言葉" , 30.5};
> のように{}で結ぶような使い方は分かるのですが・・・。
> これは何を意味しているのでしょうか。
{}で結ぶ使い方が出来るのは、配列を初期値付きで定義した時や、
構造体を初期値付きで定義する時です。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#20

投稿記事 by yuuki++ » 17年前

外出していました笑

>御津凪さん
>移動処理で一度だけしかその差となる処理を行っていないのですから。
>一度に2000発の弾を出したり消したりした時に遅延が起こるのではないでしょうか?
>(起こるかどうかはPC環境にもよりますが)
>単純に考えれば2000回の判定処理が行われると思います。
>(全消しなどの場合は専用の関数を用意すれば問題ないですが)
確かに実験の仕方がまずかったですね。しかしこれは、どんな構造のリストでも遅延が生じます。
これは判定の問題ではなく、動的メモリ確保によるボトルネックの問題です。
試しに、同時に2000発発射してみました。実際にやってみると分かりますが、遅延が生じるのは「メモリ確保」です。ボトルネックはここです。

>循環リスト構造を使った線形リストの処理と思えばいいのではないでしょうか。
自分で言っておきながら申し訳ないですが、この辺の定義は重要じゃなかったですね笑
ただ、入っているアドレスにNULLがあるかないかでこれらの違いはありますし、当然処理も異なります(が、これは些細なこと)

>私はゲームプログラマ(ポータブル系)である以上、どうしても気になってしまうのです。
商業ですか?だったらなおさら、どこがボトルネックになっているのかを見極めるのが必須なのでは?
企業では分業が基本だと思いますが、実験と保守点検は特に重視すべきでは。

わたねるさんへのレスも分けて書きますね。

box

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#21

投稿記事 by box » 17年前

今回の場合、双方向リスト構造を採用する必然性はどのあたりにありますか?

アプリケーションで、リスト構造を前へ前へとさかのぼっていく
機能が必要なのですか?
だとすれば双方向リスト構造を採用する意味は大いにあると思います。

そういう機能が必要ないのであれば、双方向リスト構造を採用すると
ポインターの張り替えの手間がかかります。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#22

投稿記事 by yuuki++ » 17年前

>わたねるさん
コードの分かりにくさに関しては謝らなければなりません笑
手っ取り早く仕上げたので説明なしにtypedefとかつかってしまいました・・・

add関数についてですが(というか全体に渡って)pListというものはリストの先頭を表しています。
addの中のpcurというのは最後尾を見つけるためにリストの先頭から順番にアドレスを入れていくものです。
最後尾を保存しておくようにしておけば、この変数もその後のwhileもいらなくなります。
if (pcur) {  //この時点でpcurにはpList(先頭)が入っています。
		i = 1;
		while(pcur->pNext) {  //pcurの次が無くなる(NULLになる)までループして
			pcur = pcur->pNext;
			i++;
		}
		pcur->pNext = p;  //最後尾になったら、その次に「新しく作った構造体のアドレス」を入れます。
	} else {  //もし先頭が無かったら
		*pList = p; //新しい奴を先頭にします。
	}

	p->pPrev = pcur;  //pcurは最後尾(なければNULL)
	p->pNext = NULL;  //今回は最後尾に追加するのでここは必ずNULLです
	p->i = i;
	return p; //アドレスを返します(動的確保だから可能。普通の変数ではできませんね)。
}
ばーっと書きましたが、この辺はリスト構造を扱う上での定石といった感じですね。
御津凪さんのコードも基本的には同じで、判定の仕方が異なるだけなので、リスト構造そのものの扱いについては結果的に同じことをしています。

typedefについては、別に使わなくてもいいんです汗
私がstructを書きたくないだけだったので・・・typedefや宣言についても詳しく触れますか?

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#23

投稿記事 by yuuki++ » 17年前

>boxさん
その通りですね。
そういえばいつの間にか双方向限定になってしまっていました。
詳しい仕様を聞いていないのに決め付けるのは良くなかったですね・・・

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#24

投稿記事 by 御津凪 » 17年前

> yuuki++ さん
リストへの追加に毎度メモリ確保をするならばそこがボトルネックでしょう。
私は確かにメモリ確保については書いてはいなかったのですが、考えていなかったわけではありません。

あらかじめ沢山のデータ分のメモリを確保して、
未使用リストと使用中リストを用意します。
(確保したデータをあらかじめ未使用リストに追加しておく)

使用するときに未使用リストからデータを取り出し、
使わなくなったら未使用リストに戻す、といった処理を行えば、
使用中のメモリ確保は一切なくなります。

ただし、このままでは固定サイズのため、いっぱいまで使った時、未使用リストから取れなくなります。
これをどうするかとかを書いていくと、どんどん長くなってしまいます(&話がそれる)ので割愛します。
コードも複雑化していきますし。
すでにこの時点でコードは多少複雑になっているはずです。
(C++のクラスを使用したとしても)

> わたねるさん

始めに提示してもらったように、住所録を追加する程度の処理なら、
今まで書いていた双方向リストは使わなくても問題ありません。

事実、 box さんの言う通り、単方向リストでも、
リストを操作する処理を書くことはできます。

私たちはおそらく「住所録」という、データの追加だけでなく、
ソートや入れ替え、挿入や削除など、
リストを容易に操作することを見据えた上で、
双方向リストについて書いてきたのだと思います。

わたねるさんはポインタと構造体の理解のための
「住所録」を作ろうとしていたのでしたね。

ポインタについて理解をするなら、
No:21359 の yuuki++ さんの書いていただいたコードが一番ではないでしょうか。

単方向リストとしてできない(もしくはできるが難しい)主な機能は、
・ソート
・入れ替え

などが挙げられます。
(挿入や任意のデータの削除は先頭から検索すれば処理できます)

box

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#25

投稿記事 by box » 17年前

単方向リスト構造でソートができない(あるいはむずかしい)というのは、
勘違いなさっているようです。

リストに挿入するタイミングで昇順または降順にしておけばよいだけのことです。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#26

投稿記事 by yuuki++ » 17年前

>御津凪さん
そうなんですよ。
それで、今の話は構造の複雑化ではなく「毎回メモリ確保する上で、判定部分の違いによる遅延」でしたね。
これまでの簡単な実験結果から、速度に影響する部分は今回の場合まずメモリ確保が挙げられます。
またゲームに関して言えば、ここを解消したとしてもおそらく次に注意すべきは画像描画でしょうね。
論理演算とif文の判定が影響する前に、それほどの弾を出したらグラフィックが先に影響するのです。
これについては、1発の弾に対して200~2000個の画像を描画するという簡単な実験を行いましたが、やはり思いっきり処理落ちします。
ソースの各部で行っている2^15~2^16回ほどの判定処理よりもずっと重いですね(グラボの性能のせいでもありますが)。


単方向リストの「挿入」については説明不足でした・・・
なぜか削除の話ばっかりしていますね汗

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#27

投稿記事 by 御津凪 » 17年前

> リストに挿入するタイミングで昇順または降順にしておけばよいだけのことです。

そうでした…。(汗
挿入のタイミングを忘れていましたね。
挿入時点でソートされているようにしておけば、
基本並べ替える必要はありませんし。

> yuuki++ さん
一発の弾にどれだけの画像を使うんだというのは置いといて。
DirectXならば、全ての弾を書き込んだテクスチャ画像を用意して(デバイスへの登録回数を抑えるため)、
頂点バッファとインデックスバッファを使用して描画命令の呼び出しを一回に抑えれば、
処理落ちは最小限に抑えられるはずです。
(DXライブラリは使ったことが無いので、そちらの方での高速化はわかりません)

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#28

投稿記事 by yuuki++ » 17年前

>御津凪さん
そういうことではないですよ笑
「何をループするか」ということで描画をループしたのです。
弾の画像云々や描画に関する最適化は「この話題では」まったく無関係ですよ。
何度も言いますが、話の本筋は「毎回メモリ確保する上で、判定部分の違いによる遅延」です。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#29

投稿記事 by 御津凪 » 17年前

求めていた回答ではありませんでしたね。すいませんでした。

> 何度も言いますが、話の本筋は「毎回メモリ確保する上で、判定部分の違いによる遅延」です。
では、例を「住所録」に変えてみましょう。
たとえば、役所のように万単位のデータが存在するとします。
この沢山のデータから任意のデータを1個ずつ削除する時、
全て削除し終えた時の処理時間が、
ダミーが存在するかしないかで判定部分の違いによる差が出るかと思います。

今までもそうでしたが実験できる環境にいないので、
確証はありませんが、まず差は出ると思います。

この差を気にする必要があるのかといわれれば無いかもしれませんが。

(ゲームでも)速度を気にしないならダミーは無くても良いです。
しかし、微々たる物であっても判定部分の違いで速度が変わるのは事実です。
(ちなみに、if文は論理演算より遅いはずです)

ところで、「毎回メモリ確保する上で」というのは今回の話に必要でしょうか?
追加時に動的にメモリ確保する必然性が無ければ、事前にバッファとして確保しておけば、
少なくともリスト操作には影響が少ないですし。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#30

投稿記事 by yuuki++ » 17年前

>御津凪さん
>ダミーが存在するかしないかで判定部分の違いによる差が出るかと思います。
>今までもそうでしたが実験できる環境にいないので、
>確証はありませんが、まず差は出ると思います。
これは当然です。たとえまったく同じアルゴリズムだったとしてもプロセッサの違いで差がでます。
というか、私は差が出ないとまでは言っていません。
どういうスタイルでコーディングするのか、その上で重視すべき点は速度だけではなく、速度遅延のオーダーと他の仕様設計との重みを考察すべきだと思っています。

また、ある現象について論理的結論を下すには、資料収集・実験・整理・報告の繰り返しで、統計データを取る場合は標本数の妥当性について論じますよね。
が、そんなのは公式データ作成におけるプロセスなので無視していいですが、最低限簡単な実験が可能なら実行して結果を考察してから論ずるべきです。
もしくは数値的解析を行ってオーダーを求めるのもいいでしょうね(面倒ですが)

>では、例を「住所録」に変えてみましょう。
>処理時間を優先しなければ(住所録のように)ダミーが無いほうが良いと思います。
う~ん笑
>しかし、ゲームなどで使用するタイプのリストだと、
一応、この発言を受けてベースにしていたつもりでしたが、見当違いでしたね・・・

また
>毎フレームにNULLかどうかの確認処理が入るので
フレーム内でループとかいろいろやってみましたが、よく考えたらこの部分「フレーム毎」なのでさらに微小になりますね。
この「微小」という現実を一体どれほどの精度で取り扱うかというのは仕様次第ですね。
それを踏まえた上で
>最近のマシンでは気になるほどではないと思います。
と発言したのですが、まさかここまで延長するとは思いませんでしたよ笑

>ところで、「毎回メモリ確保する上で」というのは今回の話に必要でしょうか?
これは今の話題に出てきているリスト構造を指した言葉です。上のほうのレスではリスト構造のコードは2つしか出てきていませんね。
そして今はそれらについて話をしていますね。
>追加時に動的にメモリ確保する必然性が無ければ、事前にバッファとして確保しておけば、
話題には上がっていましたが、本格的にこれを盛り込んで話を拡大する必要があるのですか?
バッファの確保がより高速なのは普通に考えればほぼ自明ですけど。

さらに言ってしまうと(元も子もないですが笑)、仕様の確定していない対象について極小レベルの速度差について論ずることに何か狙いがあるのでしょうか?
私はリスト構造の(とりあえずの)ソースを提示し、(御津凪さんのソースをあまり見ていなかったので)「ダミーなしのやり方です」と事実に即し発言しました。
それについて処理速度について言及されたので、とりあえず測定結果が気になったわけですが、私自身あまり重要視していなかったので「気にならない」というスタンスでいましたが。
もちろんあのソースについて言えば、あれは「とりあえず作ったもの」ですので、私自身が何の最適化も考えないわけではないですよ笑
安定したコードをとりあえず作って、最適化の段階で循環リストに落ち着くかも知れません。
あるいは別の形に発展していくかもしれません。
という見解ですが、もしかしてこの場で最善・最速のコードを生み出す必要がありましたか?

通りすがりの者

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#31

投稿記事 by 通りすがりの者 » 17年前

このスレッドは「住所録をリスト構造で実装する」件についてのものです。

ゲームプログラムの作り方は、この際どうでもいい話。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#32

投稿記事 by 御津凪 » 17年前

> もしかしてこの場で最善・最速のコードを生み出す必要がありましたか?
はっきりと言ってしまえば、必要ありません。

> ダミーはあっても無くてもこのリスト構造は作れます。
> しかし、ゲームなどで使用するタイプのリストだと、
> ダミーを用意したほうが早くなります。
yuuki++ さんに対してのこの発言は頭の片隅に覚えておく程度に捉えてほしかったのですが。
(それ以降の発言も同意義です)
まあ、そういう風に書いていなかった自分が一番悪いのですが…。

> ゲームプログラムの作り方は、この際どうでもいい話。
その通りです。
脱線してすみませんでした。

yuuki++

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#33

投稿記事 by yuuki++ » 17年前

>御津凪さん
>頭の片隅に覚えておく程度に捉えてほしかったのですが。
忠告、ということですか・・・
私は事実に即して発言してきたまでですが、ゲームプログラマーの世界というのは想像以上に厳格な考えがあるのですね。

長くなりました。確かに脱線しすぎなのでこの話は終わらせましょう。

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#34

投稿記事 by わたねる » 17年前

>> struct LIST *pList = NULL, *p, *pNext;
>これは、

>typedef struct LIST{
>} LIST,*PLIST;

>と同じように、一行で変数を複数宣言する記述です。
>よく見ると分かるとおり、
>pList には初期値(NULL)を、それ以外(p,pNext)の変数はそのままの状態で定義しています。

御津凪さんのこの説明なんですが、理解しきれていません・・・。
構造体についての知識が足りないからなのでしょうか。
struct List *pListで、List構造体から*pList変数を生み出した(上手い表現が出来ない)というところまでは分かりましたが、
やはり、{NULL , *p , *pNext}と、括弧でつながっていないことが気になり、*pList変数に対して何を定義し、何を代入しているのか良く分かりかねます・・・。
面倒でなければ、もう少し細かい説明をお願いします・・。

わたねる

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#35

投稿記事 by わたねる » 17年前

そして、単方向リストで実現するべきか、双方向リストで実現するべきか、についても混乱しています。
一応単方向リストで作ったことがあるのですが、「削除」で手詰まりを起こしてしまいました。
お暇な方がいらっしゃれば、ソースをチェックしていただくと嬉しいです。

cppファイルを貼り付けておきます。

御津凪

Re:自己参照構造体(リスト構造)を使用した住所録の作成

#36

投稿記事 by 御津凪 » 17年前

struct LIST *pList = NULL, *p, *pNext;
これは、
struct LIST *pList = NULL;
struct LIST *p;
struct LIST *pNext;
と同じです。
typedef struct LIST{ 
} LIST,*PLIST;
これも、
typedef struct LIST{ 
};
typedef struct LIST LIST;
typedef struct LIST *PLIST;
と同じです。
(こっちの方で書いたほうが分かりやすかったですね^^;)
括弧でつなぐのは変数の値を一度に指定する時です。
変数を一度に定義するには使いません。


あと、添付されたソースを拝見しました。

さくっと読んだ限りですが…。

・2回実行されるとというのは、直前に似た出力(85行目)があるからではないでしょうか。

・データの最後尾のデータを選んだときの部分では、現在では、先頭から次のポインタを NULL にしてしまっています。
 それと、条件部分の delete_number +1 は delete_number -1 ではないでしょうか。

・次の次のデータのポインタを指定するのは、
[0]->[1]->[2]->[3]
(1が削除するデータとして)
このとき、1の前にあるデータ(0)の指す次のデータを、「次の次(2)」としているからです。
これをj実行すると、
[0]->[2]->[3]
となります。

今回の例では、追加ごとにデータ領域を確保しているので、アドレスが連続しないことがあります。
なので、(prev->next_pointa)+2 ではなく、
prev->next_pointa->next_pointa と表記したほうが安全だと思います。

むしろ、"(prev->next_pointa)+2"では希望通りの動作をしません。
これだと、「prev の指すポインタの二つ先(アドレス上)のポインタ」となり、
多分「次の次の次」になっているような…。

chunezu

手も足も出ません

#37

投稿記事 by chunezu » 17年前

龍陣録の弾幕登録の所を見よう見まねでやっています。
ただ、これでは何も出てこなく、もう如何してイイかさっぱり分かりません。

これのpattern1,pattern2がちゃんと出て来る様にするにはどうしたらいいでしょうか?

 ソース nz は自機の構造体です。
//空いている敵番号を検索
int enemy_num_serch(){
    for(int i=0;i<=100;i++){//フラグのたって無いenemyを探す
        if(t.flag==0){
            return i;//使用可能番号を返す
        }
    }
    return -1;//全部埋まっていたらエラーを返す
}

//空いている弾を探す
int shot_serch(int n){
	int i;
	for(i=0;i<=200;i++){
		if(t[n].shot.flag==0){
			return i;
		}
	}
	return -1;
}

void enemyE(){
	int n;
		if((n=enemy_num_serch())!=-1){
			if(counter%60==0){
					t[n].count = 0;
					t[n].flag  = 1;
					t[n].x     = GetRand(200)+220;
					t[n].y     = GetRand(40)+420;
					t[n].px    = nz.x;
					t[n].py    = nz.y;
		}
	}
}

void pattern1(int n){
	int k;
		if(t.flag>=1){
			int aqaqa=t.count++;
			if((k=shot_serch(n))!=-1){
				if( aqaqa>=0 && aqaqa<=20 && aqaqa%3==0 ){
					t[n].shot[k].x    = t[n].x;
					t[n].shot[k].y    = t[n].y;
					t[n].shot[k].size = 8;
					t[n].shot[k].flag = 1;
					t[n].shot[k].spd  = 6;
					t[n].shot[k].knd  = 0;
					t[n].shot[k].angle = atan2( t[n].py - t[n].y , t[n].px - t[n].x );
				}
			}
		}
}

void pattern2(int n){
	int k;
		if(t.flag>=1){
			int aqaqa=t.count++;
			if((k=shot_serch(n))!=-1){
				if( aqaqa>=0 && aqaqa<=20 && aqaqa%3==0 ){
					t[n].shot[k].x    = t[n].x;
					t[n].shot[k].y    = t[n].y;
					t[n].shot[k].size = 8;
					t[n].shot[k].flag = 1;
					t[n].shot[k].spd  = 6;
					t[n].shot[k].knd  = 1;
					t[n].shot[k].angle = 90;
				}
			}
		}
}

void calc(){
	for(i=0;i<=100;i++){
		if(t.flag>=1){	if(t.count>=30){ t.flag=2; }
			for(j=0;j<=200;j++){
				if(t.shot[j].flag==1){
					t[i].shot[j].x = t[i].shot[j].x + cos(t[i].shot[j].angle) * t[i].shot[j].spd;
					t[i].shot[j].y = t[i].shot[j].y + sin(t[i].shot[j].angle) * t[i].shot[j].spd;
					if(t[i].shot[j].y<=-20){ t[i].shot[j].flag=0; }
				}
			}
		}
	}
}

void (*pattern[2])(int)={
	pattern1,
	pattern2,
};

void shot_main(){
	int i;
	for(i=0;i<100;i++){
		for(j=0;j<200;j++){//弾幕データ計算
			//フラグが立っていて、設定した種類が間違っていなければ(オーバーフロー対策)
			if(t[i].flag!=0){
				calc();//.kndの弾幕計算関数を呼ぶ関数ポインタ
				pattern[t[i].shot[j].knd](i);//i番目の弾幕を計算
			}
		}
	}
}



丸投げな質問ですいません。
どなたか回答お願いいたします。

array

Re:手も足も出ません

#38

投稿記事 by array » 17年前

多分きちんと書いてあるとは思いますが、弾を描画してあげないと、何も出てこないと思います。

龍神録ではgraph.cppで描画していたと思いますが、弾の描画関数も記載しておいた方がいいです。

結局 描画が間違っていました。と、なり兼ねません。

管理人

Re:手も足も出ません

#39

投稿記事 by 管理人 » 17年前

1から自分で作っていらっしゃるのでしょうか?
もしそれならプロジェクトのあるフォルダごと圧縮してどこかにUPしたほうが
解決が早いかもしれません。

もし手も足も出ないようなら、まずはコピペから勉強を始めるとか、
小規模なシューティングを自分で作ることから始めるとかしてみてはどうでしょうか。

それでも難しければ落ち物ゲーム(リンゴを上からふらせてカゴに入れるゲーム)とかまず作ってみてはどうでしょう。

chunezu

Re:手も足も出ません

#40

投稿記事 by chunezu » 17年前

ご回答が早くて助かります。

arrayさん
描画関数が関係ないとは言い切れませんからね。分かりずらい質問文でした・・・

管理人さん
たしかにそのほうが良さげですね。
一から作っているので、汚いスースだと思いますがupします。

アドレス
http://island.geocities.jp/nznz3102/DP.zip

管理人

Re:手も足も出ません

#41

投稿記事 by 管理人 » 17年前

まだざっとしか見てないのですが、
恐らく敵関係の情報を持っているであろうとおもわれるt変数のflagはどこでオンになりますか?
enemyE()だと思いますが、これがどこからも呼ばれていないようです。
敵が登録されないので弾も登録されないのではないでしょうか。
また、色々と問題点が多いように思います。
まず、
for(i=0;i<=100;i++)
だと、ループは101回です。
0~10を数えてみて下さい。
0,1,2,3,4,5,6,7,8,9,10
は11個ありますね。100個しか用意していないのなら
for(i=0;i<100;i++)
このようにループしないといけません。
また
for(i=0;i<=100;i++){
	for(j=0;j<=200;j++){
		if(t.shot[j].flag==1){
			
	a.x = nz.x - t.shot[j].x;
	a.y = nz.y - t.shot[j].y;
	a.r = nz.size + t.shot[j].size;

	if( a.x * a.x + a.y * a.y < a.r * a.r ){
		StopSoundMem(Splaying);
		musicTitle();
		Mainflag=0;

		for(i=0;i<=100;i++){	//弾幕の全滅アクション
			if(t.flag>=1){	t.flag=0;
				for(j=0;j<=200;j++){
					if(t.shot[j].flag==1){
								t.shot[j].flag=0;
 
 
このようになっていますが、恐らく敵と弾が全部消えればいいんでしょうけど、
ループの中に同じ変数を用いたループはさけたほうがいいのではないでしょうか。
敵や弾の削除関数を作ってやり、それを呼んでみてはどうでしょう。

また、字下げはきっちりやらないとバグの元になるので、ちゃんとやった方がいいと思います。
そしてtなどローカル変数で使い易い変数をグローバル変数にするのもバグの元になると思います。

閉鎖

“C言語何でも質問掲示板” へ戻る