c - 如何在C中实现链表的 "contains"函数

Question

我目前正在为大学做作业，我需要找到图表的总和。

为此，我相信我需要一个链表，我可以用它来记住哪些节点已被访问。我的链接列表工作正常，但我无法让 contains 函数工作。这是我的代码:

struct listnode
{
  struct N *val;
  struct listnode *next;
};


int contains(struct listnode *head,struct N* value)
{
  struct listnode *current = head;
  while (current)
  {
    if ((current -> val) == value)
    {
      return 1;
    }
    current = current -> next;
  }
  return 0;
}

注:N是图的一个节点。

任何人都可以看到我正在做的事情有任何问题吗？

编辑:当 N *值在列表中时，包含函数应返回 1，否则返回 0

编辑2:

我有一个推送功能:

void push(struct listnode *head,struct N *value)
{
  if (head)
  {
    struct listnode *current = head;
    while (current->next)
    {
      current = current -> next;
    }
    current->next = malloc(sizeof(struct listnode*));
    current->next->val = value;
    current->next->next = NULL;
  }
  else
  {
    head = malloc(sizeof(struct listnode*));
    if (head)
    {
      head -> val = value;
      head -> next = NULL;
    }
    else
    {
      printf("error");
      exit(0);
    }
  }
}

我希望下面的行返回 1:

contains(push(visited,p),p);

其中 p 是指向结构 N 的指针，访问的是我的全局链表

编辑3:

这是我的最终求和函数，我认为它应该起作用，但由于包含而不起作用。

long sum(struct N *p)
{
  if (p)
  {
    if (contains(visited,p) == 0) //if p hasnt been visited
    {
      push(visited,p); //make it visited
      return (p -> data) + sum(p -> x) + sum(p -> y) + sum(p -> z);
    }
    else
    {
      return 0;
    }
  }
  else
  {
    return 0;
  }
}

Answer 1

您的 contains 函数似乎没问题。问题是您总是向其传递一个 NULL 列表，这是由错误的 push 函数引起的。您需要在 push 中返回，或者传入具有多一级间接寻址的指针，以便您可以在 push 之外分配给 head 。另一个可能的改进是注意到无论您传入什么，新节点的 malloc 和初始化实际上是相同的。

最后，最有可能导致段错误的主要问题是，您为指向节点的指针分配了足够的空间，而不是为节点本身分配了足够的空间。

这是一个例子:

#ifdef BY_INDIRECTION
  #define RET_TYPE void
  #define IN_TYPE struct listnode **
#else
  #define RET_TYPE struct listnode *
  #define IN_TYPE struct listnode *
#endif

RET_TYPE push(IN_TYPE head, struct N *value)
{
  struct listnode *current, **next;
  if(head)
  {
    for(current = head; current->next; current = current->next) ;
    next = &(current->next);
  }
  else
  {
#ifdef BY_INDIRECTION
    next = head;
#else
    next = &head;
#endif
  }

  *next = malloc(sizeof(struct listnode));
  if(!*next) {
      printf("error");
      exit(0);
  }
  (*next)->val = value;
  (*next)->next = NULL;

#ifndef BY_INDIRECTION
  return head
#endif
}

我已将这两条建议都包含在此处。如果您想阅读我们使用间接寻址的内容(传入 listnode ** 并返回 void)，请选择 BY_INDIRECTION 所在的路径被定义为。如果您希望返回 head(并仅传入常规 listnode *)，请读取未定义 BY_INDIRECTION 的路径。

后一种方法有一个返回值，因此可以用来编写类似 if(contains(push(head, value), value)) { ... } 的缩写形式。前一种方法没有，所以你必须这样做

push(&head, value);
if(contains(head, value)) { ... }

无论如何，我都建议使用间接方法，因为在输入值之后很少有情况需要您检查是否包含。