//linkedlist.h文件
#include<iostream.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);
//重载的赋值运算符
LinkedList<T> & operator = (const LinkedList<T> &orgList) ;
//取表的大小
int Size(void) const ;
//判断表是否为空
bool IsEmpty(void) const;
//重定位当前结点
int NextNode(void) ;
int SetPosition(int pos);
int GetPosition(void) const;
//插入结点的函数
void InsertAt(const T& item);
void InsertAfter(const T& item);
//删除结点的函数
void DeleteAt(void);
void DeleteAfter(void);
//修改和访问数据的函数
T GetData(void) const;
void SetData(const T& item);
//清空链表的函数
void Clear(void);
};
//linkedlist.cpp文件
#include<iostream.h>
#include"linkedlist.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,ptr);
//若动态内存申请失败,则给出相应提示并返回空指针
if(!newNode)
{
cerr<<"GetNode:Memory allocation failed!"<<endl;
return NULL;
}
//返回指向新生成结点的指针
return newNode;
}
//链表类中释放结点空间的函数
template <class T>
void LinkedList <T>::FreeNode(Node<T> *ptr)
{
//若ptr为空,则给出相应提示并返回
if(!ptr)
{
cerr<<"FreeNode: invalid 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>
LinkedList<T> & LinkedList<T>::operator = (const LinkedList<T> &orgList)
{
Node<T> *p=orgList.front;
//清空本链表
Clear();
//将表orgList中的元素复制到本表
while(p)
{
InsertAfter(p->date);
p=p->NextNode();
}
//设置当前结点
SetPosition(orgList.position);
return *this;
}
//链表类中取表大小的函数
template <class T>
int LinkedList<T>::Size(void) const
{
return size;
}
//链表类中判断是否为空的函数
template<class T>
bool LinkedList<T>::IsEmpty(void) const
{
return size?false:true ;
}
//链表类中将后继结点设置为当前结点的函数
template <class T>
int LinkedList<T>::NextNode(void)
{
//若当前结点存在,则将其后继结点设置为当前结点
if((position>=0)&&(position<size))
{
position++;
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
else
{
//否则将当前位置设为表尾后
position=size;
}
//返回新位置
return position;
}
//链表类中重置当前位置的函数
template <class T>
int LinkedList<T>::SetPosition(int pos)
{
//若链表为空,则返回
if(!size) return -1;
//若链表为空,则返回
if(pos<0 || pos>size-1)
{
cerr<<"position error"<<endl;
return -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>::GetPosition(void) const
{
return position;
}
//链表类中在当前结点处插入新结点的函数
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
Node<T> *newNode;
if(!size)
{
//在空表中插入
newNode=GetNode(item,front);
front=rear=newNode;
position=0;
}
else if(!prevPtr)
{
//在表头结点处插入
newNode=GetNode(item,front);
front=newNode;
}
else
{
//在链表的中间位置插入
newNode=GetNode(item,currPtr);
prevPtr->InsertAfter(newNode);
}
//增加链表的大小
size++;
//新插入的结点为当前结点
currPtr=newNode;
}
//链表类中在当前结点后插入新结点的函数
template<class T>
void LinkedList<T>::InsertAfter(const T& item)
{
Node<T> *newNode;
if(!size)
{
//在空表中插入
newNode=GetNode(item);
front=rear=newNode;
position=0;
}
else if (currPtr==rear|| !currPtr)
{
//在表尾结点后插入
newNode=GetNode(item);
rear->InsertAfter(newNode);
prevPtr=rear;
rear=newNode;
position=size;
}
else
{
//在链表的中间位置插入
newNode=GetNode(item,currPtr->NextNode());
currPtr->InsertAfter(newNode);
prevPtr=currPtr;
position++;
}
//增加链表的大小
size++;
//新插入的结点为当前结点
currPtr=newNode;
}
//链表类中删除当前结点的函数
template <class T>
void LinkedList<T>::DeleteAt(void)
{
Node<T> *oldNode;
//若表为空或已到表尾之后,则给出错误提示并返回
if(!currPtr)
{
cerr<<"DeleteAt: current position is invalid!"<<endl;
return ;
}
if(!prevPtr)
{
//删除的是表头结点
oldNode=front;
front=currPtr->NextNode();
}
else
{
//删除的是表中结点
oldNode=prevPtr->DeleteAfter();
}
if(oldNode==rear)
{
//删除的是表尾结点,则修改表尾指针和当前结点位置值
rear=prevPtr;
position--;
}
//后继结点作为新的当前结点
currPtr=oldNode->NextNode();
//释放原当前结点
FreeNode(oldNode);
//链表大小减1
size--;
}
//链表类中删除当前结点后继的函数
template <class T>
void LinkedList<T>::DeleteAfter(void)
{
Node<T> *oldNode;
//若表为空或已到表尾,则给出错误提示并返回
if(!currPtr|| currPtr==rear)
{
cerr<<"DeleteAfter:current position is invalid!"<<endl;
return;
}
//保存被删除结点的指针并从链表中删除该结点
oldNode=currPtr->DeleteAfter();
if(oldNode==rear)
{
//删除的是表尾结点
rear=currPtr;
}
//释放被删除结点
FreeNode(oldNode);
//链表大小减1
size--;
}
//链表类中获取当前结点数据的函数
template <class T>
T LinkedList<T>::GetData(void) const
{
//若表为空或已到达表尾之后,则出错
if(!size || !currPtr)
{
//给出出错信息并退出
cerr<<"Data:current node not exist!"<<endl;
exit(1);
}
return currPtr->data ;
}
//链表类中修改当前结点数据的函数
template <class T>
void LinkedList<T>::SetData(const T& item)
{
//若表为空或已经达到表尾之后,则出错
if(!size || !currPtr)
{
cerr<<"Data:current node not exist!"<<endl;
exit(1);
}
//修改当前结点的值
currPtr->data=item;
}
//链表类中清空链表的函数
template <class T>
void LinkedList<T>::Clear(void)
{
Node<T> *currNode=front, *nextNode ;
while(currNode)
{
//保存后继结点指针
nextNode=currNode->NextNode();
//释放当前结点
FreeNode(currNode);
//原后继结点成为当前结点
currNode=nextNode;
}
//修改空链表数据
front=rear=prevPtr=currPtr=NULL ;
size=0;position=-1;
}
yuesefu.rar_yuesefu
版权申诉
68 浏览量
2022-09-19
13:58:35
上传
评论
收藏 22KB RAR 举报
钱亚锋
- 粉丝: 88
- 资源: 1万+
最新资源
- 教学内容及补充-cha7.rar
- 设计1.ms14
- vscode-1.64.1.tar源码文件
- vscode-1.64.0.tar源码文件
- vscode-1.52.0.tar源码文件
- Music-Player +PlayerActivity+ rockplayer+ SeeJoPlayer 播放器JAVA源码
- vscode-1.46.0.tar源码文件
- 最近很火植物大战僵尸杂交版2.08苹果+安卓+PC+防闪退工具V2+修改工具+高清工具+通关存档整合包更新
- 超级好用的截图工具PixPin,可录制Gif图
- Screenshot_2024-05-21-17-06-42-64_2332cb9b27b851b548ba47a91682926c.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈