今天來討論下鏈表中的雙向鏈表。
雙向鏈表：
概念：在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還含有兩個(gè)指針域：一個(gè)存儲直接后繼結(jié)點(diǎn)的地址，稱為右鏈域；另一個(gè)存儲直接前驅(qū)結(jié)點(diǎn)的地址，稱為左鏈域。
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
雙向鏈表常用算法：
先對三個(gè)指針作個(gè)聲明：
head：用來指向鏈表的頭部。鏈表需要一個(gè)指針來標(biāo)識，這就是頭指針。
p1：用來指向新結(jié)點(diǎn)，以及用來遍歷鏈表的每一個(gè)結(jié)點(diǎn)。
p2：用來指向當(dāng)前結(jié)點(diǎn)。
（1）雙向鏈表創(chuàng)建算法
創(chuàng)建結(jié)點(diǎn)數(shù)目為n的雙向鏈表：
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
stud* Create(int n)
{
stud *head,*p1,*p2;
head=p1=p2=NULL;
for(int i=0;i<n;i++)
{
p1=(stud*)malloc(sizeof(stud));
p1->num=i;
if(i==0)
{
head=p1;
head->lnext=NULL;
}
else
{
p2->rnext=p1
p1->lnext=p2;
}
p2=p1;
}
p2->rnext=null;
return head;
}
（2）雙向鏈表的查找算法
（一）頭結(jié)點(diǎn)輸入雙向鏈表查找算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
stud* Find_FormHead(stud *head,int i)
{
stud *p1;
p1=head;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->rnext; //遍歷鏈表
}
}
return p1;
}
（二）無序雙向鏈表查找算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
//p是鏈表中任一個(gè)結(jié)點(diǎn)指針，i是要查的號碼
stud* Find_NoSort(stud *p,int i)
{
stud *p1;
p1=p;
//先住右遍歷
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->rnext;
}
}
//往左遍歷
if(p1==NULL)
{
p1=p;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->lnext;
}
}
}
return p1;
}
（三）有序雙向鏈表查找算法（從小到大）
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
stud* Find_IsSort(stud *p,int i)
{
stud *p1;
p1=p;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
if(i > p1->num) //往右遍歷
{
p1=p1->rnext;
}
else
{
p1=p1->lnext; //往左遍歷
}
}
}
return p1;
}
（3）雙向鏈表的刪除算法
（一）頭指針輸入雙向鏈表刪除算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
bool Delete_FormHead(stud *head,int i)
{
bool flag=false;
if(head)
{
stud *p1,*p2;
while(p1->num!=i && p1->rnext!=NULL)
{
p2=p1;
p1=p1->rnext;
}
if(p1->num==i)
{
if(p1==head)
{
head=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1); //釋放已經(jīng)脫離鏈表的結(jié)點(diǎn)內(nèi)存
flag=true;
}
}
return flag;
}
（二）無序雙向鏈表刪除算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
bool Delete_NoSort(stud *p,int i)
{
bool flag=false;
if(p)
{
stud *p1,*p2;
//往右遍歷
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p2=p1;
p1=p1->rnext;
}
}
//往左遍歷
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p2=p1;
p1=p1->lnext;
}
}
}
if(p1->num == i)
{
if(p1=p)
{
p=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1)
flag=true;
}
return flag;
}
（三）有序雙向鏈表刪除算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
bool Delete_IsSort(stud *p,int i)
{
bool flag=false;
if(p)
{
stud *p1,*p2;
while(p1->num!=i && p1!=NULL)
{
p2=p1;
if(i > p->num) //往右遍歷
{
p1=p1->rnext;
}
else //往左遍歷
{
p1=p1->lnext;
}
}
if(p1->num==i)
{
if(p1==p)
{
p=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1); //釋放已經(jīng)脫離鏈表的結(jié)點(diǎn)內(nèi)存
flag=true;
}
}
return flag;
}
（4）雙向鏈表的插入算法
（一）雙向鏈表通用插入算法
說明：p0為輸入的鏈表指針，p為插入的結(jié)點(diǎn)地址
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
stud *Insert(stud *p0,stud *p)
{
stud *p1,*p2;
p1=p0;
if(!p0)
{
p0=p;
p->rnext=NULL;
p->lnext-NULL;
}
else
{
//往右遍歷
if(p->num > p1->num)
{
while(p->num > p1->num && p1->rnext!=NULL)
{
p2=p1;
p1=p1->rnext;
}
if(p->num < p1->num)
{
if(p0==p1)
{
p0=p;
}
else
{
p2->rnext=p;
p->rnext=p1;
}
}
else //把p插入鏈表尾部
{
p1->rnext=p;
p->rnext=NULL;
}
}
//往左遍歷
else
{
while(p->num < p1->num && p1->lnext!=NULL)
{
p2=p1;
p1=p1->lnext;
}
if(p->num > p1->num)
{
if(p0==p1)
{
p0=p;
}
else
{
p2->lnext=p;
p->lnext=p1;
}
}
else //把這插入鏈表頭部
{
p1->lnext=p;
p->lnext=NULL;
}
}
}
return p0;
}
（二）頭結(jié)點(diǎn)輸入雙向鏈表插入算法
typedef struct node
{
int num; //數(shù)值域
struct node *lnext; //左鏈域指針
struct node *rnect; //右鏈域指針
}stud;
stud* Insert_FormHead(stud *head,stud *p)
{
stud *p1,*p2;
p1=head;
if(!head)
{
head=p;
p->rnext=NULL;
}
else
{
while(p->num > p1->num && p1->rnext!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p->num < p1->num)
{
if(head==p1)
{
head=p;
}
else
{
p2->rnext=p;
p->rnext=NULL;
}
}
else //將p插入鏈表尾部
{
p1->rnext=p;
p->rnext=NULL;
}
}
return head;
}
