課題が全く分かりません...教えてください
Re: 課題が全く分かりません...教えてください
ヒントを出すので、これで書けるところまで書いてみてください。
●入力の読み込み方
scanf()関数を用いることで、入力を読み込むことができます。
書式%dを用いると整数を、%(最大バイト数)sを用いると空白を含まない文字列を読み込むことができます。
scanf()は成功すると読み込んだデータ数、失敗すると-1を返すので、
これを用いて読み込みが成功したかをチェックすることができます。
例
入力例
出力例
●リンクリストへの要素の追加の仕方
1. 新しいノードを用意し、値を設定する
2. 新しいノードのnextが、追加したい位置の次のノードを指すようにする
3. 追加したい位置の前のノードのnextが、新しいノードを指すようにする
「追加したい位置の次のノード」はリストの末尾への追加なら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)が先に来ているので、
単純に枝を入力順にリストの先頭に追加してしまうと、
グラフのリンクリスト表現が図のとおりにならなくなってしまいます。
そこで、枝を追加する際はリンクリストを探索し、
ラベルが昇順になる位置に枝を表すノードを追加するようにするといいでしょう。
●入力の読み込み方
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;
}
1. 新しいノードを用意し、値を設定する
2. 新しいノードのnextが、追加したい位置の次のノードを指すようにする
3. 追加したい位置の前のノードのnextが、新しいノードを指すようにする
「追加したい位置の次のノード」はリストの末尾への追加なら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)が先に来ているので、
単純に枝を入力順にリストの先頭に追加してしまうと、
グラフのリンクリスト表現が図のとおりにならなくなってしまいます。
そこで、枝を追加する際はリンクリストを探索し、
ラベルが昇順になる位置に枝を表すノードを追加するようにするといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 課題が全く分かりません...教えてください
考えてみましたが、下の図のようなリンクリストしか作ったことがなため、複数個のノードをつなげる今回のパターンは全く想像がつきませんでした。。。
■ー>■ー>■
■ー>■ー>■
Re: 課題が全く分かりません...教えてください
まずはリンクリストのことはおいといて、点ラベルと点ラベル対の読み込みだけをするプログラムを書いてみましょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 課題が全く分かりません...教えてください
読み込みは終わったのですが、リンクリストを無向グラフ?にする方法が分かりません。提出期限がもうギリギリなので教えて欲しいです。
Re: 課題が全く分かりません...教えてください
MEAさんのプログラムをベースにしたいので、読み込みまでのプログラムを貼っていただけますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 課題が全く分かりません...教えてください
リンクリストや点ラベル対関連のものは全くできてません
#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: 課題が全く分かりません...教えてください
「読み込みは終わった」と言っていたにもかかわらず点ラベル対の読み込みが書かれていないようですが、
詰んだという意味での「終わった」でしょうか?
まずはここまで読み込んだ情報をメモリに保存しましょう。
点ラベル対の読み込みは自分が提示したサンプルの
の部分をループさせればできるはずなので、引き続き考えてみてください。
詰んだという意味での「終わった」でしょうか?
まずはここまで読み込んだ情報をメモリに保存しましょう。
//点数読み込み
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; // 追加:読み込んだ枝数を保存する
//点ラベル対(枝)を読み込み
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 課題が全く分かりません...教えてください
点ラベル対の保存はどこにしたら良いですか?
#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: 課題が全く分かりません...教えてください
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");
}
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)