我已经编写了自己的列表类进行练习，这里是：
#pragma once
#include <iostream>
using namespace std;
// A linked node structure.
template <typename T>
struct LinkedNode
{
T data;
LinkedNode<T>* next;
LinkedNode<T>* prev;
};
// Class linked list.
template <typename T>
class LinkedList
{
public:
// Constructor
LinkedList()
{
mFirst = 0;
mLast = 0;
}
LinkedList(const LinkedList& rhs)
{
mFirst = 0;
mLast = 0;
// Get a pointer to the first node of rhs.
LinkedNode<T>* current = rhs.mFirst;
// While not at the end of the rhs linked list.
while( current != 0 )
{
insertLast( current->data );
current = current->next;
}
}
// Destructor
~LinkedList()
{
destroy();
}
// Overload
LinkedList& operator=(const LinkedList& rhs)
{
// Check for self assignment
if ( this == &rhs )
return *this;
// Get a pointer to the first node of rhs.
LinkedNode<T>* current = rhs.mFirst;
// While not at the end of the rhs linked list.
while( current != 0 )
{
insertLast( current->data );
current = current->next;
}
// Chain assignments a = b = c = d
return *this;
}
// Check if list is empty.
bool isEmpty()
{
if( mFirst == 0 && mLast == 0 )
return true;
else
return false;
}
// Return first and last nodes.
LinkedNode<T>* getFirst() { return mFirst; };
LinkedNode<T>* getLast() { return mLast; };
void insertFirst(T tData);
void insertLast(T tData);
bool insertAfter(T tKey, T tData);
void removeFirst();
void removeLast();
void remove(T removalCandidate);
void destroy();
private:
LinkedNode<T>* mFirst;
LinkedNode<T>* mLast;
};
template <typename T>
bool LinkedList<T>::insertAfter(T tKey, T tData)
{
if( isEmpty() ) return false;
// Get a pointer to the front of the list
LinkedNode<T>* current = mFirst;
// Loop until we find the tKey (the value of the node to insert after)
while( current->data != tKey )
{
// Hop to the next node.
current = current->next;
// Test if we reached the end, if we did we didn't find the node to insert after (tKey)
if( current == 0 )
return false;
}
// Allocate memory for the new node to insert.
LinkedNode<T>* newNode = new LinkedNode<T>();
newNode->data = tData;
// Special case: Are we inserting after the last node?
if( current == mLast )
{
newNode->next = 0;
mLast = newNode;
}
// No, else link in new node after the current node.
else
{
newNode->next = current->next;
newNode->next->prev = newNode;
}
newNode->prev = current;
current->next = newNode;
return true;
}
template <typename T>
void LinkedList<T>::insertFirst(T tData)
{
LinkedNode<T>* newNode = new LinkedNode<T>();
newNode->data = tData;
// If the list is empty, then this is the first and last node and doesn't have a previous pointer.
if( isEmpty() )
mLast = newNode;
// If the list is not empty, the new node becomes the previous node of the current first node.
else
mFirst->prev = newNode;
// The new node's next pointer is the old first pointer. May be null if this is the first node being added to the list.
newNode->next = mFirst;
//The new node becomes the first node.
mFirst = newNode;
}
template <typename T>
void LinkedList<T>::insertLast(T tData)
{
LinkedNode<T>* newNode = new LinkedNode<T>();
newNode->data = tData;
if( isEmpty() )
mFirst = newNode;
else
mLast->next = newNode;
newNode->prev = mLast;
mLast = newNode;
}
template <typename T>
void LinkedList<T>::removeFirst()
{
if( !isEmpty() )
{
LinkedNode<T>* current = mFirst;
if( mFirst == mLast )
{
mFirst->next = 0;
mLast->prev = 0;
}
else
{
mFirst = current->next;
mFirst->prev = 0;
}
delete current;
current = 0;
}
}
template <typename T>
void LinkedList<T>::removeLast()
{
if( !isEmpty() )
{
LinkedNode<T>* current = mLast;
if( mFirst == mLast )
{
mFirst = 0;
mLast = 0;
}
else
{
mLast = current->prev;
mLast->next = 0;
}
delete current;
current = 0;
}
}
template <typename T>
void LinkedList<T>::remove(T removalCandidate)
{
LinkedNode<T>* current = mFirst;
if( isEmpty() )
{
cout << "List is empty!" << endl;
}
else
{
while( current->data != removalCandidate )
{
if( current->data == removalCandidate )
{
break;
}
current = current->next;
}
}
if( current == mFirst )
removeFirst();
else if ( current == mLast )
removeLast();
else
{
// Create two linked nodes to access the next and prev nodes.
LinkedNode<T>* left = current->prev;
LinkedNode<T>* right = current->next;
left->next = right;
right->prev = left;
}
delete current;
current = 0;
}
template <typename T>
void LinkedList<T>::destroy()
{
// Is there at least one node in the list?
if( mFirst != 0 )
{
// Get a pointer to the first node.
LinkedNode<T>* current = mFirst;
// Loop until we reach the end of list.
while( current != 0 )
{
// Save the current node.
LinkedNode<T>* oldNode = current;
// Move to next node.
current = current->next;
// Delete saved node.
delete oldNode;
oldNode = 0;
}
}
mFirst = 0;
}
然后我还编写了一个堆栈和队列类，我测试它们以查看字符串是否为回文。这一切都有效。但是，当它在列表类中运行 destroy 方法时，会在
delete oldNode;
线。
队列代码：
#pragma once
#include <iostream>
#include "LinkedList.h"
#include <cassert>
template <typename T>
class Queue
{
public:
Queue(){};
~Queue()
{
mList.destroy();
}
T& getFirst()
{
assert( !isEmpty() );
return mList.getFirst()->data;
}
bool isEmpty( void )
{
return mList.isEmpty();
}
void push( T newElement )
{
mList.insertLast( newElement );
}
void pop()
{
mList.removeFirst();
}
private:
LinkedList<T> mList;
};
堆栈代码：
#pragma once
#include <iostream>
#include "LinkedList.h"
#include <cassert>
template <typename T>
class Stack
{
public:
Stack(){};
~Stack()
{
mList.destroy();
}
T& getTopItem()
{
// Throw error if list is empty.
assert( !isEmpty() );
return mList.getLast()->data;
}
bool isEmpty( void )
{
return mList.isEmpty();
}
void push( T newElement )
{
mList.insertLast( newElement );
}
void pop()
{
mList.removeLast();
}
private:
LinkedList<T> mList;
};
主要代码：
#include "Stack.h"
#include "Queue.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
Stack<char> strStack;
Queue<char> strQueue;
cout << "Enter a string: ";
string input = "";
getline(cin, input);
for( unsigned int i = 0; i < input.length(); ++i )
{
strStack.push( input[i] );
strQueue.push( input[i] );
}
bool isPalindrome = true;
// FIX PALINDROME AND ASSERTION FAIL
for( unsigned int j = 0; j < input.length(); ++j )
{
if( strStack.getTopItem() != strQueue.getFirst() )
{
isPalindrome = false;
break; // Exit for loop early.
}
// Get rid of next element out.
strStack.pop();
strQueue.pop();
}
cout << input << " is palindrome: " << isPalindrome << endl;
}
我不知道为什么，任何帮助将不胜感激。