隣接リストLを作成するプログラムについて

Question

#define N 100　　　　　　　　　　/*　グラフの点の数を最大１００個まで　*/

    struct LIST　　　　　　　　　/*　リストという構造体の宣言　*/
{
    int v_num;　　　　　　　　　/*　点の番号　*/
    struct LIST *next;　　　　　/*　次の構造体を指すポインタ　*/
 };

    struct LIST *vertex[N+1];　　/*　LIST型のポインタ配列の宣言　*/


    int main(void)

{
    struct LIST *tmp;
		
    int number; int degree;
		
    scanf("%d",&number);　　　/*　点数の読み込み　*/
		
    for(int i=1;i<=number;i++){
		
	 vertex[i]=NULL;　　　/*　配列の初期化　*/
		
	 scanf("%d",&degree);　/*　各点の次数の読み込み　*/
		
    for(int j=1;j<=degree;j++){
		
    tmp=(struct LIST*)malloc(sizeof(struct LIST));　/*　領域の確保　*/

	scanf("%d",&(tmp->v_num));　　　　　　　　　/*　隣接点の読み込み　*/

		tmp->next=vertex[i];

		vertex[i]=tmp;
}
}
	
}

freeされてないのも気になるんですが、グラフ理論入門という古本です。コード
はあまりのってないんですがリストや樹形図を勉強したいです。見ても頭にはいってこない構文なので
よくわからないです。読むのを手伝ってほしいです。わかるのは、アロー演算子は、アドレス->構造体の中身をみているってことぐらいです。struct LIST *vertex[N+1];からわかりません。

（本に記載されているソースコードの説明と図を後で追記します。）よろしくお願いします。

　汚い字ですいません

Comments

[episteme]

> 読むのを手伝ってほしいです。

なにすりゃいいですか?

[txty]

わたしもそれ思いました。明日コメントと図を載せるので、うまくいくか分かりませんが、読解してほしいです。図だけでも、わかりそうなのですが、うまく理解できるかわからないので。できれば１文１文とお願いできると幸いです。まあ明日です。

[episteme]

＞できれば１文１文とお願いできると幸いです。

それは「僕の代わりに教本を読んでください」とお願いするに等しくはないですか?　(やだよそんなの)

[txty]

そうですか。それなら受けたことないけど学校の先生みたく一方的に勝手に解釈つけてくれるのはどうでしょうか。とりあえず図をのせます。字は汚いですけど。つながっていくというイメージがわかりません。

[txty]

struct LIST *vertex[N+1];　　/*　LIST型のポインタ配列の宣言　*/は図でいうｖ１、ｖ２、ｖ３、ｖ４が１０１個あるということでよろしいでしょうか。個人的にはstruct LIST *vertex[N]でよい気がしますがなぜN+１なんでしょうか。

[txty]

struct LIST *tmp;

int number; int degree;
/*scanf("%d",&number);　　　/*　点数の読み込みがわかりません。　*/　int degreeは深さ。*/
がわかりません。

[txty]

tmp=(struct LIST*)malloc(sizeof(struct LIST));　/*　領域の確保　*/

scanf("%d",&(tmp->v_num));　　　　　　　　　/*　隣接点の読み込み　*/

は新しいメモリを確保してかえってきたアドレスから

scanf("%d",&(tmp->v_num));新しいメモリに新しい番号を入力させている。と思う。

その後の tmp->next=vertex[i];

vertex[i]=tmp;はなんでしょうか。

[txty]

epistemeさん、kazuma-sさん、丁寧な回答ありがとうございます。とりあえず、即答を避けて保留させてください。２、３日　あけます。忘れたころにコメントすると思います。

[coco_bauer]

まずは、初心者向けのC言語の本を熟読するのが良いのではないでしょうか？
C言語で書かれたプログラムを読むのに必要なC言語の文法の知識が絶望的に不足しているように思われます。
このロシア語の本を読むのを手伝ってほしいんです。ロシア語の事は何も知らないんですけど、、、というような理不尽な要求のたぐいではないですか？

[txty]

（リストと木構造を理解したいのですが）、それ以前だとすると、（初心者向けだとすると）何をすれば（どんな本を読めば）（変な本にあたると困るため）いいでしょうか。手元で役に立ってるのはｃプログラミング、株式会社インフォテックサーブと職業プログラマー入門レッドフォックス株式会社ぐらいですが、リストや木構造は早かったでしょうか。

[txty]

隣接じゃなくて、普通のリストを選ぶべきでした。しまえるデータがint 型であったので気にいったのですが。あと、ベストアンサーはずすのはどうすればよかったのですか。（ミスしてたら嫌なので）まだ聞きたいです。たしかに、読めても書くのは無理かもしれないです。

Answer 1

struct LIST vertex[N+1];　　/　LIST型のポインタ配列の宣言　*/
は図でいうｖ１、ｖ２、ｖ３、ｖ４が１０１個あるということでよろしいでしょうか。

YES. vertex[0]～vertex[100] を用意しています。

個人的にはstruct LIST *vertex[N]でよい気がしますがなぜN+１なんでしょうか。

vertex[0]を使っていないから。

int number; int degree;
scanf("%d",&number);　　　
点数の読み込みがわかりません。

なにがわかりませんか?

tmp=(struct LIST*)malloc(sizeof(struct LIST));　/*　領域の確保　/
scanf("%d",&(tmp->v_num));　　　　　　　　　/　隣接点の読み込み　*/
は新しいメモリを確保してかえってきたアドレスから
scanf("%d",&(tmp->v_num));新しいメモリに新しい番号を入力させている。と思う。

YES. struct LIST 領域を確保し、そのメンバ v_num に入力値をセットしています。

その後の
tmp->next=vertex[i];
vertex[i]=tmp;
はなんでしょうか。

あなたの描いた絵のとおり、 struct LIST を数珠繋ぎにしています。

Comments

[txty]

struct LIST *vertex[N+1];　　/*　LIST型のポインタ配列の宣言　*/がそもそもわからなかったのですが　struct LIST *vertex　ポインタを[N＋１]個用意したであってるでしょうか。

次に、scanf（"%d",&number）;でソースコードの結果から、ポインタ配列の個数を用意してるようですが、ソースコードを見た感じではそのような印象をうけなかったのですが、
　このnumberは、もしかして０？,1？から100まで限定で、使う数を限定しているということであってるでしょうか。（今、おもったんですが。）、後０を使わなかったのはなぜでしょうか。

その中でdegree深さの数だけメモリをmallocで用意していて、

残りのtmp->nextはその時点の構造体のポインタをあらわしているとおもいますが、

vertex[i]；と　vertex[i]=tmpが謎です。
つなぐは、なぜこうなるのかよろしくお願いします。間違っている点があったら、ご指摘ください。なんか読みずらくてすいません。

[episteme]

> struct LIST *vertex　ポインタを[N＋１]個用意したであってるでしょうか。
ok.

> scanf（"%d",&number）;でソースコードの結果から、ポインタ配列の個数を用意してるよう
> ですが、ソースコードを見た感じではそのような印象をうけなかったのですが、
number個のポインタ: vertex[1]～vertex[number] を「使用する」です。

> 後０を使わなかったのはなぜでしょうか。
知りません。使いたくなかったからでしょう。

> つなぐは、なぜこうなるのかよろしくお願いします。
わからないにもかかわらず、その絵が描けたのはなぜですか? 理解できません。
tmp->next = vertex[i] により、tmpの次はvertex[i]が指しているLIST
vertex[i] = tmp により、vertex[i]　にはtmpが指しているLIST となります。
なので　たとえば 1 2 3 と入力されれば vertex[i]から順番に 3→2→1 とつながります。

> なんか読みずらくてすいません。
そう思うなら修正しましょう。

[txty]

（絵は本に載ってました。文字が小さかったので自分で同じ絵を書きました。）

tmp->nextはアドレスだから、struct LIST *vertex[i]のアドレスはvertex[i]でしょうか。
（人によって違うとおもいますが、アドレスをどうやって覚えてるのでしょうか）
図によると
vertex[i]は縦列のようですが自分は図を見て右に繋ぎたいです。ソースコードをみるとvertex[i]を渡したことでつなげている気もします。どちらの認識が正しいのでしょうか。

struct LIST * vertex[i]について、わたしは間違えているかもしれません。この文を真に受けないでください。

[episteme]

> 自分は図を見て右に繋ぎたいです。

tmp->next=vertex[i];
vertex[i]=tmp;

これで右に繋いでます。

[txty]

すいません右に繋いでるという認識しかできませんでした。もうひとつ尋ねますが、図でいう　v1,v2...はどうやってつくったのでしょうか。

[txty]

聞きすぎました。でも追記はお願いしたいです。

[episteme]

何を問うているのかわかりません。

[txty]

struct LIST *vertex[N+1];　　/*　LIST型のポインタ配列の宣言　*/は、縦列ですか。横列ですか。

[episteme]

↑あなたの描いた絵のとおりですが。

[txty]

絵が理解できなくて、ちょっと混乱しています。実際のポインタ配列　vertex[N]の記述が離れているのでどっちにも見えます。しいて言えば縦列のように見えますが。どうなのでしょう。

[episteme]

V1, V2, ... Vn を vertex[1], vertex[2], ... vertex[n] と読み替えるだけちゃいますか?

[txty]

そうだと思います（自分の認識が間違えてるかもしれませんが。追記：念のため）図でいう縦列でしたか。これで大体全体像が把握できました。後は、ばらして分析してみます。有り難うございます。長らく失礼しました。

Answer 2

インデントがグチャグチャで、コードが読みにくくて仕方ありません。
読み込んだデータを表示しないと正しいどうか確かめられません。
次のように書いてみました。

#include <stdio.h>   // scanf, printf
#include <stdlib.h>  // malloc

#define N 100

struct LIST {
	int v_num;
	struct LIST *next;
};

struct LIST *vertex[N + 1];

int main(void)
{
	struct LIST *tmp;
	int number;
	int degree;

	scanf("%d", &number);
	for (int i = 1; i <= number; i++) {
		vertex[i] = NULL;
		scanf("%d", &degree);
		for (int j = 1; j <= degree; j++) {
			tmp = (struct LIST *) malloc(sizeof(struct LIST));
			scanf("%d", &(tmp->v_num));
			tmp->next = vertex[i];
			vertex[i] = tmp;
		}
	}

	for (int i = 1; i <= number; i++) {
		for (tmp = vertex[i]; tmp != NULL; tmp = tmp->next)
			printf(" %d", tmp->v_num);
		printf("\n");
	}
}

実行例

3
2 11 22
4 33 44 55 66
1 77      (ここまでが入力)
 22 11    (ここからは出力)
 66 55 44 33
 77

Comments

[txty]

ありがとうございます。インデントの整形を理解してないのですが、スペースで４つでしょうか。後、printfを入れたかったのですが、どこにどうやっていれればいけないのかわからなくて明日もコードいれられるか自信がないです。ちょっと入力練習しておきます。

[txty]

```plain text
2
4 55 66 77 88
2 55 88
出力 88 77 66 55
88 55 使い方だけ覚えたのでメモしておく
```

[txty]

調べた結果、自分は、ネスト構造は半角スペース２字、処理改行は半角スペース４字にしようと思います。（間違えたらすいません。）printfありがとうございました！