C语言实现双链表
说明
图片自己画的，有点丑，不要介意。
本文来自专栏：数据结构
后续还会继续coding。如果有需要可以关注点赞一波。
实现的功能
- 插入结点
- 删除结点
- 从头到尾遍历输出所有元素
- 获取某个结点的前驱和其后继结点
获取前驱和后继主要是为了测试双链表是否编写正确，因为双链表可以访问前驱，这是与单链表不同的地方。
结构体定义
typedef struct BiLinkNode
{
ElemType data;
struct BiLinkNode *rlink,*llink;//分别代表左指针和右指针，分别指向前驱和后继，一般也写作prior和next
}BiLink;
初始化
//初始化双链表(带头结点)
bool InitBiLinkList(BiLink *B)
{
//先申请一个头结点
BiLink *head = (BiLink *)malloc(sizeof(BiLink));
//左右指针初始为空,且表长为0
head->llink = B;
B->rlink = head;
head->rlink = NULL;//头结点之后一开始还没元素
return true;
}
插入结点
? 如下图所示：
? 绿色实线是插入前的结构，虚线是我们要进行的操作。S代表新插入的结点。
? 这里我进行的操作顺序是①②③④，当然也可以修改顺序，比如③和④的顺序可以调换。这些操作对应的代码实现是：
? ①s->rlink = p->rlink;
? ②p->rlink->llink = s;
? ③p->rlink = s;
? ④s->llink = p;
? 这里我使用了头插法实现，欢迎大家使用尾插法尝试。
//插入
bool InsertBiLinkList(BiLink *B,ElemType e)
{
//头插法
BiLink *p = B;//
//申请一个新的结点
BiLink *s = (BiLink *)malloc(sizeof(BiLink));
s->data = e;//赋值
//修改指针 将结点s插入到结点p之后
s->rlink = p->rlink;//s指针指向
p->rlink->llink = s;
p->rlink = s;
s->llink = p;
length++;//元素个数加一
return true;
}
删除结点
如图：
删除操作比插入操作要简单得多，我们只需要修改q->llink的右指针和q->rlink的左指针，将其分别指向q->rlink和q-<llink即可。
bool DeleteBinList(BiLink *B,ElemType *e)//根据值删除某个结点
{
BiLink *q;
q = B->rlink;
while(q->rlink!=NULL)//先遍历
{
if(q->data == e)//首先找到这个结点
{
q->llink->rlink = q->rlink;//修改q结点前面的后继指针
q->rlink->llink = q->llink;//修改q结点后面的前驱指针
}
q = q->rlink;
}
length--;
return true;
}
输出所有元素
只需从头到尾遍历或者从尾到头遍历即可。这里我实现从头到尾遍历。
void PrintAll(BiLink *B)
{
BiLink *q;
q = B->rlink;
//打印出所有元素
while(q->rlink!=NULL)
{
printf("%d ",q->data);
q = q->rlink;//只要没到末尾，指针++
}
}
全部代码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> //根据C99标准,C语言使用bool类型需要添加这个头文件
typedef int ElemType;
typedef struct BiLinkNode
{
ElemType data;
struct BiLinkNode *rlink,*llink;
}BiLink;
//------------ 函数声明 ----------//
void MainMenu();
bool GetLen(BiLink *B);//获取表长度，并且直接打印在屏幕上
bool InitBiLinkList(BiLink *B);//初始化
bool InsertBiLinkList(BiLink *B,ElemType e);//插入
void PrintAll(BiLink *B);//输出所有元素
bool GetPriorNode(BiLink *B,ElemType e,ElemType *ldata);//查找元素为e的前驱结点的值
bool GetNextNode(BiLink *B,ElemType e,ElemType *rdata);//查找元素为e的后继结点的值
bool DeleteBinList(BiLink *B,ElemType *e);//根据值删除某个结点
//------------ 函数声明 ----------//
int length; //表中实际长度
int main()
{
BiLink B;
int ch;
ElemType element,num,ldata,rdata;
if(InitBiLinkList(&B))
printf("初始化成功！\n");
else
printf("初始化失败！\n");
while(1)
{
MainMenu();
printf("请输入您要执行的操作:");
scanf("%d",&ch);
switch(ch)
{
case 0: printf("感谢使用，已退出！"); exit(0); break;
case 1: printf("请输入您要插入的元素:\n");
scanf("%d",&element);
if(InsertBiLinkList(&B,element))
printf("插入成功！\n");
else
printf("插入失败！\n");
break;
case 2: PrintAll(&B);
break;
case 3: if(GetLen(&B))
printf("获取成功!");
else
printf("获取失败!");
break;
case 4:
printf("请输入你要获取的当前结点的值：\n");
scanf("%d",&num);
if(GetPriorNode(&B,num,&ldata))
printf("获取成功，%d的前一结点的值为:%d\n",num,ldata);
else
printf("获取失败！");
break;
case 5:
printf("请输入你要获取的当前结点的值：\n");
scanf("%d",&num);
if(GetNextNode(&B,num,&rdata))
printf("获取成功，%d的后一结点的值为:%d\n",num,rdata);
else
printf("获取失败！");
break;
case 6:
printf("请输入你要删除的结点的值：\n");
scanf("%d",&num);
if(DeleteBinList(&B,num))
printf("删除成功!\n");
else
printf("删除失败！");
break;
default: printf("您输入的操作指令有误！请重新输入！");
}
}
return 0;
}
//主菜单，显示
void MainMenu()
{
printf("\n\n\n");
printf("\t ************* 双链表的实现 ************\n\n");
printf("\t ------- 0.退出 \n\n");
printf("\t ------- 1.插入元素\n\n");
printf("\t ------- 2.输出所有元素\n\n");
printf("\t ------- 3.获取表长度\n\n");
printf("\t ------- 4.获取某个结点的前驱结点的值\n\n");
printf("\t ------- 5.获取某个结点的后继结点的值\n\n");
printf("\t ------- 6.删除一个结点\n\n");
printf("\t *************************************\n");
}
//初始化双链表(带头结点)
bool InitBiLinkList(BiLink *B)
{
//先申请一个头结点
BiLink *head = (BiLink *)malloc(sizeof(BiLink));
//左右指针初始为空,且表长为0
head->llink = B;
B->rlink = head;
head->rlink = NULL;//头结点之后一开始还没元素
return true;
}
//插入
bool InsertBiLinkList(BiLink *B,ElemType e)
{
//头插法
BiLink *p = B;//
//申请一个新的结点
BiLink *s = (BiLink *)malloc(sizeof(BiLink));
s->data = e;//赋值
//修改指针 将结点s插入到结点p之后
s->rlink = p->rlink;//s指针指向
p->rlink->llink = s;
p->rlink = s;
s->llink = p;
length++;//元素个数加一
return true;
}
bool GetLen(BiLink *B)
{
printf("表长为:%d\n",length);
return true;
}
void PrintAll(BiLink *B)
{
BiLink *q;
q = B->rlink;
//打印出所有元素
while(q->rlink!=NULL)
{
printf("%d ",q->data);
q = q->rlink;
}
}
bool GetPriorNode(BiLink *B,ElemType e,ElemType *ldata)//查找元素为e的前驱结点的值
{
BiLink *q;
q = B->rlink;
while(q->rlink!=NULL)
{
if(q->data == e)//首先找到这个结点
*ldata = q->llink->data;
q = q->rlink;
}
return true;
}
bool GetNextNode(BiLink *B,ElemType e,ElemType *rdata)//查找元素为e的后继结点的值
{
BiLink *q;
q = B->rlink;
while(q->rlink!=NULL)
{
if(q->data == e)//首先找到这个结点
*rdata = q->rlink->data;
q = q->rlink;
}
return true;
}
bool DeleteBinList(BiLink *B,ElemType *e)//根据值删除某个结点
{
BiLink *q;
q = B->rlink;
while(q->rlink!=NULL)
{
if(q->data == e)//首先找到这个结点
{
q->llink->rlink = q->rlink;//修改q结点前面的后继指针
q->rlink->llink = q->llink;//修改q结点后面的前驱指针
}
q = q->rlink;
}
length--;
return true;
}
测试
