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

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

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 課題が全く分かりません...教えてください

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

#10

by みけCAT » 5年前

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");
  }
}

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

#9

by MEA » 5年前

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

コード: 

#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");
}
}

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

#8

by みけCAT » 5年前

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

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

コード: 

  //点数読み込み
  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;
の部分をループさせればできるはずなので、引き続き考えてみてください。

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

#7

by MEA » 5年前

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

コード: 

#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");
}
}

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

#6

by みけCAT » 5年前

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

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

#5

by MEA » 5年前

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

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

#4

by みけCAT » 5年前

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

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

#3

by MEA » 5年前

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

■ー＞■ー＞■

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

#2

by みけCAT » 5年前

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

●入力の読み込み方

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
リンクリストへの要素の追加
linked-list-20200619.png (11.75 KiB) 閲覧数: 8095 回
「追加したい位置の次のノード」はリストの末尾への追加なら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)が先に来ているので、
単純に枝を入力順にリストの先頭に追加してしまうと、
グラフのリンクリスト表現が図のとおりにならなくなってしまいます。
そこで、枝を追加する際はリンクリストを探索し、
ラベルが昇順になる位置に枝を表すノードを追加するようにするといいでしょう。

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

#1

by MEA » 5年前

添付した画像が課題なのですが、いきなり応用的なものを出されて全然分かりません。どなたか教えていただけないでしょうか？
添付ファイル
スクリーンショット 2020-06-19 16.19.06.png
スクリーンショット 2020-06-19 16.18.03.png
スクリーンショット 2020-06-19 16.18.16.png

ページトップ