課題が全く分かりません...教えてください

[MEA]

添付した画像が課題なのですが、いきなり応用的なものを出されて全然分かりません。どなたか教えていただけないでしょうか？

[みけCAT]

ヒントを出すので、これで書けるところまで書いてみてください。

●入力の読み込み方

scanf()関数を用いることで、入力を読み込むことができます。
書式%dを用いると整数を、%(最大バイト数)sを用いると空白を含まない文字列を読み込むことができます。
scanf()は成功すると読み込んだデータ数、失敗すると-1を返すので、
これを用いて読み込みが成功したかをチェックすることができます。

例

コード:

#include <stdio.h>

int main(void) {
	int ivalue;
	char cvalue1[4], cvalue2[4], cvalue3[4];
	// 整数を読み込む
	if (scanf("%d", &ivalue) != 1) return 1;
	// 文字列を読み込む (最大バイト数は終端のNUL文字の分バッファサイズより1少ない)
	if (scanf("%3s", cvalue1) != 1) return 1;
	// 書式は複数指定できる
	// ここで紹介する書式では、読み込みは空白で区切られる
	// 読み込み先は書式の数指定しないといけない
	if (scanf("%3s%3s", cvalue2, cvalue3) != 2) return 1;

	// 読み込んだデータを出力してみる
	printf("%d\n", ivalue);
	printf("%c\n", cvalue1[0]);
	printf("%c %c\n", cvalue2[0], cvalue3[0]);

	return 0;
}

入力例

コード:

42
A
B C

出力例

コード:

42
A
B C

●リンクリストへの要素の追加の仕方

1. 新しいノードを用意し、値を設定する
2. 新しいノードのnextが、追加したい位置の次のノードを指すようにする
3. 追加したい位置の前のノードのnextが、新しいノードを指すようにする

リンクリストへの要素の追加

linked-list-20200619.png (11.75 KiB) 閲覧数: 6461 回

「追加したい位置の次のノード」はリストの末尾への追加ならNULL、
「追加したい位置の前のノードのnext」はリストの先頭への追加なら
リストを指すポインタ(ここではgrp.vset[​i].link)になります。

「新しいノードを用意」するには、
A. stdlib.hをincludeし、malloc()を用いる
B. あらかじめ十分な数(例えばVMAX * VMAX)のノード配列を用意し、そこから取る
という方法があります。

●枝の追加のポイント

今回は無向グラフのようなので、
例えば「A F」という点ラベル対があったら、
A→Fの枝だけでなくF→Aの枝も追加しないといけません。
ただし、今回の入力例にはありませんが、
例えば「A A」という点ラベル対(自己ループ)については、
A→Aの枝を二重に追加してしまわないように注意するべきでしょう。

今回の入力例では、例えばB→Eの枝(B E)よりB→Aの枝(A B)が先に来ているので、
単純に枝を入力順にリストの先頭に追加してしまうと、
グラフのリンクリスト表現が図のとおりにならなくなってしまいます。
そこで、枝を追加する際はリンクリストを探索し、
ラベルが昇順になる位置に枝を表すノードを追加するようにするといいでしょう。

[MEA]

考えてみましたが、下の図のようなリンクリストしか作ったことがなため、複数個のノードをつなげる今回のパターンは全く想像がつきませんでした。。。

■ー＞■ー＞■

[みけCAT]

まずはリンクリストのことはおいといて、点ラベルと点ラベル対の読み込みだけをするプログラムを書いてみましょう。

[MEA]

読み込みは終わったのですが、リンクリストを無向グラフ？にする方法が分かりません。提出期限がもうギリギリなので教えて欲しいです。

[みけCAT]

MEAさんのプログラムをベースにしたいので、読み込みまでのプログラムを貼っていただけますか？

[MEA]

リンクリストや点ラベル対関連のものは全くできてません

コード:

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

#define VMAX 10

struct edge
{
  char label;
  struct edge *next;
};

struct vertex
{
  char label;
  struct edge *link;
};

struct graph
{
  int v,e;
  struct vertex vset[VMAX];
};

int main()
{
  struct graph grp;
  int i,n;
  char c;
  struct edge *head,*p;
  for(i=0;i<VMAX;i++)grp.vset[i].link=NULL;
  //点数読み込み
  grp.v=scanf("%d%*c",&n);
  //点ラベルを読み込み
  for(i=0;i<n;i++){
     scanf("%c%*c",&c);
   }
//枝数読み込み
grp.e=scanf("%d%*c",&n);
//点ラベル対（枝）を読み込み



//グラフの確認
  for(i=0;i<grp.v;i++){
    for(p=grp.vset[i].link; p!=NULL; p=p->next) {
      printf("(%c,%c)\n",grp.vset[i].label,p->label);

  }
}
return 0;

for(i=0;i<grp.v;i++){
  printf("[%c]:",grp.vset[i].label);
  for(p=grp.vset[i].link; p!=NULL; p=p->next){
    printf("%c",p->label);
    if(p->next !=NULL) printf("->");
  }
  printf("\n");
}
}

[みけCAT]

「読み込みは終わった」と言っていたにもかかわらず点ラベル対の読み込みが書かれていないようですが、
詰んだという意味での「終わった」でしょうか？

まずはここまで読み込んだ情報をメモリに保存しましょう。

コード:

  //点数読み込み
  grp.v=scanf("%d%*c",&n);
  // 追加：バッファオーバーラン防止
  if (n > VMAX){
    fputs("too much vertice!\n", stderr);
    return 1;
  }
  grp.v=n; // 追加：読み込んだ点数を保存する
  //点ラベルを読み込み
  for(i=0;i<n;i++){
    scanf("%c%*c",&c);
    grp.vset[i].label=c; // 追加：読み込んだ点ラベルを保存する
  }
  //枝数読み込み
  grp.e=scanf("%d%*c",&n);
  grp.e=n; // 追加：読み込んだ枝数を保存する
  //点ラベル対（枝）を読み込み

点ラベル対の読み込みは自分が提示したサンプルの

コード:

	char cvalue2[4], cvalue3[4];
	// 書式は複数指定できる
	// ここで紹介する書式では、読み込みは空白で区切られる
	// 読み込み先は書式の数指定しないといけない
	if (scanf("%3s%3s", cvalue2, cvalue3) != 2) return 1;

の部分をループさせればできるはずなので、引き続き考えてみてください。

[MEA]

点ラベル対の保存はどこにしたら良いですか？

コード:

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

#define VMAX 10

struct edge
{
  char label;
  struct edge *next;
};

struct vertex
{
  char label;
  struct edge *link;
};

struct graph
{
  int v,e;
  struct vertex vset[VMAX];
};

int main()
{
  struct graph grp;
  int i,n;
  char c1,c2;
  struct edge *head,*p;
  for(i=0;i<VMAX;i++)grp.vset[i].link=NULL;
  //点数読み込み
  grp.v=scanf("%d%*c",&n);
  grp.v=n;
  printf("\n");
  //点ラベルを読み込み
  for(i=0;i<n;i++){
     scanf("%c%*c",&c);
     grp.vset[i].label=c;
   }
   printf("\n");
  //枝数読み込み
  grp.e=scanf("%d%*c",&n);
  grp.e=n;
  printf("\n");
  //点ラベル対（枝）を読み込み
  for(i=0;i<n;i++){
    scanf("%c%*c %c%*c",&c1,&c2);
    grp.vset[i].link=
  }
  



  //グラフの確認
  for(i=0;i<grp.v;i++){
    printf("[%c]:",grp.vset[i].label);
    for(p=grp.vset[i].link; p!=NULL; p=p->next){
      printf("%c",p->label);
      if(p->next !=NULL) printf("->");
    }
    printf("\n");
}
}

[みけCAT]

grp.vset[​i].linkにしたらいいです。

コード:

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

#define VMAX 10

struct edge
{
  char label;
  struct edge *next;
};

struct vertex
{
  char label;
  struct edge *link;
};

struct graph
{
  int v,e;
  struct vertex vset[VMAX];
};

//点対(枝)をグラフに追加する関数
void add(struct vertex* g, char e)
{
  struct edge* nnode;
  //枝の行先を追加する位置を探す
  struct edge** node=&g->link;
  while(*node!=NULL && (*node)->label<e){
    node=&(*node)->next;
  }
  //枝を追加する
  nnode=malloc(sizeof(*nnode)); //新しいノードを用意し、
  if(nnode==NULL){
    perror("malloc");
    exit(1);
  }
  nnode->label=e; //値を設定する
  nnode->next=*node; //新しいノードのnextが、追加したい位置の次のノードを指すようにする
  *node=nnode; //追加したい位置の前のノードのnextが、新しいノードを指すようにする
}

int main()
{
  struct graph grp;
  int i,n;
  char c1,c2;
  struct edge *head,*p;
  for(i=0;i<VMAX;i++)grp.vset[i].link=NULL;
  //点数読み込み
  grp.v=scanf("%d%*c",&n);
  grp.v=n;
  printf("\n");
  //点ラベルを読み込み
  for(i=0;i<n;i++){
    char c; //定義されていなかったので、定義する
    scanf("%c%*c",&c);
    grp.vset[i].label=c;
  }
  printf("\n");
  //枝数読み込み
  grp.e=scanf("%d%*c",&n);
  grp.e=n;
  printf("\n");
  //点ラベル対（枝）を読み込み
  for(i=0;i<n;i++){
    int v1=-1,v2=-1,j;
    scanf("%c%*c %c%*c",&c1,&c2);
    //どの点に枝を追加するかを探す
    for(j=0; j<grp.v; j++){
      if(grp.vset[j].label==c1)v1=j;
      if(grp.vset[j].label==c2)v2=j;
    }
    if(v1<0 || v2<0){
      fputs("invalid edge exists\n", stderr);
      return 1;
    }
    //枝を追加する
    add(&grp.vset[v1],c2);
    add(&grp.vset[v2],c1);
  }
  



  //グラフの確認
  for(i=0;i<grp.v;i++){
    printf("[%c]:",grp.vset[i].label);
    for(p=grp.vset[i].link; p!=NULL; p=p->next){
      printf("%c",p->label);
      if(p->next !=NULL) printf("->");
    }
    printf("\n");
  }
}