数据结构c语言双向循环链表
双向循环链表在定义上类似于循环单链表，就多了个前指针，以方便于向前查找。在双向链表中需要同时修改两个方向的指针，是单向链表指针的两倍。
完整代码如下：
#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;
}
（完）
![【数据结构】 医院选址[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)