c++ - 按节点计算单链表中的出现次数

Question

我正在编写一个简单的应用程序，它获取一个列表并将对象保存为单链表中的节点，我们可以add()、remove()、copy() 等每个节点取决于给定的数据集。每个节点都有一个 char value，这是我们的数据，还有一个 int count，它计算相关 char 的出现。

例如对于像

这样的列表

a, a, b, b, c, a

将有三个节点(因为有三个不同的字符)，它们是:

[a,3,*next] -> [b,2,*next] -> [c,1,*next] -> nullptr

bool isAvailable() 检查数据是否已经在列表中。

问:插入数据时有两种选择:

1. 数据还没有输入:所以我们必须用给定的数据创建一个newNode，count=1和*next=NULL .

2. 数据已经输入:所以我们必须count++具有相同数据的节点。

我知道给定的数据是否可用，但如何指向具有相同数据的节点？

代码如下:

#include "stdafx.h"
#include<iostream>
using namespace std;

class Snode
{
public:
    char data;
    int count;
    Snode *next;
    Snode(char d, int c)
    {
        data = d;
        count = c;
        next = NULL;
    }
};

class set
{
private:
    Snode *head;
public:
    set()
    {
        head = NULL;
        tail = NULL;
    }
    ~set();
    void insert(char value);
    bool isAvailable(char value);
};

set::~set()
{
    Snode *t = head;
    while (t != NULL)
    {
        head = head->next;
        delete t;
    }
}

bool set::isAvailable(char value)
{
    Snode *floatingNode = new Snode(char d, int c);
    while(floatingNode != NULL)
    {
        return (value == floatingNode);
        floatingNode->next = floatingNode;
    }
}

void set::insert(char value)
{
    Snode *newNode = new Snode(char d, int c);
    data = value;
    if (head == NULL)
    {
        newNode->next = NULL;
        head = newNode;
        newNode->count++;
    }
    else
    {
        if(isAvailable)
        {
            //IDK what should i do here +_+
        }
        else
        {
            tail->next= newNode;
            newNode->next = NULL;
            tail = newNode;
        }
    }
}

Answer 1

I know if the given data is available or not, but how can I point to the node with same data?

您需要从列表的头部开始，并按照 next 指针遍历列表，直到找到具有相同 data 值的节点。完成此操作后，您将获得指向具有相同数据的节点的指针。

一些其他的注意事项:

bool set::isAvailable(char value)
{
   Snode *floatingNode = new Snode(char d, int c);
   while(floatingNode != NULL)
   {
       return (value == floatingNode);
       floatingNode->next = floatingNode;
   }
}

1. 为什么这个函数要分配一个新节点？它没有理由这样做，只需将 floatingNode 指针初始化为指向 head。

2. 此函数总是在仅查看链表中的第一个节点后返回——这不是您想要的行为。相反，它应该仅在 (value == floatingNode) 时返回 true；否则它应该留在 while 循环内，以便它也可以继续查看后续节点。只有在退出 while 循环后(因为 floatingNode 最终变为 NULL)它才应该返回 false。

3. 如果您要稍微修改 isAvailable()，它不会返回 true 或 false，而是返回 floatingPointer 或 NULL，您将拥有查找指向具有匹配数据的节点的指针的机制。

例如:

// Should return either a pointer to the Snode with data==value,
// or NULL if no such Snode is present in the list 
Snode * set::getNodeWithValueOrNullIfNotFound(char value) const
{
   [...]
}

void set::insert(char value)
{
   Snode * theNode = getNodeWithValueOrNullIfNotFound(value);
   if (theNode != NULL)
   {
      theNode->count++;
   }
   else
   {
      [create a new Snode and insert it]
   }
}