C语言链表无限循环

尝试创建一个程序来计算与strcmp进行比较的次数，同时将当前节点移动到head。虽然算法有一些问题..它有时"工作"，有时给我一个无限循环。现在已经尝试了几个小时的lldb，并且每2行代码就放置一次printf消息，但我不知道如何查明问题所在。我认为它在算法中的某个地方，但我看不出有什么问题。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node2
{
    char* word;
    struct Node2 *next;
} Node2;
Node2* head = NULL;
Node2* now = NULL;
int uniqueWords = 0;
int totalMTFRComparisons = 0;

Node2* iNode(char* word)
{   
    Node2* ptr = malloc(sizeof(Node2));
    Node2* tmp = head;
    Node2* prev = head;
    while (tmp)
    {
        totalMTFRComparisons++;
        printf("Current word: %s", tmp->word);
        if (strcmp(tmp->word, word) == 0)
        {
            prev->next = tmp->next;
            tmp->next = head;
            return tmp;
        }
        prev = tmp;
        tmp = tmp->next;
        printf("tmp incremented.n");
    }
    ptr->word = malloc(strlen(word) + 1);
    strcpy(ptr->word, word);
    ptr->next = NULL;
    if (head == NULL)
    {
        head = now = ptr;
        return ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}
char* getString()
{
    static char buffer[128];
    while (fgets(buffer, 128, stdin) != NULL)
    {
        iNode(buffer);
    }
    return buffer;
}
int main()
{
    getString();
    printf("Total words: %d, total MTFR comparisons: %dn", uniqueWords, totalMTFRComparisons);
    Node2* ptr2 = head;
    Node2* tmp2 = head;
    while (ptr2 != NULL)
    {
        tmp2 = ptr2->next;
        free(ptr2->word);
        free(ptr2);
        ptr2 = tmp2;
    }
}

我的控制台刚刚收到垃圾邮件： tmp incremented.但这并不总是发生 - 它只是偶尔发生，所以我不知道是什么原因造成的。

输入和输出示例：http://pastebin.com/QfuCm7gt

你为字符串分配的内存太少：

ptr->word = malloc(strlen(word));
strcpy(ptr->word, word);

您需要分配 strlen(word) + 1 个字节以允许空终止符。

当您写入超出分配的空间时，您将调用未定义的行为。对你来说不幸的是，这可能意味着它有时看起来工作正常——它是对未定义行为的有效响应，似乎按预期工作，除非它适合系统改变主意并表现异常。

考虑是否可以使用 strdup() 函数。如果没有，请考虑是否应该编写和使用自己的版本。不要忘记检查内存分配是否成功。

(在你修复未定义的行为之前，想知道还有什么问题，如果还有其他问题，真的没有意义。

我

写了这段代码，看看我是否可以模拟你的问题。我不能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
    char *word;
    struct Node *next;
} Node;
int totalMTFRComparisons = 0;
Node* head = NULL;
static Node* iNode(char* word)
{   
    Node* ptr = malloc(sizeof(Node));
    Node* tmp = head;
    Node* prev = head;
    while (tmp)
    {
        totalMTFRComparisons++;
        if (strcmp(tmp->word, word) == 0)
        {
            prev->next = tmp->next;
            tmp->next = head;
            //tmp->next = prev;
/* JL: Still a memory leak here. */
/* Either free(ptr) or don't allocate until after the loop */
            return tmp;
        }
        prev = tmp;
        tmp = tmp->next;
        printf("tmp incremented.n");
    }
    ptr->word = malloc(strlen(word) + 1);
    strcpy(ptr->word, word);
    ptr->next = NULL;
    if (head == NULL)
    {
        head = ptr;
        return ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}
static void dump_list(Node *node)
{
    while (node != 0)
    {
        printf("Node word: [[%s]]n", node->word);
        node = node->next;
    }
}
static void free_list(Node *node)
{
    printf("Freeing listn");
    while (node != 0)
    {
        Node *next = node->next;
        printf("Freeing: [[%s]]n", node->word);
        free(node->word);
        free(node);
        node = next;
    }
}
int main(void)
{
    char line[4096];
    while (fgets(line, sizeof(line), stdin) != 0)
    {
        printf("Line: [[%s]]n", line);
        char *ptr = line;
        char *tok;
        while ((tok = strtok(ptr, "nt ")) != 0)
        {
            printf("Word: [[%s]]n", tok);
            iNode(tok);
            ptr = NULL;
        }
        dump_list(head);
    }
    free_list(head);
    return 0;
}

这或多或少是一个MCVE。转储和自由函数只是允许我确保我可以看到列表中的内容并释放所有内存。

除了修复内存覆盖问题外，我只提供了Node类型的定义，static放在函数前面(以避免我本来会得到的编译警告之一(，并添加了两个支持函数和main();否则我没有更改您的代码。 (顺便说一下，第一次编译的唯一抱怨是关于我注意到但忘记删除的cur2 - 这很好;很少有程序，即使是我编写的程序，也能通过得那么干净。

运行时，我键入：

abc def ghi
mno pqr stuvwxyz humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long word!

我得到了输出：

abc def ghi
Line: [[abc def ghi
]]
Word: [[abc]]
Word: [[def]]
tmp incremented.
Word: [[ghi]]
tmp incremented.
tmp incremented.
Node word: [[ghi]]
Node word: [[def]]
Node word: [[abc]]
mno pqr stuvwxyz humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long word!
Line: [[mno pqr stuvwxyz humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long word!
]]
Word: [[mno]]
tmp incremented.
tmp incremented.
tmp incremented.
Word: [[pqr]]
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
Word: [[stuvwxyz]]
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
Word: [[humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long]]
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
Word: [[word!]]
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
tmp incremented.
Node word: [[word!]]
Node word: [[humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long]]
Node word: [[stuvwxyz]]
Node word: [[pqr]]
Node word: [[mno]]
Node word: [[ghi]]
Node word: [[def]]
Node word: [[abc]]
Freeing list
Freeing: [[word!]]
Freeing: [[humongously-and-tempestuously-but-neither-abstemiously-nor-facetiously-long]]
Freeing: [[stuvwxyz]]
Freeing: [[pqr]]
Freeing: [[mno]]
Freeing: [[ghi]]
Freeing: [[def]]
Freeing: [[abc]]

在Valgrind下运行时，我得到了一些奇怪的输出，但那是因为我在没有更新抑制的情况下升级了o/s(Mac OS X Yosemite到El Capitan(。泄漏都在系统代码中，而不是在这个代码中，AFAICT。

聊天后

该代码的功能之一是，如果输入两次单词，则应将该单词移动到列表的前面。我的测试是在独特的单词集上进行的。问题在于处理第一个单词的重复。此代码中似乎很健壮的修复程序：

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

typedef struct Node2
{
    char* word;
    struct Node2 *next;
} Node2;
Node2* head = NULL;
Node2* now = NULL;
int uniqueWords = 0;
int totalMTFRComparisons = 0;
bool DEBUG = true;
static
Node2* iNode(char* word)
{   
    if (DEBUG)
        printf("addNode2 called [[%s]].n", word);
    Node2* tmp = head;
    Node2* prev = 0;
    while (tmp)
    {
        totalMTFRComparisons++;
        printf("Current word: %sn", tmp->word);
        if (strcmp(tmp->word, word) == 0)
        {
            printf("Already entered: [[%s]]n", tmp->word);
            if (prev != 0)
            {
                prev->next = tmp->next;
                tmp->next = head;
                head = tmp;
            }
            //tmp->next = prev;
            return tmp;
        }
        prev = tmp;
        tmp = tmp->next;
        printf("tmp incremented.n");
    }
    Node2* ptr = malloc(sizeof(Node2));
    printf("New word: [[%s]]n", word);
    uniqueWords++;
    ptr->word = malloc(strlen(word) + 1);
    strcpy(ptr->word, word);
    ptr->next = NULL;
    if (head == NULL)
    {
        head = now = ptr;
        return ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}
static
char* getString(void)
{
    static char buffer[128];
    while (fgets(buffer, 128, stdin) != NULL)
    {
        char *nl = strchr(buffer, 'n');
        if (nl != 0)
            *nl = '';
        printf("Line: [[%s]]n", buffer);
        iNode(buffer);
    }
    return buffer;
}
int main(void)
{
    getString();
    printf("Total words: %d, total MTFR comparisons: %dn", uniqueWords, totalMTFRComparisons);
    Node2* ptr2 = head;
    Node2* tmp2 = head;
    while (ptr2 != NULL)
    {
        printf("Freeing: [[%s]]n", ptr2->word);
        tmp2 = ptr2->next;
        free(ptr2->word);
        free(ptr2);
        ptr2 = tmp2;
    }
}

它有一些诊断打印。换行符剥离意味着诊断输出比您在聊天中看到的要短，如果您费心查看聊天(字符串末尾有一个换行符 - 行被视为单词，包括换行符(。

ptr->word = malloc(strlen(word));

上行：不正确，内存很少，例如：strlen("hello"( = 5，而sizeof("hello"(会给你6

将行更改为

ptr->word = malloc(sizeof(word));

然后在 strcpy 之后将正常工作

聊天后

相关内容

最新更新

热门标签：

C语言 链表无限循环

聊天后

相关内容

最新更新

热门标签：

C语言链表无限循环