プログラマ専用SNS ミクプラ

しりとり，　といっても若干特殊なものになります．
データは次のような形式でcsvになっています．
Name,In,Out
A,a,b
B,a,c
C,a,a
D,a,h
E,b,c
F,b,e
H,b,f
I,c,d
J,c,h
K,d,i
L,e,a
M,f,a
N,g,b
O,f,c
P,h,c
Q,i,a
このようなデータがあった場合に，In,Outの関係からNameによる経路を決定する，というプログラムを作成しています。
例えば，入力として『In:a Out:c』と入れると，結果として，
経路１：A([a→b])
経路2：B-I-K-Q-A([a→c]-[c→d]-[d→i]-[i→a]-[a→b])
経路3:B-I-K-Q-C-A
…
といったように，aから始まりcで終わる経路を全て求めます．
条件として，
1.同じNameを通過しない(× C-C-C-C-…)
2.経路を，経路番号と要素番号で索引出来る状態に格納する．(ex.経路1-1=A 経路2-1=B 経路3-3=K)
3.Nameは最終的に文字列を扱う予定（試験的にアルファベットを用いている）
という条件の下，経路を求めようと思っています。
ポインタを用いたプログラムを作成していたのですが、条件2と条件3が満たせていません。特にポインタを利用すると3がネックになってしまいます。
アルゴリズムの勉強やポインタについての勉強は基礎的な部分まで行いましたが、肝心の自分のプログラムとなると
どのように作成すればよいのか皆目見当つかなくなってしまいます。
どなたか御力添え宜しくお願いします。

まずは途中でも良いので作っているプログラムを見せてください。

質問
『In:a Out:c』で、なぜ、経路１：A([a→b])になるのかわかりません。

>>h2so5様，以下のようになっていますが，基本的に後の事を考えておらず，条件２と条件３
は考慮されていません。

#include <memory.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <iostream>

using namespace std;

//パーツ格納箱の定義
typedef struct {
char partsname;
char fst;
char lst;
} parts;

parts data_table[] = {
{'A', 'a', 'b'},
{'B', 'a', 'c'},
{'C', 'a', 'a'},
{'D', 'a', 'h'},
{'E', 'b', 'c'},
{'F', 'b', 'e'},
{'H', 'b', 'f'},
{'I', 'c', 'd'},
{'J', 'c', 'h'},
{'K', 'd', 'i'},
{'L', 'e', 'a'},
{'M', 'f', 'a'},
{'N', 'g', 'b'},
{'O', 'f', 'c'},
{'P', 'h', 'c'},
{'Q', 'i', 'a'},
{ 0 , 0 , 0 }, // 終了マーク
};
//パーツチェイン格納箱の定義
typedef struct _PartsChain{
struct _PartsChain *next;
parts parts;
}p_c;
//パーツチェインを解放
void ReleasePartsChain(p_c *p)
{
while(p!=NULL){
p_c *n = p->next;
free(p);
p=n;
}
}
//入力からパーツ名を検索
parts *SearchParts(char i_partsname){
for(int i=0;data_table.partsname!=0; ++i){
if(data_table.partsname==i_partsname){
return &data_table;
}
}
}
//始点を指定してパーツを探す
p_c *SearchPartsFromfst(char inp){
p_c *findparts=NULL, *p=NULL;
for(int idx=0;data_table[idx].partsname!=0;++idx){
if(data_table[idx].fst==inp){
if(p==NULL){
p=(p_c*)malloc(sizeof(p_c));
findparts=p;
}
else{
p_c *q=(p_c*)malloc(sizeof(p_c));
p->next=q;
p=q;
}
p->next=NULL;
memcpy(&p->parts,&data_table[idx],sizeof(parts));
}
}
return findparts;
}

//パスを伸ばす
char *StretchPath(char *path,parts parts){
int new_path_length=strlen(path)+2; //NULL含む！！
char *new_path=(char*)malloc(sizeof(char)*new_path_length);
memset(new_path,0,new_path_length);
sprintf_s(new_path,sizeof(char)*new_path_length,"%s%c",path,parts.partsname);
return new_path;
}
//パスを探す
void SearchPath(char *path, char outp){
parts *path_last=SearchParts(path[strlen(path)-1]);
if(path_last->lst==outp){
printf("見つかったパス:[%s]\n",path);
return;
}
p_c *findparts=SearchPartsFromfst(path_last->lst);

for(p_c *p=findparts;p!=NULL;p=p->next){
if(strchr(path,p->parts.partsname)!=NULL){continue;}
char *new_path=StretchPath(path,p->parts);
SearchPath(new_path,outp);
free(new_path);
}
return;
}

//メイン

int main(void){
char argv[100];
cout<<"Input:";
cin>>argv[1];
cout<<"Output:";
cin>>argv[2];

p_c *p,*parts=SearchPartsFromfst(argv[1]);
for(p=parts;p!=NULL;p=p->next){
char path[2];
sprintf_s(path,sizeof(path),"%c",p->parts.partsname);
SearchPath(path,argv[2]);
}

ReleasePartsChain(parts);

return 0;

}

>>non様，
申し訳ありません．　In:a Out:bの間違いです．

GGG さんが書きました:

コード:

#include <memory.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <iostream>

using namespace std;


//パーツ格納箱の定義
typedef struct {
  char  partsname;
  char  fst;
  char  lst;
} parts;

parts data_table[] = {
  {'A', 'a', 'b'},
  {'B', 'a', 'c'},
  {'C', 'a', 'a'},
  {'D', 'a', 'h'},
  {'E', 'b', 'c'},
  {'F', 'b', 'e'},
  {'H', 'b', 'f'},
  {'I', 'c', 'd'},
  {'J', 'c', 'h'},
  {'K', 'd', 'i'},
  {'L', 'e', 'a'},
  {'M', 'f', 'a'},
  {'N', 'g', 'b'},
  {'O', 'f', 'c'},
  {'P', 'h', 'c'},
  {'Q', 'i', 'a'},
  { 0 , 0 , 0 },  // 終了マーク
};
//パーツチェイン格納箱の定義
typedef struct _PartsChain{
	struct _PartsChain *next;
	parts parts;
}p_c;
//パーツチェインを解放
void ReleasePartsChain(p_c *p)
{
	while(p!=NULL){
		p_c *n = p->next;
		free(p);
		p=n;
	}
}
//入力からパーツ名を検索
parts *SearchParts(char i_partsname){
	for(int i=0;data_table[i].partsname!=0; ++i){
		if(data_table[i].partsname==i_partsname){
			return &data_table[i];
		}
	}
}
//始点を指定してパーツを探す
p_c *SearchPartsFromfst(char inp){
	p_c *findparts=NULL, *p=NULL;
	for(int idx=0;data_table[idx].partsname!=0;++idx){
		if(data_table[idx].fst==inp){
			if(p==NULL){
				p=(p_c*)malloc(sizeof(p_c));
				findparts=p;
			}
			else{
				p_c *q=(p_c*)malloc(sizeof(p_c));
				p->next=q;
				p=q;
			}
			p->next=NULL;
			memcpy(&p->parts,&data_table[idx],sizeof(parts));
		}
	}
	return findparts;
}

//パスを伸ばす
char *StretchPath(char *path,parts parts){
	int new_path_length=strlen(path)+2;   //NULL含む！！
	char *new_path=(char*)malloc(sizeof(char)*new_path_length);
	memset(new_path,0,new_path_length);
	sprintf_s(new_path,sizeof(char)*new_path_length,"%s%c",path,parts.partsname);
	return new_path;
}
//パスを探す
void SearchPath(char *path, char outp){
	parts *path_last=SearchParts(path[strlen(path)-1]);
	if(path_last->lst==outp){
		printf("見つかったパス:[%s]\n",path);
		return;
	}
	p_c *findparts=SearchPartsFromfst(path_last->lst);
	

	for(p_c *p=findparts;p!=NULL;p=p->next){
		if(strchr(path,p->parts.partsname)!=NULL){continue;}
		char *new_path=StretchPath(path,p->parts);
		SearchPath(new_path,outp);
		free(new_path);
	}
	return;
}

//メイン

int main(void){
	char argv[100];
	cout<<"Input:";
	cin>>argv[1];
	cout<<"Output:";
	cin>>argv[2];
	
    p_c *p,*parts=SearchPartsFromfst(argv[1]);
	for(p=parts;p!=NULL;p=p->next){
		char path[2];
		sprintf_s(path,sizeof(path),"%c",p->parts.partsname);
		SearchPath(path,argv[2]);
	}
  
	ReleasePartsChain(parts);

	return 0;

}

codeタグ追加します。

添付されたプログラムの実行結果です。
Input:a
Output:b
見つかったパス:[A]
見つかったパス:[BIKQA]
見つかったパス:[BIKQCA]
見つかったパス:[BJPIKQA]
見つかったパス:[BJPIKQCA]
見つかったパス:[CA]
見つかったパス:[CBIKQA]
見つかったパス:[CBJPIKQA]
見つかったパス:[CDPIKQA]
見つかったパス:[DPIKQA]
見つかったパス:[DPIKQCA]

で，まだプログラムは見ていないけど，何が問題なのですか？

>>nohiro19様，
ありがとうございます。。。　今後気をつけます。。。

>>non様，おはようございます．
このプログラムの結果の場合だと，質問文に書き込んだ条件２，３を無視している事になってしまっています．
例えば，データの要素が
{'Arcadia', 'ask', 'breach'},
{'Bioshock', 'ask', 'cost'},
{'Criminal', 'ask', 'ask'},…
というように単語になると89行目等で明らかにおかしくなってしまう事がわかります．
さらに，例えば出力結果がナンバリングされていないのですが，仮に上から経路１，経路２…経路11とナンバリングされていた
とすると，経路2の要素3=K，経路10の要素2=P　の様に参照できないのです．
理想は全ての経路がpath[経路番号][要素番号]という２次元配列に格納できることなのですが…

やっと，プログラムを見る時間ができましたので，斜め読みしました。
Nameを見に行くのは無駄だなという感じがしました。しりとりには関係ないですからね。番号も構造体に持てば，簡単に
なりそうでした。
ちょっと，お尋ねしますが，このプログラムはご自身で作られたものですか？
このプログラムを自力で作れたのなら，単語（文字列）にすることはそう難しくないと思います。
構造体に，単語を格納とともに，先頭の文字や最後の文字を格納するメンバーを作ればよいと思います。
また，経路を格納することも，StretchPathのところで，リスト構造に作っていけばできそうです。

>>non様，返信ありがとうございます．

>Nameを見に行くのは無駄だなという感じがしました。しりとりには関係ないですからね。番号も構造体に持てば，簡単になりそうでした。
　確かに，現時点ではあまり関係ないのですが，最終的には『ある入出力をもつパーツを，入出力関係から繋げる』という目的があり，そこで必要になる予定です．補足になりますが，上の目的のため，In/Outというのは『頭文字』ではなくあくまで『単語』になります．

　>ちょっと，お尋ねしますが，このプログラムはご自身で作られたものですか？
すべてを自分で作ったわけありません．プログラミング自体の知識が乏しく，ヒントを頂き，それを元に穴埋めの様な形で書きました．

　>このプログラムを自力で作れたのなら，単語（文字列）にすることはそう難しくないと思います。
　構造体に，単語を格納とともに，先頭の文字や最後の文字を格納するメンバーを作ればよいと思います。
また，経路を格納することも，StretchPathのところで，リスト構造に作っていけばできそうです。
　先の理由から，正直言うとあまり細かい事が理解できていません．大まかに『こういう関数がこういう風に動いているな』という流れの雰囲気を掴んでいる程度です…　
　自身でもあまり理解していない状態でこのように質問をしてしまうのは早計だと思いますが，自分に出来ることはやりました。
　御力をお貸しいただければと思います．
　
　
　
　
　

C++ で書いても良いのでしょうか？

コード:

#include <iostream>
#include <string>
#include <list>
#include <map>

using namespace std;
 
struct parts {
    char *partsname;
    char *fst;
    char *lst;
};
 
parts data_table[] = {
    {"AA", "aa", "bb"},
    {"BB", "aa", "cc"},
    {"CC", "aa", "aa"},
    {"DD", "aa", "hh"},
    {"EE", "bb", "cc"},
    {"FF", "bb", "ee"},
    {"HH", "bb", "ff"},
    {"II", "cc", "dd"},
    {"JJ", "cc", "hh"},
    {"KK", "dd", "ii"},
    {"LL", "ee", "aa"},
    {"MM", "ff", "aa"},
    {"NN", "gg", "bb"},
    {"OO", "ff", "cc"},
    {"PP", "hh", "cc"},
    {"QQ", "ii", "aa"},
};

const int data_table_size = sizeof(data_table) / sizeof(data_table[0]);

struct Parts {
    parts *dp;
    bool  used;

    Parts(parts *dp = 0, bool used = false) : dp(dp), used(used) { }
};

typedef list<Parts> PartsList;
typedef map<string, PartsList> PartsMap;
typedef list<parts *> Path;

struct Data {
    PartsMap  partsMap;
    Path      path;
    string    output;

    Data(const string& output) : output(output) {
        for (int i = 0; i < data_table_size; i++) {
            string fst = data_table[i].fst;
            partsMap[fst].push_back(Parts(&data_table[i]));
        }
    }

    void printPath() {
        cout << "見つけたパス: [";
        for (Path::iterator i = path.begin(); i != path.end(); ++i)
            cout << " " << (*i)->partsname;
        cout << " ]\n";
    }

    void search(const string& input) {
        if (input == output) { printPath(); return; }
        PartsList& pl = partsMap[input];
        for (PartsList::iterator i = pl.begin(); i != pl.end(); ++i) {
            if (i->used) continue;
            i->used = true;
            path.push_back(i->dp);
            search(i->dp->lst);
            path.pop_back();
            i->used = false;
        }
    }
};

int main()
{
    string input, output;
    cout << "Input: "; cin >> input;
    cout << "Output: "; cin >> output;
    Data data(output);
    data.search(input);
    return 0;
}

実行結果

コード:

Input: aa
Output: bb
見つけたパス: [ AA ]
見つけたパス: [ BB II KK QQ AA ]
見つけたパス: [ BB II KK QQ CC AA ]
見つけたパス: [ BB JJ PP II KK QQ AA ]
見つけたパス: [ BB JJ PP II KK QQ CC AA ]
見つけたパス: [ CC AA ]
見つけたパス: [ CC BB II KK QQ AA ]
見つけたパス: [ CC BB JJ PP II KK QQ AA ]
見つけたパス: [ CC DD PP II KK QQ AA ]
見つけたパス: [ DD PP II KK QQ AA ]
見つけたパス: [ DD PP II KK QQ CC AA ]

GGG さんが書きました:2.経路を，経路番号と要素番号で索引出来る状態に格納する．(ex.経路1-1=A 経路2-1=B 経路3-3=K)

すみません。この条件を忘れていたので、追加しました。

コード:


#include <iostream>
#include <string>
#include <list>
#include <map>
#include <vector>

using namespace std;
 
struct parts {
    char *partsname;
    char *fst;
    char *lst;
};
 
parts data_table[] = {
    {"AA", "aa", "bb"},
    {"BB", "aa", "cc"},
    {"CC", "aa", "aa"},
    {"DD", "aa", "hh"},
    {"EE", "bb", "cc"},
    {"FF", "bb", "ee"},
    {"HH", "bb", "ff"},
    {"II", "cc", "dd"},
    {"JJ", "cc", "hh"},
    {"KK", "dd", "ii"},
    {"LL", "ee", "aa"},
    {"MM", "ff", "aa"},
    {"NN", "gg", "bb"},
    {"OO", "ff", "cc"},
    {"PP", "hh", "cc"},
    {"QQ", "ii", "aa"},
};

const int data_table_size = sizeof(data_table) / sizeof(data_table[0]);

struct Parts {
    parts *dp;
    bool  used;

    Parts(parts *dp = 0, bool used = false) : dp(dp), used(used) { }
};

typedef list<Parts> PartsList;
typedef map<string, PartsList> PartsMap;
typedef list<parts *> Path;
typedef vector<parts *> PathVec;
typedef vector<PathVec> PathMat;

class Data {
    PartsMap  partsMap;
    Path      path;
    string    output;
    PathMat   pathMat;

public:
    Data(const string& output) : output(output) {
        for (int i = 0; i < data_table_size; i++) {
            string fst = data_table[i].fst;
            partsMap[fst].push_back(Parts(&data_table[i]));
        }
    }

    void search(const string& input) {
        if (input == output) {
            printPath();
            PathVec pv(path.begin(), path.end());
            pathMat.push_back(pv);
        } else {
            PartsList& pl = partsMap[input];
            for (PartsList::iterator i = pl.begin(); i != pl.end(); ++i) {
                if (i->used) continue;
                i->used = true;
                path.push_back(i->dp);
                search(i->dp->lst);
                path.pop_back();
                i->used = false;
            }
        }
    }

    void printElement(size_t pathNo, size_t elementNo) {
        if (pathNo >= pathMat.size()) { cout << "不正な経路番号\n"; return; }
        PathVec& pv = pathMat[pathNo];
        if (elementNo >= pv.size()) { cout << "不正な要素番号\n"; return; }
        cout << pv[elementNo]->partsname << endl;
    }

private:
    void printPath() {
        cout << "見つけたパス: [";
        for (Path::iterator i = path.begin(); i != path.end(); ++i)
            cout << " " << (*i)->partsname;
        cout << " ]\n";
    }
};

int main()
{
    string input, output;
    cout << "Input: "; cin >> input;
    cout << "Output: "; cin >> output;
    Data data(output);
    data.search(input);

    int pathNo, elementNo;
    while (true) {
        cout << "経路番号: "; cin >> pathNo;
        if (!cin || pathNo < 0) break;
        cout << "要素番号: "; cin >> elementNo;
        if (!cin || elementNo < 0) break;
        data.printElement(pathNo-1, elementNo-1);
    }
    return 0;
}

実行結果

コード:

Input: aa
Output: bb
見つけたパス: [ AA ]
見つけたパス: [ BB II KK QQ AA ]
見つけたパス: [ BB II KK QQ CC AA ]
見つけたパス: [ BB JJ PP II KK QQ AA ]
見つけたパス: [ BB JJ PP II KK QQ CC AA ]
見つけたパス: [ CC AA ]
見つけたパス: [ CC BB II KK QQ AA ]
見つけたパス: [ CC BB JJ PP II KK QQ AA ]
見つけたパス: [ CC DD PP II KK QQ AA ]
見つけたパス: [ DD PP II KK QQ AA ]
見つけたパス: [ DD PP II KK QQ CC AA ]
経路番号: 1
要素番号: 1
AA
経路番号: 2
要素番号: 1
BB
経路番号: 3
要素番号: 3
KK
経路番号: -1

>>かずま様，
返信遅れてしまい申し訳ありません。

ありがとうございます；；
こんなにもずばりその通りのプログラムを書いていただけるとは…
先にも述べたように自分はまだまだ未熟者ですので，多々わからない所がありますが…
解読(?)して学びたいと思います．また質問させていただくかもしれませんが・・・
本当にありがとうございました．

プログラマ専用SNS ミクプラ

データ(csvファイル)を用いてしりとりを行う

データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う

Re: データ(csvファイル)を用いてしりとりを行う