我目前正在为大学做作业,我需要找到图表的总和。
为此,我相信我需要一个链表,我可以用它来记住哪些节点已被访问。我的链接列表工作正常,但我无法让 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;
}
}
最佳答案
您的 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)) { ... }
无论如何,我都建议使用间接方法,因为在输入值之后很少有情况需要您检查是否包含。
关于c - 如何在C中实现链表的 "contains"函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42009776/