0

我们被告知我们的输入文件将是一个简单的数字列表:

1 3 4

2 3

3 4

4 1 2

其中第一个数字是源节点,后面的数字是它的相邻节点。

我试图弄清楚如何最好地存储它。我想首先初始化一个“图形”,一个包含所有这些节点的数组。然后在逐行读取文件时,我会将根节点存储到图形数组中,然后用以下数字更新节点的 outlist(相邻节点),直到到达行尾,对每一行重复此操作,直到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 callocorrealloc调用的成功结果,它们可能(很少)失败。

请注意,我不知道您的GraphNode类型是如何声明的(只是猜测)。

我假设并猜测您已经声明了类似

 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 回答