时间仓促,没有加注释.但是看后我保证你受益匪浅.
// Node 类 Node.h
#ifndef NODE_CLASS
#define NODE_CLASS
#include <iostream.h>
template <typename T>
class Node
{
public:
T data;
Node(const T &item,Node<T> * ptrnext=NULL);
void InsertAfter(Node<T> *p);
Node<T> * DeleteAfter(void);
Node<T> * NextNode(void)const;
private:
Node<T> * next;
};
template <typename T>
Node<T>::Node(const T &item,Node<T> *ptrnext):data(item),next(ptrnext)
{
}
template <typename T>
void Node<T>::InsertAfter(Node<T> *p)
{
p->next=next;
next=p;
}
template <typename T>
Node<T> * Node<T>::DeleteAfter(void)
{
Node<T> *tempptr=next;
if(next==NULL)
return NULL;
next=tempptr->next;
return tempptr;
}
template<typename T>
Node<T> * Node<T>::NextNode(void)const
{
return next;
}
#endif
Nodelib.h :提供一些方法
#include <iostream.h>
#include "Node.h"
enum AppendNewLine{noNewLine,addNewLine};
template <typename T>
Node<T> * GetNode(const T &item,Node<T> *nextPtr=NULL)
{
Node<T> *newNode;
newNode=new Node<T>(item,nextPtr);
if(newNode==NULL)
{
cerr<<"Memory allocation failure!"<<endl;
exit(0);
}
return newNode;
}
template <typename T>
void InsertFront(Node<T> * &head,T item)
{
head=GetNode(item,head);
}
template <typename T>
void PrintList(Node<T>*head,AppendNewLine addnl)
{
Node<T> *currptr=head;
while(currptr!=NULL)
{
if(addnl==addNewLine)
cout<<currptr->data<<endl;
else
cout<<currptr->data<<" ";
currptr=currptr->NextNode();
}
}
template <typename T>
void InsertRear(Node<T> * &head,const T &item)
{
Node<T> *currptr=head,*newNode;
if(currptr==NULL)
InsertFront(head,item);
else
{
while(currptr->NextNode!=NULL)
{
currptr=currptr->NextNode();
}
newNode=GetNode(item);
currptr->InsertAfter(newNode);
}
}
template<typename T>
void DeleteFront(Node<T> *&head)
{
Node<T> *p=head;
if(head!=NULL)
{
head=head->NextNode();
delete p;
}
}
template <typename T>
void Delete(Node<T> *&head,T key)
{
Node<T> *currptr=head,*prevptr=NULL;
if(currptr==NULL)
return;
while(currptr!=NULL&&currptr->data!=key)
{
prevptr=currptr;
currptr=currptr-NextNode();
}
if(currptr!=NULL)
{
if(prevptr==NULL)
head=head->NextNode();
else
{
prevptr->DeleteAfter();
delete currptr;
}
}
}
Linklist.h :链表类的实现
#ifndef LINKLIST_CLASS
#define LINKLIST_CLASS
#include <iostream.h>
#include <stdlib.h>
#include "Node.h"
template <class T>
class LinkList
{
private:
Node<T> *front;
Node<T> *rear;
Node<T> *currPtr;
Node<T> *prevPtr;
int size;
int position;
Node<T> * GetNode(const T &item,Node<T> *nextPtr=NULL);
void FreeNode(Node<T> *p);
void CopyList(const LinkList<T> &L);
public:
LinkList(void);
LinkList(const LinkList<T> &L);
~LinkList(void);
LinkList<T> & operator =(const LinkList<T> &L);
LinkList<T> operator +( LinkList<T> &L);
LinkList<T> & operator +=(LinkList<T> &L);
int ListSize(void)const;
int ListEmpty(void)const;
void Reset(int pos=0);
void Next(void);
int EndOfList(void)const;
int CurrentPosition(void)const;
void InsertFront(const T&item);
void InsertRear(const T&item);
void InsertAt(const T&item);
void InsertAfter(const T&item);
T DeleteFront(void);
void DeleteAt(void);
T&Data(void);
void ClearList(void);
};
template <class T>
Node<T> * LinkList<T>::GetNode(const T&item,Node<T> *nextPtr)
{
Node<T> *newNode;
newNode=new Node<T>(item,nextPtr);
if(newNode==NULL)
{
cerr<<"Memory allocation failure!"<<endl;
exit(0);
}
return newNode;
}
template <class T>
void LinkList<T>::FreeNode(Node<T> *p)
{
if(p==NULL)
return ;
else
delete p;
}
template <class T>
void LinkList<T>::CopyList(const LinkList<T> &L)
{
Node<T> *p=L.front;
while(p!=NULL)
{
InsertRear(p->data);
p=p->NextNode();
}
if(position==-1)
return;
prevPtr=NULL;
currPtr=front;
for(int pos=0;pos!=position;pos++)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
}
template <class T>
LinkList<T>::LinkList(void):front(NULL),rear(NULL),
currPtr(NULL),prevPtr(NULL),size(0),position(-1)
{
}
template <class T>
LinkList<T>::LinkList(const LinkList<T> &L)
{
front=NULL;
rear=NULL;
currPtr=NULL;
prevPtr=NULL;
size=0;
position=-1;
CopyList(L);
}
template <class T>
void LinkList<T>::ClearList(void)
{
Node<T> *currposition,*nextposition;
currposition=front;
while(currposition!=NULL)
{
nextposition=currposition->NextNode();
FreeNode(currposition);
currposition=nextposition;
}
front=rear=NULL;
prevPtr=currPtr=NULL;
size=0;
position=-1;
}
template <class T>
LinkList<T>::~LinkList(void)
{
ClearList();
}
template <class T>
LinkList<T> & LinkList<T>::operator =(const LinkList<T> &L)
{
if(this==&L) return *this;
ClearList();
CopyList(L);
return *this;
}
template <class T>
LinkList<T> LinkList<T>::operator +( LinkList<T> &L)
{
LinkList<T> temp;
Reset();
L.Reset();
while(!EndOfList())
{
temp.InsertRear(Data());
Next();
}
L.Reset();
while(!L.EndOfList())
{
temp.InsertRear(L.Data());
L.Next();
}
return temp;
}
template <class T>
LinkList<T> & LinkList<T>::operator +=(LinkList<T> &L)
{
if(this==&L)
{
LinkList<T> temp=L;
temp.Reset();
while(!temp.EndOfList())
{
InsertRear(temp.Data());
temp.Next();
}
}
else
{
L.Reset();
while(!L.EndOfList())
{
InsertRear(L.Data());
L.Next();
}
}
return *this;
}
template <class T>
int LinkList<T>::ListSize(void)const
{
return size;
}
template <class T>
int LinkList<T>::ListEmpty(void)const
{
return size==0;
}
template <class T>
void LinkList<T>::Reset(int pos)
{
int startpos;
if(front==NULL)
return;
if(pos<0||pos>size-1)
{
cerr<<"Reset:Invalid list position."<<endl;
return;
}
if(pos==0)
{
prevPtr=NULL;
currPtr=front;
position=0;
}
else
{
currPtr=front->NextNode();
prevPtr=front;
startpos=1;
for(position=startpos;position!=pos;position++)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
}
}
template <class T>
void LinkList<T>::Next(void)
{
if(currPtr!=NULL)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
position++;
}
}
template <class T>
T &LinkList<T>::Data(void)
{
if(size==0||currPtr==NULL)
{
cerr<<"Data:Invalid reference!"<<endl;
exit(0);
}
return currPtr->data;
}
template <class T>
int LinkList<T>::EndOfList(void)const
{
return prevPtr==rear;
}
template <class T>
int LinkList<T>::CurrentPosition(void)const
{
return position;
}
template <class T>
void LinkList<T>::InsertFront(const T&item)
{
front=GetNode(item,front);
if(size==0)
{
rear=front;
}
size++;
Reset();
}
template <class T>
void LinkList<T>::InsertRear(const T&item)
{
Node<T> *newNode;
if(front==NULL)
InsertFront(item);
else
{
while(currPtr!=NULL)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
newNode=GetNode(item,front);
prevPtr->InsertAfter(newNode);
currPtr=newNode;
rear=newNode;
size++;
position=size-1;
}
}
template <class T>
void LinkList<T>::InsertAt(const T&item)
{
Node<T> * newNode;
if(prevPtr==NULL)
{
newNode=GetNode(item,front);
front=newNode;
}
else
{
newNode=GetNode(item,front);
prevPtr->InsertAfter(newNode);
}
if(prevPtr==rear)
{
rear=newNode;
position=size;
}
currPtr=newNode;
size++;
}
template <class T>
void LinkList<T>::InsertAfter(const T&item)
{
Next();
InsertAt(item);
}
template <class T>
T LinkList<T>::DeleteFront(void)
{
T temp;
temp=front->data;
Reset();
DeleteAt();
return temp;
}
template <class T>
void LinkList<T>::DeleteAt(void)
{
Node<T> *p;
if(currPtr==NULL)
{
cerr<<"Invalid !"<<endl;
exit(0);
}
if(prevPtr==NULL)
{
p=front;
front=front->NextNode();
}
else
p=prevPtr->DeleteAfter();
if(p==rear)
{
rear=prevPtr;
position--;
}
currPtr=p->NextNode();
FreeNode(p);
size--;
}
#endif
Linklistlib.h //其中lstack 和lqueue是用链表实现的堆栈类和队列类
#ifndef LINKLISTLIB_CLASS
#define LINKLISTLIB_CLASS
#include <iostream.h>
#include "lstack.h"
#include "lqueue.h"
class LinkList;
template <class T>
void PrintList(LinkList<T> & L)
{
for(L.Reset();!L.EndOfList();L.Next())
cout<<L.Data()<<" ";
}
template <class T>
void ConcatLists(LinkList<T> &L1,LinkList<T> &L2)
{
L1.Reset();
L2.Reset();
while(!L2.EndOfList())
{
L1.InsertRear(L2.Data());
L2.Next();
}
}
template <class T>
void FindMax(LinkList<T> &l)
{
if(l.ListEmpty())
{
cerr<<"FindMax: list empty!"<<endl;
exit(0);
}
l.Reset();
T max=l.Data();
int maxLoc=0;
for(l.Next();!l.EndOfList();l.Next())
if(l.Data()>max)
{
max=l.Data();
maxLoc=l.CurrentPosition();
}
l.Reset(maxLoc);
}
template <class T>
void Split(LinkList<T> &l,LinkList<T> &l1,LinkList<T> &l2)
{
int i=1;
for(l.Reset();!l.EndOfList();l.Next())
{
if(i==1)
{
l1.InsertRear(l.Data());
i=0;
}
else
{
l2.InsertRear(l.Data());
i=1;
}
}
}
template <class T>
void DeleteRear(LinkList<T> &l)
{
if(l.ListEmpty())
{
cerr<<"The list is empty!"<<endl;
return;
}
else
{
l.Reset(l.ListSize()-1);
}
l.DeleteAt();
}
void OddEven(LinkList<int> &l,LinkList<int> &l1,LinkList<int> &l2)
{
for(l.Reset();!l.EndOfList();l.Next())
{
if(l.Data()%2==0)
l1.InsertRear(l.Data());
else
l2.InsertRear(l.Data());
}
}
template <class T>
void ReverseList(LinkList<T> &l)
{
LStack<T> s;
for(l.Reset();!l.EndOfList();l.Next())
s.Push(l.Data());
l.Reset();
while(!s.StackEmpty())
{
l.Data()=s.Pop();
l.Next();
}
}
#endif
