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

Question

我正在编写一个简单的应用程序，它获取 list 并将对象保存为 nodes 在 单链表 中，我们可以 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() 检查数据是否已经在列表中。

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

数据还没有输入：所以我们必须用给定的数据创建一个newNode，count=1和*next=NULL。
数据已经输入：所以我们必须count++具有相同数据的节点。

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

代码如下：

#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;
   }
}

为什么这个函数要分配一个new Snode？它没有理由这样做，只需将 floatingNode 指针初始化为指向 head 即可。
此函数总是 returns 在仅查看链表中的第一个节点之后——这不是您想要的行为。相反，它应该 return 只有在 (value == floatingNode) 时才为真；否则它应该留在 while 循环内，以便它也可以继续查看后续节点。只有在它退出 while 循环后（因为 floatingNode 最终变为 NULL）才应该 return false.
如果您要稍微修改 isAvailable()，那么 return 将 true 或 false 改为 return 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]
   }
}

Answer 2

您的代码中有很多问题，让我们看看它们是什么：

首先，Snode不需要是class，你可以使用简单的strcut；因为我们需要一切 public。（不是错误，而是很好的做法）
你可以简单地初始化 count = 1 和 next = nullptr，这样就不需要初始化它们抛出构造函数。唯一需要通过构造函数初始化的元素是Snod的data.
因为 c++11 你可以使用关键字 nullptr 而不是 NULL，它表示 pointer literal.
成员函数bool set::isAvailable(char value)不会像你想的那样起作用。在这里你不必要地创建了一个 new Snode 并检查它是否指向 nullptr 这甚至不允许你进入循环。顺便说一句，你在循环中写的也错了。 return (value == floatingNode); 是什么意思？ floatingNode 是类型 Snode；不是 char.

听说是正确的实施。由于我们不想覆盖头部，因此将创建一个 Node* 指针并将 head 分配给它。然后遍历列表，直到找到匹配项。如果没有找到，我们将到达isAvailable()和false.return.

的结尾

     inline bool isAvailable(const char& value)
     {
         Node *findPos = head;

         while(findPos != nullptr)
         {
             if(findPos -> data == value) return true;
             else findPos = findPos->next_node;
         }
         return false;
     }

在void set::insert(char value)中，你的逻辑是正确的，但是实现是错误的。以下是正确的实现方式。（希望评论能帮助大家理解。

void insert(const char& value)
{
    if(head == nullptr) // first case
    {
        Node *newNode = new Node(value);
        newNode->next_node = head;
        head = newNode;
    }
    else if(isAvailable(value)) // if node available
    {
        Node *temp = head;
        while(temp->data != value)  // find the node
            temp = temp->next_node;
        temp->count += 1;           // and count it by 1
    }
    else                            // all new nodes
    {
        Node *temp = head;
        while(temp->next_node != nullptr) // to find the null point (end of list)
            temp = temp->next_node;

        temp = temp->next_node = new Node(value); // create a node and assign there
    }
}

您的析构函数不会删除您创建的所有内容。它将是 UB，因为您正在删除新创建的 Snode t（即 Snode *t = head;）。正确的实现如下。（取消注释调试消息以理解。）

   ~set()
    {
        Node* temp = head;
        while( temp != nullptr )
        {
            Node* next = temp->next_node;
            //std::cout << "deleting \t" << temp->data << std::endl;
            delete temp;
            temp = next;
        }
        head = nullptr;
    }

最后但并非最不重要的一点是，这里的命名 (set) 与代码的确切作用是不同的。这看起来更像是一个没有重复项的简单链表。不过这没关系，为了玩弄指针和列表。

为了使代码或迭代更高效，您可以执行如下操作。在 isAvailable() 中，如果值匹配/如果您找到 node，您也可以简单地增加其计数。那么在insert()中，你可以想到，如果node是不是可用的部分。

希望这对您有所帮助。看到一个DEMO

#include <iostream>

// since you wanna have all of Node in public, declare as struct
struct Node
{
    char data;
    int count = 1;
    Node*  next_node = nullptr;
    Node(const char& a) // create a constrcor which will initilize data
        : data(a) {}    // at the time of Node creation
};

class set
{
private:
    Node *head;             // need only head, if it's a simple list
public:
    set()   :head(nullptr) {}   // constructor set it to nullptr
    ~set()
    {
        Node* temp = head;
        while( temp != nullptr )
        {
            Node* next = temp->next_node;
            //std::cout << "deleting \t" << temp->data << std::endl;
            delete temp;
            temp = next;
        }
        head = nullptr;
    }

    inline bool isAvailable(const char& value)
    {
        Node *findPos = head;

        while(findPos != nullptr)
        {
            if(findPos -> data == value) return true;
            else findPos = findPos->next_node;
        }
        return false;
    }

    void insert(const char& value)
    {
        if(head == nullptr) // first case
        {
            Node *newNode = new Node(value);
            newNode->next_node = head;
            head = newNode;
        }
        else if(isAvailable(value)) // if node available
        {
            Node *temp = head;
            while(temp->data != value)  // find the node
                temp = temp->next_node;
            temp->count += 1;           // and count it by 1
        }
        else                            // all new nodes
        {
            Node *temp = head;
            while(temp->next_node != nullptr) // to find the null point (end of list)
                temp = temp->next_node;

            temp = temp->next_node = new Node(value);
        }
    }

    void print() const      // just to print
    {
        Node *temp = head;
        while(temp != nullptr)
        {
            std::cout << temp->data << " " << temp->count << "\n";
            temp = temp->next_node;
        }
    }
};


int main()
{
    ::set mySet;

    mySet.insert('a');
    mySet.insert('a');
    mySet.insert('b');
    mySet.insert('b');
    mySet.insert('c');
    mySet.insert('a');

    mySet.print();

    return 0;
}

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

Counting occurrence in singly linked list by nodes

c++

algorithm

data-structures

singly-linked-list

c++11