C语言中怎么建立一个双向链表

这篇文章给大家介绍C语言中怎么建立一个双向链表，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

C语言数据结构 双向链表的建立与基本操作

1.双向链表的建立

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，要将首节点的prior指针和尾节点的next指针指向NULL，这是十分关键的一步，因为这是之后用来判断空表的条件。同时，当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

2.双向链表的插入操作

由于定义双向链表时指针域中多了一个prior指针，插入操作相应变得复杂，但基本操作也并不难理解。只需记住在处理前驱和后继指针与插入节点的关系时，应始终把握好“有序原则”，即若将插入节点与两个已存在的节点构成三角形，则应先处理“向上”的指针，再处理“向下”的指针。下面用代码描述其过程:

pinsert->prior=p; pinsert->next=p->next; p->next->prior=pinsert; p->next=pinsert;

3.双向链表的删除操作

理解了双向链表的插入操作后，删除操作便十分容易理解。下面用代码描述其过程:

 p->prior->next=p->next;   p->next->prior=p->prior;   free(p);

双向链表的其他操作与单链表类似，在此不再赘述，完整的代码如下:

#include<stdio.h> #include<stdlib.h> #include<time.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int status; typedef int elemtype; typedef struct node{   elemtype data;   struct node * next;   struct node * prior; }node; typedef struct node* dlinklist; status visit(elemtype c){   printf("%d ",c); } /*双向链表初始化*/ status initdlinklist(dlinklist * head,dlinklist * tail){   (*head)=(dlinklist)malloc(sizeof(node));   (*tail)=(dlinklist)malloc(sizeof(node));   if(!(*head)||!(*tail))     return ERROR;   /*这一步很关键*/    (*head)->prior=NULL;   (*tail)->next=NULL;   /*链表为空时让头指向尾*/   (*head)->next=(*tail);   (*tail)->prior=(*head); } /*判定是否为空*/ status emptylinklist(dlinklist head,dlinklist tail){   if(head->next==tail)     return TRUE;   else     return FALSE; }  /*尾插法创建链表*/  status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){   dlinklist pmove=tail,pinsert;   pinsert=(dlinklist)malloc(sizeof(node));   if(!pinsert)      return ERROR;   pinsert->data=data;   pinsert->next=NULL;   pinsert->prior=NULL;   tail->prior->next=pinsert;   pinsert->prior=tail->prior;   pinsert->next=tail;   tail->prior=pinsert; }  /*头插法创建链表*/  status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){   dlinklist pmove=head,qmove=tail,pinsert;   pinsert=(dlinklist)malloc(sizeof(node));   if(!pinsert)     return ERROR;   else{     pinsert->data=data;     pinsert->prior=pmove;     pinsert->next=pmove->next;     pmove->next->prior=pinsert;     pmove->next=pinsert;   } } /*正序打印链表*/  status traverselist(dlinklist head,dlinklist tail){   /*dlinklist pmove=head->next;   while(pmove!=tail){     printf("%d ",pmove->data);     pmove=pmove->next;   }   printf("\n");   return OK;*/   dlinklist pmove=head->next;   while(pmove!=tail){     visit(pmove->data);     pmove=pmove->next;   }   printf("\n"); } /*返回第一个值为data的元素的位序*/ status locateelem(dlinklist head,dlinklist tail,elemtype data){   dlinklist pmove=head->next;   int pos=1;   while(pmove&&pmove->data!=data){     pmove=pmove->next;     pos++;   }   return pos; } /*返回表长*/ status listlength(dlinklist head,dlinklist tail){   dlinklist pmove=head->next;   int length=0;   while(pmove!=tail){     pmove=pmove->next;     length++;   }   return length; } /*逆序打印链表*/ status inverse(dlinklist head,dlinklist tail){   dlinklist pmove=tail->prior;   while(pmove!=head){     visit(pmove->data);     pmove=pmove->prior;   }   printf("\n"); } /*删除链表中第pos个位置的元素，并用data返回*/ status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){   int i=1;   dlinklist pmove=head->next;   while(pmove&&i<pos){     pmove=pmove->next;     i++;   }   if(!pmove||i>pos){     printf("输入数据非法\n");     return ERROR;   }   else{     *data=pmove->data;     pmove->next->prior=pmove->prior;     pmove->prior->next=pmove->next;     free(pmove);   } } /*在链表尾插入元素*/ status inserttail(dlinklist head,dlinklist tail,elemtype data){   dlinklist pinsert;   pinsert=(dlinklist)malloc(sizeof(node));   pinsert->data=data;   pinsert->next=NULL;   pinsert->prior=NULL;   tail->prior->next=pinsert;   pinsert->prior=tail->prior;   pinsert->next=tail;   tail->prior=pinsert;   return OK; }  int main(void){   dlinklist head,tail;   int i=0;   elemtype data=0;   initdlinklist(&head,&tail);   if(emptylinklist(head,tail))     printf("链表为空\n");   else     printf("链表不为空\n");   printf("头插法创建链表\n");    for(i=0;i<10;i++){     createdlinklisthead(head,tail,i);   }   traverselist(head,tail);   for(i=0;i<10;i++){     printf("表中值为%d的元素的位置为",i);      printf("%d位\n",locateelem(head,tail,i));   }   printf("表长为%d\n",listlength(head,tail));   printf("逆序打印链表");   inverse(head,tail);   for(i=0;i<10;i++){     deleteelem(head,tail,1,&data);     printf("被删除的元素为%d\n",data);   }   traverselist(head,tail);   if(emptylinklist(head,tail))     printf("链表为空\n");   else     printf("链表不为空\n");     printf("尾插法创建链表\n");   for(i=0;i<10;i++){     //inserttail(head,tail,i);     createdlinklisttail(head,tail,i);   }   traverselist(head,tail);   printf("逆序打印链表");   inverse(head,tail); }

关于C语言中怎么建立一个双向链表就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。