リストに文字列を昇順に追加

[問題]
ファイルやキーボードから入力された単語とその出現回数をノードに持ち，単語のアルファベット順に連
結された以下に示すような単方向連結リスト WordCountListl クラスを新たに作成します。このリストでは，リストにない単語が挿入されると，新たにノードが挿入される，それ以外は，出現回数を更新する

プログラムは以下のようになっています。

#include<iostream>
#include<fstream>

using namespace std;
class WordCountList{ //　単語とその出現回数をノードにもち，アルファベット順につなげた連結リスト
 private:
  class Node{
  public:
    string word; // 単語
    int count;   //出現回数
    Node *next;
    Node(string s="", int ct=0,  Node *np=NULL){word=s; count=ct; next=np;}	
    ~Node(){cout<<word<<" has been deleted..."<<endl;}
  };
  Node *head;    //連結リストの先頭ポインタ		
  int node_num;  // 連結リストにあるノードの個数
 
  void clear(); //ノードを全て削除

 public: 
  WordCountList(){ head=NULL; node_num=0; }
  ~WordCountList(){ clear(); };
  int size() const{ return node_num; }; 
  void insert(string w); // 単語を挿入. すでにあれば，出現回数をインクリメント
  void remove(string w); //　単語を削除. 1回減算，或は，ノード削除 
  void print() const; //単語と出現回数をアルファベット順に昇順表示
  void printR() const; //単語と出現回数をアルファベット順とは反対に降順表示
};
void WordCountList::clear(){
    Node *ptr = head, *tmp;
    while(ptr!=NULL){
        tmp = ptr->next;
        delete ptr;
        ptr = tmp;
    }
}
void WordCountList::insert(string w){
    Node *ptr = head;
    if (head==NULL || head->word > w){
        head = new Node(w, head->count, head);
        head->count++;
    }
    else{
        while(ptr->next != NULL){
            if(ptr->next->word ==w){
                ptr->next->count++;
                return;
            }
            if(ptr->next->word > w){
                ptr->next = new Node(w, ptr->next->count, ptr->next);
                ptr->next->count++;
                return;
            }
            ptr = ptr->next;
        }
        ptr->next = new Node(w, ptr->next->count, ptr->next);
    }
}

void WordCountList::remove(string w){
    if(head==NULL) return;
	  else if(head->word==w){
		    Node *ps=head;
		    head=head->next;
		    delete ps;
	  }
	  else{
		    Node *pb=0;
		    for(Node *ps=head;ps;ps=ps->next){
			      if(ps->word==w){
				    pb->next=ps->next;
				    delete ps;
				    return;
			  }
			  pb=ps;
		}
	  cout<<w<<" cannot be found"<<endl;
	}
}

void WordCountList::print() const{
    for(Node *p=head;p;p=p->next){
		    cout<<p->word<< "(" << p->count << ") ";
	  }
}

void WordCountList::printR() const{
  Node *ptr=head,*swap;
  while(ptr->next != NULL){
      ptr = ptr->next;
  }
  Node *tmp=head;
  while(tmp!=ptr){
      swap = tmp->next;
      if(ptr->next==NULL){
        cout<<ptr->word<< "(" << ptr->count << ") ";
        ptr->next = tmp;
        tmp->next = NULL;
      }
      else{
        cout<<ptr->word<< "(" << ptr->count << ") ";
        tmp->next = ptr->next;
        ptr->next = tmp;
      }
      tmp = swap;
  }
}
int main(){
  int stop=0; // loop stop flag; 
  int n, ct, num;				
  char  select;			
  string input, w;
  
  WordCountList wlist;	
  while( !stop && cout<<" Select I/R/S/P/p/C/W/T/t/Q-->" && cin>>select){
    switch(select){
    case 'I': case 'i': cin >> w;  wlist.insert(w);   break;
    case 'R': case 'r': cin >> w;   wlist.remove(w); break;
    case 'S': case 's': cout<<"List length = "<<wlist.size()<<" nodes"<<endl;	break;
    case 'p': wlist.print();  break; // ascending order
    case 'P': wlist.printR();  break; // descending order
    case 'Q': case 'q':  stop=1; break;
    default: cerr <<"Command Error\n";  stop=1;
    }
  }
  return 0;
}

[求める実行結果]
Select I/R/S/P/p/C/W/T/t/Q-->i cat
Select I/R/S/P/p/C/W/T/t/Q-->i dog
Select I/R/S/P/p/C/W/T/t/Q-->i horse
Select I/R/S/P/p/C/W/T/t/Q-->i zebra
Select I/R/S/P/p/C/W/T/t/Q-->i turtle
Select I/R/S/P/p/C/W/T/t/Q-->i cat
Select I/R/S/P/p/C/W/T/t/Q-->i ant
Select I/R/S/P/p/C/W/T/t/Q-->i dog
Select I/R/S/P/p/C/W/T/t/Q-->i horse
Select I/R/S/P/p/C/W/T/t/Q-->i cat
Select I/R/S/P/p/C/W/T/t/Q-->p
ant(1) cat(3) dog(2) horse(2) turtle(1) zebra(1)
Select I/R/S/P/p/C/W/T/t/Q-->P
zebra(1) turtle(1) horse(2) dog(2) cat(3) ant(1)

[現状の実行結果]
Select I/R/S/P/p/C/W/T/t/Q-->i cat
これで終了してしまいます。

このことからinsert関数が上手く機能していないのかと考えました。

したがって
こういった時の解決の仕方または正しいコードの考え方などを
指摘していただけるとありがたいです。
よろしくお願いいたします。

行動規範の内容に同意します

回答2件

C++
1void WordCountList::insert(string w){
2    Node *ptr = head;
3    if (head==NULL || head->word > w){ // head が NULL のとき
4        head = new Node(w, head->count, head); // head->count をアクセスするのはご法度ちゃうか?
5        head->count++;
6    }
7    ...

[余計なお世話] list使ってre-writeしてみた:

C++
1#include <iostream>
2#include <fstream>
3#include <string>
4#include <list>
5#include <utility>
6#include <algorithm>
7
8class WordCountList { //　単語とその出現回数をノードにもち，アルファベット順につなげた連結リスト
9    using Node = std::pair<std::string,int>;
10    std::list<Node> words;
11    static bool node_less(const Node& a, const Node& b) { return a.first < b.first; }
12    void clear() { words.clear(); } //ノードを全て削除
13
14public:
15    WordCountList() { }
16    ~WordCountList() { clear(); };
17    int size() const { return words.size(); };
18    // 単語を挿入. すでにあれば，出現回数をインクリメント
19    void insert(const std::string& w) {
20      Node node(w,1);
21      auto iter = std::lower_bound(words.begin(), words.end(), node);
22      if ( iter != words.end() && iter->first == w ) iter->second++;
23      else words.insert(iter, node);
24    }
25    //　単語を削除. 1回減算，或は，ノード削除 
26    void remove(const std::string& w) {
27        Node node(w, 0);
28        auto iter = std::lower_bound(words.begin(), words.end(), node);
29        if ( iter != words.end() && iter->first == w) {
30          if ( --iter->second <= 0 ) words.erase(iter);
31        }
32    }
33    //単語と出現回数をアルファベット順に昇順表示
34    void print() const {
35      for ( auto iter = words.cbegin(); iter != words.cend(); ++iter ) {
36        std::cout << iter->first << "(" << iter->second << ") ";
37      }
38    }
39    //単語と出現回数をアルファベット順とは反対に降順表示
40    void printR() const {
41      for (auto iter = words.crbegin(); iter != words.crend(); ++iter) {
42        std::cout << iter->first << "(" << iter->second << ") ";
43      }
44    }
45};
46
47int main() {
48    using namespace std;
49    int stop = 0; // loop stop flag; 
50    int n, ct, num;
51    char  select;
52    string input, w;
53
54    WordCountList wlist;
55    while (!stop && cout << " Select I/R/S/P/p/C/W/T/t/Q-->" && cin >> select) {
56        switch (select) {
57        case 'I': case 'i': cin >> w;  wlist.insert(w);   break;
58        case 'R': case 'r': cin >> w;  wlist.remove(w); break;
59        case 'S': case 's': cout << "List length = " << wlist.size() << " nodes" << endl;    break;
60        case 'p': wlist.print();  break; // ascending order
61        case 'P': wlist.printR();  break; // descending order
62        case 'Q': case 'q':  stop = 1; break;
63        default: cerr << "Command Error\n";  stop = 1;
64        }
65    }
66    return 0;
67}

投稿2020/07/06 07:26

編集2020/07/06 08:50

episteme

総合スコア16614

episteme

2020/07/06 07:26

ｶﾌﾞｯﾀ...

program777

2020/07/07 07:32

ご回答ありがとうございます。ご指摘いただいたところ参考に改めてinsert関数を作成してみました。 void WordCountList::insert(string w){ Node *ptr = head; if (head==NULL){ head = new Node(w); head->count++; } else if (head->word > w){ Node *p = head; head = new Node(w, head->count, head); head->count++; head->next = p; } else{ while(ptr!= NULL){ if(ptr->word ==w){ ptr->count++; return; } else if(ptr->word > w){ Node *p = ptr; ptr = new Node(w, ptr->count, ptr); ptr->next = p; return; } ptr = ptr->next; } ptr=new Node(w,ptr->count,ptr); } ｝このコードだと、実行したときに Select I/R/S/P/p/C/W/T/t/Q-->i cat Select I/R/S/P/p/C/W/T/t/Q-->i dog で終了してしまいます。訂正箇所分かれば、アドバイいただけるとありがたいです。また、今回はlistはincludeせず考えています。

行動規範の内容に同意します

headがNULLのときにhead->countでNULLポインタの逆参照して落ちます。

C++
1void WordCountList::insert(string w) {
2    Node* ptr = head;
3    if (head == NULL || head->word > w) {
4        head = new Node(w, head->count, head); // <- ここ