《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》雙向鏈表的實(shí)現(xiàn)
清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬(wàn)冊(cè)
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）
以下是本人對(duì)該紫皮書(shū)第二章線性表中雙向鏈表的代碼實(shí)現(xiàn)，該鏈表為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，課本上僅涉及到插入操作與刪除操作，以下代碼實(shí)現(xiàn)中該功能與課本上的代碼基本相同，本人另外補(bǔ)充了尾插法建立鏈表與鏈表的打印，另外相對(duì)于以往額外處理了非法輸入字母等問(wèn)題。
雙向鏈表的完整數(shù)據(jù)結(jié)構(gòu)與動(dòng)態(tài)單鏈表類似
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯）?
//帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表
#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為指向表中某一頭結(jié)點(diǎn)的指針，則顯然有：
d->next->prior=d->prior->next=d
*/
Status Init_DuL(DuLinkList& L);//初始化雙向循環(huán)鏈表
void CreatList_DuL_R(DuLinkList& L, int n);//尾插法創(chuàng)建雙向循環(huán)鏈表
void ShowList_DuL(DuLinkList L);//打印鏈表
DuLNode* GetElemP_DuL(DuLinkList L, int i);//查找第i位置的元素并返回指向該位置的指針
Status ListInsert_Dul(DuLinkList& L, int i, ElemType e);//在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e
Status ListDelete_Dul(DuLinkList& L, int i, ElemType e);//刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素
void Menu()
{
printf("**************************\n");
printf("********0.退出系統(tǒng)********\n");
printf("********1.創(chuàng)建鏈表********\n");
printf("********2.插入元素********\n");
printf("********3.刪除元素********\n");
printf("********4.打印表單********\n");
printf("**************************\n");
}
//注：本程序需創(chuàng)建鏈表后才能插入元素
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');//防止輸入非法字符導(dǎo)致程序崩潰
switch (option)
{
case 1:
printf("使用尾插法創(chuàng)建雙向循環(huán)鏈表，請(qǐng)輸入待創(chuàng)建鏈表中的元素個(gè)數(shù)：");
while (scanf("%d", &num) != 1)
{
while (getchar() != '\n');
printf("你輸入了非法字符，請(qǐng)重新輸入：");
}
printf("請(qǐng)輸入鏈表中的元素：");
CreatList_DuL_R(MyList, num);
break;
case 2:
printf("請(qǐng)輸入你想插入的位置：");
while (scanf("%d", &position) != 1)
{
printf("你輸入了非法字符，請(qǐng)重新輸入：");
while (getchar() != '\n');
}
if (position <= 0)
{
printf("插入位置不合法\n");
break;
}
while (getchar() != '\n');
printf("請(qǐng)輸入你想插入的元素：");
while (scanf("%d", &value) != 1)
{
printf("你輸入了非法字符，請(qǐng)重新輸入：");
while (getchar() != '\n');
}
if (ListInsert_Dul(MyList, position, value))
{
printf("插入成功！\n");
}
else
{
printf("插入失敗，請(qǐng)重試\n");
}
break;
case 3:
printf("請(qǐng)輸入你想刪除的位置：");
while (scanf("%d", &position) != 1)
{
printf("你輸入了非法字符，請(qǐng)重新輸入：");
while (getchar() != '\n');
}
if (ListDelete_Dul(MyList, position, value))
{
printf("刪除成功！\n");
}
else
{
printf("刪除失敗，請(qǐng)重試");
}
break;
case 4:
printf("鏈表中的元素有：");
ShowList_DuL(MyList);
break;
case 0:
exit(0);
break;
default:
printf("你輸入了非法字符，請(qǐng)重新輸入：");
break;
}
Menu();
}
return 0;
}
Status Init_DuL(DuLinkList& L)//初始化雙向循環(huán)鏈表
{
L = (DuLinkList)malloc(sizeof(DuLNode));
if (!L)
{
exit(OVERFLOW);
}
L->prior = L;
L->next = L;
}
void CreatList_DuL_R(DuLinkList& L,int n)//尾插法創(chuàng)建雙向循環(huán)鏈表
{
if (L->next == L)//如果該鏈表為空
{
DuLNode* p = (DuLinkList)malloc(sizeof(DuLNode));
if (!p)
{
exit(OVERFLOW);
}
while (scanf("%d", &p->data) != 1)
{
printf("你輸入了非法字符，請(qǐng)重新輸入：");
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("你輸入了非法字符，請(qǐng)重新輸入：");
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)//在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e
{
DuLNode* p;
if (!(p = GetElemP_DuL(L, i)))//如果插入位置不合法則報(bào)錯(cuò)
{
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)//刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素
{
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;
}
