单链表节点字符出现次数统计：插入时定位目标节点的疑问

Hey there! Let's work through this problem step by step. I see you're building a singly linked list to track character occurrence counts, and you're stuck on targeting existing nodes when inserting duplicates. Let's fix this together—your core idea is solid, we just need to tweak the implementation details.

First, Let's Spot the Key Issues in Your Current Code #

Before jumping to fixes, let's call out the critical problems that are blocking you:

• Broken isAvailable() function: Right now, you're creating a new empty node instead of traversing your existing list. The loop logic is also invalid (you return before moving to the next node, and setting floatingNode->next = floatingNode creates an infinite loop).
• Undeclared tail member: Your set class uses a tail pointer but never declares it in the private section—this will throw a compile error.
• Invalid insert() logic: You're initializing newNode with placeholder parameters (char d, int c) which isn't valid syntax, and you're trying to access data directly without referencing a node instance.
• Redundant work: Even if isAvailable() worked, you'd have to traverse the list twice (once to check existence, once to find the node to update) which is inefficient.

Let's Rewrite the Code with Fixes #

We'll adjust the code to make node lookup direct, simplify the insert logic, and fix all compile errors. Here's the revised version with explanations:

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

class Snode {
public:
    char data;
    int count;
    Snode *next;
    // Simplified constructor with member initializer list
    Snode(char d, int c) : data(d), count(c), next(nullptr) {}
};

class set {
private:
    Snode *head;
    Snode *tail; // Added: declare tail since we use it in insert
public:
    set() : head(nullptr), tail(nullptr) {} // Clean initialization syntax
    ~set();
    void insert(char value);
    bool isAvailable(char value);
private:
    // Helper function: finds and returns the node with the given char (or nullptr if not found)
    Snode* findNode(char value) {
        Snode *current = head;
        while (current != nullptr) {
            if (current->data == value) {
                return current; // Return matching node immediately
            }
            current = current->next;
        }
        return nullptr; // No match found
    }
};

set::~set() {
    // Your destructor logic was correct—keep it!
    Snode *t = head;
    while (t != nullptr) {
        head = head->next;
        delete t;
        t = head;
    }
}

// Reuse findNode to implement isAvailable
bool set::isAvailable(char value) {
    return findNode(value) != nullptr;
}

void set::insert(char value) {
    // First, check if the character already exists
    Snode* existingNode = findNode(value);
    if (existingNode != nullptr) {
        // Case 2: Character exists—just increment the count
        existingNode->count++;
        return;
    }

    // Case 1: Character doesn't exist—create a new node
    Snode *newNode = new Snode(value, 1); // Initialize with target char and count=1
    if (head == nullptr) {
        // Empty list: head and tail both point to the new node
        head = newNode;
        tail = newNode;
    } else {
        // Add new node to the end of the list
        tail->next = newNode;
        tail = newNode;
    }
}

Key Improvements Explained #

• findNode() helper: This function handles traversal once, returning the matching node directly. This avoids the inefficiency of traversing the list twice (once to check existence, once to update the count).
• Simplified insert logic: We first check for an existing node. If found, we just increment its count. If not, we create a new node and add it to the list (handling empty and non-empty cases correctly).
• Fixed compile errors: Added the missing tail member to the set class, fixed constructor syntax, and removed invalid placeholder parameters.
• Cleaner initialization: Used member initializer lists in constructors for more readable and efficient code.

Testing with Your Example #

If you insert the sequence a, a, b, b, c, a:

1. First a: creates a new node [a, 1] (head and tail point to it)
2. Second a: finds the existing node, increments count to 2
3. First b: creates new node [b, 1], adds to tail
4. Second b: increments count to 2
5. c: creates new node [c, 1], adds to tail
6. Third a: increments count to 3

Resulting in the linked list you wanted:
[a,3] -> [b,2] -> [c,1] -> nullptr

内容的提问来源于stack exchange，提问作者nitwit