c++ - ここでポインタを誤用していますか? ループ条件が正しく機能していないようです

Question

私は、任意のオブジェクトタイプのデータを保持するノードのリンクリストを格納する必要がある割り当てに取り組んでいます。現在、プロセスを簡素化するために、オブジェクトタイプを Employee に設定してクラスを作成しています (以下に投稿します)。すべての機能を落としたら、それをテンプレートに変換します。

私の問題は、2 つの並べ替えられたリストを取り、それらを呼び出し元のオブジェクトリスト (まだ並べ替えられている) にマージする "マージ" 関数があることです。どのループに入っているかを確認するためだけに、「first」、「second」、「third」、「fourth」というデバッグステートメントを設定し、cmd プロンプトが「fourth」を出力する無限ループに入ります。どちらのリストも = NULL のノードで終わらないかのようであり、まるで最後まで実行されないかのようです... かなり混乱しています。問題の関数は次のとおりです。

//----------------------------------------------------------------------------
// merge
// merges two sorted lists into one sorted list
void List::merge(List* LA, List* LB)
{
   Node* mergedPtr = NULL; //pointer for merged list
   Node* laPtr = LA->head; //pointer for List A
   Node* lbPtr = LB->head; //pointer for List B

   makeEmpty();

   while(laPtr != NULL && lbPtr != NULL)
   {
      if(*laPtr->data <= *lbPtr->data)
      {
         if(head == NULL) //special base case
         {
            head = laPtr;
            mergedPtr = head;
            cout << "first";
         }
         else
         {
            mergedPtr->next = laPtr;
            mergedPtr = mergedPtr->next;
            cout << "second";
         }
         laPtr = laPtr->next; //advance pointer for List A
      }
      else if(*laPtr->data > *lbPtr->data)
      {
         if(head == NULL) //special base case
         {
            head = lbPtr;
            mergedPtr = head;
            cout << "third";
         }
         else
         {
            mergedPtr->next = lbPtr;
            mergedPtr = mergedPtr->next;f
            cout << "fourth";
         }
         lbPtr = lbPtr->next; //advance pointer for List B
      }

      mergedPtr = mergedPtr->next; //advance pointer for merged list
   }

   /*if(laPtr != NULL)
   {
      while(laPtr != NULL)
      {
         mergedPtr->next = laPtr;
         laPtr = laPtr->next;
      }
   }
   else if(lbPtr != NULL)
   {
      while(lbPtr != NULL)
      {
         mergedPtr->next = lbPtr;
         lbPtr = lbPtr->next;
      }
   }*/
}

私はそれを数回書き直し、問題に取り組むさまざまな方法を試しましたが、常に同じ問題があるようです. リストの 1 つが無限であることを示しているようですが、私のテストクラス (すぐ下に投稿します) では、1 つのリストには 2 つの項目があり、もう 1 つのリストには 4 つの項目があります...読み取り元の infile には、単に 4 つのエントリがあります。

ダックドナルド 2 35000 ダックダフィー 4 12000 マウスミッキー 1 100000 グーフグーフィー 7 250

テストクラスでは、エントリを追加してから削除します。次に、別のリストを使用して makeEmpty() 関数をテストします。次に、マージ用の別のリストがありますが、マージ関数内で無限ループに陥っているため、結果はありません。必要に応じて、テストクラスを次に示します。

//////////////////////////////////////////////////////////////////////////////
//////////////////////////////  listdriver.cpp  //////////////////////////////
//////////////////////////////////////////////////////////////////////////////

// Driver for simple linked list
#include "list.h"

// to compile under unix/linux:  g++ nodedata.cpp list.cpp listdriver.cpp

int main() {
   Employee* ptr; 
   List mylist;

   // create file object and open the datafile
   ifstream infile("listdata.txt");
   if (!infile) {
      cout << "File could not be opened." << endl;
      return 1;
   }

   // build list from data file 
   mylist.buildList(infile);                 
   cout << "Original list: " << endl << mylist << endl;

   // insert another node where data is pre-determined
   ptr = new Employee("Lee","Law");
   mylist.insert(ptr); 
   cout << " List after insert: " << endl << mylist << endl;

   Employee* temp;
   List testEmpty;
   temp = new Employee("Zebra", "Zee");
   testEmpty.insert(temp);
   temp = new Employee("Jackson", "Jack");
   testEmpty.insert(temp);
   cout << endl << " testEmpty after inserting 2 new employees: " << endl << testEmpty << endl;

   List mergeTest;
   cout << "testtesttest" << endl;
   mergeTest.merge(&testEmpty, &mylist);
   cout << endl << " mergeTest after calling merge(testEmpty, mylist): " << endl << mergeTest << endl;
}

これは Employee オブジェクトですが、問題には関係ないと思います:

#include "employee.h"

// incomplete class and not fully documented

//--------------------------  constructor  -----------------------------------
Employee::Employee(string last, string first, int id, int sal) {
   idNumber = (id >= 0 && id <= MAXID? id : -1);
   salary = (sal >= 0 ? sal : -1);
   lastName = last;
   firstName = first;
}   

//--------------------------  destructor  ------------------------------------
// Needed so that memory for strings is properly deallocated
Employee::~Employee() { }

//---------------------- copy constructor  -----------------------------------
   Employee::Employee(const Employee& E) {
      lastName = E.lastName;
      firstName = E.firstName;
      idNumber = E.idNumber;
      salary = E.salary;
   }

//-------------------------- operator= ---------------------------------------
   Employee& Employee::operator=(const Employee& E) {
      if (&E != this) {
         idNumber = E.idNumber;
         salary = E.salary;
         lastName = E.lastName;
         firstName = E.firstName;
      }
      return *this;
   }

//-----------------------------  setData  ------------------------------------
// set data from file
bool Employee::setData(ifstream& inFile) {
   inFile >> lastName >> firstName >> idNumber >> salary;
   return idNumber  >= 0 && idNumber <= MAXID && salary >= 0; 
}

//-------------------------------  <  ----------------------------------------
// < defined by value of name
bool Employee::operator<(const Employee& E) const { 
   return lastName < E.lastName ||
          (lastName == E.lastName && firstName < E.firstName);
}


//-------------------------------  <= ----------------------------------------
// < defined by value of inamedNumber
bool Employee::operator<=(const Employee& E) const { 
   return *this < E || *this == E;
}

//-------------------------------  >  ----------------------------------------
// > defined by value of name
bool Employee::operator>(const Employee& E) const { 
   return lastName > E.lastName ||
          (lastName == E.lastName && firstName > E.firstName);
}

//-------------------------------  >= ----------------------------------------
// < defined by value of name
bool Employee::operator>=(const Employee& E) const { 
   return *this > E || *this == E;
}

//----------------- operator == (equality) ----------------
// if name of calling and passed object are equal,
//   return true, otherwise false
//
bool Employee::operator==(const Employee& E) const {
   return lastName == E.lastName && firstName == E.firstName;
}

//----------------- operator != (inequality) ----------------
// return opposite value of operator==
bool Employee::operator!=(const Employee& E) const {
   return !(*this == E);
}

//-------------------------------  <<  ---------------------------------------
// display Employee object

ostream& operator<<(ostream& output, const Employee& E) { 
   output << setw(4) << E.idNumber << setw(7) << E.salary << "  " 
          << E.lastName << " " << E.firstName << endl; 
   return output;
}

問題がマージではなく他の場所にあると誰かが指摘したとしても、あまり驚かないでしょう...そのため、残りのクラスコードを以下に投稿しています（要求されると思います）。問題は、クラス内の他の関数との接続が見られないことです。私が挿入と削除を使用するテストドライバーですが、リストの中央にあるノードを使用しているため、最後に存在するNULLへのポインターを台無しにすることはありません...以下にリストされているマージ関数の2つのバージョンがあります. 下のものはコメントアウトされていますが、このスレッドでそれがどのように見えるかはわかりません. ヒントをいただければ幸いです。障害物にぶつかりました:l

////////////////////////////////  list.cpp file  /////////////////////////////

#include "list.h"

//----------------------------------------------------------------------------
// Constructor 
List::List()
{
   head = NULL;
}

//----------------------------------------------------------------------------
// Copy Constructor 
/*List::List(const List &other)
{

}*/

//----------------------------------------------------------------------------
// Destructor 
// Can just call makeEmpty()
List::~List()
{
   makeEmpty();
}

//----------------------------------------------------------------------------
// retrieve
// retrieves an object from the list
bool List::retrieve(Employee* target, Employee* other)
{
   if (isEmpty())
   {
      other = NULL;
      return false;
   }
   else
   {
      Node* ptr = head;

      while(ptr != NULL && ptr->data != target)
      {
         ptr = ptr->next;
      }
      if(ptr == NULL)
      {
         return false;
      }

      other = ptr->data;
      return true;
   }
}

//----------------------------------------------------------------------------
// remove
// remove an object from the list
bool List::remove(Employee* target, Employee* other) 
{
   if (isEmpty()) 
   {
      other = NULL;
      return false;
   }
   else
   {
      Node* ptr = head;
      Node* lastPtr = NULL;

      while(ptr != NULL && ptr->data != target) 
      {
         lastPtr = ptr;
         ptr = ptr->next;
      }
      if(ptr == NULL) 
      {
         return false;
      }

      other = ptr->data;
      lastPtr->next = ptr->next; // skips over target for list pointers
      delete ptr; //deletes now obsolete node from the list and memory
      return true;
   }
}



//----------------------------------------------------------------------------
// isEmpty 
// check to see if List is empty
bool List::isEmpty() const 
{
   return head == NULL;
}

//----------------------------------------------------------------------------
// makeEmpty 
// empty out the list, deallocate all memory for all Nodes and each Object
void List::makeEmpty()
{
   Node* tempPtr;

   while(head != NULL)
   {
      tempPtr = head;
      delete head->data;
      head = tempPtr->next;
      delete tempPtr;
   }   
}

//----------------------------------------------------------------------------
// insert 
// insert an item into list; operator< of the NodeData class
// has the responsibility for the sorting criteria
bool List::insert(Employee* dataptr) 
{                    

   Node* ptr = new Node;
   if (ptr == NULL) return false;                 // out of memory, bail
   ptr->data = dataptr;                           // link the node to data

   // if the list is empty or if the node should be inserted before 
   // the first node of the list
   if (isEmpty() || *ptr->data < *head->data) 
   {
      ptr->next = head;                           
      head = ptr;
   }

   // then check the rest of the list until we find where it belongs 
   else {

      Node* current = head->next;          // to walk list
      Node* previous = head;               // to walk list, lags behind

      // walk until end of the list or found position to insert
      while (current != NULL && *current->data < *ptr->data) 
      {
            previous = current;                  // walk to next node
            current = current->next;
      }

      // insert new node, link it in
      ptr->next = current; 
      previous->next = ptr; 
   }
   return true;
}

//----------------------------------------------------------------------------
// merge
// merges two sorted lists into one sorted list
void List::merge(List* LA, List* LB)
{
   Node* mergedPtr = NULL; //pointer for merged list
   Node* laPtr = LA->head; //pointer for List A
   Node* lbPtr = LB->head; //pointer for List B

   makeEmpty();

   while(laPtr != NULL && lbPtr != NULL)
   {
      if(*laPtr->data <= *lbPtr->data)
      {
         if(head == NULL) //special base case
         {
            head = laPtr;
            mergedPtr = head;
            cout << "first";
         }
         else
         {
            mergedPtr->next = laPtr;
            mergedPtr = mergedPtr->next;
            cout << "second";
         }
         laPtr = laPtr->next; //advance pointer for List A
      }
      else if(*laPtr->data > *lbPtr->data)
      {
         if(head == NULL) //special base case
         {
            head = lbPtr;
            mergedPtr = head;
            cout << "third";
         }
         else
         {
            mergedPtr->next = lbPtr;
            mergedPtr = mergedPtr->next;f
            cout << "fourth";
         }
         lbPtr = lbPtr->next; //advance pointer for List B
      }

      mergedPtr = mergedPtr->next; //advance pointer for merged list
   }

   /*if(laPtr != NULL)
   {
      while(laPtr != NULL)
      {
         mergedPtr->next = laPtr;
         laPtr = laPtr->next;
      }
   }
   else if(lbPtr != NULL)
   {
      while(lbPtr != NULL)
      {
         mergedPtr->next = lbPtr;
         lbPtr = lbPtr->next;
      }
   }*/
}


//----------------------------------------------------------------------------
// merge
// merges two sorted lists into one sorted list
/*void List::merge(List LA, List LB)
{
   //merge sort - take first element from each list, compare, higher value goes first; continue until done sorting
   List* Temp = new List(); //define a new list to be merged into
   Node* LAA = LA.head;
   Node* LBB = LB.head;

   //special case: first copied element is set as head
   if(Temp->head == NULL)
   {
      Node* tempNode;

      cout << "code test: first" << endl;
      if(LAA->data <= LBB->data)
      {
         tempNode = LAA;
         Temp->head = tempNode;
         LAA = LAA->next;
      } 
      else
      {
         tempNode = LBB;
         Temp->head = tempNode;
         LBB = LBB->next;
      }
   }
   cout << "code test: second" << endl;

   //rest of lists
   Node* tempPtr;
   while(LAA != NULL && LBB != NULL)
   {
      tempPtr = Temp->head;
      if(LAA->data <= LBB->data)
      {
         tempPtr->next = LAA;
         LAA = LAA->next;
      }
      else
      {
         tempPtr->next = LBB;
         LBB = LBB->next;
      }
   }
   cout << "code test: third" << endl;

   //catches the remainder extra from either list (messy solution)
   if(LAA != NULL)
   {
      while(LAA != NULL)
      {
         tempPtr->next = LAA;
         LAA = LAA->next;
      }
   }
   if(LBB != NULL)
   {
      while(LBB != NULL)
      {
         tempPtr->next = LBB;
         LBB = LBB->next;
      }
   }
   cout << "code test: fourth" << endl;

}*/

//----------------------------------------------------------------------------
// intersect
// takes the common nodes from two lists and sorts them into a new list
void List::intersect(List* LA, List* LB)
{
   List* temp = new List();
   Node* tempPtr = NULL;
   Node* LAPtr = LA->head;
   Node* LBPtr = LB->head;

   while(LAPtr != NULL && LBPtr != NULL)
   {
      while(LAPtr->data < LBPtr->data)
      {
         LAPtr = LAPtr->next;
      }
      while(LAPtr->data > LBPtr->data)
      {
         LBPtr = LBPtr->next;
      }
      //base case when new list is empty
      if(LAPtr->data == LBPtr->data && temp->head == NULL)
      {
         temp->head = LAPtr;
         tempPtr = head;
         LAPtr = LAPtr->next;
         LBPtr =LBPtr->next;
      }
      //create new node copying the common node and add it to the end of the new list
      //advance the list pointers
      if(LAPtr->data == LBPtr->data)
      {
         Node* tempNode = new Node;
         tempNode->data = LAPtr->data;
         tempNode->next = NULL;
         tempPtr->next = tempNode;
         LAPtr = LAPtr->next;
         LBPtr =LBPtr->next;
      }

   }
}

//----------------------------------------------------------------------------
// buildList 
// continually insert new items into the list
void List::buildList(ifstream& infile) 
{
   Employee* ptr;
   bool successfulRead;                            // read good data
   bool success;                                   // successfully insert
   for (;;) 
   {
      ptr = new Employee;
      successfulRead = ptr->setData(infile);       // fill the NodeData object
      if (infile.eof()) 
      {
         delete ptr;
         break;
      }

      // insert good data into the list, otherwise ignore it
      if (successfulRead) 
      {
         success = insert(ptr);
      }
      else 
      {
         delete ptr;
      }
      if (!success) break;
   }
}

//----------------------------------------------------------------------------
// operator<<  
// output operator for class List, print data, 
// responsibility for output is left to object stored in the list
ostream& operator<<(ostream& output, const List& thelist) 
{

   List::Node* current = thelist.head;
   while (current != NULL) 
   { 
      output << *current->data;
      current = current->next;
   }
   return output;                      // enables output << x << y;
}

//----------------------------------------------------------------------------
// operator=  
// sets one list equal to another
List& List::operator=(const List &other)
{
   if(this == &other)
      return *this;
   Node* tempPtr;

   while(head != NULL) //copy of makeEmpty code; empties the list for new data to be entered
   {
      tempPtr = head;
      delete head->data;
      head = tempPtr->next;
      delete tempPtr;
   }
   tempPtr = other.head; //to navigate other list
   head = tempPtr;
   Node* disPtr; //to build this list
   disPtr = head;
   while(tempPtr->next != NULL)
   {
      Node* temp = new Node;
      disPtr->next = temp; //creates a copy of node
      disPtr->next->data = tempPtr->next->data;
      disPtr->next->next = tempPtr->next->next;

      disPtr = disPtr->next;
      tempPtr = tempPtr->next;
   }

   return *this;
}
//----------------------------------------------------------------------------
// operator==
// checks if two lists are the same
bool List::operator==(List* LB)
{
   Node* LAPtr = head;
   Node* LBPtr = LB->head;
   while(LAPtr != NULL && LBPtr != NULL)
   {
      if(LAPtr->data != LBPtr->data)
      {
         return false;
      }
      LAPtr = LAPtr->next;
      LBPtr = LBPtr->next;
      if(LAPtr->data == NULL && LBPtr->data != NULL)
      {
         return false;
      }
      if (LAPtr->data == NULL && LBPtr->data != NULL)
      {
         return false;
      }
   }
   return true;
}

//----------------------------------------------------------------------------
// operator!=
// checks if two lists are not the same
bool List::operator!=(List* LB)
{
   Node* LAPtr = head;
   Node* LBPtr = LB->head;
   while(LAPtr != NULL && LBPtr != NULL)
   {
      if(LAPtr->data == LBPtr->data)
      {
         return false;
      }
      LAPtr = LAPtr->next;
      LBPtr = LBPtr->next;
   }
   return true;
}

score 0 · Accepted Answer

あなたが呼んでいます

    mergedPtr = mergedPtr->next;

二回。これにより、未定義の動作が発生します。また、NULL の代わりに nullptr を使用する必要があります。

c++ - ここでポインタを誤用していますか? ループ条件が正しく機能していないようです

1 に答える 1

Related

Reference