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

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

2023-06-15 66
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 带头双向循环链表增删查改实现（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语言
有礼貌的灰绅士
目录
相关文章
西柚与蓝莓
|
6月前
|
C语言
对链表使用插入排序的C语言实现示例
对链表使用插入排序的C语言实现示例
西柚与蓝莓
56 1
修修修也
|
6月前
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
修修修也
58 0
ephemerals__
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
44 4
石小浪♪
|
1月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装，包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
石小浪♪
26 0
ephemerals__
|
17天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
37 0
石小浪♪
|
1月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法，包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除，以及链表的打印等功能。文章通过具体的代码示例，展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除，以及如何清空和销毁链表。
石小浪♪
30 0
单链表之无头链表(C语言版)
石小浪♪
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表，并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现，以及一个示例程序来演示这些操作。
石小浪♪
22 0
TiAmoZhang
|
4月前
|
存储 数据管理 C语言
C语言实战 | 使用链表完成“贪吃蛇”游戏
【7月更文挑战第1天】整体思维，即系统思维，强调以整体视角理解事物。在编程中，结构体体现这种思想，将相关变量打包处理。示例展示了如何用链表而非数组实现“贪吃蛇”游戏，链表提供了更灵活的动态数据管理。一系列代码图片详细描绘了链表结构体在游戏中的应用，包括节点定义、移动、碰撞检测等，凸显了使用链表的优势和代码的清晰组织。
TiAmoZhang
44 0
C语言实战 | 使用链表完成“贪吃蛇”游戏
7fa6b5ui5pmtk
|
5月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
31 2
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
45 2