0

入力ファイルは数字の単純なリストになると言われています。

1 3 4

2 3

3 4

4 1 2

最初の数字がソース ノードで、次の数字が隣接ノードです。

どうやって保存するのがベストなのか模索中です。最初に、これらすべてのノードを含む配列である「グラフ」を初期化したかったのです。次に、ファイルを 1 行ずつ読み取って、ルート ノードをグラフ配列に格納し、ノードのアウトリスト (隣接するノード) を次の番号で更新して、行の終わりに到達するまで、これを各行で繰り返します。 EOF。

ただし、グラフを初期化する方法に苦労しています。サイズがヒットしたら、特定のサイズと realloc() を想定するだけですか? 最初にファイルを読み取り、行数を数えてサイズを確認してから、ファイルを再度読み取ってノードを保存しますか? 他に方法はありますか？

私のデータ構造のコードは次のとおりです。

int initialize (Graph *mygraph, int MaxSize) {
  mygraph->MaxSize = MaxSize;
  mygraph->table = (Node *)malloc(sizeof(Node) * MaxSize);
  return 0;
}

  int insert_node (Graph *mygraph, int n, char *name) {
  mygraph->table[n].name = strdup(name);
  mygraph->table[n].outdegree = 0;
  return 0;
}

  int insert_link (Graph *mygraph, int source, int target) {
  List *newList = (List *)malloc(sizeof(List));
  newList->index = target;
  newList->next = mygraph->table[source].outlist;
  mygraph->table[source].outlist = newList;
  return 0;
}

したがって、ファイルを読み取ると、

  1. グラフを初期化します。

  2. 最初の数値を読み取り、それを新しいグラフ ノードとして保存します。

  3. 「\n」を押すまで次の番号を読み取り、これらを上記のルート ノードへのグラフ リンクとして保存します。

  4. EOFに達するまで、これを各行に対して行います。

ご覧のとおり、ファイル全体が読み取られるまで、「MaxSize」が何であるかわかりません。

ありがとう！私はCにかなり慣れていないので、ばかげたことをした場合は申し訳ありません。

4

1 に答える 1

1

いくつかの初期推定値MaxSize(例: 8) を取得し、必要に応じてデータを拡張することができます (おそらくgraph->MaxSize += graph->MaxSize/2) を使用reallocするかmalloc、より大きな新しいチャンクを -ing し、古いチャンクを内部にコピーしてから、freeその古いチャンクを -ing します)。mallocor呼び出しの成功結果を確認することを忘れないでください。(まれに) 失敗する可能calloc性があります。realloc

あなたのGraphandNode型がどのように宣言されているかはわかりません (推測です)。

私はあなたが次のようなものを宣言したと仮定しています

 typedef struct node_st Node;
 typedef struct graph_st Graph;
 struct node_st {
    char*name; // strdup-ed
    unsigned outdegree;
 };
 struct graph_st {
   unsigned MaxSize;
   Node* table; //calloc-ed, of allocated size MaxSize
 };

たとえば、あなたのinsert_node関数は

void insert_node (Graph *mygraph, int n, char *name) {
  assert (mygraph != NULL);
  assert (n >= 0);
  assert (name != NULL && *name != (char)0);
  unsigned maxsize = mygraph->MaxSize;
  if (maxsize <= n) {
    unsigned newmaxsize = n + maxsize/2 + 1;
    Node* newtable = calloc (newmaxsize, sizeof(Node));
    if (!newtable) 
       perror("growing table in graph"), exit(EXIT_FAILURE);
    for (unsigned i=0; i<maxsize; i++) 
       newtable[i] = mygraph->table[i];
    free (mygraph->table);
    mygraph->table = newtable;
    mygraph->MaxSize = newmaxsize;
  };
  mygraph->table[n].name = strdup(name);
  mygraph->table[n].outdegree = 0;
}

おそらくinsert_node、値を返す必要はありません (そうしないと、常に 0 を返すとは限りません)。だから私はそれをvoid返す関数（つまり、「手続き」または「ルーチン」）にしました。

于 2012-10-13T13:37:33.567 に答える