备案控制台
开发者社区 开发与运维 文章 正文

带头双向循环链表增删查改实现（C语言）

2023-06-15 48
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 带头双向循环链表增删查改实现（C语言）

结点结构与头结点的创建

创建两个源文件和一个头文件

test.c

linked_list.c

linked_list.h

带头双向循环链表，那么，结点的结构就要有两个指针域，分别指向前一个结点和后一个结点。

整个链表大概就是这样一个结构。

#define TYPE int 
typedef struct Linked_list//结点的内部结构
{
  struct Linked_list* prev;//前指针
  struct Linked_list* next;//后指针
  TYPE data;
}LL;

创建头结点时要注意，我们要的时循环结构，所以也要让头结点的前指针和后指针都指向自己才符合循环结构。（在后面的操作也是比较方便的）

LL* ListCreate()//创建头结点
{
  LL* head = (LL*)malloc(sizeof(LL));
  if (head == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  head->next = head;
  head->prev = head;
  return head;
}

头插尾插

因为有头结点的关系，就不需要判断是否是第一个结点的问题了。

这里尾插就很方便了，不像之前需要遍历找尾，因为是循环链表，尾的next就是头结点。

当然这里要先写一个创建新结点的函数。

//linked_list.c
LL* BuyLisNode(TYPE x)
{
  LL* newnode = (LL*)malloc(sizeof(LL));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;//因为是要链接进链表的结点，所以指向空就可以了
  newnode->prev = NULL;
  return newnode;//返回新结点的地址
}

尾插

void ListPushBack(LL* phead, TYPE x)//尾插
{
  assert(phead);
  LL* newnode = BuyLisNode(x);
  LL* tail = phead->prev;//储存尾结点
  tail->next = newnode;//让尾的next指向新节点
  newnode->prev = tail;//新结点的prev指向尾
  newnode->next = phead;//新节点的next指向头结点
  phead->prev = newnode;//头结点的prev指向新结点
}

头插

void ListPushFront(LL* phead, TYPE x)//头插
{
  assert(phead);
  LL* newnode = BuyLisNode(x);
  LL* head = phead->next;//储存头结点的下一个结点
  phead->next = newnode;//让头结点的next指向新结点
  newnode->prev = phead;//新结点的prev指向头结点
  newnode->next = head;//新结点next指向头结点的下一个结点
  head->prev = newnode;//头结点的下一个结点指向新结点
}

打印链表

这里就要遍历链表了，因为是循环结构，所以结尾就不用空指针进行判断了。

void ListPrint(LL* phead)//打印链表
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)//遍历链表，结尾是cur指向的的如果是phead就说明上一个结点就是尾
  {
    printf("%d ", cur->data);//打印
    cur = cur->next;
  }
  printf("\n");
}

头删与尾删

删除的话，我们需要写一个函数判断链表中是否还有数据，如果只剩一个头结点就不能继续删除了。

bool estimate(LL* phead)//判断是否还有数据
{
  return phead->next == phead;//这里要注意，相等返回1，不相同返回0
}

尾删

删除尾结点的时候要将倒数第二个结点与头结点进行连接。

void ListPopBack(LL* phead)// 尾删
{
  assert(phead);
  assert(!estimate(phead));//判断是否还有数据，这里别忘记用!号
  LL* cur = phead->prev;//储存要删除的尾结点
  phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点
  cur->prev->next = phead;//让倒是第二个结点的next指向头结点
  free(cur);//释放
}

头删

删除第一个结点也要注意判断是否还有数据和第二个结点与头结点的连接。

void ListPopFront(LL* phead)//头删
{
  assert(phead);
  assert(!estimate(phead));
  LL* cur = phead->next;//储存要删除的第一个结点
  phead->next = cur->next;//头结点的next指向第二个结点
  cur->next->prev = phead;//第二个结点的prev指向头结点
  free(cur);//释放
}

链表的查找

LL* ListFind(LL* phead, TYPE x)//查找
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;//找到返回当前地址
    }
    cur = cur->next;
  }
  return NULL;//找不到返回空指针
}

在pos的前面进行插入与删除pos位置的结点

pos是配合查找的，如果pos传错了也没办法。

插入

void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入
{
  LL* cur = BuyLisNode(x);// 创建新结点
  LL* prev = pos->prev;//找到pos前面的结点
  pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系
  cur->next = pos;
  cur->prev = prev;
  prev->next = cur;
}

删除

void ListErase(LL* pos)//删除pos位置的结点
{
  LL* prev = pos->prev;//储存pos前面的结点
  LL* next = pos->next;//储存pos后面的结点
  prev->next = next;//让pos前后结点建立联系
  next->prev = prev;
  free(pos);//释放
}

销毁链表

这里注意，头结点也要释放掉。

void ListDestory(LL* phead)//销毁链表
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)//释放除了头结点以外的结点
  {
    LL* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);//释放头结点
}

完整代码

linked_list.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int TYPE;
typedef struct Linked_list//结点的内部结构
{
  struct Linked_list* prev;//前指针
  struct Linked_list* next;//后指针
  TYPE data;
}LL;
LL* ListCreate();//创建头结点
void ListPushBack(LL* phead, TYPE x);//尾插
void ListPushFront(LL* phead, TYPE x);//头插
void ListPrint(LL* phead);//打印链表
void ListPopBack(LL* phead);// 尾删
void ListPopFront(LL* phead);//头删
LL* ListFind(LL* phead, TYPE x);//查找
void ListInsert(LL* pos, TYPE x);//在pos的前面进行插入
void ListErase(LL* pos);//删除pos位置的结点
void ListDestory(LL* phead);//销毁链表

linked_list.c

#include "linked_list.h"
LL* ListCreate()//创建头结点
{
  LL* head = (LL*)malloc(sizeof(LL));
  if (head==NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  head->next = head;
  head->prev = head;
  return head;
}
LL* BuyLisNode(TYPE x)//创建新结点
{
  LL* newnode = (LL*)malloc(sizeof(LL));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;//因为是链接进链表的结点，所以指向空就可以了
  newnode->prev = NULL;
  return newnode;
}
void ListPushBack(LL* phead, TYPE x)//尾插
{
  assert(phead);
  LL* newnode = BuyLisNode(x);//创建新结点
  LL* tail = phead->prev;//储存尾结点
  tail->next = newnode;//让尾的next指向新节点
  newnode->prev = tail;//新结点的prev指向尾
  newnode->next = phead;//新节点的next指向头结点
  phead->prev = newnode;//头结点的prev指向新结点
}
void ListPushFront(LL* phead, TYPE x)//头插
{
  assert(phead);
  LL* newnode = BuyLisNode(x);
  LL* head = phead->next;//储存头结点的下一个结点
  phead->next = newnode;//让头结点的next指向新结点
  newnode->prev = phead;//新结点的prev指向头结点
  newnode->next = head;//新结点next指向头结点的下一个结点
  head->prev = newnode;//头结点的下一个结点指向新结点
}
bool estimate(LL* phead)//判断是否还有数据
{
  return phead->next == phead;//这里要注意，相等返回0，不相同返回1
}
void ListPrint(LL* phead)//打印链表
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)//遍历链表
  {
    printf("%d ", cur->data);//打印
    cur = cur->next;
  }
  printf("\n");
}
void ListPopBack(LL* phead)// 尾删
{
  assert(phead);
  assert(!estimate(phead));//判断是否还有数据
  LL* cur = phead->prev;//储存要删除的尾结点
  phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点
  cur->prev->next = phead;//让倒是第二个结点的next指向头结点
  free(cur);//释放
}
void ListPopFront(LL* phead)//头删
{
  assert(phead);
  assert(!estimate(phead));
  LL* cur = phead->next;//储存要删除的第一个结点
  phead->next = cur->next;//头结点的next指向第二个结点
  cur->next->prev = phead;//第二个结点的prev指向头结点
  free(cur);//释放
}
LL* ListFind(LL* phead, TYPE x)//查找
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;//找到返回当前地址
    }
    cur = cur->next;
  }
  return NULL;//找不到返回空指针
}
void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入
{
  LL* cur = BuyLisNode(x);// 创建新结点
  LL* prev = pos->prev;//找到pos前面的结点
  pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系
  cur->next = pos;
  cur->prev = prev;
  prev->next = cur;
}
void ListErase(LL* pos)//删除pos位置的结点
{
  LL* prev = pos->prev;//储存pos前面的结点
  LL* next = pos->next;//储存pos后面的结点
  prev->next = next;//让pos前后结点建立联系
  next->prev = prev;
  free(pos);//释放
}
void ListDestory(LL* phead)//销毁链表
{
  assert(phead);
  LL* cur = phead->next;
  while (cur != phead)//释放除了头结点以外的结点
  {
    LL* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);//释放头结点
}

test.c

#include "linked_list.h"
void test()
{
  LL* head = NULL;
  head = ListCreate();//创建头结点
  ListPushBack(head, 5);//尾插
  ListPushBack(head, 7);//尾插
  ListPushFront(head, 8);//头插
  ListPushFront(head, 6);//头插
  ListPopBack(head);//尾删
  ListPopFront(head);//头删
  ListPrint(head);//打印链表
  LL* pos = ListFind(head, 5);//查找
  if (pos != NULL)
  {
    printf("YES\n");
  }
  else
  {
    printf("NO\n");
  }
  ListInsert(pos, 3);//在pos的前面进行插入
  ListPrint(head);//打印链表
  ListErase(pos);//删除pos位置的结点
  ListPrint(head);//打印链表
  ListDestory(head);//销毁链表
  ListPrint(head);//打印链表
}
int main()
{
  test();
  return 0;
}

运行结果：

文章标签：
C语言
关键词：
链表c语言
链表增删查改
双向循环链表C语言
双向循环链表增删查改C语言
有礼貌的灰绅士
目录
相关文章
西柚与蓝莓
|
23小时前
|
C语言
对链表使用插入排序的C语言实现示例
对链表使用插入排序的C语言实现示例
西柚与蓝莓
14 1
修修修也
|
23小时前
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
修修修也
11 0
一枕眠秋雨
|
23小时前
|
C语言
基于链表实现的链式管理系统(C语言课设)
基于链表实现的链式管理系统(C语言课设)
一枕眠秋雨
18 2
是Nero哦
|
23小时前
|
C语言
链接未来：深入理解链表数据结构（二.c语言实现带头双向循环链表）
链接未来：深入理解链表数据结构（二.c语言实现带头双向循环链表）
是Nero哦
33 0
码农日常
|
23小时前
|
测试技术
LeetCode | 141.环形链表（C语言版）
LeetCode | 141.环形链表（C语言版）
码农日常
30 1
码农日常
|
23小时前
|
算法 测试技术
LeetCode | 206.反转链表（C语言版）
LeetCode | 206.反转链表（C语言版）
码农日常
34 0
码农日常
|
23小时前
|
测试技术
LeetCode | 24.两两交换链表中的节点（C语言版）
LeetCode | 24.两两交换链表中的节点（C语言版）
码农日常
38 0
早點睡.
|
23小时前
|
前端开发 C语言
c语言中的链表
c语言中的链表
早點睡.
9 1
GOTXX
|
23小时前
|
存储 C语言
数据结构之单链表详解（C语言手撕）
数据结构之单链表详解（C语言手撕）
GOTXX
46 1
sumith
|
23小时前
|
C语言
C语言(链表、栈、树)
C语言(链表、栈、树)
sumith
11 0

热门文章

最新文章

  • 1
    C语言实现矩阵转置
  • 2
    C语言C/Ｓ架构PACS影像归档和通信系统源码 医院PACS系统源码
  • 3
    pta浙大版《C语言程序设计（第3版）》 习题6-4 使用函数输出指定范围内的Fibonacci数 (20分)
  • 4
    C语言基础知识：数据在内存中的存储解析（整数，浮点数）
  • 5
    【精通C语言】：分支结构if语句的灵活运用
  • 6
    PTA 浙大版《C语言程序设计（第3版）》题目集 习题8-4 报数 (20分)
  • 7
    PTA 浙大版《C语言程序设计（第3版）》题目集 习题8-6 删除字符 (20分)
  • 8
    浙大版《C语言程序设计（第3版）》题目集 练习8-2 计算两数的和与差 (10分)
  • 9
    C语言中逻辑表达式的深入探讨
  • 10
    C语言中字符串的引用与数组元素操作
  • 1
    数据结构基础：双链表结构、实现
    16
  • 2
    尾插法建立链表
    5
  • 3
    线性表、链表、栈和队列的初始化
    17
  • 4
    三种方法实现获取链表中的倒数第ｎ个元素
    15
  • 5
    【力扣】21. 合并两个有序链表
    14
  • 6
    数据结构|双向链表|带头结点|头插|尾插|尾删|头删
    12
  • 7
    算法系列--链表刷题(二)（下）
    18
  • 8
    算法系列--递归(一)--与链表有关（上）
    28
  • 9
    数据结构--链表刷题(一)快慢指针（上）
    16
  • 10
    【优选算法专栏】专题九：链表--------两两交换链表中的节点
    17

    • 相关课程

    更多
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考