《数据结构（C语言版）》双向链表的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第二章线性表中双向链表的代码实现，该链表为带头结点的双向循环链表，课本上仅涉及到插入操作与删除操作，以下代码实现中该功能与课本上的代码基本相同，本人另外补充了尾插法建立链表与链表的打印，另外相对于以往额外处理了非法输入字母等问题。
双向链表的完整数据结构与动态单链表类似
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
//带头结点的双向循环链表
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct DuLNode
{
ElemType data;
struct DuLNode* prior;
struct DuLNode* next;
}DuLNode, * DuLinkList;
/*
双向链表中，若d为指向表中某一头结点的指针，则显然有：
d->next->prior=d->prior->next=d
*/
Status Init_DuL(DuLinkList& L);//初始化双向循环链表
void CreatList_DuL_R(DuLinkList& L, int n);//尾插法创建双向循环链表
void ShowList_DuL(DuLinkList L);//打印链表
DuLNode* GetElemP_DuL(DuLinkList L, int i);//查找第i位置的元素并返回指向该位置的指针
Status ListInsert_Dul(DuLinkList& L, int i, ElemType e);//在带头结点的双链循环线性表L中第i个位置之前插入元素e
Status ListDelete_Dul(DuLinkList& L, int i, ElemType e);//删除带头结点的双链循环线性表L的第i个元素
void Menu()
{
printf("**************************\n");
printf("********0.退出系统********\n");
printf("********1.创建链表********\n");
printf("********2.插入元素********\n");
printf("********3.删除元素********\n");
printf("********4.打印表单********\n");
printf("**************************\n");
}
//注：本程序需创建链表后才能插入元素
int main()
{
DuLinkList MyList;
int num = 0;
int position = 0;
int value = 0;
int option = 0;
int ret;
Init_DuL(MyList);
Menu();
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');//防止输入非法字符导致程序崩溃
switch (option)
{
case 1:
printf("使用尾插法创建双向循环链表，请输入待创建链表中的元素个数：");
while (scanf("%d", &num) != 1)
{
while (getchar() != '\n');
printf("你输入了非法字符，请重新输入：");
}
printf("请输入链表中的元素：");
CreatList_DuL_R(MyList, num);
break;
case 2:
printf("请输入你想插入的位置：");
while (scanf("%d", &position) != 1)
{
printf("你输入了非法字符，请重新输入：");
while (getchar() != '\n');
}
if (position <= 0)
{
printf("插入位置不合法\n");
break;
}
while (getchar() != '\n');
printf("请输入你想插入的元素：");
while (scanf("%d", &value) != 1)
{
printf("你输入了非法字符，请重新输入：");
while (getchar() != '\n');
}
if (ListInsert_Dul(MyList, position, value))
{
printf("插入成功！\n");
}
else
{
printf("插入失败，请重试\n");
}
break;
case 3:
printf("请输入你想删除的位置：");
while (scanf("%d", &position) != 1)
{
printf("你输入了非法字符，请重新输入：");
while (getchar() != '\n');
}
if (ListDelete_Dul(MyList, position, value))
{
printf("删除成功！\n");
}
else
{
printf("删除失败，请重试");
}
break;
case 4:
printf("链表中的元素有：");
ShowList_DuL(MyList);
break;
case 0:
exit(0);
break;
default:
printf("你输入了非法字符，请重新输入：");
break;
}
Menu();
}
return 0;
}
Status Init_DuL(DuLinkList& L)//初始化双向循环链表
{
L = (DuLinkList)malloc(sizeof(DuLNode));
if (!L)
{
exit(OVERFLOW);
}
L->prior = L;
L->next = L;
}
void CreatList_DuL_R(DuLinkList& L,int n)//尾插法创建双向循环链表
{
if (L->next == L)//如果该链表为空
{
DuLNode* p = (DuLinkList)malloc(sizeof(DuLNode));
if (!p)
{
exit(OVERFLOW);
}
while (scanf("%d", &p->data) != 1)
{
printf("你输入了非法字符，请重新输入：");
while (getchar() != '\n');
}
L->next = p;
p->prior = L;
p->next = L;
L->prior = p;
}
if (L->next != L)//如果链表中已有元素
{
for (int i = 1; i < n; i++)
{
DuLNode* p = (DuLinkList)malloc(sizeof(DuLNode));
if (!p)
{
exit(OVERFLOW);
}
while (scanf("%d", &p->data) != 1)
{
printf("你输入了非法字符，请重新输入：");
while (getchar() != '\n');
}
L->prior->next = p;
p->prior = L->prior;
L->prior = p;
p->next = L;
}
}
}
void ShowList_DuL(DuLinkList L)//打印链表
{
if (L->next == L)
{
printf("该链表为空表");
}
DuLNode* p = L->next;
while (p != L)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
DuLNode* GetElemP_DuL(DuLinkList L, int i)//查找第i位置的元素并返回指向该位置的指针
{
DuLNode* p = L->next;
int j = 1;
while (p!=L &&j < i)
{
p = p->next;
j++;
}
if (p==L ||j > i)
{
return ERROR;
}
return p;
}
Status ListInsert_Dul(DuLinkList& L, int i, ElemType e)//在带头结点的双链循环线性表L中第i个位置之前插入元素e
{
DuLNode* p;
if (!(p = GetElemP_DuL(L, i)))//如果插入位置不合法则报错
{
return ERROR;
}
DuLNode* s;
if (!(s = (DuLinkList)malloc(sizeof(DuLNode))))
{
exit(OVERFLOW);
}
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return OK;
}
Status ListDelete_Dul(DuLinkList& L, int i, ElemType e)//删除带头结点的双链循环线性表L的第i个元素
{
DuLNode* p;
if (!(p = GetElemP_DuL(L, i)))
{
return ERROR;
}
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
