お待たせしました.読み込み用サンプルプログラムです.
> 今まで、テキストでの保存しかやったことがないのでこれを機会に
> バイナリでの保存を勉強していきたいと思います。
#5 は fwrite() を fprintf() に変えればほとんどそのままでテキストファイル用になります.
ただし,読み込み側では構文のチェックなどを行わなければならないので少々面倒です.
●#5 に対する変更
#5 で使用したデータ構造を,読み込み/書き出しで共用できるようにするため,一部変更しました.
(1) Node_t::name[] の要素数の宣言を変更:MAXNAME → 1 に変更.
読み込み時にスタックを余計に消費しないようにするため.
この変更は #5 のプログラムには影響なし.
実際には必要なサイズを確保する.名前の長さは事実上無制限になる.
#define MAXNAME は不要になったので削除.
(2) TraverseArgs_t のメンバを変更
・out メンバを,読み込みにも使用するようにしたため,名前を fp に変更.
#5 のプログラムで out を fp に変更すること.
・読み込みに必要なメンバ (nodeTable) を追加.この変更は #5 のプログラムには影響なし.
●問題点
さっき,#5 のプログラムの問題に気付きました.(^^;)
ツリーが空 (節点が一つもない,root=NULL) の時はクラッシュします.
つまり,空のツリーは保存できません.
現在の実装では,子節点の childExists フラグを書くようになっていますが,
それを廃止して,節点自身の nodeExists フラグを書くようにする方がいいです.
つまり,SaveSubtree() で最初に nodeExists = (node != NULL) を読み書きし,
それが偽ならば節点の読み書きをしないようにします.
(#5 と対応させるため,次の読み込みプログラムにはこの変更を行っていません.)
●読み込み用サンプルプログラム (コンパイルは通してますが,動かしてはいません.)
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#define MAXLINKS 4 /* 1節点から出る最大リンク数 */
#define OK 0
#define FAIL (-1)
/* 節点のデータ構造の定義 */
typedef struct Node Node_t;
struct Node {
Node_t *child[2]; /* 左右の子節点へのポインタ */
Node_t *link[MAXLINKS]; /* 木の親子関係以外の節点間リンクまたは NULL.*/
/* この配列の添字がリンクIDとなる.*/
unsigned no; /* 節点番号 */
/* 以下,この節点自身のデータ */
int data;
char name[1]; /* 節点名 (の最初の1バイトのみ宣言) */
};
/* トラバース中に各節点からアクセスされる変数をまとめた構造体 */
typedef struct {
unsigned nNodes; /* トラバース中は現在までに読み込んだ節点数,トラバース後は節点の総数.*/
unsigned nLinks; /* 節点間リンクの総数 */
Node_t **nodeTable; /* 節点番号を節点へのポインタに変換するための配列 */
FILE *fp; /* ファイルの入出力ストリーム */
const char *fileName; /* ファイル名 */
} TraverseArgs_t;
/* 変数 var (ポインタ以外) をバイナリファイルから読む.*/
#define ReadVar(var, in) (fread(&(var), 1, sizeof(var), (in)) == sizeof(var))
/* node 以下の部分木を削除する.*/
void DeleteSubtree(Node_t *node)
{
if(node != NULL) {
unsigned i;
for(i = 0; i < 2; i++) DeleteSubtree(node->child[i]);
free(node);
}
}
/* 読み込みエラーのメッセージを出力する.*/
void ReadError(const TraverseArgs_t *args)
{
if((errno == 0) && feof(args->fp)) {
/* おそらく,ファイルが途中で終わってしまったためのエラー.*/
fprintf(stderr, "\"%s\": ファイルが途中で終わっています。", args->fileName);
} else {
fprintf(stderr, "\"%s\": 読み込みエラー (%s)\n", args->fileName, strerror(errno));
}
}
/* 部分木を読み,その根節点へのポインタを *pNode に返す.*/
int LoadSubtree(Node_t **pNode, TraverseArgs_t *args)
{
Node_t nodeBuf; /* 読み込んだ節点データを一時的に格納しておくためのバッファ */
Node_t *node; /* 読み込み成功時に生成される節点を指す.*/
char *name = NULL; /* 節点名を一時的に格納するバッファを指す.*/
size_t length; /* 節点名のバイト数 (終端 '\0' を含まない.) */
unsigned i;
unsigned char childExists; /* 子節点が存在しているときそのときに限り真.*/
*pNode = NULL; /* エラーの時に返す値を設定しておく.*/
/* nodeBuf を初期化する.
* nodeBuf.link[*] を NULL に,nodeBuf.name を空文字列に初期化しておく必要があるので,
* これらを memset() でまとめて行う.
*/
memset(&nodeBuf, 0, sizeof(nodeBuf));
/* 節点番号および節点自身のデータを読む.*/
if(!ReadVar(nodeBuf.no, args->fp) ||
!ReadVar(nodeBuf.data, args->fp) ||
!ReadVar(length, args->fp)) {
ReadError:
ReadError(args);
goto Error;
}
if(length > 0) {
/* 名前が空文字列でない場合 */
/* 名前用のバッファを確保する.*/
if((name = malloc(length + 1)) == NULL) {
NoMemory: /* メモリ不足 */
fprintf(stderr, "%s\n", strerror(errno));
goto Error;
}
/* 名前を読む.*/
if(fread(name, 1, length, args->fp) != length) goto ReadError;
name[length] = '\0';
}
/* 左右の子節点以下の部分木を読む.*/
for(i = 0; i < 2; i++) {
if(!ReadVar(childExists, args->fp)) goto ReadError;
if(childExists && (LoadSubtree(&nodeBuf.child[i], args) == FAIL)) goto Error;
}
/* 新しい節点を作成する.
* (下記の malloc() の引数は,本来は
* offsetof(Node_t, name[0]) + length + 1 (終端 '\0' の分)
* だが,定数を一つにまとめて書いてある.)
*/
if((node = malloc(offsetof(Node_t, name[1]) + length)) == NULL) goto NoMemory;
/* nodeBuf を *node にコピーする.*/
*node = nodeBuf;
if(name != NULL) {
/* 節点名をコピーする.*/
strcpy(node->name, name);
free(name);
}
/*読み込み成功 */
args->nNodes++; /* 読み込んだ節点数を数える.*/
*pNode = node; /* 読み込んだ部分木の根節点へのポインタを返す.*/
return OK;
Error:
if(name != NULL) free(name);
for(i = 0; i < 2; i++) DeleteSubtree(nodeBuf.child[i]);
return FAIL;
}
/* 節点番号を節点へのポインタに変換するためのテーブル (配列) を作成する.
* node 以下の部分木の各節点をテーブルに登録する.
* args->nodeTable[0 ~ args->nNodes-1] は NULL に初期化されていなければならない.
*/
int MakeNodeTable(Node_t *node, TraverseArgs_t *args)
{
if(node != NULL) {
unsigned i;
if((node->no < 1) || (node->no > args->nNodes)) {
fprintf(stderr, "節点番号 %u は範囲外です。(有効範囲:1~%u)\n",
node->no, args->nNodes);
return FAIL;
}
i = node->no - 1; /* 節点番号を配列の添字に変換.*/
if(args->nodeTable[i] != NULL) {
/* 既に同じ節点番号で別の節点が登録されている場合 */
fprintf(stderr, "節点番号 %u が重複しています。\n", node->no);
return FAIL;
}
args->nodeTable[i] = node; /* node を登録する.*/
/* node の子孫を登録する.*/
for(i = 0; i < 2; i++) {
if(MakeNodeTable(node->child[i], args) == FAIL) return FAIL;
}
}
return OK;
}
/* 節点番号を節点へのポインタに変換する.*/
Node_t *NodeNoToPointer(unsigned nodeNo, const TraverseArgs_t *args)
{
Node_t *node;
if((nodeNo < 1) || (nodeNo > args->nNodes)) {
fprintf(stderr, "節点番号 %u は範囲外です。\n", nodeNo);
return NULL;
}
if((node = args->nodeTable[nodeNo]) == NULL)
fprintf(stderr, "節点番号 %u は定義されていません。\n", nodeNo);
return node;
}
/* 全リンク情報を読む.*/
int LoadLinks(const TraverseArgs_t *args)
{
Node_t *fromNode, *toNode;
unsigned fromNodeNo, toNodeNo, linkId, i;
for(i = 0; i < args->nLinks; i++) {
/* 1組のリンク情報を読む.*/
if(!ReadVar(fromNodeNo, args->fp) ||
!ReadVar(linkId, args->fp) ||
!ReadVar(toNodeNo, args->fp)) {
ReadError(args);
return FAIL;
}
if(linkId >= MAXLINKS) {
fprintf(stderr, "\"%s\", Link #%u: LinkID %u は範囲外です。\n",
args->fileName, i, linkId);
return FAIL;
}
if(((fromNode = NodeNoToPointer(fromNodeNo, args)) == NULL) ||
((toNode = NodeNoToPointer(toNodeNo, args)) == NULL))
return FAIL;
/* リンク読み込み成功:リンクを設定する.*/
fromNode->link[linkId] = toNode;
}
return OK;
}
/* バイナリツリー全体をバイナリファイルから読む.
* 出力:(1) *pRoot:ツリーの根節点へのポインタ.
* (2) *pNodes:ツリーの全節点数.
*/
int LoadTree(const char *fileName, Node_t **pRoot, unsigned *pNNodes)
{
TraverseArgs_t args;
Node_t *root = NULL; /* バイナリツリーの根節点 */
/* エラーの場合に返す値を設定しておく.*/
*pRoot = NULL;
*pNNodes = 0;
args.nNodes = 0;
args.nLinks = 0;
args.nodeTable = NULL;
//args.fp = NULL;
args.fileName = fileName;
if((args.fp = fopen(fileName, "rb")) == NULL) {
fprintf(stderr, "\"%s\" をオープンできません。(%s)\n", fileName, strerror(errno));
goto Error;
}
/* 木構造および全節点の情報を読み込むとともに,節点数を数える.*/
if(LoadSubtree(&root, &args) == FAIL) return FAIL;
/* 全リンク数を読む.*/
if(!ReadVar(args.nLinks, args.fp)) {
ReadError(&args);
goto Error;
}
if(args.nLinks > 0) {
/* リンク情報がある場合 */
/* 節点番号を節点へのポインタに変換するためのテーブルを作成する.
* 配列の全要素を NULL に初期化しておく必要があるため,
* malloc() ではなく calloc() を使用する.
*/
if((args.nodeTable = calloc(sizeof(args.nodeTable[0]), args.nLinks)) == NULL) {
/* メモリ不足 */
fprintf(stderr, "%s\n", strerror(errno));
goto Error;
}
if(MakeNodeTable(root, &args) == FAIL) goto Error;
/* リンク情報を読む.*/
if(LoadLinks(&args) == FAIL) goto Error;
free(args.nodeTable);
args.nodeTable = NULL;
}
/* 読み込み成功 */
fclose(args.fp);
return OK;
Error:
if(args.nodeTable != NULL) free(args.nodeTable);
if(args.fp != NULL) fclose(args.fp);
DeleteSubtree(root);
return FAIL;
}
お礼
ご回答ありがとうございます。 mapですか。選択肢外でした。 ただ、mapだとキーのソートによってで単方向ポインタなら実現できそうですが、私が作ろうとしている双方向ポインタは無理ではないでしょうか? あと、構造体に格納するデータは複数あるのでmapでは対応できないような気がします。 私の勘違いであれば申し訳ございません。参考意見ありがとうございました。