时间戳

首页 > 解决方案 > 根据给定的子字符串删除多个字符串

c - 根据给定的子字符串删除多个字符串

问题描述

我正在尝试创建一个包含名称（例如Andy, Barry, Matilda）的代码，并且当我输入某个子字符串（例如子字符串是y时，名称将被删除，因此Andy 和 Barry将被删除。唯一的一个左边是玛蒂尔达）。任何人都可以为我提供帮助吗？

我的代码是：

void del(char key[]) 
{
    if(head == NULL)
    {
        printf("There's no data\n");
    }
    else{
        curr = head;
        while(curr != NULL && strcmp(curr->name, key) != 0)
        {
            curr = curr->next;
        }
        if(curr == NULL)
        {
            printf("Node is not in the list\n");
        }
        if(curr == head & curr == tail)
        {
            free(curr);
            head = tail = NULL;
        }
        else if(curr == head)
        {
            head = head->next;
            free(curr);
            head->prev = NULL;
        }
        else if(curr == tail)
        {
            tail = tail->prev;
            free(curr);
            tail->next = NULL;
        }
        else
        {
            curr->prev->next = curr->next;
            curr->next->prev = curr->prev;
            free(curr);
        }
    }
}

标签： cdata-structureslinked-list

解决方案

你没有提供很多信息来继续，但我认为这对社区来说是新的。根据您提供的内容，很明显，您至少有一个双向链接列表，其中有一个字符串作为数据成员。同样清楚的是，您已将 thehead和tail指针都声明为全局变量（这不是一个好习惯，因为您应该将函数所需的任何信息作为参数传递，但对于本学习练习，它提供了最小的简化）

根据您所描述的您希望您的del函数执行的操作，您想要遍历您的链表测试name成员是否包含子字符串key，如果是，您想要从列表中删除该节点。

你有两个主要问题：

  1. 您使用错误的字符串函数来检查name成员中的子字符串。strcmp()只会找到完整name匹配您的key. 相反，您希望在;中的任何位置都strstr()可以匹配。keyname
  2. 通过尝试单独使用指向当前节点的指针来迭代列表，而不是同时使用指针和当前节点的地址，您会使节点删除过于复杂。请参阅Linus 了解指针

要纠正您的拳头问题，您只需更改strcmp()为strstr()匹配中key的任何位置name，例如

        ...
        if (strstr(curr->name, key) != NULL) {  /* strstr, not strcmp, to find key */
            ...

要解决第二个问题，您需要重新编写del函数。为此，您必须了解在删除多个节点时进行迭代与通过迭代查找要删除的单个节点有何不同。当循环查找要删除的单个节点时，您只需在每次迭代中前进到列表中的下一个节点，直到找到该节点，然后删除该节点。

当可能从列表中删除多个节点时，您不能这样做。为什么？当您删除具有匹配子字符串的节点时，列表中的下一个节点将取代它。您不能只在此删除后前进到下一个节点，因为在您删除第一个节点后现在是当前节点的节点也可能包含您要查找的子字符串。如果您只是盲目地前进到下一个节点并且当前删除后还包含子字符串，您将跳过删除该节点。

从代码的角度来看，这意味着你需要在else你的下面添加一个子句if，例如

        if (strstr(curr->name, key) != NULL) {  /* strstr, not strcmp, to find key */
            ...
        else
            ...

根据您的if条款，下一个节点在删除后替换当前节点，因此您不会再次前进到列表中的下一个节点。这样，新的当前节点将在下一次迭代中检查匹配的子字符串。如果不匹配，您只会前进到您的else子句下的下一个节点。key

当同时使用指向当前节点的指针和当前节点的地址进行迭代时，您不必处理特殊情况。您将始终将当前地址的内容设置为列表中的下一个节点。（head不会改变，因为您已将该地址处的结构设置为删除时的下一个）您需要的唯一检查是检查您是否正在删除tail节点。在这种情况下，您需要更新tail节点以指向前一个节点，因为您将删除tail当前指向的内容。否则，您需要做的就是更新->prev您移动到当前地址的节点的指针，使其指向列表中的前一个节点。

考虑到这一点，您的del功能可简化为：

void del (char key[])
{
    if (head == NULL) {                         /* check empty */
        puts ("list-empty");
        return;
    }
    node_t  **ppnode = &head,                   /* address of current node */
            *curr = head;                       /* pointer to current node */

    while (curr) {
        if (strstr(curr->name, key) != NULL) {  /* strstr, not strcmp, to find key */
            *ppnode = curr->next;               /* fill address w/next node */
            if (curr != tail)                   /* if not tail */
                (*ppnode)->prev = curr->prev;   /* set ->prev to prev node */
            else    /* otherwise */
                tail = curr->prev;              /* update tail pointer */
            free (curr);                        /* free node */
            curr = *ppnode;                     /* set new current node */
        }
        else {  /* node to keep */
            ppnode = &curr->next;               /* set address to addres of next */
            curr = curr->next;                  /* advance to next node */
        }
    }
}

在不了解您的代码的更多信息的情况下，我们所能做的就是编写一个简短的示例，将您的字符串作为节点添加到列表中（使用固定name来简化事情）。一个简短的例子，如：

int main (void) {

    add ("Andy");           /* add nodes to list */
    add ("Barry");
    add ("Matilda");

    prnfwd();               /* print forward and reverse */
    prnrev();
    putchar ('\n');

    del ("y");              /* delete nodes containing substring "y" */

    prnfwd();               /* print forward and reverse */
    prnrev();

    del_list();             /* free allocated memory */
}

添加节点，在两个方向上迭代列表，调用del ("y");删除字符串包含子字符串的所有节点"y"（注意与字符不同'y'），然后在两个方向上再次迭代列表，在释放所有之前输出剩​​余的内容列表中的内存。

示例使用/输出

给定示例字符串的结果将是：

$ ./bin/lldglobaldelkey
 Andy Barry Matilda
 Matilda Barry Andy

 Matilda
 Matilda

该示例的完整实现是：

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

#define MAXNM 64

typedef struct node_t {
    char name[MAXNM];
    struct node_t *prev, *next;
} node_t;

node_t *head, *tail;

/** add node at end of list, update tail to end */
node_t *add (const char *s)
{
    node_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node)                              /* validate allocation */
        return NULL;

    strcpy (node->name, s);                 /* initialize new node */
    node->prev = node->next = NULL;

    if (!head)                              /* if 1st node, node is head/tail */
        head = tail = node;
    else {                                  /* otherwise */
        node->prev = tail;                  /* set prev to tail */
        tail->next = node;                  /* add at end, update tail pointer */
        tail = node;
    }

    return node;    /* return new node */
}

/* print list forward */
void prnfwd (void)
{
    if (!head) {                            /* check empty */
        puts ("list-empty");
        return;
    }

    for (node_t *n = head; n; n = n->next)  /* iterate over nodes - forward */
        printf (" %s", n->name);
    putchar ('\n');
}

/* print list reverse */
void prnrev (void)
{
    if (!head) {                            /* check empty */
        puts ("list-empty");
        return;
    }

    for (node_t *n = tail; n; n = n->prev)  /* iterate over nodes - reverse */
        printf (" %s", n->name);
    putchar ('\n');
}

/** delete all nodes in list */
void del_list (void)
{
    node_t *n = head;

    if (!head) {                            /* check empty */
        puts ("list-empty");
        return;
    }

    while (n) {                             /* iterate over nodes - forward */
        node_t *victim = n;                 /* save ptr to node to delete */
        n = n->next;                        /* advance to next */
        free (victim);                      /* delete node */
    }

    head = tail = NULL;                     /* set pointers NULL */
}

void del (char key[])
{
    if (head == NULL) {                         /* check empty */
        puts ("list-empty");
        return;
    }
    node_t  **ppnode = &head,                   /* address of current node */
            *curr = head;                       /* pointer to current node */

    while (curr) {
        if (strstr(curr->name, key) != NULL) {  /* strstr, not strcmp, to find key */
            *ppnode = curr->next;               /* fill address w/next node */
            if (curr != tail)                   /* if not tail */
                (*ppnode)->prev = curr->prev;   /* set ->prev to prev node */
            else    /* otherwise */
                tail = curr->prev;              /* update tail pointer */
            free (curr);                        /* free node */
            curr = *ppnode;                     /* set new current node */
        }
        else {  /* node to keep */
            ppnode = &curr->next;               /* set address to addres of next */
            curr = curr->next;                  /* advance to next node */
        }
    }
}

int main (void) {

    add ("Andy");           /* add nodes to list */
    add ("Barry");
    add ("Matilda");

    prnfwd();               /* print forward and reverse */
    prnrev();
    putchar ('\n');

    del ("y");              /* delete nodes containing substring "y" */

    prnfwd();               /* print forward and reverse */
    prnrev();

    del_list();             /* free allocated memory */
}

内存使用/错误检查

在您编写的任何动态分配内存的代码中，对于分配的任何内存块，您有 2 个责任：（1）始终保留指向内存块起始地址的指针，（2）它可以在它不存在时被释放更需要。

您必须使用内存错误检查程序，以确保您不会尝试访问内存或写入超出/超出分配块的范围，尝试读取或基于未初始化值的条件跳转，最后确认释放所有分配的内存。

对于 Linuxvalgrind是正常的选择。每个平台都有类似的内存检查器。它们都易于使用，只需通过它运行您的程序即可。

$ valgrind ./bin/lldglobaldelkey
==10704== Memcheck, a memory error detector
==10704== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10704== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==10704== Command: ./bin/lldglobaldelkey
==10704==
 Andy Barry Matilda
 Matilda Barry Andy

 Matilda
 Matilda
==10704==
==10704== HEAP SUMMARY:
==10704==     in use at exit: 0 bytes in 0 blocks
==10704==   total heap usage: 4 allocs, 4 frees, 1,264 bytes allocated
==10704==
==10704== All heap blocks were freed -- no leaks are possible
==10704==
==10704== For counts of detected and suppressed errors, rerun with: -v
==10704== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认您已释放所有已分配的内存并且没有内存错误。

我希望这接近你的实现。如果您还有其他问题，请仔细查看并告诉我。

推荐阅读