template <class T>
Node<T>::Node(const T& item,Node<T> *ptr):data(item),next(ptr)
{}
template <class T>
Node<T>::~Node(void)
{}
template <class T>
Node<T> * Node<T>::NextNode(void) const
{
return next;
}
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
p->next=next; //将当前结点的后继结点链接到结点 p 之后
next=p; //将结点 p 作为当前结点的后继结点
}
template <class T>
Node<T> * Node<T>::DeleteAfter(void)
{
Node<T> *ptr=next; //保存当前结点的后继结点
if(ptr==NULL) return NULL; //若没有后继结点，则返回空指针
next=ptr->next; //当前结点指向其原来的后继的后继，即 ptr 的后继
return ptr; //返回指向被删除结点的指针
}
//链表类的定义
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include"Node.cpp"
template<class T>
class LinkedList
{
private:
Node<T> *front,*rear; //定义指向头指针和指向尾指针
Node<T> *prevptr,*currptr; //用于访问数据、插入和删除结点指针
int size; //表中的结点数
int position; //表中当前结点位置计数
Node<T>*GetNode(const T& item,Node<T>*ptr=NULL); //申请结点的函数
void FreeNode(Node<T>*p); //释放结点的函数
public:单链表程序
LinkedList(void); //构造函数
~LinkedList(void); //析构函数
int Size(void)const; //取表中结点大小的函数
int SetPosition(int pos); //重定位当前结点的函数
int Getposition(void)const; //取当前结点位置的函数
int NextNode(void); //将后继结点设置为当前结点的函数
int InsertAt(const T&item);//在当前结点处插入新结点的函数
void InsertAfter(const T&item); //在当前结点后插入新结点的函数
void DeleteAt(void); // 删除当前结点的函数
void DeleteAfter(void); //删除当前结点后继的函数
T GetData(void)const; //获取当前结点数据的函数
void SetData(const T& item); //修改当前结点数据的函数
bool IsEmpty(void)const;//判断链表是否为空的函数
void Clear(void); //清空链表的函数
void WuXu(int k); //显示最小值
};
# endif
// 链表的类的实现文件 LinkedList.cpp
#include"LinkedList.h"
#include<iostream.h>
#include<stdlib.h>
template <class T>
Node<T>*LinkedList<T>::GetNode(const T&item,Node<T>*ptr) //申请结点空间的函数
{
Node<T>*newNode=new Node<T>(item);
if(!newNode) //若动态内存申请失败，给出相应的提示并返回空指针
{
cerr<<" GetNode: Memoery allocation failed!"<<endl;
return NULL;
}
return newNode; //返回指向新生成结点的指针
}template <class T>
void LinkedList<T>::FreeNode(Node<T>*ptr) //释放结点空间的函数
{
if(!ptr) //若ptr为空，则给出相应提示并返回
{
cerr<<"FreeNode: invaild node pointer!"<<endl;
return ;
}
delete ptr;//释放结点占用的内存空间
}
template <class T>
LinkedList<T>:: LinkedList(void)//建立一个空链表
{
front=NULL;
rear=NULL;
prevptr=NULL;
currptr=NULL;
size=0;
position=-1;
}
template <class T>
LinkedList<T>::~LinkedList(void) //析构函数
{
Clear(); //清空链表，释放所有的结点的内存空间
}
template <class T>
int LinkedList<T>::Size(void)const // 取连表的大小的函数
{
return size;
}
template<class T>
int LinkedList<T>::NextNode(void) //将当后继结点设置为当前结点的函数
{
if(position>=0&&position<size)//若当前结点存在，将其后继结点设置为当前结点
{
position++;
prevptr=currptr;
currptr=currptr->NextNode();
}
else
{
position=0;
prevptr=currptr;
currptr=currptr->NextNode(); //否则将当前结点的位置设为表尾后
}
return position; //返回新的位置
}
template <class T>
int LinkedList<T>:: Getposition(void)const
{
return position;
}
template <class T>
int LinkedList<T>::SetPosition(int pos) //重置当前结点位置的函数
{
if(!size) return -1; //若为空，则返回-1
prevptr=NULL; //寻找对应结点
currptr=front;
position=0;
for(int k=0;k<pos;k++)//寻找对应结点
{
position++;
prevptr=currptr;
currptr=currptr->NextNode();
}
//返回当前结点位置
return position;}template <class T>
int LinkedList<T>::InsertAt(const T&item) //在当前结点处插入新的结点的函数
{
Node<T> L*newNode;
if(!size) //在空表中插入
{
newNode=GetNode(item,front);
front=rear=newNode;
postion=0;
}
else if(!prevptr) //在表头结点插入
{
newNode=GetNode(item,front);
front=newNode;
}
else //在表中间位置插入
{
newNode=GetNode(item, currptr);
prevptr->InsertAfter(newNode);
}
size++; //增加链表的长度
currptr=newNode;//新插入的结点作为当前结点