反饋

雙向鏈表

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

中文名: 雙向鏈表
類別: 鏈表

特點: 每個數據結點中都有兩個指針
應用: 孔子電路
方法: 正序查找，逆序查找

雙向鏈表鏈表的操作

線性表的雙向鏈表存儲結構：

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; /*頭結點的兩個指針域均指向自身 */
}

驗證是否為空表^[1] ：

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<i)
{
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;
}

正序查找^[1] ：

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 <assert.h>
template<class T>
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<class T>
int LinkedList<T>::elementToatal()const
{
int Total=0;
for(Node* p=head->next;p!=head;p=p->next) ++Total;
return Total;
}
/**********************************************
*在position指定的位置插入元素。原來position及後面的元
*素後移
***********************************************/
template<class T>
void LinkedList<T>::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<class T>
T LinkedList<T>::getElement(int index)const
{
assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,鏈表是否空
Node* p=head->next;
while(--index) p=p->next;
return p->data;
}
/**********************************
*刪除指定元素，並返回它
**********************************/
template<class T>
T LinkedList<T>::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<class T>
void LinkedList<T>::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<class T>
int LinkedList<T>::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<class T>
void LinkedList<T>::Traverse(void (*visit)(T&element))
{
Node* p=head->next;
while(p!=head)
{
visit(p->data);//注意此時外部visit函數有權限修改LinkedList<T>的私有數據
p=p->next;
}
}
/*************************************************
*反向遍歷，以鏈表中每個元素作為參數調用visit函數
*************************************************/
template<class T>
void LinkedList<T>::TraverseBack(void (*visit)(T&element))
{
Node* p=head->prior;
while(p!=head)
{
visit(p->data);//注意此時外部visit函數有權限修改LinkedList<T>的私有數據
p=p->prior;
}
}
/**************************************************
*返回鏈表的元素引用，並可讀寫.實際上鍊表沒有[]意義上的所有功能
*因此[]函數是有限制的.重載它是為了客户端代碼簡潔，因為從鏈表讀寫
*數據是最常用的
***************************************************/
template<class T>
T& LinkedList<T>::operator [](int index)
{
assert(index>0 && index<=elementToatal() && !isEmpty());//[]函數使用前提條件
Node* p=head->next;
while(--index) p=p->next;
return p->data;
}
/***************************
*清空鏈表
***************************/
template<class T>
void LinkedList<T>::clearAllElement()
{
Node* p=head->next,*pTemp=0;
while(p!=head)
{
pTemp=p->next;
delete p;
p=pTemp;
}
head->prior=head->next=head;//收尾工作
}
/******************************
*析構函數，若內存足夠沒必要調用該函數
*******************************/
template<class T>
LinkedList<T>::~LinkedList()
{
if(head)//防止用户顯式析構後，對象又剛好超出作用域再調用該函數
{
clearAllElement();
delete head;
head=0;
}
}

雙向鏈表循環鏈表

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

參考資料

1. 任志國, 蔡曉龍, 白麗麗,等. 插入排序算法的雙鏈表模擬[J]. 電腦編程技巧與維護, 2010(6):8-9.

雙向鏈表的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：31次歷史版本
最近更新：自己的神7 （2022-06-14）

1 鏈表的操作
2 元素的操作
3 雙向鏈表模板
4 循環鏈表

雙向鏈表

目錄

雙向鏈表鏈表的操作

雙向鏈表元素的操作

雙向鏈表雙向鏈表模板

雙向鏈表循環鏈表