数据结构-双向链表（c语言实现）
/1.创建一个空的双向链表//2.链表指定位置插入数据//3.遍历双向链表//4.指定位置删除 -双向链表// 5.判断双向链表是否为空// 6.求双向链表的长度// 7.查找指定数据出现的位置// 8.修改指定位置的数据// 9.删除双向链表中的指定数据// 10.转置双向链表。
·
前面的文章我曾写过单向链表的实现，下面分享一下双向链表的几个常见的函数接口
目录
功能介绍
//1.创建一个空的双向链表
double_t *createDoubleLink(void);
//2.链表指定位置插入数据
int insertPost(double_t *p, int post, datatype_t data);
//3.遍历双向链表
void showDouble(double_t *p);
//4.指定位置删除 -双向链表
int delectPost(double_t *p, int post);
// 5.判断双向链表是否为空
int isEmptyDouble(double_t *p);
// 6.求双向链表的长度
int lenDouble(double_t *p);
// 7.查找指定数据出现的位置
int searchData(double_t *p, datatype_t data);
// 8.修改指定位置的数据
int changePost(double_t *p, int post, datatype_t data);
// 9.删除双向链表中的指定数据
int delectData(double_t *p,datatype_t data);
// 10.转置双向链表
void resortDouble(double_t *p);代码模块
1.创建一个空的双向链表
double_t *createDoubleLink(void)
{
//1.开辟保存头尾节点地址及长度的结构体空间
double_t *p = (double_t *)malloc(sizeof(double_t));
if (NULL == p)
{
printf("malloc double err.\n");
return NULL;
}
//2.初始化-创建一个无效头节点
p->head = p->tail = (link_t *)malloc(sizeof(link_t));
if (NULL == p->head)
{
printf("malloc node err.\n");
free(p);
return NULL;
}
//初始化节点 空链表
p->head->prior = NULL;
p->head->next = NULL;
p->len = 0;
return p;
}2.初始化-创建一个无效头节点
int insertPost(double_t *p, int post, datatype_t data)
{
link_t *pt = NULL; //暂时保存头或尾节点的地址，进行遍历
//1.判断插入位置是否正确(容错处理)
if (post < 0 || post > p->len)
{
printf("post err.\n");
return -1;
}
//2.创建一个新节点保存插入的数据，并初始化节点
link_t *pnew = (link_t *)malloc(sizeof(link_t));
if (NULL == pnew)
{
printf("mallco node err.\n");
return -1;
}
pnew->prior = pnew->next = NULL;
pnew->data = data;
//3.判断是尾插，还是中间插入
if (post == p->len)
{
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew;
}
else
{
//4.判断是从头遍历到制定位置前一个位置插入，还是从尾遍历到指定位置前一个位置
// 插入方式：1》移动到指定位置往前插(先连前边再连后边)
//2》移动到指定位置前一个位置往后插(先连后边再连前边)
if (post < p->len / 2)
{ //头开始
pt = p->head;
for (int i = 0; i < post; i++)
{
pt = pt->next;
}
}
else
{
pt = p->tail;
for (int i = 0; i < p->len - post; i++)
{
pt = pt->prior;
}
}
//5.插入，先连后边再连前边
pnew->prior = pt->next->prior;
pt->next->prior = pnew;
pnew->next = pt->next;
pt->next = pnew;
}
p->len++;
return 0;
}3.遍历双向链表
void showDouble(double_t *p)
{
//正向遍历
link_t *pt = NULL;
pt = p->head;
while (pt->next != NULL)
{
pt = pt->next;
printf("%d ", pt->data);
}
putchar(10);
//反向遍历
pt = p->tail;
while (pt->prior != NULL)
{
printf("%d ", pt->data);
pt = pt->prior;
}
putchar(10);
}4.指定位置删除 -双向链表
int delectPost(double_t *p, int post)
{
link_t *pdel = NULL;
if (post < 0 || post >= p->len)
{
printf("delect post err.\n");
return -1;
}
//判断尾删，中间删除
if (post == p->len - 1)
{
pdel = p->tail;
p->tail = p->tail->prior;
p->tail->next = NULL;
}
else
{
//将pdel移动删除节点位置
//从头
if (post < p->len / 2)
{
pdel = p->head;
for (int i = 0; i <= post; i++)
{
pdel = pdel->next;
}
}
else
{
pdel = p->tail;
for (int i = 0; i < p->len - post - 1; i++)
{
pdel = pdel->prior;
}
}
//跨过这个节点
pdel->prior->next = pdel->next;
pdel->next->prior = pdel->prior;
}
//释放节点空间
free(pdel);
pdel = NULL;
p->len--;
return 0;
}5.判断链表是否为空
int isEmptyDouble(double_t *p)
{
return p->head == p->tail;
}6.求双向链表的长度
int lenDouble(double_t *p)
{
return p->len;
}7.查找指定数据出现的位置
int searchData(double_t *p, datatype_t data)
{
if (isEmptyDouble(p))
{
printf("is empty.\n");
return -1;
}
int post = 0;
link_t *pt = p->head;
while (pt->next != NULL)
{
pt = pt->next;
if (pt->data == data)
return post;
post++;
}
return -1;
}8.修改指定位置的数据
int changePost(double_t *p, int post, datatype_t data)
{
if (post < 0 || post >= p->len)
{
printf("post err.\n");
return -1;
}
link_t *pdel=NULL;
if (post < p->len / 2)
{
pdel = p->head;
for (int i = 0; i <= post; i++)
{
pdel = pdel->next;
}
}
else
{
pdel = p->tail;
for (int i = 0; i < p->len - post - 1; i++)
{
pdel = pdel->prior;
}
}
pdel->data=data;
return 0;
}9.删除双向链表中的指定数据
int delectData(double_t *p,datatype_t data)
{
if(isEmptyDouble(p))
{
printf("is empty.\n");
return -1;
}
int post=0;
link_t *pt=p->head;
while(pt->next != NULL)
{
pt=pt->next;
if(pt->data == data)
{
pt=pt->prior;
delectPost(p,post);
}else
post++;
}
}10.转置双向链表
void resortDouble(double_t *p)
{
link_t *pt=NULL;//暂时保存砍下的头
link_t *ph=NULL;//保存断开之后的无头双向链表
if(isEmptyDouble(p))
{
printf("is empty.\n");
return ;
}
//1.断开
ph=p->head->next;
p->tail=p->head;
p->head->next=NULL;
p->len=0;
//2.循环无头单向链表砍头插入到有头双向链表的头节点之后
while(ph !=NULL)
{
pt=ph;
ph=ph->next;
pt->next=pt->prior=NULL;
if(p->len == 0)
{
p->tail->next=pt;
pt->prior=p->tail;
p->tail=pt;
}else
{
pt->prior=p->head->next->prior;
p->head->next->prior=pt;
pt->next=p->head->next;
p->head->next=pt;
}
p->len++;
}
}完整代码
#include <stdio.h>
#include <stdlib.h>
//节点结构体
typedef int datatype_t;
typedef struct node_t
{
datatype_t data;
struct node_t *prior;
struct node_t *next;
} link_t;
//保存头尾节点地址及长度的结构体
typedef struct
{
link_t *head;
link_t *tail;
int len;
} double_t;
//1.创建一个空的双向链表
double_t *createDoubleLink(void);
//2.链表指定位置插入数据
int insertPost(double_t *p, int post, datatype_t data);
//3.遍历双向链表
void showDouble(double_t *p);
//4.指定位置删除 -双向链表
int delectPost(double_t *p, int post);
// 5.判断双向链表是否为空
int isEmptyDouble(double_t *p);
// 6.求双向链表的长度
int lenDouble(double_t *p);
// 7.查找指定数据出现的位置
int searchData(double_t *p, datatype_t data);
// 8.修改指定位置的数据
int changePost(double_t *p, int post, datatype_t data);
// 9.删除双向链表中的指定数据
int delectData(double_t *p,datatype_t data);
// 10.转置双向链表
void resortDouble(double_t *p);
int main(int argc, char const *argv[])
{
//可根据自己使用进行添加功能
return 0;
}
//1.创建一个空的双向链表
double_t *createDoubleLink(void)
{
//1.开辟保存头尾节点地址及长度的结构体空间
double_t *p = (double_t *)malloc(sizeof(double_t));
if (NULL == p)
{
printf("malloc double err.\n");
return NULL;
}
//2.初始化-创建一个无效头节点
p->head = p->tail = (link_t *)malloc(sizeof(link_t));
if (NULL == p->head)
{
printf("malloc node err.\n");
free(p);
return NULL;
}
//初始化节点 空链表
p->head->prior = NULL;
p->head->next = NULL;
p->len = 0;
return p;
}
//2.链表指定位置插入数据
int insertPost(double_t *p, int post, datatype_t data)
{
link_t *pt = NULL; //暂时保存头或尾节点的地址，进行遍历
//1.判断插入位置是否正确(容错处理)
if (post < 0 || post > p->len)
{
printf("post err.\n");
return -1;
}
//2.创建一个新节点保存插入的数据，并初始化节点
link_t *pnew = (link_t *)malloc(sizeof(link_t));
if (NULL == pnew)
{
printf("mallco node err.\n");
return -1;
}
pnew->prior = pnew->next = NULL;
pnew->data = data;
//3.判断是尾插，还是中间插入
if (post == p->len)
{
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew;
}
else
{
//4.判断是从头遍历到制定位置前一个位置插入，还是从尾遍历到指定位置前一个位置
// 插入方式：1》移动到指定位置往前插(先连前边再连后边)
//2》移动到指定位置前一个位置往后插(先连后边再连前边)
if (post < p->len / 2)
{ //头开始
pt = p->head;
for (int i = 0; i < post; i++)
{
pt = pt->next;
}
}
else
{
pt = p->tail;
for (int i = 0; i < p->len - post; i++)
{
pt = pt->prior;
}
}
//5.插入，先连后边再连前边
pnew->prior = pt->next->prior;
pt->next->prior = pnew;
pnew->next = pt->next;
pt->next = pnew;
}
p->len++;
return 0;
}
//3.遍历双向链表
void showDouble(double_t *p)
{
//正向遍历
link_t *pt = NULL;
pt = p->head;
while (pt->next != NULL)
{
pt = pt->next;
printf("%d ", pt->data);
}
putchar(10);
//反向遍历
pt = p->tail;
while (pt->prior != NULL)
{
printf("%d ", pt->data);
pt = pt->prior;
}
putchar(10);
}
//4.指定位置删除 -双向链表
int delectPost(double_t *p, int post)
{
link_t *pdel = NULL;
if (post < 0 || post >= p->len)
{
printf("delect post err.\n");
return -1;
}
//判断尾删，中间删除
if (post == p->len - 1)
{
pdel = p->tail;
p->tail = p->tail->prior;
p->tail->next = NULL;
}
else
{
//将pdel移动删除节点位置
//从头
if (post < p->len / 2)
{
pdel = p->head;
for (int i = 0; i <= post; i++)
{
pdel = pdel->next;
}
}
else
{
pdel = p->tail;
for (int i = 0; i < p->len - post - 1; i++)
{
pdel = pdel->prior;
}
}
//跨过这个节点
pdel->prior->next = pdel->next;
pdel->next->prior = pdel->prior;
}
//释放节点空间
free(pdel);
pdel = NULL;
p->len--;
return 0;
}
// 5.判断双向链表是否为空
int isEmptyDouble(double_t *p)
{
return p->head == p->tail;
}
// 6.求双向链表的长度
int lenDouble(double_t *p)
{
return p->len;
}
// 7.查找指定数据出现的位置
int searchData(double_t *p, datatype_t data)
{
if (isEmptyDouble(p))
{
printf("is empty.\n");
return -1;
}
int post = 0;
link_t *pt = p->head;
while (pt->next != NULL)
{
pt = pt->next;
if (pt->data == data)
return post;
post++;
}
return -1;
}
// 8.修改指定位置的数据
int changePost(double_t *p, int post, datatype_t data)
{
if (post < 0 || post >= p->len)
{
printf("post err.\n");
return -1;
}
link_t *pdel=NULL;
if (post < p->len / 2)
{
pdel = p->head;
for (int i = 0; i <= post; i++)
{
pdel = pdel->next;
}
}
else
{
pdel = p->tail;
for (int i = 0; i < p->len - post - 1; i++)
{
pdel = pdel->prior;
}
}
pdel->data=data;
return 0;
}
// 9.删除双向链表中的指定数据
int delectData(double_t *p,datatype_t data)
{
if(isEmptyDouble(p))
{
printf("is empty.\n");
return -1;
}
int post=0;
link_t *pt=p->head;
while(pt->next != NULL)
{
pt=pt->next;
if(pt->data == data)
{
pt=pt->prior;
delectPost(p,post);
}else
post++;
}
}
// 10.转置双向链表
void resortDouble(double_t *p)
{
link_t *pt=NULL;//暂时保存砍下的头
link_t *ph=NULL;//保存断开之后的无头双向链表
if(isEmptyDouble(p))
{
printf("is empty.\n");
return ;
}
//1.断开
ph=p->head->next;
p->tail=p->head;
p->head->next=NULL;
p->len=0;
//2.循环无头单向链表砍头插入到有头双向链表的头节点之后
while(ph !=NULL)
{
pt=ph;
ph=ph->next;
pt->next=pt->prior=NULL;
if(p->len == 0)
{
p->tail->next=pt;
pt->prior=p->tail;
p->tail=pt;
}else
{
pt->prior=p->head->next->prior;
p->head->next->prior=pt;
pt->next=p->head->next;
p->head->next=pt;
}
p->len++;
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)