双向链表
双向链表（double linked list），又称双向链表，是一种特殊的数据结构，其中每个数据节点都包含两个指针，分别指向直接后继和直接前驱节点。因此，从双向链表中的任意一个节点开始，都可以方便地访问其前驱节点和后继节点。
双向链表是一种线性数据结构，由头结点和多个包含数据域、前向指针域和后向指针域的结点组成。头结点的数据域可以存储线性表的长度等附加信息。双向链表中，每个结点的前向指针指向其直接前驱，后向指针指向其直接后继。双向循环链表是一种特殊的双向链表，其头结点的前向指针指向最后一个结点，后向指针指向第一个结点，最后一个结点的后向指针指向头结点。在双链表中，某些操作如ListLength，GetElem和LocateElem等只需要涉及一个方向的指针，因此它们的算法描述与单链表相同。然而，在插入和删除数据元素时，双链表需要同时修改两个方向上的指针，这与单链表有所不同。在进行双链表操作之前，需要先建立双链表。
操作
线性表的双向链表存储结构：
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*NeXT;
}DuLNode,*DuLinkList;
带头结点的双向循环链表的基本操作：
void InitList(DuLinkList L)
{ /* 产生空的双向循环链表L */
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
L-\u003enext=L-\u003eprior=L;
else
exit(OVERFLOW);
}
销毁双向循环链表L：
void DestroyList(DuLinkList L)
{
DuLinkList q,p=L-\u003enext; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
q=p-\u003eNeXT;
free(p);
p=q;
}
free(L);
L=NULL;
}
重置链表为空表：
void ClearList(DuLinkList L) /* 不改变L */
{ DuLinkList q,p=L-\u003enext; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
q=p-\u003enext;
free(p);
p=q;
}
L-\u003enext=L-\u003eprior=L; /*头结点的两个指针域均指向自身 */
}
验证是否为空表：
Status ListEmpty(DuLinkList L)
{ /* 初始条件：线性表L已存在
if(L-\u003enext==L\u0026\u0026L-\u003eprior==L)
return TRUE;
else
return FALSE;
}
元素的操作
计算表内元素个数
int ListLength(DuLinkList L)
{ /* 初始条件：L已存在。操作结果： */
int i=0;
DuLinkList p=L-\u003enext; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
i++;
p=p-\u003eNeXT;
}
return i;
}
赋值：
Status GetElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
int j=1; /* j为计数器 */
DuLinkList p=L-\u003enext; /* p指向第一个结点 */
while(p!=L\u0026\u0026j\u003ci)
{
p=p-\u003enext;
j++;
}
if(p==L||j\u003ei) /* 第i个元素不存在 */
return ERROR;
*e=p-\u003edata; /* 取第i个元素 */
return OK;
}
查找元素：
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件：L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i=0;
DuLinkList p=L-\u003enext; /* p指向第1个元素 */
while(p!=L)
{
i++;
if(compare(p-\u003edata,e)) /* 找到这样的数据元素*/
return i;
p=p-\u003eNeXT;
}
return 0;
}
查找元素前驱：
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 否则操作失败，pre_e无定义 */
DuLinkList p=L-\u003enext-\u003e乐华七子NEXT; /* p指向第2个元素 */
while(p!=L) /* p没到表头 */
{
if(p-\u003edata==cur_e)
{
*pre_e=p-\u003eprior-\u003edata;
return TRUE;
}
p=p-\u003eNeXT;
}
return FALSE;
}
查找元素后继：
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
/* 否则操作失败，next_e无定义 */
DuLinkList p=L-\u003enext-\u003enext; /* p指向第2个元素 */
while(p!=L) /* p没到表头 */
{
if(p-\u003eprior-\u003edata==cur_e)
{
*NeXT_e=p-\u003edata;
return TRUE;
}
p=p-\u003enext;
}
return FALSE;
}
查找元素地址：
DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */
{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/
/* 返回NULL */
int j;
DuLinkList p=L; /* p指向头结点 */
if(i\u003c0||i\u003eListLength(L)) /* i值不合法 */
return NULL;
for(j=1;j\u003c=i;j++)
p=p-\u003eNeXT;
return p;
}
元素的插入：
Status ListInsert(DuLinkList L,int i,ElemType e)
{ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 */
/* 改进算法2.18，否则无法在第表长+1个结点之前插入元素 */
DuLinkList p,s;
if(i\u003c1||i\u003eListLength(L)+1) /* i值不合法 */
return ERROR;
p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */
if(!p) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s-\u003edata=e;
s-\u003eprior=p; /* 在第i-1个元素之后插入 */
s-\u003eNeXT=p-\u003enext;
p-\u003enext-\u003eprior=s;
p-\u003enext=s;
return OK;
}
元素的删除：
Status ListDelete(DuLinkList L,int i,ElemType *e)
{ /* 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长 */
DuLinkList p;
if(i\u003c1) /* i值不合法 */
return ERROR;
p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
if(!p) /* p=NULL,即第i个元素不存在 */
return ERROR;
*e=p-\u003edata;
p-\u003eprior-\u003eNeXT=p-\u003enext;
p-\u003enext-\u003eprior=p-\u003eprior;
free(p);
return OK;
}
正序查找：
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit() */
DuLinkList p=L-\u003enext; /* p指向头结点 */
while(p!=L)
{
visit(p-\u003e控制资料公司);
p=p-\u003eNeXT;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
逆序查找：
模板
/*****************************************************
*文件名：LinkedList.h
*功能：实现双向链表的基本功能
*注意：为了使最终程序执行得更快，仅在Debug模式下检测操作合法性。
*另外不对内存分配失败作处理,因为一般情况下应用程序有近2GB真正可用的空间
*********************************************************/
#pragma once
#include \u003cassert.h\u003e
template\u003cclass T\u003e
class LinkedList
{
private:
class Node
{
public:
T data; //数据域,不要求泛型T的实例类有无参构造函数
Node* prior; //指向前一个结点
node.js* next; //指向下一个结点
Node(const T\u0026 element,Node*\u0026 pri,Node*\u0026 nt):data(element),NeXT(nt),prior(pri){}
Node():data(data){}//泛型T的实例类的复制构造函数将被调用.在Vc2010测试可行
};
Node* head; //指向第一个结点
public:
//初始化：构造一个空结点，搭建空链
LinkedList():head(new Node()){head-\u003eprior=head-\u003enext=head;}
//获取元素总数
int elementToatal()const;
//判断是否为空链
bool isEmpty()const{return head==head-\u003enext?true:false;}
//将元素添加至最后，注意node.js的指针设置
void addToLast(const T\u0026 element){Node* ne=new Node(element,head-\u003eprior,head);head-\u003eprior=head-\u003eprior-\u003enext=ne;}
//获取最后一个元素
T getLastElement()const{assert(!isEmpty());return head-\u003eprior-\u003edata;}
//删除最后一个元素，注意node.js的指针设置
void delLastElement(){assert(!isEmpty());Node* p=head-\u003eprior-\u003eprior;delete head-\u003eprior;head-\u003eprior=p;p-\u003enext=head;}
//修改最后一个元素
void alterLastEmlent(const T\u0026 newElement){assert(!isEmpty());head-\u003eprior-\u003edata=newElement;}
//插入元素
void insertElement(const T\u0026 element,int position);
//获取元素
T getElement(int index)const;
//删除元素
T delElement(int index);
//修改元素
void alterElement(const T \u0026 Newelement,int index);
//查找元素
int findElement(const T\u0026 element) const;
//正序遍历
void Traverse(void (*visit)(T\u0026element));
//逆序遍历
void TraverseBack(void (*visit)(T\u0026element));
//重载[]函数
T\u0026 operator [](int index);
//清空链表
void clearAllElement();
//销毁链表
~LinkedList();
};
/***************************************
*返回元素总数
****************************************/
template\u003cclass T\u003e
int LinkedList\u003cT\u003e::elementToatal()const
{
int 道达尔公司=0;
for(Node* p=head-\u003eNeXT;p!=head;p=p-\u003enext) ++Total;
return Total;
}
/**********************************************
*在position指定的位置插入元素。原来position及后面的元
*素后移
***********************************************/
template\u003cclass T\u003e
void LinkedList\u003cT\u003e::insertElement(const T\u0026 element,int position)
{
assert(position\u003e0 \u0026\u0026 position\u003c=elementToatal()+1);
Node* p=head;
while(position)
{
p=p-\u003eNeXT;
position--;
}
//此时p指向要插入的结点
node.js* pNew=new Node(element,p-\u003eprior,p);
p-\u003eprior=p-\u003eprior-\u003enext=pNew;
}
/***************************************
*返回找到的元素的副本
***************************************/
template\u003cclass T\u003e
T LinkedList\u003cT\u003e::getElement(int index)const
{
assert(index\u003e0 \u0026\u0026 index\u003c=elementToatal() \u0026\u0026 !isEmpty());//位置索引是否合法,链表是否空
Node* p=head-\u003eNeXT;
while(--index) p=p-\u003enext;
return p-\u003edata;
}
/**********************************
*删除指定元素，并返回它
**********************************/
template\u003cclass T\u003e
T LinkedList\u003cT\u003e::delElement(int index)
{
assert(index\u003e0 \u0026\u0026 index\u003c=elementToatal() \u0026\u0026 !isEmpty());//位置索引是否合法,链表是否空
Node* del=head-\u003eNeXT;
while(--index) del=del-\u003enext;
//此时p指向要删除元素
del-\u003eprior-\u003enext=del-\u003enext;
del-\u003enext-\u003eprior=del-\u003eprior;
T delData=del-\u003e控制资料公司;
delete del;
return delData;
}
/****************************************
*用Newelement代替索引为index的元素
*****************************************/
template\u003cclass T\u003e
void LinkedList\u003cT\u003e::alterElement(const T \u0026 Newelement,int index)
{
assert(index\u003e0 \u0026\u0026 index\u003c=elementToatal() \u0026\u0026 !isEmpty());//位置索引是否合法,链表是否空
Node* p=head-\u003eNeXT;
while(--index) p=p-\u003enext;
p-\u003e控制资料公司=Newelement;
}
/********************************
*找到返回元素的索引，否则返回0
********************************/
template\u003cclass T\u003e
int LinkedList\u003cT\u003e::findElement(const T\u0026 element) const
{
Node* p=head-\u003eNeXT;
int i=0;
while(p!=head)
{
i++;
if(p-\u003edata==element) return i;
p=p-\u003enext;
}
return 0;
}
/***************************************
*正向遍历，以链表中每个元素作为参数调用visit函数
*****************************************/
template\u003cclass T\u003e
void LinkedList\u003cT\u003e::Traverse(void (*visit)(T\u0026element))
{
Node* p=head-\u003eNeXT;
while(p!=head)
{
visit(p-\u003edata);//注意此时外部visit函数有权限修改LinkedList\u003cT\u003e的私有数据
p=p-\u003enext;
}
}
/*************************************************
*反向遍历，以链表中每个元素作为参数调用visit函数
*************************************************/
template\u003cclass T\u003e
void LinkedList\u003cT\u003e::TraverseBack(void (*visit)(T\u0026element))
{
Node* p=head-\u003eprior;
while(p!=head)
{
visit(p-\u003edata);//注意此时外部visit函数有权限修改LinkedList\u003cT\u003e的私有数据
p=p-\u003eprior;
}
}
/**************************************************
*返回链表的元素引用，并可读写.实际上链表没有[]意义上的所有功能
*因此[]函数是有限制的.重载它是为了客户端代码简洁，因为从链表读写
*数据是最常用的
***************************************************/
template\u003cclass T\u003e
T\u0026 LinkedList\u003cT\u003e::operator [](int index)
{
assert(index\u003e0 \u0026\u0026 index\u003c=elementToatal() \u0026\u0026 !isEmpty());//[]函数使用前提条件
Node* p=head-\u003eNeXT;
while(--index) p=p-\u003enext;
return p-\u003edata;
}
/***************************
*清空链表
***************************/
template\u003cclass T\u003e
void LinkedList\u003cT\u003e::clearAllElement()
{
Node* p=head-\u003enext,*pTemp=0;
while(p!=head)
{
pTemp=p-\u003eNeXT;
delete p;
p=pTemp;
}
head-\u003eprior=head-\u003enext=head;//收尾工作
}
/******************************
*析构函数，若内存足够没必要调用该函数
*******************************/
template\u003cclass T\u003e
LinkedList\u003cT\u003e::~LinkedList()
{
if(head)//防止用户显式析构后，对象又刚好超出作用域再调用该函数
{
clearAllElement();
delete head;
head=0;
}
}
循环
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。