使用head_return和tail_return从链表中查找和删除

Question

我正在处理一个链表示例。我在查找和删除函数，它遍历列表以查找特定元素。find_remove函数不起作用。应用程序中的所有其他函数(head_return、tail_return等)

如果有人能指出我在find_remove中哪里出了问题，我将不胜感激。

#include <iostream>
using namespace std;
struct node_ll
{
    int payload;
    node_ll* next;//Pointer to the next node
};
void head_insert(node_ll** list, int pload)
{
    node_ll* temp = new node_ll;//Create a new node, and let temp be the address of that node.
    temp->payload = pload;//Set the payload of the struct whose address is temp to pload.
    temp->next = *list;//Set the next of the struct whose address is temp to the address of the old head of the list.
    *list = temp;//The address of the old head of the list is changed to the address of the struct temp.
};
void tail_insert(node_ll** list, int pload)
{
    if (*list == NULL)
    {
        head_insert(list, pload);
    }
    else
    {
        node_ll* temp = new node_ll;
        for (temp = *list; temp->next; temp = temp->next);
        temp->next = new node_ll;
        temp->next->payload = pload;
        temp->next->next = NULL;
    }
}
int head_return (node_ll** list)
{
    if (*list != NULL)
    {
    int temp = (*list)->payload;
      node_ll* trash = *list;
      *list = (*list)->next;
      delete trash;
      return temp;
    }
    else
    {
        return 0;
    }
}
int tail_return (node_ll** list)
{
    if (*list != NULL)
    {
      if ((*list)->next == NULL)
        {
            return head_return(list);
        }
        else
        {
      node_ll* trash;
            for (trash = *list; trash->next->next; trash = trash->next);
            int temp = trash->next->payload;
            delete trash->next;
            trash->next = NULL;
            return temp;
        }
    }
    else
    {
        return 0;
    }
}
void find_remove (node_ll** list, int pload)
{
    if (*list != NULL)
    {
        node_ll* temp;//Declared before loop for use after loop.
        for (temp = *list; temp->next; temp = temp->next)
        {
            if (temp->payload == pload)
            {
                int trash = head_return(&temp);
            }
        }
        if (temp->payload == pload)
        {
            int trash = tail_return(list);
        }
    }
}
void print_ll (node_ll** list)
{
  node_ll* temp = *list;//Let temp be the address of the node that is the head of the list.
    while(temp)// != NULL
    {
        cout << temp->payload << endl;//Print out payload of the struct whose address is temp.
        temp = temp->next;//Set the address of temp equal to the address stored in next of the struct whose address is temp.
    }
}
int main()
{
    node_ll *blist = NULL;
    tail_insert(&blist, 2);
    tail_insert(&blist, 4);
    tail_insert(&blist, 6);
    find_remove(&blist, 4);
    print_ll(&blist);
    cout << 'n';
    system("PAUSE");
    return 0;
}

编辑:

这是我重写你代码的尝试。

void find_remove (node_ll** list, int pload)
{
    if (*list != NULL)
    {
        while (*list && (*list)->payload == pload)
        {
            head_return(list);
        }
        if (*list != NULL)
        {
            node_ll* temp;
            for (temp = *list; temp->next->next; temp = temp->next)
            {
                if (temp->next->payload == pload)
                {
                    node_ll* trash = temp->next;
                    temp->next = temp->next->next;
                    head_return(&trash);
                }
            }
        }
    }
}

编辑2:谢谢你！如果在开始处有多个匹配节点，在中间有多个匹配节点或在结束处有多个匹配节点，则此新解决方案有效。

void find_remove (node_ll** list, int pload)
{
    if (*list != NULL)
    {
        while (*list && (*list)->payload == pload)
        {
            head_return(list);
        }
        if (*list != NULL)
        {
            node_ll* temp;
            for (temp = *list; temp->next; temp = temp->next)
            {
                while (temp->next->next != NULL && temp->next->payload == pload)
                {
                    node_ll* trash = temp->next;
                    temp->next = temp->next->next;
                    head_return(&trash);
                }
            }
            if (temp->next == NULL && temp->payload == pload)
            {
                tail_return(list);
            }
        }
    }
}

Answer 1

崩溃是由于你的循环逻辑不正确，你也没有保持跟踪前一个节点，这意味着你没有正确地重置链表，这是最简单的修复:

void find_remove (node_ll** list, int pload)
{
    if (*list != NULL)
    {
        node_ll* temp, *prev=NULL;//Declared before loop for use after loop.
        for (temp = *list; temp != NULL; temp = temp->next)
        {
            if (temp->payload == pload)
            {
               if( NULL != prev )
               {
                  prev->next = temp->next ;
               }
                int trash = head_return(&temp);
            }
            prev=temp ;
         }
   }
}

虽然老实说，代码有很多风格问题，更像C风格的代码而不是c++风格的代码。你可以考虑查看Code Review。

更新:

如果你在修改后的代码中修改了它，它就可以工作了:

for (temp = *list; temp->next != NULL; temp = temp->next)
                   ^^^^^^^^^^^^^^^^^^

在循环的顶部，您永远不知道temp->next是否为NULL，因此执行temp->next->next永远无效。