雙向鏈表

雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。

目錄
1操作 2元素的操作 3模板
4循環

操作

線性表的雙向鏈表存儲結構：
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
帶頭結點的雙向循環鏈表的基本操作：
void InitList(DuLinkList 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; 
while(p!=L) 
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
}
重置鏈表為空表：
void ClearList(DuLinkList L) 
{ DuLinkList q,p=L->next; 
while(p!=L) 
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; 
}
驗證是否為空表：
Status ListEmpty(DuLinkList L)
{ 
int i=0;
DuLinkList p=L->next; 
while(p!=L) 
{
i++;
p=p->next;
}
return i;
}
賦值：
Status GetElem(DuLinkList L,int i,ElemType *e)
{ 
int j=1; 
DuLinkList p=L->next; 
while(p!=L&&j
{
p=p->next;
j++;
}
if(p==L||j>i) 
return ERROR;
*e=p->data; 
return OK;
}
查找元素：
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ 
int i=0;
DuLinkList p=L->next; 
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)
{ 
DuLinkList p=L->next->next; 
while(p!=L) 
{
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)
{ 
DuLinkList p=L->next->next; 
while(p!=L) 
{
if(p->prior->data==cur_e)
{
*next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
查找元素地址：
DuLinkList GetElemP(DuLinkList L,int i) 
{ 
int j;
DuLinkList p=L; 
if(i<0||i>ListLength(L)) 
return NULL;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
元素的插入：
Status ListInsert(DuLinkList L,int i,ElemType e)
{ 
DuLinkList p,s;
if(i<1||i>ListLength(L)+1) 
return ERROR;
p=GetElemP(L,i-1); 
if(!p) 
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e;
s->prior=p; 
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
元素的刪除：
Status ListDelete(DuLinkList L,int i,ElemType *e)
{ 
DuLinkList p;
if(i<1) 
return ERROR;
p=GetElemP(L,i); 
if(!p) 
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))
{ 
DuLinkList p=L->next; 
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
逆序查找：
{ 
DuLinkList p=L->prior; 
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}

模板

#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;
}
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;
}
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;
}
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;
}
template
void LinkedList::Traverse(void (*visit)(T&element))
{
Node* p=head->next;
while(p!=head)
{
visit(p->data);//注意此時外部visit函數有許可權修改LinkedList的私有數據
p=p->next;
}
}
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;
}
}

循環

循環鏈表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鏈表中的任何一個結點出發都能找到任何其他結點。循環鏈表的操作和單鏈表的操作基本一致，差別僅僅在於演演算法中的循環條件有所不同。

基本信息

中文名
雙向鏈表
別名
類別
鏈表
特點
每個數據結點中都有兩個指針
亦稱
雙鏈表
應用
孔子電路
方法
正序查找、逆序查找
  • 目錄