C语言实现双链表
文章目录
- 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-
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
#include
#include //根据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的前一结点的值为:%dn",num,ldata);
else
printf("获取失败！");
break;
case 5:
printf("请输入你要获取的当前结点的值：n");
scanf("%d",&num);
if(GetNextNode(&B,num,&rdata))
printf("获取成功，%d的后一结点的值为:%dn",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("nnn");
printf("t ************* 双链表的实现 ************nn");
printf("t ------- 0.退出 nn");
printf("t ------- 1.插入元素nn");
printf("t ------- 2.输出所有元素nn");
printf("t ------- 3.获取表长度nn");
printf("t ------- 4.获取某个结点的前驱结点的值nn");
printf("t ------- 5.获取某个结点的后继结点的值nn");
printf("t ------- 6.删除一个结点nn");
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("表长为:%dn",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;
}
测试
