リンクリスト内のすべての一致するノードを見つけるC++

Question

リンクされたリスト内のノードのすべての出現を見つける関数を作成すると、その関数はメイン関数に出現回数を返し、出現回数を返します。プログラムはコンパイルされますが、ちょうどフリーズし、検索する正しい名前を入力すると何も起こらないようですが、リストにない間違った名前を入力すると、findall関数は0を返し、残りのプログラムは動作します良い。見てください。

main.cppに

#include <iostream> 
#include <fstream> 
#include <string> 
using namespace std; 

#include "List.h" 

void extra(list &); 

/*********************************** 
* Main 
* Test function - DO NOT CHANGE 
***********************************/ 
void main() 
{ 
    list a; 
    extra(a); 
} 

/*********************************** 
* Extra Credit 
* Test function - DO NOT CHANGE 
***********************************/ 

void extra(list &a) 
{ int i,n; 
    node_ptr map[4]; 
    string first,last; 

// Find node 

    cout << endl; 
    cout << "Enter First and Last name: "; 
    cin >> first >> last; 
    n = a.findall(first,last,map,4); 
// Display forwards 

    cout << endl; 
    cout << "Find List\n--------------\n"; 
    for (i = 0; i < n; i++) 
    { 
     map[i]->put(cout); 
    } 
} 

List.h

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

class list 
{ public: 
     list();            // Empty constructor 
     ~list();           // Destructor 

     int findall(string, string, node_ptr*, int); 

     node *find(string, string);       // Locate a note 


    private: 
     node *head; 
}; 

Node.h

#include <iostream> 
#include <string> 
using namespace std; 


class list; 

class node 
{ friend list; 
    public: 
    node();       // Null constructor 
    ~node();       // Destructor 

    void put(ostream &out);   // Put 

    private: 
    string first,last; 
    int age; 
    node *next; 
}; 

typedef node * node_ptr; 

List.cpp

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

/** 
* Empty Constructor 
* 
*/ 

list::list() 
{ 
    head = nullptr; 
} 

/** 
* Destructor Constructor 
* 
*/ 

list::~list() 
{ if (head == nullptr) return; 

    node *p = head, *t; 

    while (p) 
    { 
     t = p; 
     p = p->next; 
     delete t; 
    } 

    head = nullptr; 
} 

/** 
* Locate node 
* 
*/ 

node *list::find(string last, string first) 
{ 
    node *temp = head; 
    while (temp) 
    { 
     if (temp->first == first && temp->last == last) return temp; 
     temp = temp->next; 
    } 
    return nullptr; 
} 


/** 
* Find all. 
* 
*/ 

int list::findall(string first, string last, node_ptr* map, int n) 
{ 
    int ans; 
    ans = 0; 
    *map = find(first, last); 
    while (*map != NULL) 
    { 
     ans++; 
     *map = (*map)->next; 
     *map = find(first, last); 

    } 
    return ans; 
} 

Node.cpp

#include "Node.h" 
#include <iostream> 
#include <string> 
#include <iomanip> 
using namespace std; 

/** 
* Empty Constructor 
* 
*/ 

node::node() 
{ 
    last = ""; 
    first = ""; 
    age = 0; 
    next = nullptr; 
} 


/** 
* Destructor 
* 
*/ 

node::~node() 
{ if (next != nullptr) next = nullptr; 
} 

/** 
* Put 
* 
*/ 

void node::put(ostream &out) 
{ out << setw(14) << left << last << setw(14) << first << setw(10) << age << endl; 
} 

本当にありがとうございます。ありがとうございました。

Answer 1

findall()は無限ループに詰まるのでフリーズします。

一致するノードが見つからない場合、最初にfind()を呼び出すと、nullptrとfindall()が返されます。

しかし、一致するノードが見つかった場合は、リスト全体を最初から再度検索するためにfind()を呼び出すループが入力されます。それは以前と同じノードを見つけるでしょう。その後、find()にもう一度やり直してください。この問題を解決するために

find()が一致するノードを返す場合、あなたは前の検索が中断したところそれは、検索を開始することができますfind()への次の呼び出しでnextノードを渡す必要があります。あなたがリストの終わりに達するまで繰り返す。

class list 
{ public: 
    ... 

     int findall(string first, string last, node_ptr *map, int n); 

     node_ptr find(string first, string last, node_ptr start = nullptr);    // Locate a note 

    ... 
}; 

node_ptr list::find(string last, string first, node_ptr start) 
{ 
    node_ptr temp = (start) ? start : head; 
    while (temp) 
    { 
     if ((temp->first == first) && (temp->last == last)) break; 
     temp = temp->next; 
    } 
    return temp; 
} 

int list::findall(string first, string last, node_ptr* map, int n) 
{ 
    int ans = 0; 
    node_ptr temp = nullptr; 
    while (ans < n) 
    { 
     temp = find(first, last, temp); 
     if (!temp) break; 
     *map++ = temp; 
     ++ans; 
     temp = temp->next; 
    } 
    return ans; 
} 

更新：あなたはfind()の署名を変更することはできませんならば、あなたはfind()が何を複製するfindall()を再記述する必要があります。

class list 
{ public: 
    ... 

     int findall(string first, string last, node_ptr *map, int n); 

     node_ptr find(string first, string last);    // Locate a node 

    ... 
}; 

node_ptr list::find(string last, string first) 
{ 
    node_ptr temp = head; 
    while (temp) 
    { 
     if ((temp->first == first) && (temp->last == last)) break; 
     temp = temp->next; 
    } 
    return temp; 
} 

int list::findall(string first, string last, node_ptr* map, int n) 
{ 
    int ans = 0; 
    node_ptr temp = head; 
    while (ans < n) 
    { 
     while (temp) 
     { 
      if ((temp->first == first) && (temp->last == last)) break; 
      temp = temp->next; 
     } 
     if (!temp) break; 
     *map++ = temp; 
     ++ans; 
     temp = temp->next; 
    } 
    return ans; 
}