c - 如何将一棵简单的树写入文件并读回？

Question

我有一些代码可以根据指向节点的指针创建一个简单的树，我想将这棵树(及其数据)写入一个文件，然后将其从文件读回内存。我怎样才能做到这一点 ？这是我创建一棵简单树的代码:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

struct Node 
{ 
    void *data; 

    struct Node *left; 
    struct Node *right;
};

int main(void) 
{ 
    unsigned int_size = sizeof(int);
    int data;

    /* Tree root node */
    struct Node *start = (struct Node*)malloc(sizeof(struct Node));

    data = 5;

    start->data = malloc(int_size);
    memcpy(start->data, &data, int_size);

    /* Left node of root */
    start->left = (struct Node*)malloc(sizeof(struct Node));

    data = 4;

    start->left->data = malloc(int_size);
    memcpy(start->left->data, &data, int_size);

    start->left->left = NULL;
    start->left->right = NULL;

    /* Right node of root */
    start->right = (struct Node*)malloc(sizeof(struct Node));

    data = 3;

    start->right->data = malloc(int_size);
    memcpy(start->right->data, &data, int_size);

    start->right->left = NULL;
    start->right->right = NULL;

    /* Print data */

    printf("%d\n",*(int*)(start->data));
    printf("%d\n",*(int*)(start->left->data));
    printf("%d\n",*(int*)(start->right->data));

    return 0; 
}

Answer 1

这里有一个建议，我使用预处理器宏 TYPE 来更改类型和分离函数来读/写该类​​型的元素，我还使用函数 mk 轻松创建节点而不是像对每个节点所做的那样复制代码。

对于序列化，我使用了一种非常简单的方法

• 'e'表示空节点
• 'n'表示一个非空节点，然后我写值然后左再右节点

我还添加了 pr 以轻松打印树作为调试功能。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

#define TYPE int

struct Node 
{ 
  TYPE data; 

  struct Node *left; 
  struct Node *right;
};

/* make a new Node */
struct Node * mk(TYPE v, struct Node * l, struct Node * r)
{
  struct Node * n = malloc(sizeof(struct Node));

  if (n == NULL) {
    fprintf(stderr, "not enough memory\n");
    exit(-1);
  }

  n->data = v;
  n->left = l;
  n->right = r;

  return n;
}

/* write/read data */
void wrData(TYPE v, FILE * fp)
{
  fprintf(fp, "%d", v); /* dedicated to int */
}

TYPE rdData(FILE * fp)
{
  TYPE v;

  fscanf(fp, "%d", &v); /* dedicated to int */
  return v;
}

/* serialize a tree */
void wr(struct Node * n, FILE * fp)
{
  if (n == NULL)
    fputc('e', fp);
  else {
    fputc('n', fp);
    wrData(n->data, fp);
    wr(n->left, fp);
    wr(n->right, fp);
  }
}

/* unserialize a tree */
struct Node * rd(FILE * fp)
{
  switch (fgetc(fp)) {
  case 'e':
    return NULL;
  case 'n':
    {
      TYPE v = rdData(fp);
      struct Node * l = rd(fp);

      return mk(v, l, rd(fp));
    }
  default:
    fprintf(stderr, "invalid file");
    exit(-1);
  }
}

/* for debug, show tree */
void pr(struct Node * t)
{
  if (t == NULL)
    printf("()");
  else {
    putchar('(');
    pr(t->left);
    putchar(' ');
    wrData(t->data, stdout);
    putchar(' ');
    pr(t->right);
    putchar(')');
  }
}

/* free a tree */
void del(struct Node * t)
{
  if (t != NULL) {
    del(t->left);
    del(t->right);
    free(t);
  }
}

int main() 
{ 
    /* Tree root node */
    struct Node *start = mk(5, mk(4, NULL, NULL), mk(3, NULL, NULL));

    /* show it */
    pr(start);
    putchar('\n');

    /* serialize */
    FILE * fp;

    if ((fp = fopen("/tmp/t", "w")) == 0) {
      fprintf(stderr, " cannot open /tmp/t to write");
      exit(-1);
    }
    wr(start, fp);
    fclose(fp);

    /* free tree */
    del(start);

    /* unserialize */
    if ((fp = fopen("/tmp/t", "r")) == 0) {
      fprintf(stderr, " cannot open /tmp/t to read");
      exit(-1);
    }
    start = rd(fp);
    fclose(fp);

    /* show it */
    pr(start);
    putchar('\n');

    /* free it */
    del(start);

    return 0; 
}

编译和执行:

/tmp % gcc -pedantic -Wextra -Wall t.c
/tmp % ./a.out
((() 4 ()) 5 (() 3 ()))
((() 4 ()) 5 (() 3 ()))
/tmp % cat t ; echo
n5n4een3ee

在 valgrind 下执行:

/tmp % valgrind ./a.out
==19907== Memcheck, a memory error detector
==19907== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==19907== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==19907== Command: ./a.out
==19907== 
((() 4 ()) 5 (() 3 ()))
((() 4 ()) 5 (() 3 ()))
==19907== 
==19907== HEAP SUMMARY:
==19907==     in use at exit: 0 bytes in 0 blocks
==19907==   total heap usage: 8 allocs, 8 frees, 1,280 bytes allocated
==19907== 
==19907== All heap blocks were freed -- no leaks are possible
==19907== 
==19907== For counts of detected and suppressed errors, rerun with: -v
==19907== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)