链表搜索不起作用（SIGBUS 错误和内存泄漏）

Linked List Search not working (SIGBUS error and memory leak)

提问人： 提问时间：8/24/2022 更新时间：8/24/2022 访问量：90

问：

我制作了一个实现链表的 C 程序，但它不起作用......我实现的所有内容都取自网站或 stackoverflow，它似乎对每个人都有效，但仍然对我不起作用。 每次我运行程序（它在 STDIN 中输入一系列单词，一个用于行）它给我并调试它时，它似乎卡在搜索功能中的行中......我哪里错了？我想有一些与指针有关的东西，但我不明白是什么。 程序开始工作并打印一些东西，然后中断，值没有，因为它说。Process finished with exit code 138 (interrupted by signal 10: SIGBUS)if (strcmp(var->word, searched) == 0)tempwordread memory from 0x6c62430000600000 failed (0 of 1 bytes read)

代码如下：

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


struct node{
    char* word;
    struct node* next;
};

int search(struct node** head, char* searched);
void Print(struct node* head);
void Free_All(struct node* head);
void Insert(struct node** head, char* word);
void Delete(struct node* head, char* to_delete);
int Count(struct node* head);


int main() {
    static struct node *head = NULL;

    int temp;
    char word[20];

    for (;;) {
        temp = scanf("%s", word);

        if (strcmp(word, "Print") == 0) {
            Print(head);
        }
        else if (strcmp(word, "Stop") == 0) {
            break;
        } 
        else if (temp == EOF) {
            Free_All(head);
            return 0;
        } 
        else {
            Insert(&head, word);
        }
    }

    scanf("%s", word);
    int found = search(&head, word);

    if (found == 0) {
        printf("!! ERROR !!");
        return 1;
    }

    else {
        char to_delete[15];
        scanf("%s", to_delete);
        Delete(head,to_delete);

        // DO OTHER STUFF
    }

    int count = Count(head);
    printf("Remaining nodes: %d",count);
    Free_All(head);
}




int search(struct node** head, char* searched) {
    struct node* var = *head;

    while (var != NULL) {
        if (strcmp(var->word, searched) == 0)
            return 1;
        var = var->next;
    }
    return 0;
}

void Print(struct node* head){
    struct node* temp = head;
    while (temp) {
        printf("%s \n", temp->word);
        temp = temp->next;
    }
}

void Free_All(struct node* head){
    struct node* temp;
    temp = head;

    while( temp != NULL ){
        head= head->next;
        free(temp);
        temp = head;
    }
}


void Insert(struct node** head, char* word)
{
    // Create new node
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->word = malloc(strlen(word)+1);
    new_node->word = strcpy(new_node->word,word);
    new_node->next = NULL;

    if (*head== NULL || strcmp((*head)->word, new_node->word) >= 0) {
        new_node->next = *head;
        *head= new_node;
    }
    else {
        struct node* temp = *head;
        temp = *head;
        while (temp->next != NULL && strcmp(temp->next->word, new_node->word) < 0) {
            temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
    }
}

void Delete(struct node* head, char* to_delete) {
    struct node *temp = head;
    struct node *prev = NULL;
    while(temp != NULL){
        if(strcmp(temp->word, to_delete) == 0)
        {
            if(prev == NULL){
                head = head->next;
                free(temp);
                return;
            }
            else{
                prev->next = temp->next;
                free(temp);
                return;
            }
        }
        prev = temp;
        temp = temp->next;
    }
}

int Count(struct node* head){
    int counter = 0;
    struct node* var = head;
    while (var != NULL)
    {
        counter++;
        var = var->next;
    }
    return counter;
}

编辑：解决了主要的错别字

C 表 单链列表 按值传递 函数定义

评论

1赞 Barmar 8/24/2022
如果他们进入，你就会打电话，因为它不是或EOF。Insert()PrintStop
0赞 WhozCraig 8/24/2022
^^^ IOW， WTB anelse
0赞 Fe2O3 8/24/2022
Delete( )接收头指针的 COPY，而不是头指针的地址。如果删除第一个条目，则 head in 指向无效内存。Insert（） 也好不到哪里去......拿一张纸和笔，画出你想要发生的事情......S-L-O-W-L-Y...main()
0赞 8/24/2022
@Fe2O3你能更好地解释一下你的意思吗？由于 Vlad 的帮助，我似乎解决了 Delete（），但我不明白 Insert（） 中的问题在哪里......不幸的是，我已经用纸和笔检查了很长时间，但我仍然被困住了，因为我对链表不是很熟悉。谢谢

答：

0赞 Vlad from Moscow 8/24/2022 #1

该函数按值接受指向头节点的指针Delete

void Delete(struct node* head, char* to_delete);

因此，该函数处理在 main 中声明的指针头值的副本

static struct node *head = NULL;

更改 main 中声明的指针头值的副本会使原始指针的值保持不变。

您需要通过指向指针的指针通过引用传递指针。

例如，可以按以下方式声明和定义函数。

int Delete( struct node **head, const char *to_delete ) 
{
    while ( *head != NULL && strcmp( ( *head )->word, to_delete ) != 0 )
    {
        head = &( *head )->next;
    }

    int success = *head != NULL;

    if ( success )
    {
        struct node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }

    return success;
}

注意这个for循环

for (;;) {
    temp = scanf("%s", word);

    if (strcmp(word, "Print") == 0) {
        Print(head);
    }

    if (strcmp(word, "Stop") == 0) {
        break;
    } else if (temp == EOF) {
        Free_All(head);
        return 0;
    } else {
        Insert(&head, word);
    }
}

逻辑错误。例如，如果用户将输入字符串，那么除了调用函数之外，还将调用该函数"Print"Print

Insert(&head, word);

而且这个功能实际上并没有释放所有人。它不会释放数据成员指向的字符数组。Free_Allword

void Free_All(struct node* head){
    struct node* temp;
    temp = head;

    while( temp != NULL ){
        head= head->next;
        free(temp);
        temp = head;
    }
}

该函数还应通过引用接受指向头节点的指针。它看起来像这样

void Free_All( struct node **head )
{
    while ( *head != NULL )
    {
        free( ( *head )->word );
        struct node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

评论

0赞 8/24/2022
感谢您的回复。对于主要的问题，这是一个错别字，我现在在编辑中解决了它。至于删除功能，我更改了它，仍然没有任何变化，它仍然停在搜索功能中，在高亮的行处。至于free_all函数，相反，如果我调试它给我并说它无法读取 （*head）->键SIGABRT (signal SIGABRT)
0赞 Vlad from Moscow 8/24/2022
@patosette 我在您的结构声明中没有看到任何名称为“key”的数据成员。
0赞 8/24/2022
对不起，我的意思是“单词”，它无法阅读（*头）->单词
0赞 8/24/2022
我检查了（输入单词后立即打印列表），我确定插入和打印功能正在工作，因此问题似乎出在搜索（以及基于搜索的删除）功能上
0赞 Vlad from Moscow 8/24/2022
@patosette 正如我所展示的，Search/Define 函数Free_All没有问题。
0赞 Fe2O3 8/24/2022 #2

我没有时间或耐心逐行检查您的代码出了什么问题。现在，删除列表中的第一项不会影响 'main（）' 中的“head”指针，因此使用该指针指向 or 是未定义的行为。Count()FreeAll()

下面是一些代码。使用铅笔和纸来跟踪正在使用的极少数变量，以及指针指向的位置。

void Print( struct node *p ) {
    for( ; p; p = p->next )
        printf( "%s ", p->word );
    putchar( '\n' );
}

void Insert( struct node **head, char *word ) {
    // assemble new node
    struct node *nn = (struct node*)malloc( sizeof node );
    nn->word = (char*)malloc( strlen( word ) + 1 );
    nn->word = strcpy( nn->word, word );
    nn->next = NULL;

    // find insertion point
    struct node *pPrev = NULL;
    struct node *pThis = *head;
    while( pThis && strcmp( word, pThis->word ) >= 0 )
        pPrev = pThis, pThis = pThis->next;

    // insert into (possibly empty) list
    if( pThis ) nn->next = pThis;
    if( pPrev ) pPrev->next = nn;
    if( pThis == *head ) *head = nn; // new head?
}

void Delete( struct node **head, char *word ) {
    struct node *pPrev = NULL;

    for( struct node *pThis = *head; pThis; pPrev = pThis, pThis = pThis->next ) {
        int res = strcmp( pThis->word, word );

        if( res < 0 ) // not found yet
            continue;
        if( res > 0 ) // gone beyond, so not present
            break;

        // Found!
        if( pPrev ) pPrev->next = pThis->next; // excise from list
        if( pThis == *head ) *head = pThis->next; // change head??
        free( pThis->word ); // release memory
        free( pThis ); // release memory
        break;
    }
}

int main() {
    struct node *head = NULL;

    char word[20];

    printf( "Entry phase:\n" );
    for( ;; ) {
        Print( head );

        scanf( "%s", word );

        if( strcmp( word, "Stop" ) == 0 )
            break;

        Insert( &head, word );
    }

    printf( "Delete phase:\n" );
    while( head ) {
        Print( head );

        scanf( "%s", word );

        if( strcmp( word, "Stop" ) == 0 )
            break;

        Delete( &head, word );
    }

    return 0;
}

输出：

Entry phase:

baker
baker
delta
baker delta
able
able baker delta
epsilon
able baker delta epsilon
charlie
able baker charlie delta epsilon
Stop
Delete phase:
able baker charlie delta epsilon
able
baker charlie delta epsilon
epsilon
baker charlie delta
charlie
baker delta
baker
delta
delta
{ program halts }

评论

0赞 8/24/2022
谢谢，我按照你的例子解决了一些问题......虽然还是不行，停在SIME线调试...我会再次敲打我的头检查，同时再次感谢

上一个：速度和动量 - 我不能走得太远

下一个：关于 Go 的地图和切片的设计问题让我很困扰