0

我正在使用链接列表来实现索引程序。如果多次读取同一个词，我需要删除当前节点，增加计数，并添加一个新节点。我无法向该程序添加更多功能。我想我必须以某种方式使用 get_count ，但我不确定。

例如，而不是看起来像这样：

第 1
个 第 1 个

它应该是：

2

我怎样才能做到这一点？提前致谢！

头文件：

#ifndef CONCORDANCE_H
#define CONCORDANCE_H

#include <iostream>
#include <cstdlib>

const int MAX = 8;

class Concordance
{
    public:
        typedef char Word[MAX+1];

        // CONSTRUCTOR
        Concordance()
        {
            first = NULL;
        }

        // DESTRUCTOR
        ~Concordance();

        // MODIFICATION MEMBER FUNCTIONS
        void insert(Word& word, int& n);
        void remove(Word& word);
        int get_count(Word& word);

        // OTHER FUNCTIONS
        int length() const;
        friend std::ostream& operator << (std::ostream& out_s, Concordance& c); 

    private:
        // NODE STRUCT
        struct Node
        {
            Word wd;
            int count;
            Node *next;
        };
        Node *first;    

        // GET_NODE FUNCTION
        Node* get_node(Word& word, int& count, Node* link);   
};

#endif

班级：

//class definition
#include "concordance.h"
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;

Concordance::~Concordance()
{
    Node *temp;
    while(first != NULL)
    {
        temp = first;
        first = first -> next;
        delete temp;
    }
}

void Concordance::insert(Word& word, int& n)
{
    Node *prev;

    if(first == NULL || strcmp(first -> wd, word) > 0)
        first = get_node(word, n, first);
    else
    {
        prev = first;

        while(prev -> next != NULL && strcmp(prev -> next -> wd, word) < 0)
            prev = prev -> next;

        prev -> next = get_node(word, n, prev -> next);
    }
}

void Concordance::remove(Word& word)
{
    Node *prev, *temp;
    prev = temp;

    if(prev -> wd == word)
    {
        first = first -> next;
        delete prev;
    }

    else
    {
        while(strcmp(prev -> next -> wd, word) > 0)
        prev = prev -> next;
        temp = prev -> next;
        prev -> next = temp -> next;
        delete temp;
    }

}

int Concordance::get_count(Word& word)
{
    while(strcmp(first -> wd, word) != 0)
        first = first -> next;

    return first -> count;
}

int Concordance::length() const
{
    Node *cursor;
    int length;

    length = 0;
    for(cursor = first; cursor != NULL; cursor = cursor -> next )
      length++;
    return length;
}

Concordance::Node* Concordance::get_node (Word& word, int& count, Node* link)
{
    Node *temp;

    temp = new Node;
    strcpy(temp-> wd, word);
    temp-> next = link;
    temp -> count = count+1;
    return temp;
}

ostream& operator << (ostream& out_s, Concordance& c)
{
    Concordance::Node *output;

    out_s << "Word" << setw(10) << " " << "Count" << setw(8) << endl;
    out_s << "--------------------" << endl;

    for(output = c.first; output != NULL && output->next != NULL; output = output-> next )
        out_s << left << setw(10) << output-> wd << right << setw(9) << output -> count << endl;

    if(output != NULL)
        out_s << output-> wd << setw(13) << " " << output -> count << endl;
    out_s << "--------------------" << endl;

    return out_s;
}
4

1 回答 1

0

基本上，您需要在列表中搜索现有单词，如果找到，只需增加现有节点结构中的计数：

Node* existing = first;
while (strcmp(existing->wd, word) != 0)
    existing = existing->next;
if (existing)
    ++existing->count;
else
{
    // not already existing, so add new node
}

但是，如果您被允许，我强烈建议您使用 astd::map代替 - 因为实际上所有事情都会为您处理：

std::map<std::string, int> mapWords;
// for each word:
++mapWords[word];

这两行代码几乎可以替换所有链表代码，另外一个好处是查找会更快，因为地图使用二叉树而不是必须线性搜索的链表。

如果你有一个 C++11 编译器，你也可以使用unordered_map它使用哈希表并且可以更快，因为地图中的元素没有保持排序。

于 2013-09-25T01:31:23.047 回答