/* *姓名：劉金石 *時間2017年2月5日 *線性表之雙鏈表基本操作 */#include <stdio.h>#include <stdlib.h>//雙鏈表的存儲結(jié)構(gòu)typedef char ElemType;typedef struct DNode{    ElemType date;//存放元素值    struct DNode *PRior;//指向前驅(qū)節(jié)點    struct DNode *next;//指向后繼節(jié)點}DLinkList;//頭插法建立雙鏈表void InitList(DLinkList *&L)	//初始化{	L=(DLinkList *)malloc(sizeof(DLinkList));  	//創(chuàng)建頭結(jié)點	L->prior=L->next=NULL;}void DestroyList(DLinkList *&L)	//銷毀線性表{	DLinkList *p=L,*q=p->next;	while (q!=NULL)	{		free(p);		p=q;		q=p->next;	}	free(p);}bool ListEmpty(DLinkList *L)	//判線性表是否為空表{	return(L->next==NULL);}int ListLength(DLinkList *L)	//求線性表的長度{	DLinkList *p=L;int i=0;	while (p->next!=NULL)	{		i++;		p=p->next;	}	return(i);}void DispList(DLinkList *L)	//輸出線性表{	DLinkList *p=L->next;	while (p!=NULL)	{		printf("%c ",p->date);		p=p->next;	}	printf("/n");}bool GetElem(DLinkList *L,int i,ElemType &e)	//求線性表中某個數(shù)據(jù)元素值{	int j=0;	DLinkList *p=L;	while (j<i && p!=NULL)	{		j++;		p=p->next;	}	if (p==NULL)		return false;	else	{		e=p->date;		return true;	}}int LocateElem(DLinkList *&L,ElemType e)	//按元素值查找{	int n=1;	DLinkList *p=L->next;	while (p!=NULL && p->date!=e)	{		n++;		p=p->next;	}	if (p==NULL)		return(0);	else		return(n);}void CreateListF(DLinkList *&L,ElemType a[],int n){    DLinkList *s;    int i=0;    L=(DLinkList *)malloc(sizeof(DLinkList));    L->next=L->prior=NULL;//前后指針域置為NULL    for(i=0;i<n;i++)    {        s=(DLinkList *)malloc(sizeof(DLinkList));        s->date=a[i];        /*************************/        s->next=L->next;        if(L->next!=NULL)//若L后存在數(shù)據(jù)節(jié)點，則修改L->next的前驅(qū)指針            L->next->prior=s;        L->next=s;        s->prior=L;        /*************************/    }}//尾插法建立雙鏈表void CreateListR(DLinkList *&L,ElemType a[],int n){    DLinkList *s,*r;//r指針指向鏈表的最后一個節(jié)點    int i=0;    L=(DLinkList *)malloc(sizeof(DLinkList));    r=L;    for(i=0;i<n;i++)    {        s=(DLinkList *)malloc(sizeof(DLinkList));        s->date=a[i];        /*************************/        L->next=s;        s->prior=L;        r=s;//r指向尾節(jié)點        /*************************/    }    r->next=NULL;}//插入節(jié)點bool ListInsert(DLinkList *&L,int i,ElemType e){//次算法在雙蓮表第i個位置插入值為e的節(jié)點    int j=0;    DLinkList *p=L,*s;    /*************************/    //找到第i-1個節(jié)點    while(j<i-1&&p!=NULL)    {        j++;        p=p->next;    }    /*************************/    if(p==NULL)        return false;    else    {        s=(DLinkList *)malloc(sizeof(DLinkList));        s->date=e;        /*************************/        //頭插法        s->next=p->next;        if(p->next!=NULL)            p->next->prior=s;        s->prior=p;        p->next=s;        /*************************/        return true;    }}//刪除雙蓮表中第i個節(jié)點bool ListDelete(DLinkList *&L,int i,ElemType &e){    int j=0;    DLinkList *p=L,*q;    /*************************/    //找到第i-1個節(jié)點    while(j<i-1&&p!=NULL)    {        j++;        p=p->next;    }    /*************************/    if(p==NULL)        return false;    else    {        q=p->next;        if(q==NULL)            return false;        e=q->date;        /*************************/        p->next=q->next;        if(p->next!=NULL)//若*p后存在后繼節(jié)點則修改其前驅(qū)指針           p->next->prior=p;        free(q);//釋放*q節(jié)點        /*************************/        return true;    }}int main(){	DLinkList *h;	ElemType e;	printf("雙鏈表的基本運算如下:/n");	printf("  (1)初始化雙鏈表h/n");	InitList(h);	printf("  (2)依次采用尾插法插入a,b,c,d,e元素/n");	ListInsert(h,1,'a');	ListInsert(h,2,'b');	ListInsert(h,3,'c');	ListInsert(h,4,'d');	ListInsert(h,5,'e');	printf("  (3)輸出雙鏈表h:");	DispList(h);	printf("  (4)雙鏈表h長度=%d/n",ListLength(h));	printf("  (5)雙鏈表h為%s/n",(ListEmpty(h)?"空":"非空"));	GetElem(h,3,e);	printf("  (6)雙鏈表h的第3個元素=%c/n",e);	printf("  (7)元素a的位置=%d/n",LocateElem(h,'a'));	printf("  (8)在第4個元素位置上插入f元素/n");	ListInsert(h,4,'f');	printf("  (9)輸出雙鏈表h:");	DispList(h);	printf("  (10)刪除h的第3個元素/n");	ListDelete(h,3,e);	printf("  (11)輸出雙鏈表h:");	DispList(h);	printf("  (12)釋放雙鏈表h/n");	DestroyList(h);	return 0;}運行結(jié)果：
總結(jié)：雙鏈表的基本操作和單鏈表差不太多，就是多了一個指針。有時候不清楚可以畫一下圖，思路就清晰了。像插入元素刪除元素定位元素等操作都是先找到元素或者前一個元素的位置，此過程用while循環(huán)，然后就是前插或者后插法的運用。