C：比较字符串

Question

我正在使用下面的代码将节点添加到双链表，并根据 word 按字母顺序排列它们。节点由 char * word、struct NODES * prev 和 struct NODES * next 组成。我运行遇到一个问题，在阅读 file testing a 之后，列表看起来像 NULL <- a <-> file <-> testing -> NULL 添加一个包含 word = c 的节点，它将 c 放在 [=20 之前=] 而不是介于 a 和 file 之间。该函数打印 "Add: Placing c before list head c" 并且似乎正在计算 c < a。但即使该评估不正确，我也不知道在进行任何节点操作之前它是如何替换 a 的。如果有人知道可能导致此问题的原因，我将不胜感激。 P.S。 incoming NODES * arg 始终采用 arg -> next == NULL; arg -> prev == NULL; arg -> word != NULL; 的形式，但如果尚未添加任何节点，列表可以将所有字段设为 NULL，list -> prev 在调用函数时应始终为 NULL 以及函数终止。

int addToList(struct NODES * list, struct NODES * arg){
fprintf(stderr,"Add: Adding %s\n", arg->word);
if(list->word == NULL){
    list->word = (char *)malloc(strlen(arg->word));
    strcpy(list->word, arg->word);
    list->next = NULL;
    list->prev = NULL;
    fprintf(stderr,"Add: Head %s\n", list->word);
    return 2;
}
struct NODES * abc = list;
while(abc->word != NULL){
    if(strcmp(abc->word, arg->word)<0){
        fprintf(stderr, "abc %s < arg %s", abc->word, arg->word);
        if (abc->next != NULL)
            abc = abc->next;
        else{
            abc->next = malloc(sizeof(NODE));
            abc->next->prev = abc;
            abc = abc->next;
            abc->next = NULL;
            abc->word = NULL;
        }
    }
    else if(abc == list){
        fprintf(stderr, "Add: Placing %s before list head %s\n", arg->word, list->word);
        arg->next = list;
        list->prev = arg;
        arg->prev = NULL;
        list = arg;
        fprintf(stderr, "Add: Placed %s before %s\n", list->word, list->next->word);
        return 3;
    }
    else{
        fprintf(stderr, "Add: Placing %s between %s and %s\n", arg->word, abc->word, abc->next->word);
        arg->next = abc;
        arg->prev = abc->prev;
        if(abc->prev != NULL)
            abc->prev->next = arg;
        abc->prev = arg;
        fprintf(stderr, "Added %s after %s and before %s\n", arg->word, arg->prev, arg->next->word);
        return 1;
    }
}
abc->word = (char *)malloc(strlen(arg->word));
strcpy(abc->word, arg->word);
fprintf(stderr, "Added %s after %s and before %s\n", abc->word, abc->prev->word, abc->next);
return 1;
}

已更新以反映建议：

int addToList(struct NODES ** list, struct NODES * arg){
fprintf(stderr,"Add: Adding %s current head %s\n", arg -> word, (*list)->word);
if((*list) -> word == NULL){
    (*list) -> word = malloc(strlen(arg->word)+1);
    strcpy((*list) -> word, arg -> word);
    (*list) -> next = NULL;
    (*list) -> prev = NULL;
    fprintf(stderr,"Add: Head %s\n", (*list) -> word);
    return 2;
}
struct NODES * abc = (*list);
//while arg > abc
fprintf(stderr,"Comparing %s and %s\n", abc->word,arg->word);
while(strcmp(abc->word, arg->word)<0){
    fprintf(stderr,"Comparing %s and %s\n", abc->word,arg->word);
    if (abc -> next == NULL)
        break;
    abc = abc -> next;
}
if (abc == (*list)){
    if(!(strcmp(abc->word, arg->word)<0)){
        arg -> next = abc;
        arg -> prev = NULL;
        abc -> prev = arg;
        *list = arg;
    }
    else{
        abc -> next = arg;
        arg -> prev = abc;
        abc -> next = NULL;
    }
    return 5;
}
if(abc -> next != NULL){
    fprintf(stderr, "Inserting %s between %s and %s\n", arg -> word, abc->prev->word,abc->word); 
    arg -> next = abc;
    arg -> prev = abc -> prev;
    arg -> prev -> next = arg;
    abc -> prev = arg;
    fprintf(stderr, "Added %s before %s and after %s\n", arg->word, arg->prev->word,arg->next->word);
    return 3;
}
return 0
}

Answer 1

我怀疑你的问题出在这里：

list->word = (char *)malloc(strlen(arg->word));
strcpy(list->word, arg->word);

由于您没有为终止空字符分配空间，以后对 strcmp 的调用将超出分配的缓冲区。这可能有各种行为，很可能也是您看到的行为。

此外，drop the (char *) cast，它可能会隐藏您的代码的其他问题。

Answer 2

函数接收的 list 参数是调用者拥有的列表指针的副本。对于 return 修改后的列表指针，函数可能是这样的：

int addToList(struct NODES ** list, struct NODES * arg)

它会被称为这样的东西：

result = addToList(&list, arg);

该函数将像这样提供一个新的列表指针

*list = arg;

并且您当前拥有的所有列表访问权限将更加间接

if(list->word == NULL)

会变成

if((*list)->word == NULL)

更新

试试这个简化的代码，我发现这比让我的头脑更容易。

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

struct NODES {
    struct NODES *prev;
    struct NODES *next;
    char *word;
};

void showList(struct NODES * list) {
    while (list) {
        if (list->prev)
            printf("%-10s", list->prev->word);
        else
            printf("%-10s", "NULL");
        printf(" <- %-10s -> ", list->word);
        if (list->next)
            printf("%-10s", list->next->word);
        else
            printf("%-10s", "NULL");
        printf("\n");
        list = list->next;
    }
}

int addToList(struct NODES ** list, char *word){
    struct NODES *wptr, *lptr = *list, *pptr = NULL;
    if ((wptr = malloc(sizeof(struct NODES))) == NULL)
        return -1;
    wptr->prev = NULL; 
    wptr->next = NULL;
    if ((wptr->word = strdup(word)) == NULL)
        return -2;

    if (lptr == NULL) {
        *list = wptr;                 // first list item
        return 0;
    }

    while (lptr) {
        if (strcmp(word, lptr->word) <= 0) {
            wptr->next = lptr;        // insert before current node
            wptr->prev = pptr;
            if (pptr)
                pptr->next = wptr;
            else
                *list = wptr;
            lptr->prev = wptr;
            return 1;
        }
        pptr = lptr;
        lptr = lptr->next;
    }

    wptr->prev = pptr;                // insert at tail
    pptr->next = wptr;
    return 2;
}

int main()
{
    struct NODES *list = NULL;
    addToList(&list, "one");
    addToList(&list, "two");
    addToList(&list, "three");
    addToList(&list, "four");
    addToList(&list, "five");
    showList(list);
    return 0;
}

程序输出：

NULL       <- five       -> four
five       <- four       -> one
four       <- one        -> three
one        <- three      -> two
three      <- two        -> NULL

C：比较字符串

C: Comparing Strings

c

sorting

doubly-linked-list

strcmp