C语言 测试链接列表中是否存在字符串

Question

我对 LinkedList 的经验很少，无法弄清楚测试字符串是否在其中一个节点中的逻辑。该程序总体上正在等待客户端发送DNS查询，然后在无限循环中发回响应。我想做的是：

确定链接列表是否具有客户端请求的主机名。如果不存在，请将其添加到 LinkedList，并在执行查找后将答案保存到同一节点。如果它在那里，只需给客户我已经查找并存储在answer[]中的答案。

下面是一段简化的代码：

struct queryCache {
    char* hostName;
    uint8_t answer[UDP_RECV_SIZE];
    struct queryCache* next;
};
struct queryCache* qcRoot;
int main (int argc, char** argv) {
    // ...unrelated code
    qcRoot = malloc(sizeof(struct queryCache));
    qcRoot->hostName = 0;
    qcRoot->next = 0;
    while (1) {
        // Wait for client with recvfrom()
        char* cqHostName;
        // Code that malloc()s and strcpy()s the client hostname into cqHostName
        // Determine if cqHostName is in the cache
        int hostNameInCache = 0;
        struct queryCache* currQC = qcRoot;
        while (currQC) {
            if (!strcmp(currQC->hostName, cqHostName)) {
                puts("In the cache");
                hostNameInCache = 1;
                break;
            }
            currQC = currQC->next;
        }
        // If cqHostName is not in the cache add its name
        if (!hostNameInCache) {
            currQC->hostName = malloc(strlen(cqHostName)+1);
            strcpy(currQC->hostName, cqHostName);
            printf("Added HOSTNAME: %s to the cachen", cqHostName);
            currQC->next = malloc(sizeof(struct queryCache));
            currQC = currQC->next;
            currQC->hostName = 0;
            currQC->next = 0;
        }
        // Code that does a recursive DNS
        // Code that will copy the response into the appropriate answer[] of the LinkedList
    }
}

该程序似乎只是在第一个客户端请求后退出而不会给出错误。如果我删除 LinkedList 代码，它工作得很好，所以我很确定出了什么问题与我检查字符串是否在 LinkedList 中的方式有关。

Answer 1

当 hostNameInCache 为 0 时，很可能currQC是 NULL ，所以你不能推迟它。

将 while 循环的条件更改为

#------------v
while (currQC->next) {
    if (!strcmp(currQC->hostName, cqHostName)) {
            puts("In the cache");
            hostNameInCache = 1;
            break;
        }
        currQC = currQC->next;
}

Answer 2

根据您的代码，当您尝试执行currQC->hostName = malloc(strlen(cqHostName)+1);时，currQC 为空。

您接受的答案恰好可以解决这种特定情况，但是在while循环中，如果您这样做while(currQC->next)那么您会错过检查列表中的最后一项。

因此，该代码引入了另一个问题，但不会立即显现出来。我建议检查下一个元素是否为 null，如果它像 if (!currQC->next) break; else currQC=currQC->next 一样，则中断。

编辑：当然，我的建议意味着您将希望将while循环替换为do {}while（1）;相反，因为while条件将不再被测试。

Answer 3

在 C 中，通常有两种方法来处理单链表：作为堆栈或作为队列。

将列表作为堆栈处理时，您可以在头部添加新项目。将其作为队列处理时，您可以在尾部添加新项目。

---

最简单的是堆栈方法：

struct node
{
    int data;
    struct node *next;
};
...
struct node *head = NULL;
/* Add one node */
struct node *n1 = malloc(sizeof(struct node));
n1->data = 1;
n1->next = head;   /* This and the next line is what adds the node */
head = n1;
/* Add another node */
struct node *n2 = malloc(sizeof(struct node));
n2->data = 2;
n2->next = head;   /* This and the next line is what adds the node */
head = n2;

在上面的代码之后，列表包含两个节点：

2 --> 1 --> 空

---

对于队列方法，您需要跟踪尾部和头部：

struct node *head = NULL;
struct node *tail = NULL;
/* Add one node */
struct node *n1 = malloc(sizeof(struct node));
n1->data = 1;
n1->next = NULL;
if (tail != NULL)
    tail->next = n1;
else
{
    /* List is empty */
    head = tail = n1;
}
/* Add another node */
struct node *n2 = malloc(sizeof(struct node));
n2->data = 2;
n2->next = NULL;
if (tail != NULL)
    tail->next = n2;
else
{
    /* List is empty */
    head = tail = n2;
}

在此之后，列表看起来像

1 --> 2 --> 空

---

我建议你读几遍这个答案，并思考你对列表的处理与这里使用的方法有何不同。我还建议您使用调试器逐行单步执行代码，以查看为什么列表处理无法按预期工作。