我正在处理一项任务，该任务要求我存储一个包含任何对象类型数据的节点的链接列表。目前我正在构建对象类型设置为 Employee 的类（我将在下面发布）以简化过程。在我得到所有功能后，我会将其转换为模板。
我的问题是我有一个“合并”函数，它接受两个排序列表，然后将它们合并到调用对象列表中（仍然排序）。我设置调试语句“第一”“第二”“第三”和“第四”只是为了查看正在输入哪些循环，并且 cmd 提示符进入打印“第四”的无限循环。就好像两个列表都没有以 = 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;
}
}*/
}
我已经重写了几次并尝试了不同的方法来解决这个问题，但它似乎总是有同样的问题。似乎表明其中一个列表是无限的，但是在我的测试类（我将在下面发布）中，一个列表有两个项目，另一个有 4 个......它读取的 infile 只包含 4 个条目：
Duck Donald 2 35000 Duck Daffy 4 12000 Mouse Mickey 1 100000 Goof Goofy 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 的指针......下面列出了两个版本的合并函数. 较低的已被注释掉，但不确定该线程上的可见性。任何提示将不胜感激。我遇到了障碍：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;
}