0

在我的作业中，我必须创建一个用户输入详细信息的二叉树。

用户做的第一件事是如果他们想要创建一个数字树，则输入 1，如果他们想要一个单词树，则输入 2。

他们选择的树类型是程序运行期间的类型。

为了完成分配，必须编写许多函数（和一些结构）。

我的问题是如何编写适用于 int 和 char 的通用函数？

例如，如果它是一个数字树，那么节点的结构将包括： int key; list_t* 值列表；节点*左；节点* 对；

但如果它是一个单词列表，那么结构看起来是一样的，只是它不是 int key，而是 char key。

提前感谢您的帮助！

4

3 回答 3

2

您可以采取的方法是将结构中的数据定义为联合，如下所示：

struct _Node
{
  ...
  union
  {
    char* c;
    int i;
  } data;
};

比用户做出选择时，根据它访问正确的联合成员。

编辑

例如，假设用户选择了一种类型int。并且您希望在树中插入一个新值。（为了简洁起见，我将省略错误检查，但请记住检查内存分配是否成功）。

struct _Node* newElem = allocNode();

if (get_user_elected_type() == INT)
    newElem->data.i = user_input.i; // Your methods will also need to accept a union

这种方式有严重的缺点（例如，添加新类型并不容易）。最重要的是，它演示了 C 中的泛型编程是多么糟糕。（使用void*最终会变得一样糟糕）。

于 2013-02-14T11:02:17.873 回答
0

解决此问题的解决方案很少（您尝试做的事情称为泛型编程）

  1. 使用 void * 键，并用正确的数据填充它（建议这样做，因为更通用，但也更复杂）
  2. 使用union带有 2 个字段的 a：一个 int 和一个 char*
于 2013-02-14T11:03:05.847 回答
0

对于家庭作业，更简单的方法是使用union数据类型：

struct node {
  union {
    char *s
    int   i;
  } data;
  struct node *left;
  struct node *right;
};

并创建两组函数，一组用于管理整数值，另一组用于管理字符串值：

void insertIntNode(struct node *root, struct node *newNode)
{
  if (newNode->data.i < root->data.i)
    if (root->left != NULL)
      insertIntNode(root->left, newNode);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insertIntNode(root->right, newNode);
    else
      root->right = newNode;
}

void insertWordNode(struct node *root, struct node *newNode)
{
  if (strcmp(root->data.s, newNode->data.s) < 0)
    if (root->left != NULL)
      insertWordNode(root->left, newNode);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insertWordNode(root->right, newNode);
    else
      root->right = newNode;
  }

请记住，您需要对单词数据进行一些额外的内存管理：

struct node *createWordNode(char *str)
{
  struct node *r = malloc(sizeof *r);
  if (r)
  {
    r->data.s = malloc(strlen(str) + 1);
    if (r->s) 
      strcpy(r->data.s, str); 
    r->left = r->right = NULL;
  }
  return r;
}

void destroyWordNode(struct node **n)
{
  free((*n)->data.s);
  free(*n);
  *n = NULL;
}

更灵活的方法是使用 avoid *指向您的数据项，然后将所有类型感知操作（分配、赋值、比较、显示等）委托给隐藏在一组函数指针后面的其他函数。例如：

struct node {
  void *data;
  struct node *left;
  struct node *right;
};

struct node *newNode(void *data, void *(*copy)(const void *))
{
  struct node *n = malloc(sizeof *n);
  if (n)
  {
    n->left = n->right = NULL;
    n->data = copy(data);
  }
  return n;
}

void insert(struct node *root, struct node *newNode, 
    int (*compare)(const void *, const void *))
{
  if (compare(newNode->data, root->data) < 0)
    if (root->left != NULL)
      insert(root->left, newNode, compare);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insert(root->right, newNode);
    else
      root->right = newNode;
}

在上面的示例中，为节点data元素分配内存和比较两个data元素的细节被委托给其他函数，指向这些函数的指针作为参数传递给列表管理函数。这样你就可以编写一个newNode和insert函数，但它能够处理任意节点数据类型。因此，对于您的整数树，您可以编写如下函数

void *copyInt(const void *data)
{
  const int *src = data;
  int *dst = malloc(sizeof *dst);
  if (dst)
  {
    *dst = *src;
  }
  return dst;
}

int compareInt(const void *lhs, const void *rhs)
{
  const int *ilhs = lhs;
  const int *irhs = rhs;
  if (*ilhs < *irhs)
    return -1;
  else if (*ilhs == *irhs)
    return 0;
  else
    return 1;
}

然后你会打电话newNode给insert喜欢

void insertIntValue(struct node *root, int value)
{
  struct node *n = newNode(&value, copyInt);
  if (n)
    insert(root, n, compareInt);
}

这种方法的最大缺点是您将类型安全性扔到窗外并进入迎面而来的交通；因为我们正在使用void *一切。编译器将无法为我们捕获类型不匹配。没有什么可以阻止您将错误的复制或比较函数传递给特定类型的通用例程。

insertIntValue这给我们带来了第二个缺点——您仍然需要为您想要支持的每种数据类型（insertFloatValue、insertStringValue、insertMyObnoxiousDataTypeValue等）以及所有委托编写一个类型感知接口（例如上面的函数）。部分是为了避免类型安全问题，部分是因为我们的“通用”函数确实不是为了直接调用而设计的。例如，该newNode函数需要一个指针作为第一个参数，这意味着您不能编写类似

struct node *n = newNode(10, copyInt);

或者

struct node *n = newNode(3.14159, copyDouble);

IOW，您不能将文字作为第一个参数传递；你必须传递一个对象的地址。

第三个主要缺点是您最终会进行大量内存管理，这很痛苦。您必须创建输入的副本；否则，您最终会将相同的指针值（传递给 的指针值newNode）分配给树中的每个节点。每个都malloc必须有一个匹配free项，否则您最终会泄漏大量内存。您必须遵守如何分配和解除分配数据项的规定。

坦率地说，用 C 语言构建健壮的通用容器是一件非常痛苦的事情。这样做的唯一真正原因是您可以真正体会到 C++ 中的模板以及 Java 和 C# 中的泛型的价值。

于 2013-02-14T12:20:55.483 回答