双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

操作

线性表的双向链表存储结构：

typedef struct DuLNode

{

ElemType data;

struct DuLNode *prior,*next;

}DuLNode,*DuLinkList;

带头结点的双向循环链表的基本操作：

void InitList(DuLinkList L)

{ /* 产生空的双向循环链表L */

L=(DuLinkList)malloc(sizeof(DuLNode));

if(L)

L->next=L->prior=L;

else

exit(OVERFLOW);

}

销毁双向循环链表L：

void DestroyList(DuLinkList L)

{

DuLinkList q,p=L->next; /* p指向第一个结点 */

while(p!=L) /* p没到表头 */

{

q=p->next;

free(p);

p=q;

}

free(L);

L=NULL;

}

重置链表为空表：

void ClearList(DuLinkList L) /* 不改变L */

{ 　DuLinkList q,p=L->next; /* p指向第一个结点 */

while(p!=L) /* p没到表头 */

{

q=p->next;

free(p);

p=q;

}

L->next=L->prior=L; /*头结点的两个指针域均指向自身 */

}

验证是否为空表：

Status ListEmpty(DuLinkList L)

{ /* 初始条件：线性表L已存在

if(L->next==L&&L->prior==L)

return TRUE;

else

return FALSE;

}

元素的操作

计算表内元素个数

int ListLength(DuLinkList L)

{ /* 初始条件：L已存在。操作结果： */

int i=0;

DuLinkList p=L->next; /* p指向第一个结点 */

while(p!=L) /* p没到表头 */

{

i++;

p=p->next;

}

return i;

}

赋值：

Status GetElem(DuLinkList L,int i,ElemType *e)

{ /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */

int j=1; /* j为计数器 */

DuLinkList p=L->next; /* p指向第一个结点 */

while(p!=L&&j

{

p=p->next;

j++;

}

if(p==L||j>i) /* 第i个元素不存在 */

return ERROR;

*e=p->data; /* 取第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->next; /* p指向第1个元素 */

while(p!=L)

{

i++;

if(compare(p->data,e)) /* 找到这样的数据元素*/

return i;

p=p->next;

}

return 0;

}

查找元素前驱：

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)

{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */

/* 否则操作失败，pre_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

while(p!=L) /* p没到表头 */

{

if(p->data==cur_e)

{

*pre_e=p->prior->data;

return TRUE;

}

p=p->next;

}

return FALSE;

}

查找元素后继：

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)

{ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */

/* 否则操作失败，next_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

while(p!=L) /* p没到表头 */

{

if(p->prior->data==cur_e)

{

*next_e=p->data;

return TRUE;

}

p=p->next;

}

return FALSE;

}

查找元素地址：

DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */

{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/

/* 返回NULL */

int j;

DuLinkList p=L; /* p指向头结点 */

if(i<0||i>ListLength(L)) /* i值不合法 */

return NULL;

for(j=1;j<=i;j++)

p=p->next;

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<1||i>ListLength(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->data=e;

s->prior=p; /* 在第i-1个元素之后插入 */

s->next=p->next;

p->next->prior=s;

p->next=s;

return OK;

}

元素的删除：

Status ListDelete(DuLinkList L,int i,ElemType *e)

{ /* 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长 */

DuLinkList p;

if(i<1) /* i值不合法 */

return ERROR;

p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */

if(!p) /* p=NULL,即第i个元素不存在 */

return ERROR;

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

return OK;

}

正序查找：

void ListTraverse(DuLinkList L,void(*visit)(ElemType))

{ /* 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit() */

DuLinkList p=L->next; /* p指向头结点 */

while(p!=L)

{

visit(p->data);

p=p->next;

}

printf("\n");

}

void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))

逆序查找：

{ /* 由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()。另加 */ DuLinkList p=L->prior; /* p指向尾结点 */ while(p!=L) { visit(p->data); p=p->prior; } printf("\n"); }

模板

/*****************************************************

*文件名：LinkedList.h

*功能：实现双向链表的基本功能

*注意：为了使最终程序执行得更快，仅在Debug模式下检测操作合法性。

*另外不对内存分配失败作处理,因为一般情况下应用程序有近2GB真正可用的空间

*********************************************************/

#pragma once

#include 

template

class LinkedList

{

private:

class Node

{

public:

T data; //数据域,不要求泛型T的实例类有无参构造函数

Node* prior; //指向前一个结点

Node* next; //指向下一个结点

Node(const T& element,Node*& pri,Node*& nt):data(element),next(nt),prior(pri){}

Node():data(data){}//泛型T的实例类的复制构造函数将被调用.在Vc2010测试可行

};

Node* head; //指向第一个结点

public:

//初始化：构造一个空结点，搭建空链

LinkedList():head(new Node()){head->prior=head->next=head;}

//获取元素总数

int elementToatal()const;

//判断是否为空链

bool isEmpty()const{return head==head->next?true:false;}

//将元素添加至最后，注意node的指针设置

void addToLast(const T& element){Node* ne=new Node(element,head->prior,head);head->prior=head->prior->next=ne;}

//获取最后一个元素

T getLastElement()const{assert(!isEmpty());return head->prior->data;}

//删除最后一个元素，注意node的指针设置

void delLastElement(){assert(!isEmpty());Node* p=head->prior->prior;delete head->prior;head->prior=p;p->next=head;}

//修改最后一个元素

void alterLastEmlent(const T& newElement){assert(!isEmpty());head->prior->data=newElement;}

//插入元素

void insertElement(const T& element,int position);

//获取元素

T getElement(int index)const;

//删除元素

T delElement(int index);

//修改元素

void alterElement(const T & Newelement,int index);

//查找元素

int findElement(const T& element) const;

//正序遍历

void Traverse(void (*visit)(T&element));

//逆序遍历

void TraverseBack(void (*visit)(T&element));

//重载[]函数

T& operator [](int index);

//清空链表

void clearAllElement();

//销毁链表

~LinkedList();

};

/***************************************

*返回元素总数

****************************************/

template

int LinkedList::elementToatal()const

{

int Total=0;

for(Node* p=head->next;p!=head;p=p->next) ++Total;

return Total;

}

/**********************************************

*在position指定的位置插入元素。原来position及后面的元

*素后移

***********************************************/

template

void LinkedList::insertElement(const T& element,int position)

{

assert(position>0 && position<=elementToatal()+1);

Node* p=head;

while(position)

{

p=p->next;

position--;

}

//此时p指向要插入的结点

Node* pNew=new Node(element,p->prior,p);

p->prior=p->prior->next=pNew;

}

/***************************************

*返回找到的元素的副本

***************************************/

template

T LinkedList::getElement(int index)const

{

assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空

Node* p=head->next;

while(--index) p=p->next;

return p->data;

}

/**********************************

*删除指定元素，并返回它

**********************************/

template

T LinkedList::delElement(int index)

{

assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空

Node* del=head->next;

while(--index) del=del->next;

//此时p指向要删除元素

del->prior->next=del->next;

del->next->prior=del->prior;

T delData=del->data;

delete del;

return delData;

}

/****************************************

*用Newelement代替索引为index的元素

*****************************************/

template

void LinkedList::alterElement(const T & Newelement,int index)

{

assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空

Node* p=head->next;

while(--index) p=p->next;

p->data=Newelement;

}

/********************************

*找到返回元素的索引，否则返回0

********************************/

template

int LinkedList::findElement(const T& element) const

{

Node* p=head->next;

int i=0;

while(p!=head)

{

i++;

if(p->data==element) return i;

p=p->next;

}

return 0;

}

/***************************************

*正向遍历，以链表中每个元素作为参数调用visit函数

*****************************************/

template

void LinkedList::Traverse(void (*visit)(T&element))

{

Node* p=head->next;

while(p!=head)

{

visit(p->data);//注意此时外部visit函数有权限修改LinkedList的私有数据

p=p->next;

}

}

/*************************************************

*反向遍历，以链表中每个元素作为参数调用visit函数

*************************************************/

template

void LinkedList::TraverseBack(void (*visit)(T&element))

{

Node* p=head->prior;

while(p!=head)

{

visit(p->data);//注意此时外部visit函数有权限修改LinkedList的私有数据

p=p->prior;

}

}

/**************************************************

*返回链表的元素引用，并可读写.实际上链表没有[]意义上的所有功能

*因此[]函数是有限制的.重载它是为了客户端代码简洁，因为从链表读写

*数据是最常用的

***************************************************/

template

T& LinkedList::operator [](int index)

{

assert(index>0 && index<=elementToatal() && !isEmpty());//[]函数使用前提条件

Node* p=head->next;

while(--index) p=p->next;

return p->data;

}

/***************************

*清空链表

***************************/

template

void LinkedList::clearAllElement()

{

Node* p=head->next,*pTemp=0;

while(p!=head)

{

pTemp=p->next;

delete p;

p=pTemp;

}

head->prior=head->next=head;//收尾工作

}

/******************************

*析构函数，若内存足够没必要调用该函数

*******************************/

template

LinkedList::~LinkedList()

{

if(head)//防止用户显式析构后，对象又刚好超出作用域再调用该函数

{

clearAllElement();

delete head;

head=0;

}

}

循环

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。