双向循环链表在定义上类似于循环单链表，就多了个前指针，以方便于向前查找。在双向链表中需要同时修改两个方向的指针，是单向链表指针的两倍。 完整代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct DuLNode { int data;//结点的数据域 struct DuLNode *prior;//结点的后指针域 struct DuLNode *next;//结点的前指针域 }DuLNode,*DuLinkList;//DuLinkList为指向结构体LNode的指针类型 DuLNode* InitDuList()//初始化链表 构建一个空的线性表 { DuLNode* L = (DuLNode*)malloc(sizeof(DuLNode)); if(L==NULL)//判断申请L结点是否为空 { printf("ERROR!\n"); return 0; } L->data = NULL;//定义头结点 L->next = L; L->prior = L; } void Interrupt(void)//创建一个中断函数 { while(1)//用于检测换行符，使函数脱离scanf的连续输出 if(getchar()=='\n') break; } DuLinkList CreatDuList1(DuLinkList &L)//尾插法创建链表 { int a,b,i; DuLNode* p = L;//导入头结点，并创建一个结点s指向头结点 printf("请输入表长： "); scanf("%d",&a);//输入要插入的链表长度 Interrupt();//中断scanf printf("请输入表数据： "); for(i=0;i<a;i++) { scanf("%d",&b);//输入要链表数据 DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个结点 s->data = b; p->next = s; s->prior = p; s->next = L; L->prior = s; p = p->next; } Interrupt(); return 0; } DuLinkList CreatDuList2(DuLinkList &L)//头插法创建链表 { int a,b,i; DuLNode* p = L;//导入头结点，并创建一个结点s指向头结点 printf("请输入表长： "); scanf("%d",&a);//输入要插入的链表长度 Interrupt(); printf("请输入表数据： "); for(i=0;i<a;i++) { scanf("%d",&b);//输入要链表数据 DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个结点 s->data = b; L->next = s; s->prior = L; s->next = p; p->prior = s; p = s; } Interrupt(); return 0; } int Length(DuLinkList L)//求链表长度 { int i=0; DuLNode* p = L; while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件 { if(p->next == L) break; p = p->next; i++; } return i;//返回链表长度 } void TraverseDuLNode(DuLinkList L)//遍历链表，并输出链表 { DuLNode* p = L;//创建一个结点并指向头结点 if(Length(L) == 0)//判断链表是否为空 { printf("空表\n"); } else { while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件 { p = p->next; printf("%d ",p->data); if(p->next == L)//判断break循环条件 break; } printf("\n"); } } int LocateElem(DuLinkList L,int e)//按值查找操作。在表L中查找具有给定关键字值的元素 { DuLNode* p = L;//创建一个结点并指向头结点 int i=0; if(Length(L)==0) { printf("空表无法查询\n"); return 0; } else { bool a = true;//利用bool类型，来判断链表中是否存在要查找的值 scanf("%d",&e);//要查找的值 Interrupt(); while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件 { p = p->next; i++; if(p->data == e) { printf("第 %d 位 ",i); a = false; } if(p->next == L) break; } if(a)//链表中没有要查找的值 printf("没找到！"); printf("\n"); return 0; } } int GetElem(DuLinkList L,int i)//按位查找操作 { if(Length(L) == 0)//判断链表是否为空 { printf("空表无法查询！\n"); return 0; } scanf("%d",&i);//输入要查找第几位 Interrupt(); int j=0; DuLNode* p = L;//创建一个结点并指向头结点 if(i<1||i>Length(L))//判断输入的i值是否合理 { printf("ERROR!\n"); return 0; } else { for( ;j<i;j++)//利用循环，是p结点指向第i位 p = p->next; printf("%d\n",p->data); return 0; } } int DuListInsert(DuLinkList &L,int i,int e)//插入操作 { int j; DuLNode* p = L;//创建一个结点并指向头结点 scanf("%d %d",&i,&e);//输入要插入链表的位置，和值 Interrupt(); if(i<1||i>Length(L)+1)//判断插入链表的位置是否合理 { printf("ERROR!"); return 0; } else { DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个新结点 s->data = e; for(j=1;j<i;j++)//利用循环，是p结点指向第i-1位 p = p->next; p->next->prior = s; s->next = p->next; p->next = s; s->prior = p; printf("插入成功\n"); } } int DuListDelete(DuLinkList &L,int i)//删除操作 { int j; DuLNode* p = L;//创建一个结点并指向头结点 scanf("%d",&i);//输入要删除链表的结点位置 Interrupt(); if(Length(L)==0)//判断要删除的链表是否为空表 { printf("ERROR!\n"); return 0; } if(i<1||i>Length(L))//判断删除的结点位置是否合理 { printf("ERROR!\n"); return 0; } else { for(j=0;j<i;j++)//利用循环，是p结点指向第i位 p = p->next; p->prior->next = p->next; p->next->prior = p->prior; printf("删除成功\n"); return 0; } } int main() { int a,b,i=0; char c; DuLinkList L;//将L定义为LinkList类型的变量，便于直接引用 L = InitDuList(); printf("输入0为尾插法（其他为头插法）："); scanf("%d",&b); Interrupt();//中断scanf if(b==0) CreatDuList1(L);//尾插法 else CreatDuList2(L);//头插法 TraverseDuLNode(L); printf("操作输入序号选择：\n 1：遍历链表\n 2:链表的按位查找\n 3:删除链表元素\n 4:插入链表元素\n 5:链表的按值查找\n 6：表长\n输入#退出\n"); while(1) { int f = 0; printf("请选择："); scanf("%c",&c); Interrupt();//中断scanf switch(c) { case '1': printf("遍历并输出链表： ");TraverseDuLNode(L); break; case '2': printf("链表的按位查找（取值位置）： ");GetElem(L,a); break; case '3': printf("删除并返回要删除的元素（删除的位置）： ");DuListDelete(L,a); break; case '4': printf("插入元素（位置 插入的元素）： ");DuListInsert(L,a,a); break; case '5': printf("链表的按值查找（输入要查找的元素）： ");LocateElem(L,a); break; case '6': a = Length(L);printf("链表长为： %d\n",a); break; case '#': f = 1; break; default: printf("ERROR\n"); } if (f == 1) { printf("已正常退出!\n"); break; } } free(L); return 0; }（完）
