运行直到某个值链接列表

Question

我想对节点求和，直到达到0，并用新值更新原始链表。

注意：它跳过0，直到它达到一个要计算和的数字或链表的末尾。

节点定义：

struct Node {
int data;
Node* next;
};
void updateLinkedList(Node* head)
{
Node* currentNode = head;
int temp = 0;
int sum = 0;

while (currentNode != NULL)
{
    temp = currentNode->data;
    while(temp != 0)
    {
        sum = sum + currentNode->data;
        currentNode = currentNode->next;
    }
}
}

我正在尝试做下一件事：

用户输入链表：

1 2 0 5 3 0 4

更新的链表：

3 8 4

Answer 1

该函数可以通过以下方式实现

void updateLinkedList( Node * &head )
{
    for ( Node **current = &head; *current != nullptr; )
    {
        if ( ( *current )->data == 0 )
        {
            Node *tmp = *current;
            *current = ( *current )->next;
            delete tmp;
        }
        else
        {
            while ( ( *current )->next != NULL && ( *current )->next->data != 0 )
            {
                ( *current )->data += ( *current )->next->data;
                Node *tmp = ( *current )->next;
                ( *current )->next = ( *current )->next->next;
                delete tmp;
            }
            current = &( *current )->next;
        }
    }
}

这是一个示范节目。

#include <iostream>
struct Node
{
    int data;
    Node *next;
};
void clear( Node * &head )
{
    while (head != nullptr)
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}
void assign( Node * &head, const int a[], size_t n )
{
    clear( head );
    for (Node **current = &head; n--; current = &( *current )->next)
    {
        *current = new Node{ *a++, nullptr };
    }
}
std::ostream &display( const Node * const &head, std::ostream &os = std::cout )
{
    for (const Node *current = head; current != nullptr; current = current->next)
    {
        os << current->data << " -> ";
    }
    return os << "null";
}
void updateLinkedList( Node * &head )
{
    for (Node **current = &head; *current != nullptr; )
    {
        if (( *current )->data == 0)
        {
            Node *tmp = *current;
            *current = ( *current )->next;
            delete tmp;
        }
        else
        {
            while (( *current )->next != NULL && ( *current )->next->data != 0)
            {
                ( *current )->data += ( *current )->next->data;
                Node *tmp = ( *current )->next;
                ( *current )->next = ( *current )->next->next;
                delete tmp;
            }
            current = &( *current )->next;
        }
    }
}
int main()
{
    Node *head = nullptr;
    const int a[] = { 0, 0, 1, 2, 0, 5, 3, 0, 4 };
    const size_t N = sizeof( a ) / sizeof( *a );
    assign( head, a, N );
    display( head ) << 'n';
    updateLinkedList( head );
    display( head ) << 'n';
    clear( head );
}

程序输出为

0 -> 0 -> 1 -> 2 -> 0 -> 5 -> 3 -> 0 -> 4 -> null
3 -> 8 -> 4 -> null

Answer 2

在现代C++中，您很少希望直接处理内存分配。您通常会使用标准库或其他库中的类。这是因为很容易忘记一些东西，导致整个程序崩溃或造成内存泄漏。

熟悉内存分配并知道如何手动实现链表是很重要的。这是弗拉德的回答。

我想补充一点：在未来，您可能希望使用更高级别的功能。如果使用标准容器之一std::forward_list，我会这样编写函数。

void updateLinkedList(std::forward_list<int>& list)
{
    auto lastIt = list.before_begin();
    for (auto it = std::begin(list); it != std::end(list);)
    {
        if (*it)
        {
            lastIt = it++;
            int sum = *lastIt;
            while (it != std::end(list) && *it)
            {
                sum += *it;
                it++;
                list.erase_after(lastIt);
            }
            *lastIt = sum;
        }
        else
        {
            it++;
            list.erase_after(lastIt);
        }
    }
}

编辑：用于测试：

#include <forward_list>
#include <iostream>
void printList(const std::forward_list<int>& list)
{
    std::cout << "{ ";
    for (auto& i : list)
    {
        std::cout << i << ", ";
    }
    std::cout << "}n";
}
void updateLinkedList(std::forward_list<int>& list)
{
    auto lastIt = list.before_begin();
    for (auto it = std::begin(list); it != std::end(list);)
    {
        if (*it)
        {
            lastIt = it++;
            int sum = *lastIt;
            while (it != std::end(list) && *it)
            {
                sum += *it;
                it++;
                list.erase_after(lastIt);
            }
            *lastIt = sum;
        }
        else
        {
            it++;
            list.erase_after(lastIt);
        }
    }
}
int main() {
    std::forward_list list{
        0, 0, 1, 2, 0, 5, 3, 0, 0, 4, 0, 0, 0,
    };
    printList(list);
    updateLinkedList(list);
    printList(list);
}

在编译器资源管理器上。

Answer 3

在函数中，如果temp=0，因为没有在循环内的任何位置更新temp。currentNode指向的节点会更新，但temp指的是在进入内部while循环之前currentNode最初指向的节点所包含的值。