////////////////////////////////////////////////////////////////////////////
//// Link.h
//// 适用教材：《数据结构》C++版
//// 刘大有等编著 高等教育出版社
////////////////////////////////////////////////////////////////////////////
#ifndef __LINKEDLIST_HPP__
#define __LINKEDLIST_HPP__
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
extern "C" {
int exit(int);
};
//单链表结点类定义
template <class T> //结点数据域data的类型以参数 (模板)形式提供
class Node {
public: //公有成员
T data; //数据域，允许外部直接访问
private: //私有成员
Node<T> *next; //指针域(链域)，指向后继结点的指针
public: //公有成员
//构造函数(初始化data和next)
Node(const T& item, Node<T> *pNext=NULL) :
data(item), next(pNext){}
//在当前结点之后插入指针p所指结点
void InsertAfter(Node<T> *p) {
if (!p) return; //若p为空，则返回
p->next = next; //将待插入结点p的next指向当前结点的next域
next = p; //将当前结点的next更新为待插入结点p
}
//删除当前结点的后继结点并返回被删除结点的地址
Node<T> *DeleteAfter() {
if (!next) return NULL; //若无后继(next为NULL)，则返回
Node<T> *pNext = next; //next不为空，则记录其地址(留待函数返回后做处理)
next = next->next; //用后继结点(next)的后继来更改当前结点的next域
return pNext; //返回已记录下的待删除结点地址
}
//返回指向当前结点的后继结点的指针
Node<T> *NextNode() const { return next; }
T GetData() const { return data; }
void SetData(const T &item) { data = item; }
};
//单链表类定义
template <class T>
class LinkedList {
private:
Node<T> *front, *rear; //表头,表尾
Node<T> *currptr; //指向当前结点的指针
int size; //表长(结点的个数)
private:
//生成新结点
Node<T> *GetNode(const T& item, Node<T> *pNext = NULL) {
Node<T> *newNode;
//新分配一结点存储空间并初始化数据成员
newNode = new Node<T>(item, pNext);
if (!newNode) {
cerr << "存储空间分配失败！程序将终止。" << endl;
exit(1);
}
return newNode;
}
//释放结点p
void *freeNode(Node<T> *p) { if (p) delete p; }
private:
//当链表为空时插入结点时的处理
int InsertNewNodeWhenListIsEmpty(const T &item) {
if (size > 0) return 0; //不为空表，返回False(0)
currptr = GetNode(item);
front = currptr;
rear = currptr;
size ++;
return 1; //在空表中插入了结点，返回True(1)
}
public:
//构造函数
LinkedList() {
front = NULL;
rear = NULL;
currptr = NULL;
size = 0;
}
//拷贝构造函数
LinkedList(const LinkedList<T> &L) {
size = 0;
Node<T> *p;
p = L.front;
if (!p) { //L为空链表
front = NULL;
rear = NULL;
currptr = NULL;
return;
}
front = GetNode(p->GetData());
currptr = front;
rear = front;
p = p->NextNode();
while (p) {
rear = GetNode(p->GetData());
currptr->InsertAfter(rear);
p = p->NextNode();
currptr = rear;
}
currptr = front;
}
//析构函数
~LinkedList() {
ClearList();
}
public:
//带入运算符的重载
LinkedList<T> & operator=(const LinkedList<T> &L) {
ClearList(); //先清空当前List内容
Node<T> *p;
p = L.front; //p指向待拷贝链表L的表头
if (!p) { //L为空链表
front = NULL;
rear = NULL;
currptr = NULL;
prevptr = NULL;
return;
}
front = GetNode(p->GetData());
currptr = front;
prevptr = front;
rear = front;
p = p->NextNode();
while (p) {
rear = GetNode(p->GetData());
currptr->InsertAfter(rear);
p = p->NextNode();
currptr = rear;
}
currptr = front;
}
public:
//返回表长
int ListSize() const {
return size;
}
//判断链表是否为空
int ListEmpty() const {
return size == 0;
}
//重置当前指针currptr
void Reset(int pos = 0) {
//若pos超出范围，则返回
if (pos < 0 || pos >= size) return;
register int i = 0;
currptr = front; //从表头开始
//将currptr定位至位序为pos的结点处
while (i < pos) {
currptr = currptr->NextNode();
i ++;
}
}
//将当前指针定位至数据域取值为item的结点处
int Locate(const T &item, int bBeginFromCurrentPos = 1) {
if (size == 0) return -1; //空表时返回-1
Node<T> *p;
if (!currptr) currptr = front;
if (bBeginFromCurrentPos != 1)
p = front; //从表头结点开始
else
p = currptr; //从当前位置开始
while (p) {
if (p->GetData() == item) break; //T所对应的数据类型应支持==运算符
p = p->NextNode();
}
if (!p) return -1;
currptr = p; //定位至所找到的结点
return ThisPosition(); //返回该结点的位序
}
//移动currptr至下一结点
void Next() {
if (size == 0) return; //若为空表，则不处理
if (currptr == rear) return; //若为表尾，则不再后移
if (!currptr) { currptr = front; return; } //若为NULL则移向表头
currptr = currptr->NextNode(); //移向下一结点
}
//判断是否表尾
int EndOfList() const {
return currptr == rear;
}
//返回currptr结点位序
int ThisPosition() const {
if (size == 0) return -1; //空表时返回-1
Node<T> *p = front;
register int i = 0;
while (p && (p != currptr)) {
p = p->NextNode();
i++;
}
if (p) return i; //若找到currptr所指结点，则返回其位序
else return -1; //未找到时，返回-1
}
public:
//表头插入
void InsertFront(const T &item) {
front = GetNode(item, front);
currptr = front;
if (size == 0) rear = front;
size ++;
}
//表尾插入
void InsertRear(const T &item) {
currptr = GetNode(item);
if (size == 0)
front = currptr;
else
rear->InsertAfter(currptr);
rear = currptr;
size ++;
}
//在当前节点前插入
void InsertAt(const T &item) {
if (InsertNewNodeWhenListIsEmpty(item)) return; //链表为空时的插入
if (currptr == front) {
InsertFront(item);
return;
}
prevptr = front;
while (prevptr && (prevptr->NextNode() != currptr))
prevptr = prevptr->NextNode();
if (!prevptr) return;
currptr = GetNode(item);
prevptr->InsertAfter(currptr);
}
//在当前结点后插入
void InsertAfter(const T &item) {
if (InsertNewNodeWhenListIsEmpty(item)) return; //为空时的插入
if (!currptr) { //若currptr为空，则插入表头
currptr = GetNode(item, front);
front = currptr;
size ++;
return;
}
//在当前结点之后插入新结点
currptr->InsertAfter(GetNode(item));
if (currptr == rear) //若为表尾插入，则修改rear指针
rear = currptr->NextNode();
currptr = currptr->NextNode();
size ++;
}
//在指定位置（位序）处插入结点
void InsertAtPos(const T &item, int pos = -1) {
if (pos <= 0) { InsertFront(item); return; }
if (pos >= size) { InsertRear(item); return; }
if (size == 0) { InsertNewNodeWhenListIsEmpty(item); return; }
register int i = 1;
currptr = front;
//定位至位序为pos的结点的前驱结点处
while (currptr && (i < pos)) {
currptr = currptr->NextNode();
i ++;
}
if (!currptr) return;
currptr->InsertAfter(GetNode(item));
currptr = currptr->NextNode();
size ++;
}
//删除表头结点
void DeleteFront() {
if (!front) return; //链表已空
currptr = front->NextNode();
delete front;
front = currptr;
size --;
if (size == 0) rear = currptr; //链表已空, NULL
}
//删除当前结点
void DeleteAt() {
if (!currptr) return; //若无当前结点
if (currptr == front) { //若为表头
currptr = front->NextNode();
delete front;
front = currptr;
size --;
if (size == 0) rear = currptr; //链表已空, NULL
return;
}
Node<T> *prevptr = front;
while (prevptr) { //查找currptr的前驱结点
if (prevptr->NextNode() == currptr) break;
prevptr = prevptr->NextNode();
}
if (!prevptr) return;
if (currptr == rear) //若当前结点为表尾，则更新表尾
rear = prevptr;
prevptr->DeleteAfter(); //从链表中脱离结点currptr
delete currptr; //释放结点
if (prevptr->NextNode()) //更新currptr的值
currptr = prevptr->NextNode();
else
currptr = prevptr;
}
//删除指定位序处的结点
void DeleteAtPos(int pos = -1) {
if (pos < 1) { DeleteFront(); return; }
register int i = 1;
Node<T> *p = front;
while (p && (i < pos)) {
p = p->NextNode();
i ++;
}
if (!p) return;
currptr = p->DeleteAfter();
delete currptr;
if (p->NextNode()) //更新currptr的值
currptr = p->NextNode();
else
currptr = p;
}
//返回当前结点的数据域值(data)
T &Data() {
if (currptr)
return currptr->GetData();
//else
// return T();
}
//清空整个链表
void ClearList() {
while (front) {
currptr = front->NextNode();
delete front;
front = currptr;
}
//front = NULL;
rear = NULL;
currptr = NULL;
size = 0;
}
//输出List结点内容，每行m个。
void PrintList(
const char* sDelimiter = " ", //结点间的分隔符(串)
int m = -1, //每输出m个元素后换行，m<=0时忽略
ostream &stream = cout, //缺省输出到屏幕cout
int bEndWithNewLine = 1 //输出完毕后是否换行
) const {
Node<T> *p = front;
register int cnt = 0;
while (p) { //结点数据域类型T需支持输出运算符<<
stream << p->GetData();
if (p != rear) stream << sDelimiter;
p = p->NextNode();
if (m < 1) continue;
if (++cnt == m) {
stream << endl;
cnt = 0;
}
}
if (bEndWithNewLine && (m < 1 || cnt > 0))
stream << endl;
}
};
#endif //!__LINKEDLIST_HPP__
