0

リンクされたリストを使用して、コンコーダンス プログラムを実装しています。同じ単語が複数回読み取られる場合は、現在のノードを削除し、カウントを増やして、新しいノードを追加する必要があります。このプログラムにこれ以上機能を追加することはできません。どうにかして get_count を使用する必要があると考えていますが、よくわかりません。

たとえば、次のようにする代わりに:

ザ 1
ザ 1

そのはず：

THE 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
}

ただし、許可されている場合は、代わりに a を使用することを強くお勧めします。std::mapこれは、実質的にすべてが処理されるためです。

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

これらの 2 行のコードは、実質的にすべての連結リスト コードを置き換えることができます。追加の利点は、線形検索が必要な連結リストではなく、マップがバイナリ ツリーを使用するため、ルックアップがはるかに高速になることです。

C++11 コンパイラを使用している場合は、unordered_mapハッシュ テーブルを使用するものを使用することもできます。マップ内の要素はソートされていないため、さらに高速になります。

于 2013-09-25T01:31:23.047 に答える