一、线性表
线性表是一种抽象的数据类型，下面介绍几种具体的线性表存储结构（即物理结构）：顺序、链式和静态链式。无论线性表采用哪种数据结构，她们的逻辑结构是一样的，都有以下性质：除第一个元素外，线性表中每个元素都有一个前驱元素；除最后一个元素外，线性表中每一个元素都有一个后继元素。
实现：
//线性表抽象类的定义
template<typename T>class AList
{
public:
void ClearList(); //重置线性表为空表
bool ListEmpty()const; //若线性表为空表，则返回 true；否则返回 false
int LocateElem(T e, bool(*eq) (T, T))const;
//返回第一个与 e 满足关系 eq() 的数据元素的位序，若这样的元素不存在，则返回值为 0
bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const;
//若 e 与表的某数据元素满足定义的 eq() 相等关系，且该数据不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const;
//若 e 与表中的某数据元素满足定义的 eq() 相等关系，且该数据不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
bool ListDelete(int i, T &e);
//删除线性表第 i 个数据元素（1 <= i <= ListLength()），并用 e 返回其值
void ListTraverse(void(*visit) (T*))const;
//依次对每个数据元素调用函数 visit()
virtual bool GetElem(int i, T &e)const=0; //纯虚函数
//用 e 返回线性表第 i 个元素的值（1 <= i <= ListLength()）
virtual bool ListInsert(int i, T e)=0;
//在线性表第 i 个位置（1 <= i <= ListLength()）之前插入新的数据元素
virtual int ListLength()const=0; //返回线性表的长度，常成员函数，不改变对象的值
};
1. 顺序存储结构
顺序存储结构容易实现随机查找线性表的第 i 个元素的操作，但在实现插入和删除操作时要移动大量的数据元素。所以，它适用于数据相对稳定的线性表。
实现：
//继承 AList 的顺序表类
template<typename T>class SqList: public AList<T>
{
friend void MergeList(const SqList<T>&, const SqList<T>&, SqList<T>&);
//声明普通函数 MerfeList() 为 SqList 类的友元
private:
T *elem; //线性表存储空间的基址
int length; //线性表的当前表长
int listsize; //线性表当前的存储容量
public:
SqList(int k=1)
{//构造函数，动态生成具有 k 个初始存储空间的空线性表
elem = new T[k];
assert(elem != NULL); //存储分配失败，退出
length = 0; //空表长度为 0
listsize = k; //初始存储容量
}
~SqList()
{//析构函数
delete[] elem; //释放 elem 所指的存储空间数组
}
void ClearList()
{//重置线性表为空表
length = 0;
}
bool ListEmpty()const //常成员函数，不会改变对象的值
{//若线性表为空表，则返回 true；否则返回 false
return length == 0;
}
int ListLength()const
{//返回线性表的长度
return length;
}
bool GetElem(int i, T &e)const
{//用 e 返回线性表第 i 个元素的值（1 <= i <= ListLength()）
if (i < 1 || i > length) //i 不再表的范围之内
return false;
e = *(elem + i - 1); //将第 i 个元素的值赋给 e
return true;
}
int LocateElem(T e, bool(*eq) (T, T))const
{//返回第一个与 e 满足关系 eq() 的数据元素的位序，若这样的元素不存在，则返回值为 0
int i = 1; //i 的初值指第一个元素
while(i <= length && !eq(*(elem + i - 1), e))
//i 没超出表的范围且 i 指向的数据元素与 e 不满足关系
i++; //计数加 1 ，继续往后找
if (i <= length) //找到满足关系的数据元素
return i; //返回其位序
else //没找到满足关系的数据元素
return 0;
}
int PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
{//若 e 与表的某数据元素满足 eq() 关系，且该数据元素不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
int i = LocateElem(e, eq); //将第一个满足关系的数据元素的位序赋给 i
if (i <= 1) //没找到，或是第一个元素
return false; //操作失败
else //找到了值为 e 的元素，其位序为 i
{
pre_e = *(elem + i - 2); //将前一个元素的值赋给 pre_e
return true; //操作成功
}
}
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
{//若 e 与表的某数据元素满足 eq() 关系，且该数据元素不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
int i = LocateElem(e, eq);
if (i == 0 || i == length) //没找到，或是最后一个元素
return false;
else
{
next_e = *(elem + i);
return true;
}
}
bool ListInsert(int i, T e)
{//在线性表第 i 个位置（1 <= i <= ListLength()）之前插入新的数据元素 e
T *newbase, *q, *p;
if (i < 1 || i > length) //i 值不合法
return false;
if (length == listsize) //当前存储空间已满
{
newbase = new T[listsize * 2];
assert(newbase != NULL); //存储空间分配失败，退出
for (int j = 0; j < length; j++)
*(newbase + j) = *(elem + j); //将原表空间中的数据复制到新的表空间
delete[] elem; //释放原表空间
elem = newbase; //新基址赋给 elem
listsize *= 2; //更新存储容量
}
q = elem + i - 1; // q 为插入位置
for (p = elem + length - 1; p >= q; p--) //插入位置之后的元素后移
*(p + 1) = *p;
*q = e;
length++;
return true;
}
bool ListDelete(int i, T &e)
{//删除线性表第 i 个元素（1 <= i <= ListLength()），并用 e 返回其值
T *p, *q;
if (i < 1 || i > length) //i 值不合法
return false;
p = elem + i - 1; //p 为被删除元素的位置
e = *p;
q = elem + length -1; //q 为表尾元素的位置
for (++p; p <= q; ++p) //被删除元素之后的元素前移
*(p - 1) = *p;
length--;
return true;
}
void ListTraverse(void(*visit) (T*))const;
{//依次对每个数据元素调用函数 visit()
for (int i = 0; i < length; i++)
visit(elem + i); //对每个数据元素调用 visit()
cout << endl;
}
};
2. 链式存储
与顺序存储相比，链式存储结构在实现插入、删除的操作时不需要移动大量数据元素，但是不容易实现随机存取线性表的第 i 个数据元素的操作。所以，链式存储结构适用于经常需要进行插入和删除操作的线性表。
2.1 单链表
实现：
//单链表结点类型结构体
template<typename T>struct LNode
{
T data; //结点数据类型
LNode<T> *next; //后继指针
}；
//单链表的类
template<typename T>class LinkList: public AList
{//带模板并继承 AList 的单链表类
friend void MergeList(LinkList<T>&, LinkList<T>&);
protected:
LNode<T> *Head; //头指针
public:
LinkList()
{//构造函数，构造一个空的线性表
Head = new LNode<T>; //产生头结点
assert(Head != NULL); //存储空间分配失败，退出
Head->next = NULL; //头结点的指针为空
}
~LinkList()
{//析构函数，销毁线性表
ClearList(); //置为空表
delete Head; //释放头结点
}
void ClearList()const
{//重置线性表为空
LNode<T> *q, *p = Head->next; //p 指向第一个结点
Head->next = NULL; //头结点指针域为空
while(!p = NULL) //释放其他结点
{
q = p->next;
delete p;
p = q;
}
}
bool ListEmpty()const
{//若线性表为空表，则返回 true，否则返回 false
return Head->next == NULL;
}
int ListLength()const
{//返回线性表的长度
int i = 0; //计数器初值为 0
LNode<T> *p = Head->next; //p 指向第一个结点
while(p != NULL) //没到表尾
{
i++;
p->next;
}
return i;
}
bool GetElem(int i, T &e)const
{//当第 i 个元素存在（1 <= i <= ListLength()）时，其值赋给 e 并返回 true ，
//否则返回 false
int j = 1;
LNode<T> *p = Head->next; //p 指向第一个结点
while(p != NULL && j < i) //顺序查找
{
j++;
p = p->next;
}
if (p == NULL || j > i)
return false;
e = p->data;
return true;
}
int LocateElem(T e, bool(*eq) (T, T))const
{//返回第一个与 e 满足 eq() 关系的数据元素的位序，若这样的元素不存在，则返回 0
int i = 0;
LNode<T> *p = Head->next;
while(p != NULL)
{
i++;
if (eq(p->data, e))
return i;
p = p->next;
}
return 0;
}
bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
{//若 e 与表中的某数据元素满足 eq() 关系，且该元素不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
LNode<T> *p = Head->next;
while(p != NULL && p->next != NULL) //p 所指结点有后继
{
q = p->next;
if (eq(q->data, e))
{
pre_e = p->data;
return true;
}
p = q; //p 的后继 q 不等于 e ，p 向后移
}
return false;
}
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
{//若 e 与表中某数据元素满足 eq() 关系，且该元素不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
LNode<T> *p = Head->next;
while(p != NULL && p->next != NULL)
{
if (eq(p->data, e))
{
next_e = p->next->data;
return true;
}
p = p->next;
}
return false;
}
bool ListInsert(int i, T e)
{//在带头结点的单链表中第 i 个位置（1 <= i <= ListLength()）之前插入新的数据元素 e
int j = 0;
LNode<T> *s, *p = Head;
while(p != NULL && j < i-1) //寻找第 i-1 个结点
{
j++;
p = p->next;
}
if (p == NULL || j > i-1) //i 小于 1 或者大于表长+1
return false;
s = new LNode<T>; //生成新结点
if (s == NULL) //生成新结点失败
return false; //插入失败
s->data = e;
s->next = p->next; //新结点指向原第 i 个结点
p-next = s; //原第 i-1 个结点指向新结点
return true; //插入成功
}
bool ListDelete(int i, T &e)const
{//在带头结点的单链线性表中删除第 i 个数据元素（1 <= i <= ListLength()），
//并用 e 返回其值
int j = 0;
LNode<T> *q, *p = Head;
while(p->next != NULL && j < i-1) //寻找第 i 个结点，并令 p 指向其前驱
{
j++;
p = p->next;
}
if (p->next == NULL || j > i-1)
return false;
q = p->next; //q 指向删除结点
p->next = q->next; //待删结点的前驱指向待删结点的后继
e = q->data;
delete q;
return true;
}
void ListTraverse(void(*visit) (T*))const
{//依次对每个数据元素调用函数 visit()
LNode<T> *p = Head->next;
while(p != NULL)
{
visit(&p->data);
p = p->next;
}
cout << endl;
}
};
2.2 单循环链表
单循环链表结点的存储结构和单链表结点的一样，不同的是：单循环链表最后一个结点的指针域指向头结点，而不是 NULL 。这样，由表尾很容易找到表头。但若链表较长，则由表头找到表尾仍较费时。因而，单循环链表往往设立尾指针而不是头指针。这样，查找最后一个结点和头结点都很方便。这在两个链表首尾相连合并成一个链表时尤为方便。
实现：
//设立尾指针的单循环链表的类
template<typename T>class LinkListCy: public AList
{//带模板并继承 AList 的单循环链表类
friend void MergeList(LinkListCy<T>&, LinkListCy<T>&);
private:
LNode<T> *Tail; //尾指针
public:
LinkListCy()
{//构造函数，构造一个空的线性表
Tail = new LNode<T>; //产生头结点，并使 Tail 指向此头结点（尾指针指向头结点）
assert(Tail != NULL); //存储分配失败，退出
Tail->next = Tail; //头结点的指针域指向头结点
}
~LinkListCy()
{//析构函数，销毁线性表
ClearList(); //将线性表重置为空表
delete Tail; //释放头结点
}
void ClearList()
{//将线性表重置为空表
LNode<T> *p, *q;
Tail = Tail->next; //Tail 指向头结点
p = Tail->next; //p 指向第一个结点
while(p != Tail) //没到表尾
{
q = p->next;
delete p;
p = q;
}
Tail->next = Tail; //头结点指针域指向自身
}
bool ListEmpty()const
{//若线性表为空表，则返回 true ；否则返回 false
return Tail->next==Tail;
}
int ListLength()const
{//返回线性表中数据元素个数
int i = 0;
LNode<T> *p = Tail->next; //p指向头结点
while(p != Tail)
{
i++;
p = p->next;
}
return i;
}
bool GetElem(int i, T &e)const
{//在第 i 个元素存在时，其值赋给 e 并返回 true ；否则返回 false
int j = 1;
LNode<T> *p = Tail->next->next; //p 指向第一个结点
if (i <= 0 || i > ListLength())
return false;
while(j < i)
{
j++;
p = p->next;
}
e = p->data;
return true;
}
int LocateElem(T e, bool(*eq) (T, T))const
{//返回第一个与 e 满足 eq() 关系的数据元素的位序，若这样的元素不存在，则返回 0
int i = 0;
LNode<T> *p = Tail->next->next; //p 指向第一个结点
while(p != Tail->next)
{
i++;
if (eq(p->data, e))
return i;
p = p->next;
}
return 0;
}
bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
{//若 e 与表中的某数据元素满足 eq() 关系，且该元素不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
LNode<T> *q, *p = Tail->next->next; //p 指向第一个结点
q = p->next;
while(q != Tail->next)
{
if (eq(q->data, e))
{
pre_e = p->data;
return true;
}
p = q; //p 的后继 q 不等于 e ，p 向后移
q = q->next;
}
return false;
}
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
{//若 e 与表中某数据元素满足 eq() 关系，且该元素不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
LNode<T> *p = Tail->next->next;
while(p != Tail)
{
if (eq(p->data, e))
{
next_e = p->next->data;
return true;
}
p = p->next;
}
return false;
}
bool ListInsert(int i, T e)
{//在带头结点的单链表中第 i 个位置（1 <= i <= ListLength()）之前插入新的数据元素 e
int j = 0;
LNode<T> *p = Head;
if (i <= 0 || i > ListLength()+1)
return false;
while(j < i-1) //寻找第 i-1 个结点
{
j++;
p = p->next;
}
s = new LNode<T>; //生成新结点
if (s == NULL) //生成新结点失败
return false; //插入失败
s->data = e;
s->next = p->next; //新结点指向原第 i 个结点
p-next = s; //原第 i-1 个结点指向新结点
if (p == Tail) //插在表尾
Tail = s;
return true; //插入成功
}
bool ListDelete(int i, T &e)
{//在带头结点的单链线性表中删除第 i 个数据元素（1 <= i <= ListLength()），
//并用 e 返回其值
int j = 0;
LNode<T> *q, *p = Tail->next;
if (i <= 0 || i > ListLength())
return false;
while(j < i-1) //寻找第 i 个结点，并令 p 指向其前驱
{
j++;
p = p->next;
}
q = p->next; //q 指向删除结点
p->next = q->next; //待删结点的前驱指向待删结点的后继
e = q->data;
if (Tail == q)
Tail=p;
delete q;
return true;
}
void ListTraverse(void(*visit) (T*))const
{//依次对每个数据元素调用函数 visit()
LNode<T> *p = Tail->next->next;
while(p != Tail->next) //p 不指向头结点
{
visit(&p->data);
p = p->next;
}
cout << endl;
}
};
2.3 双向循环链表
实现：
//双向结点类型结构体
template<typename T>struct DLNode
{
T data;
DLNode<T> *prior, *next;
}
//双向链表类
template<typename T> class DLinkList: public AList<T>
{//带模板并继承 AList 的双向链表类
private:
DLNode<T> *Head; //头指针
DLNode<T>* GetElemP(int i)const
{//在双向链表中返回第 i 个结点的地址，i 为 0 ，则返回头结点的地址
//若第 i 个结点不存在，则返回 NULL
int j = 0;
DLNode<T> *p = Head;
if (i < 0)
return NULL;
if (i == 0)
return p;
do
{
p = p->next;
j++;
}while(p != Head && j < i); //p 没返回到头结点并且还没到第 i 个结点
if (p == Head) //查找失败
return NULL;
else
return p;
}
DLNode<T>* GetElemE(T e, bool(*eq) (T, T))const
{//在双向链表中返回第一个与 e 满足定义的 eq() 相等关系的数据元素地址
//若这样的数据元素不存在，返回 NULL
DLNode<T> *P = Head->next;
while(p != Head && !eq(p->data, e))
p = p->next;
if (p == Head) //这样的元素不存在
return NULL;
else
return p;
}
public:
DLinkList()
{//构造一个空的双向循环链表
Head = new DLNode<T>; //产生头结点
assert(Head != NULL)
Head->next = Head->prior = Head; //头结点的指针域指向自身
}
~DLinkList()
{//析构函数，销毁双向链表
ClearList(); //置为空表
delete Head; //释放头结点
}
void ClearList()const
{//重置双向循环线性表为空表
DLNode<T> *P = Head->next;
while(p != Head)
{
p = p->next;
delete p->prior;
}
Head->next = Head->prior = Head;
}
bool ListEmpty()const
{//若线性表为空表，则返回 true ；否则返回 false
return Head->next == Head;
}
int ListLength()const
{//返回线性表的长度
int i = 0;
DLNode<T> *p = Head->next;
while(p != Head)
{
i++;
p = p->next;
}
return i;
}
bool GetElem(int i, T &e)const
{//在第 i 个元素存在时，其值赋给 e 并返回 true ；否则返回 false
DLNode<T> *p = GetElemP(i); //p 指向第 i 个结点
if (p != NULL) //第 i 个结点存在
{
e = p->data;
return true;
}
else
return false;
}
int LocateElem(T e, bool(*eq) (T, T))const
{//返回第一个与 e 满足 eq() 关系的数据元素的位序，若这样的元素不存在，则返回 0
int i = 0;
LNode<T> *p = Head->next; //p 指向第一个结点
while(p != Head)
{
i++;
if (eq(p->data, e))
return i;
p = p->next;
}
return 0;
}
bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
{//若 e 与表中的某数据元素满足 eq() 关系，且该元素不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
LNode<T> *p = GetElemE(e, eq); //p 指向结点 e
if (p != NULL && p->prior != Head) //p 指向值为 e 的结点且该结点不是第一个结点
{
pre_e = p->prior->data;
return true;
}
return false;
}
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
{//若 e 与表中某数据元素满足 eq() 关系，且该元素不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
DLNode<T> *p = GetElemE(e, eq); //p 指向结点 e
if (p != NULL && p->next != Head) //p 指向值为e的结点且该结点不是最后一个结点
{
pre_e = p->next->data;
return true;
}
return false;
}
bool ListInsert(int i, T e)
{//在带头结点的单链表中第 i 个位置（1 <= i <= ListLength()）之前插入新的数据元素 e
DLNode<T> *s, *p = GetElemP(i-1); //确定第 i 个结点前驱的位置指针 p
if (p = NULL) //第 i 个结点的前驱不存在（设头结点为第 0 个结点）
return false;
s = new DLNode<T>; //生成新结点
if (s == NULL)
return false; //生成失败
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
return true;
}
bool ListDelete(int i, T &e)
{//在带头结点的单链线性表中删除第 i 个数据元素（1 <= i <= ListLength()），
//并用 e 返回其值
DLNode<T> *p =GetElemP(i);
if (p == NULL)
return false;
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
return true;
}
void ListTraverse(void(*visit) (T*))const
{//依次对每个数据元素调用函数 visit()
DLNode<T> *p = Head->next;
while(p != Head) //p 不指向头结点
{
visit(&p->data);
p = p->next;
}
cout << endl;
}
void ListBackTraverse(void(*visit) (T*))const
{//由双向循环线性表的头结点出发，逆序对每个元素调用函数 visit()
DLNode<T> *p = Head->prior; //p 指向尾结点
while(p != Head)
{
visit(&p->data);
p = p->prior;
}
cout << endl;
}
};
2.4 不设头结点的链表
链表也可以不设头结点，这样看起来更自然一些。但不设头结点会使得对第 1 个元素做插入或删除的操作与其他元素不同，这会带来编程上的麻烦。不设头结点的双向循环链表在动态存储管理中有应用。下面对它们做简单介绍，因为是简单介绍，没有完全实现线性表抽象类 AList 的 3 个纯虚函数，故他们不能继承 AList 。
实现：
//不设头结点的单链表类
template<typename T>class LinkListNH
{//带模板的不设头结点的单链表类
private:
LNode<T> *Head; //头指针
public:
LinkListNH()
{//构造函数，构造一个空的线性表
Head = NULL; //指针为空
}
~LinkListNH()
{//析构函数，销毁线性表
ClearList(); //将线性表重置为空表
}
void ClearList()
{//将线性表重置为空表
LNode<T> *p;
while(Head != NULL) //表不为空
{
p = Head; //p 指向第一个结点
Head = Head->next; //Head 指向下一个结点
delete p;
}
}
int ListLength()const
{//返回线性表的长度
int i = 0;
LNode<T> *p = Head; //p指向头结点
while(p != NULL)
{
i++;
p = p->next;
}
return i;
}
int LocateElem(T e, bool(*eq) (T, T))const
{//返回第一个与 e 满足 eq() 关系的数据元素的位序，若这样的元素不存在，则返回 0
int i = 0;
LNode<T> *p = Head; //p 指向第一个结点
while(p != NULL)
{
i++;
if (eq(p->data, e))
return i;
p = p->next;
}
return 0;
}
LNode<T>* Point(T e, bool(*eq) (T, T), LNode<T>* &p)const
{//查找表中第一个与 e 满足 eq() 关系的结点，如找到，返回指向该结点的指针，
//p 指向该结点的前驱（若该结点是第一个结点，则 p=NULL）,没找到则返回NULL，p无定义
if (Head) //表不空
if (eq(Head->data, e))
{
p = NULL;
return Head;
}
else
{
p = Head;
while(p->next->data, e)
if (eq(p->next->data, e))
return p->next;
else
p = p->next;
}
return NULL;
}
bool ListInsert(int i, T e)
{//在不设头结点的单链线性表第 i 个位置之前插入元素 e
int j = 1;
LNode<T> *s, *p = Head;
if (i < 1)
return false;
s = new LNode<T>;
if (s == NULL)
return false;
s->data = e;
if (i == 1) //插在表头
{
s->next = Head; //新结点指向原第一结点
Head = s; //Head 指向新结点
}
else
{//插在表的其余处
while(p != NULL && j < i-1) //寻找第 i-1 个结点
{
j++;
p = p->next;
}
if (p == NULL) //i 大于表长+1
return false;
else //p 指向第 i-1 个结点
{
s->next = p->next;
p-next = s;
}
}
return true;
}
bool ListDelete(T e, bool(*eq) (T, T))
{//在不设头结点的单链线性表中，删除与 e 满足 eq() 关系的结点
LNode<T> *p, *q;
q = Point(e, eq, p); //p 指向待删结点的前驱
if (q == NULL) //没找到待删结点
return false;
else //找到待删结点
{
if (p == NULL) //待删结点是第一个结点
Head = q->next;
else
p->next = q->next;
delete q;
return true;
}
}
void ListTraverse(void(*visit) (T*))const
{//依次对每个数据元素调用函数 visit()
LNode<T> *p = Head; //p 指向第一个结点
while(p != NULL) //p 所指结点存在
{
visit(&p->data);
p = p->next;
}
cout << endl;
}
};
//不设头结点的双向链表的类
template<typename T>class DLinkListNH
{//带模板的不设头结点的双向链表类
friend void Joseph(int, int);
friend class BoundaryLogo; //声明边界标识法类为友类
friend class BuddySystem; //声明伙伴系统为友类
private：
DLNode<T> *Head; //头指针
DLNode<T>* GetElemP(int i)const
{//在双向链表中返回第 i 个结点的地址，若第 i 个结点不存在，返回 NULL
int j = 1;
DLNode<T> *p = Head; //p 指向第一个结点
if (i <= 0 || Head == NULL)
return NULL;
if (i == 1) //第一个结点
return p;
do
{
p = p->next;
j++;
}while(p != Head && j < i);
if (p == Head) //第 i 个结点不存在
return NULL;
else
return p;
}
public:
DLinkListNH()
{//构造一个空的双向循环链表
Head = NULL; //头指针为空
}
~DLinkListNH()
{//析构函数，销毁双向循环链表
ClearList();
}
void ClearList()
{//重置双向循环链表为空表
//不带头结点的循环链表可以解开先循环再依次删除，
//也可以不解开循环进行依次删除，不过最后还得单独把头指针所指向的结点删除
DLNode<T> *p = Head; //p 指向第一个结点
if (Head != NULL)
{
Head->prior->next = NULL; //打开循环链表为单链表，很关键
while(p != NULL)
{
p = p->next;
delete Head;
Head = p;
}
}
}
int ListLength()const
{//返回线性表的长度
int i = 0;
DLNode<T> *p = Head;
if (Head != NULL)
do
{
i++;
p = p->next;
}while(p != Head);
return i;
}
bool ListInsert(int i, T e)
{//在不设头结点的双向循环链表中第 i 个位置之前插入新的数据元素 e
DLNode<T> *s, *p = GetElemP(i-1); //p 指向第 i-1 个结点
s = new DLNode<T>;
if (s == NULL)
return false;
s->data = e;
if (i == 1) //在第一个结点前插入
{
if (Head == NULL)
s->prior = s->next =s;
else
{
s->prior = Head->prior;
s->next = Head;
s->prior->next = s;
s->next->prior =s;
}
Head = s;
return true;
}
else //i > 1
{
if (p == NULL) //第 i-1 个结点不存在
return false;
else
{
s->next = p->next;
s->prior = p;
s->next->prior = s;
p->next = s;
return true;
}
}
}
bool ListDelete(int i, T &e)
{//删除不带头结点的双向循环链表的第 i 个元素，并用 e 返回其值
DLNode<T> *p = GetElemP(i); //p 指向第 i 个结点
if (p == NULL)
return false;
e = p->data;
if (p->next == p) //表中只有一个元素，且将被删除
Head == NULL;
else //表中有多个元素
{
P->next->prior = p->prior;
p->prior->next = p->next;
if (p == Head) //删除的是第一个结点
Head = p->next;
}
delete p;
return true;
}
void ListTraverse(void(*visit) (T*))const
{//依次对双向循环链表的每个数据元素调用函数 visit()
DLNode<T> *p = Head;
if (Head != NULL)
do
{
visit(p->data);
p = p->next;
}while(p != Head)
cout << endl;
}
};
用不设头结点的循环链表解决某些问题比较方便，如约瑟夫环问题：n 个小孩围坐一圈，由第一个小孩开始，依次循环报数，报到 m 的小孩出列。从下一个小孩重新开始循环报数，直到所有小孩都出列，求小孩出列顺序。
C++ 的标准模板库（STL）也提供了链表类的操作，称为 list （表），使用双向链表实现的。可以访问cplusplus查询相关操作函数。
3. 静态链表存储结构
顺序存储结构也可以实现链式存储功能。首先，开辟一个充分大的结构体数组。结构体数组的一个成员（data）存放数据，另一个成员（link）存放链表中的下一个数据元素在数组中的位置（下标），这称为静态链表。
静态链表存于数组中，单聊标的输出却不是按数组的顺序输出的，是由一个指定的位置开始根据 link 的值依次输出的。静态链表存储结构在赫夫曼树和内部排序中都有应用。
实现：
const int MAX_SIZE = 10; //静态链表的最大长度
//静态链表类
template<typename T>class StLinkList
{//带模板的静态链表类
struct component //类内定义的结构体，只用于本类内
{
T data;
int link;
};
private:
component SL[MAX_SIZE]; //静态数组
int NEW()
{//若备用链表非空，则返回分配的结点下标（备用链表的第一个结点）；否则返回 0
int i = SL[MAX_SIZE - 1].link; //备用链表第一个结点的位置
if (i) //备用链表非空
SL[MAX_SIZE - 1].link = SL[i].link;
//备用链表的头结点指向原备用链表的第二个结点
return i; //返回新开辟结点的下标
}
void DELETE(int k)
{//将下标为 k 的空闲结点回收到备用链表中，成为备用链表的第一个结点
SL[k].link = SL[MAX_SIZE - 1].link; //回收结点的下标指向备用链表的第一个结点
SL[MAX_SIZE - 1].link = k; //备用链表的头结点指向新回收的结点
}
public:
StLinkList()
{//构造一个空的链表，表头为单元 [0]，其余单元链成一个备用链表
//备用链表表头为最后一个单元 [MAX_SIZE - 1]，link 域 0 表示空指针
int i;
SL[0].link = 0; //[0] 为空链表的表头
SL[MAX_SIZE - 1].link = 1; //[1] 为备用链表的第一个单元
for(i = 1; i < MAX_SIZE - 2; i++)
//将其余单元链成以 [MAX_SIZE - 1] 为表头的备用链表
SL[i].link = i + 1;
SL[MAX_SIZE - 2].link = 0;
}
void ClearList()
{//将静态链表重置为空表
int j, i = SL[MAX_SIZE - 1].link; //i 指示备用链表第一个结点的位序
while(i) //未到备用链表表尾
{
j = i;
i = SL[i].link;
}
SL[j].link = SL[0].link; //链表的第一个结点接到备用链表的尾部
Sl[0].link = 0; //链表空
}
bool ListEmpty()const
{//若是空表，返回 true；否则返回 false
return SL[0].link == 0;
}
int ListLength()const
{//返回表中数据元素个数
int j = 0, i = SL[0].link; //i 指向链表的第一个结点的位序
while(i)
{
i = SL[i].link;
j++;
}
return j;
}
bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
{//若 e 与表中某数据元素满足定义的 eq() 关系，且该数据不是表中第一个，
//则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
int j, i = SL[0].link;
do
{
j = i;
i = SL[i].link;
}while(i && !eq(Sl[i].data, e)); //i 所指元素存在且其值不是 e ，继续循环
if (i) //找到该元素
{
pre_e = SL[i].data;
return true;
}
return false; //没找到该元素，或其无前驱
}
bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
{//若 e 与表中某数据元素满足定义的 eq() 关系，且该元素不是表中最后一个，
//则用 next_e 返回它的后继，否则操作失败，next_e 无定义
int i = SL[0].link;
while(i)
{
if (eq(SL[i].data, e) && SL[i].link) //找到该元素且其有后继
{
next_e = SL[SL[i].link].data;
return true;
}
i = SL[i].link;
}
return false; //不存在该元素，或者其无后继
}
bool ListInsert(int i, T e)
{//在静态链表的第 i 个元素
int m, k = 0; //k 指示头结点的位序
for (m = 1; m < i; m++)
{
k = SL[k].link; //k 指向下一结点
if (k == 0) //已到表尾
break;
}
if (m < i) //表中没有第 i-1 个结点
return false;
else //表中有第 i-1 个结点，并由 k 指向
{
m = NEW(); //申请新单元
if (m) //申请成功
{
SL[m].data = e;
SL[m].link = SL[k].link;
SL[k].link = m;
return true;
}
return false;
}
}
bool ListDelete(int i, T &e)
{//删除第 i 个数据元素，并用 e 返回其值
int m, k = 0; //k 指示头结点的位序
for(m = 1; m < i; m++)
{
k = SL[k].link;
if (k == 0) //已到表尾
break;
}
if (m < i || SL[k].link == 0) //表中没有第 i-1 个结点或者没有第 i 个结点
return false;
else
{
m = SL[k].link;
SL[k].link = SL[m].link;
e = SL[m].data;
DELETE(m);
return true;
}
}
void ListTraverse(void(*visit) (T*))
{//依次对每个元素调用函数 visit()
int i = SL[0].link;
while(i)
{
visit(&SL[i].data);
i = SL[i].link;
}
cout << endl;
}
};
静态链表存储于数组中，但其顺序却不是按数组下标的顺序，而是像链表一样，由当前结点 link 域的值决定下一结点的位置，这是链表的特性；又由于用数组存储，故称为静态链表。我们只要知道第一个结点（头结点）的位置就可以依次找到静态链表中的其他结点。我们将不再链表中的空闲结点也链接成一个静态链表，成为 “备用链表” 。静态链表数组 SL 中有一个链表头结点在位置 [0]，有一个备用链表头结点在位置 [MAX_SIZE - 1] ，其余结点不再链表中就在备用链表中。
当静态链表需要新结点时，我们把备用链表中的第一个结点从备用链表中删除，作为新结点插入静态链表。当删除静态链表中的结点时，被删除的结点插入备用链表中，成为备用链表的第一个结点。之所以从备用链表删除结点或是插入结点的操作都在表头进行，是因为这样的效率最高。
备注：如果不理解备用链表，可以参考下面这篇博客：
静态链表 C实现。
静态链表和单链表的主要区别：
- 单链表的结点通过 new 关键字产生，结点被限制在动态存储区这个大范围内。因此，指示结点位置的指针类型实际上是常整型。而静态链表的结点被限制在静态数组这个小范围内。因此，指示结点位置的指针类型（link）一般是整型；
- 单链表不用的结点通过 delete 关键字释放，释放后的结点由编译软件管理。而静态链表中不用的结点要自己管理（插入到备用链表中）。
