データ構造のテキスト保存について（C言語）

質問

趣味でＣの勉強をしています。

リスト構造や二分木構造のデータをテキストファイルに保存、読み込み再構成させたいです。
データ構造の要素（構造体）に別の要素を指すポインタが含まれてのですが、この情報をテキスト化する方法が有りますか？

考えたのは、各要素にID番号などユニークな記号をつけてポインタ値の代わりにそのIDをテキストに保存しておき、再構成の際にはそのIDとmallocで取得した要素のアドレスを関連つけるテーブルを作成して、テーブルの全ての要素のアドレスが決定したら、各要素内のポインタに対応するアドレスを設定するというものです。

これで問題はないと思うのですが、もっと適切な方法或いはライブラリなどありましたらご教示をお願いします。

またテキスト保存の一般的なフォーマットがありましたら併せて教えていただけると嬉しいです。
構造体の要素としては、ポインタの他に文字列(char配列)、int、doubleなどがありテキストファイルの状態で値が読み取り可能である方が良いです。

使用環境はWindows上のMingw gccです。

よろしくお願いします。

回答No.5

racene · ベストアンサー

シリアライズですね。
http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%AA%E3%82%A2%E3%83%A9%E3%82%A4%E3%82%BA
あたりを読むと良いと思います。

JavaやC++なら色々あるみたいですが、Cだとちょっとわからないですね。
検索してみたところ、C言語向けのライブラリとしては
http://kmaebashi.com/programmer/serializer/index.html
がありました。

お礼

ご回答ありがとうございました。

なるほどシリアライズというのですね、勉強になります。

ライブラリのリンクのご紹介ありがとうございました。
実を言いますと前橋さんのページは別件で良く拝見することがあるのですが、このページには気がつきませんでした。じっくり勉強させていただこうと思います。

回答No.4

noname#208507

ASN.1 という、データを色々な方法で符号化するための規格があります。
http://ja.wikipedia.org/wiki/Abstract_Syntax_Notation_One

しかし一般的と言えるほど認知度は広くはないですね。

手っ取り早いのは、質問者さんが考えられた方法だと思います。私の周囲でもほぼ同じ実装方法をとっています。新しいファイル形式を決めると、よくテキストでもバイナリでも保存できるようにしています。

リスト構造の場合は各要素に0から順に番号を振り、ポインタをこの番号に置き換えてます。

（配列で作った二分木のような）隙間のある疎なデータ構造では、保存するファイルから無駄を無くすため、やはり変換テーブルを用意しています。要素はいったん配列に詰め込んで0から順に番号を振り、変換テーブルに番号と本来の位置の対応を記録しています。

これで問題はないでしょう。

お礼

ご回答ありがとうございました。
自分の考えたものと同じような方法をとられているとのご回答をいただけて、ホッとしております。

ASN.1のご紹介ありがとうございました。
いろいろと新しい知識を得ることができて参考になります。

回答No.3

chie65536（@chie65535）

因みに、要素を減らす場合は、メモリの再確保はしないで、構造体内に使用中かどうかを示すメンバを用意し、それを「未使用」にすれば良い（要素を増やす時に未使用になっている物を再利用しても良い）

構造体内のメンバ変数の「要素番号」に意味があるので「未使用になって空いた隙間を詰める」と言う処理はできない。

お礼

ご回答ありがとうございました。

回答No.2

chie65536（@chie65535）

構造体を配列化すればよい。

配列化すれば、ポインタの変わりに要素番号を使える。

//構造体定義
typedef struct hogehoge {
int parent; //親の番号
int right; //右の子の番号
int left; //左の子の番号
//以下、中身省略
} ListData;

//構造体のポインタ宣言。使用時は配列参照する
ListData *array_struct = NULL;
ListData *new_array_struct;
ListData *new_struct;
int array_size = 0;

//要素を１つ増やす
new_array_struct = realloc(array_struct,sizeof(ListData[1]) * ++array_size);
if (new_array_struct) {
//メモリ確保に成功したら
array_struct = new_array_struct;

new_struct = &array_struct[array_size - 1]; //新しく増えた要素
//新しく増えた要素を初期化
new_struct->parent = -1;
new_struct->right = -1;
new_struct->left = -1;
} else {
//メモリ確保に失敗したらメモリ開放して異常終了
free(array_struct);
abort_exit("memory alloc error");
}

二分木データの配列array_structで、自分自身が０番、右の子が２番、左の子が５番ならば、array_struct[0].rightが２、arraystruct[0].leftが５となり、array_struct[2].parentとarray_struct[5].parentが０になる。

親が居なければparentが-1、左右の子が居なければrightやleftが-1になっていれば良い。

右の子のデータを参照するなら「array_struct[array_struct[自分の番号].right].構造体メンバ変数」で参照できる。

テキストに出力する場合は「要素番号をそのままテキスト出力」するだけ。

テキストから入力する場合は「テキスト入力してそのまま要素番号を格納」するだけ。

変換テーブルなんぞ必要ない。

お礼

ご回答ありがとうございました。
ポインタの代わりに配列にするというのは盲点でした。

ただreallocというのは、そのたびに全部のデータをコピーするのですよね。
データ構築時の時間ロスが気になりますが、大規模でなければ問題ないのかな？

回答No.1

jjk65536

テキストファイルで構造的なデータを保存するライブラリと言われると、
すぐ思いつくのはXMLですね。
ライブラリもたくさんあります。

> 構造体の要素としては、ポインタの他に文字列(char配列)、int、doubleなどがあり

これらが保持出来ればテキストには拘らない、と解釈すると
SQLなんかも視野に入ってくると思います。
私自身はSqliteとMysqlをC言語からコールしたことがあります。
2分木でもSQLで表現できますよ。

> またテキスト保存の一般的なフォーマットがありましたら併せて教えていただけると嬉しいです。

CSV、XMLあたりじゃないでしょうか。
ほかは私は知りません、すみません。

お礼

ご回答ありがとうございました。
SQLについては、ほんの少しかじった程度でしたので、二分木構造を表現できるとは知りませんでした。
参考になりました。