C說話雙向鏈表的表現與完成實例詳解。本站提示廣大學習愛好者：（C說話雙向鏈表的表現與完成實例詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話雙向鏈表的表現與完成實例詳解正文
1.概述：
C說話中一種更龐雜的鏈表是“雙向鏈表”或“雙面鏈表”。其表中的每一個節點有兩個銜接：一個指向前一個節點，（當這個“銜接”為第一個“銜接”時，指向空值或許空列表）；而另外一個指向下一個節點，（當這個“銜接”為最初一個“銜接”時，指向空值或許空列表）
一個雙向鏈表有三個整數值: 數值, 向後的節點鏈接, 向前的節點鏈接
在一些初級說話中, XOR-linking 供給一種在雙向鏈表中經由過程用一個詞來表現兩個鏈接（前後），我們平日不倡導這類做法。
雙向鏈表也叫雙鏈表。雙向鏈表中不只有指向後一個節點的指針，還有指向前一個節點的指針。如許可以從任何一個節點拜訪前一個節點，固然也能夠拜訪後一個節點，以致全部鏈表。普通是在須要年夜批量的別的貯存數據在鏈表中的地位的時刻用。雙向鏈表也能夠合營上面的其他鏈表的擴大應用。
因為別的貯存了指向鏈表內容的指針，而且能夠會修正相鄰的節點，有的時刻第一個節點能夠會被刪除或許在之前添加一個新的節點。這時候候就要修正指向首個節點的指針。有一種便利的可以清除這類特別情形的辦法是在最初一個節點以後、第一個節點之前貯存一個永久不會被刪除或許挪動的虛擬節點，構成一個上面說的輪回鏈表。這個虛擬節點以後的節點就是真實的第一個節點。這類情形平日可以用這個虛擬節點直接表現這個鏈表，關於把鏈表零丁的存在數組裡的情形，也能夠直接用這個數組表現鏈表並用第0個或許第-1個（假如編譯器支撐）節點固定的表現這個虛擬節點。
2.法式完成：
/* c2-4.h 線性表的雙向鏈表存儲構造 */
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
/* bo2-5.c 雙鏈輪回線性表(存儲構造由c2-4.h界說)的根本操作(14個) */
Status InitList(DuLinkList *L)
{ /* 發生空的雙向輪回鏈表L */
*L=(DuLinkList)malloc(sizeof(DuLNode));
if(*L)
{
(*L)->next=(*L)->prior=*L;
return OK;
}
else
return OVERFLOW;
}
Status DestroyList(DuLinkList *L)
{ /* 操作成果：燒毀雙向輪回鏈表L */
DuLinkList q,p=(*L)->next; /* p指向第一個結點 */
while(p!=*L) /* p沒到表頭 */
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
return OK;
}
Status ClearList(DuLinkList L) /* 不轉變L */
{ /* 初始前提：L已存在。操作成果：將L重置為空表 */
DuLinkList q,p=L->next; /* p指向第一個結點 */
while(p!=L) /* p沒到表頭 */
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; /* 頭結點的兩個指針域均指向本身 */
return OK;
}
Status ListEmpty(DuLinkList L)
{ /* 初始前提：線性表L已存在。操作成果：若L為空表，則前往TRUE，不然前往FALSE */
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{ /* 初始前提：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指向第i個元素或p指向頭結點 */
{
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個元素的地位指針(算法2.18、2.19要挪用的函數) */
int j;
DuLinkList p=L;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
Status ListInsert(DuLinkList L,int i,ElemType e) /* 改良算法2.18 */
{ /* 在帶頭結點的雙鏈輪回線性表L中第i個地位之前拔出元素e，i的正當值為1≤i≤表長+1 */
DuLinkList p,s;
if(i<1||i>ListLength(L)+1) /* i值不正當 */
return ERROR;
p=GetElemP(L,i-1); /* 在L中肯定第i-1個元素的地位指針p */
if(!p) /* p=NULL,即第i-1個元素不存在 */
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e; /* 在第i-1個元素以後拔出 */
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
Status ListDelete(DuLinkList L,int i,ElemType *e) /* 算法2.19 */
{ /* 刪除帶頭結點的雙鏈輪回線性表L的第i個元素,i的正當值為1≤i≤表長+1 */
DuLinkList p;
if(i<1||i>ListLength(L)) /* 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");
}
