author openxmp@163.com
链表操作：
1） 插入
2） operator []
3) 翻转（递归）
4） 翻转（非递归）
5） 求长度
#include <iostream>
using namespace std;
#include <stdio.h>
template<typename T>
class List
{
//A template-parameter shall not be redeclared within its scope
//(including nested scopes). A template-parameter shall not have the same
//name as the template name.
template<typename U> friend List<U> * recursiveReverse ( List<U> * list );
template<typename U> friend List<U> * noneRecursiveReverse ( List<U> * list );
public:
List( );
List( T &value );
bool push_back( T &value );
T operator [] ( int index );
size_t getSize();
List *getHead( );
List *getTail( );
T getValue ();
void dump( );
public:
List *mFirstNode;
List *mNextNode;
T mValue;
};
template<typename U>
List<U> *
recursiveReverse ( List<U> * list )
{
static List<U> * firstNode = 0;
if ( 0 == list ->mNextNode )
{
list ->mFirstNode = list;
firstNode = list;
return list;
}
List<U> * node = recursiveReverse( list -> mNextNode );
list -> mNextNode->mNextNode = list;
list -> mNextNode = 0;
node -> mFirstNode = firstNode;
return node;
}
template<typename U>
List<U> * noneRecursiveReverse ( List<U> *list )
{
List<U> * recursiveHead = 0;
List<U> * nextNode = 0;
while ( list )
{
nextNode = list->mNextNode;
list->mNextNode = recursiveHead;
recursiveHead = list;
list = nextNode;
}
recursiveHead->mFirstNode = recursiveHead;
return recursiveHead;
}
template<typename T>
List<T>::List():mFirstNode(0),mNextNode(0)
{
}
template<typename T>
List<T>::List(T & value)
{
mValue = value;
}
template<typename T>
bool
List<T>::push_back( T & value )
{
if ( 0 == mFirstNode )
{
mFirstNode = this;
mNextNode = 0;
mValue = value;
return true;
}
List *node = new List( value );
if ( ! node )
{
return false;
}
node->mFirstNode = mFirstNode;
node->mNextNode = 0;
List *lastNode = mFirstNode;
while ( lastNode ->mNextNode )
{
lastNode = lastNode->mNextNode;
}
lastNode->mNextNode = node;
return true;
}
template<typename T>
T
List<T>::operator [] ( int index )
{
if ( index < 0 || index > getSize() )
{
return 0;
}
List *theNode = mFirstNode;
while ( theNode )
{
if ( 0 == index )
{
return theNode->mValue;
}
theNode = theNode ->mNextNode;
index --;
}
return 0;
}
template<typename T>
size_t
List<T>::getSize()
{
size_t retval = 0 ;
List * node = mFirstNode;
while ( node )
{
retval ++;
node = node ->mNextNode;
}
return retval;
}
template<typename T>
List<T> *
List<T>::getHead()
{
return mFirstNode;
}
template<typename T>
List<T> *
List<T>::getTail()
{
List * theNode = mFirstNode;
while ( theNode -> mNextNode )
{
theNode = theNode->mNextNode;
}
return theNode;
}
template<typename T>
T
List<T>::getValue()
{
return mValue;
}
template<typename T>
void
List<T>::dump()
{
List * node = mFirstNode;
cout << " start dump "<<endl;
while ( node )
{
fprintf(stderr,"[value %d] [address %p]\n",node->mValue,node);
node = node ->mNextNode;
}
cout << endl<< " dump finished " << endl;
}
void unitTest()
{
typedef List<int> INTLIST;
INTLIST intList ;
for (int i = 0; i < 10; ++i)
{
intList.push_back(i);
}
cout << "get Head "<< intList.getHead()->getValue()<<endl;
cout << "get Tail "<< intList.getTail()->getValue()<<endl;
INTLIST *reverseResult = recursiveReverse( & intList );
reverseResult->dump();
reverseResult = recursiveReverse(reverseResult);
reverseResult->dump();
reverseResult = noneRecursiveReverse(reverseResult);
reverseResult->dump();
}
int main()
{
unitTest();
return 0;
}
链表翻转
#include <iostream>
using namespace std;
struct Node
{
Node(int value):mValue(value),mNextNode(0)
{
}
int mValue;
Node *mNextNode;
};
Node *reverse(Node *input)
{
Node *retval = 0;
Node *nextNode = 0;
while ( input )
{
nextNode = input->mNextNode;
input ->mNextNode = retval;
retval = input;
input = nextNode;
}
return retval;
}
void PrintNode ( Node * head )
{
while ( head )
{
cout << head->mValue<<endl;
head = head->mNextNode;
}
}
int main(int argc, char const *argv[])
{
Node *head = 0;
Node *currentNode = head;
for (int i = 0; i < 10; ++i)
{
Node *tmpNode = new Node(i);
if ( 0 == i )
{
currentNode = tmpNode;
head = tmpNode;
continue;
}
currentNode->mNextNode = tmpNode;
currentNode = tmpNode;
}
Node *reverseNode = reverse(head);
PrintNode(reverseNode);
return 0;
}