备案控制台
开发者社区 云计算 文章 正文

【数据结构】带头双向循环链表（小白入门必备知识）(下）

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

7.链表尾删节点

图解:

当链表不止一个节点时:

0b528dd116cc4f4ab37c8baa0d6fdc96.png

当链表只有一个节点（哨兵位不算）时:

d6ad27d7130b47ea8f9cc891fde2d0a4.png

若链表为NULL(只剩哨兵位就是链表为NULL)时，再尾删就会出错

40e42fd7b67545d58fcd04277b352327.png

检查链表是否为空,进行函数封装:

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}


函数解析:

       LTEmpty(LTNode* phead)是一个函数调用，它将链表头节点phead作为参数传递给LTEmpty函数。LTEmpty函数的作用是判断循环链表是否为空，如果为空则返回true，否则返回false。

      如果LTEmpty(phead)返回true，即链表为空，那么!LTEmpty(phead)将为false。如果LTEmpty(phead)返回false，即链表不为空，那么 !LTEmpty(phead)将为true

assert 宏用于在运行时进行断言检查。它接受一个表达式作为参数，如果表达式的结果为false,则会触发断言失败，程序可能会终止执行。如果表达式的结果为true，则断言通过，程序继续执行。

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail= phead->prev;
  LTNode* tailPrev=tail->prev ;
  free(tail); //先删除再链接
  tailPrev->next = phead;
  phead->prev = tailPrev;
}


代码执行:

f45cb9379c5349cd9fe53c4dc404d011.png


8.链表头删节点

链表不止一个结点时:

图解:

数字代表顺序

b279defa1b6642a4bacd909c2633a8bc.png

链表为一个结点时:

数字代表顺序

2a521fb2316a4770b8ef0613a76c741e.png

函数代码: 

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* first = phead->next;
  LTNode* second = first->next;
  phead->next = second;
  second->prev = phead;  
  free(first);
}


代码执行:

222bdd82256b45b1bd1d58b0bd2c2da3.png


9.链表查找/修改某个值

LTNode* STFind(LTNode* phead, LTDataType x)
{
  //assert(phead);
  LTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
    if (cur->data == phead->data)//若重新回到哨兵位，则说明链表遍历完毕，找不到x值，返回NULL
    {
      break;
    }
  }
  return NULL;
}


代码执行:

找到了:

2ecb59104b0e423e9dfb7c2068c3fe27.png

找不到:

97e127a603a04d7ab816084aad327052.png

10.在链表pos位置之前插入值

图解:

7021207859a1447c9fe2abe5575339cd.png

void LTInsert(LTNode* pos,LTDataType x)//输入要删除的数的位置即可
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* prev = pos->prev;
  prev->next = newnode;
  newnode->next = pos;
  newnode->prev = prev;
  pos->prev = newnode;
}

代码执行:

6367d93446dd49c5b37f908c0ea60349.png

LTInsert实现尾插操作:
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead, x);
}


LTInsert实现头插操作:
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead->next);
  LTInsert(phead->next, x);
}


11.在链表pos位置处删除此节点

01ee5648cfc648c095c3ba3278c4e99b.png

void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
  free(pos);
}


代码执行:

53ab2f8b0cff416ea8cfd5627761dc74.png

LTErase实现尾删:
//LTPopBack链表尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
    assert(!LTEmpty(phead));
  LTErase(phead->prev);
}


LTErase实现头删
//LTPopFront链表头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->next);
}


12.求链表的长度函数

简单来说就是计算链表的结点个数

void TestList8()//求链表长度
{
  LTNode* plist = LTInit();
  size_t count = LTSize(plist);
  printf("当前链表长度为:%zu\n", count);
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  count = LTSize(plist);
  printf("当前链表长度为%zu", count);
}


代码执行：

20d83969ce54430989898dee0ad3221f.png

13.释放链表动态申请的空间

函数代码:

void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}


Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化和尾插
void TestList1()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
}
//头插
void TestList2()
{
  LTNode* plist = LTInit();
  LTPushFront(plist, 1);
  LTPushFront(plist, 2);
  LTPushFront(plist, 3);
  LTPushFront(plist, 4);
  LTPrint(plist);
}
//尾删
void TestList3()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
}
//头删
void TestList4()
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
}
void TestList5()//查找/修改
{
  LTNode* plist = LTInit();
  printf("尾插:");
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  printf("请输入你要找的值:");
  int n = 0;
  scanf("%d", &n);
  LTNode* find = STFind(plist,n);
  if (find)
  {
    printf("找到了\n");
    find->data = 300;
    printf("修改节点的值成功\n");
    LTPrint(plist);
  } 
  else
  {
    printf("没找到\n");
  }
}
void TestList6()//pos之前插入值
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  LTNode* pos = STFind(plist, 3);
  if (pos)
  {
    LTInsert( pos, 30);
  }
  LTPrint(plist);
}
void TestList7()//删除pos位置的值
{
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  LTNode* pos = STFind(plist, 3);
  if (pos)
  {
    LTErase(pos);
  }
  LTPrint(plist);
}
void TestList8()//求链表长度
{
  LTNode* plist = LTInit();
  size_t count = LTSize(plist);
  printf("当前链表长度为:%zu\n", count);
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPrint(plist);
  count = LTSize(plist);
  printf("当前链表长度为%zu", count);
}
int main()
{
  //TestList1();//初始化和尾插
  TestList2();//头插
  //TestList3();//尾删
  //TestList4();//头删
  //TestList5();//查找、修改
  //TestList6();pos之前插入值
  //TestList7();//删除pos位置的值
  //TestList8();//求链表长度
}


List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDataType data;
}LTNode;
LTNode*LTInit();
void LTPrint(LTNode* phead);
//判断链表是否为NULL
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* STFind(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
//计算链表节点个数
size_t LTSize(LTNode* phead);
//释放链表
void LTErase(LTNode* pos);


List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}
LTNode* LTInit()
{
  LTNode* guard = BuyLTNode(-1);
  guard->next = guard;
  guard->prev = guard;
  return guard;
}
//打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  printf("guard<==>");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d<==>", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}
//尾插
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  
//  LTNode* tail = phead->prev;
//  LTNode* newnode = BuyLTNode(x);
//  
//  tail->next= newnode;
//  newnode->prev = tail;
//  newnode->next = phead;
//  phead->prev = newnode;
//}
//头插
//方法一,不需要创建变量
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  LTNode* newnode = BuyLTNode(x);
//
//  newnode->next = phead->next;//把头结点后面的d1的地址赋值给新结点的next
//  phead->next->prev = newnode;//d1指向新节点
//  
//  phead->next = newnode;//改变头节点的next，让它指向新结点
//  newnode->prev = phead;//新结点的prev指向phead头插完毕.
//}
//方法二创建一个first变量
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  LTNode* newnode = BuyLTNode(x);
//  LTNode* first = phead->next;
//
//  phead->next = newnode;
//  newnode->next = first;
//  newnode->prev = phead;
//  first->prev = newnode;
//
//}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail= phead->prev;
  LTNode* tailPrev=tail->prev ;
  free(tail); //先删除再链接
  tailPrev->next = phead;
  phead->prev = tailPrev;
}
LTNode* STFind(LTNode* phead, LTDataType x)
{
  //assert(phead);
  LTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
    if (cur->data == phead->data)
    {
      break;
    }
  }
  return NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* first = phead->next;
  LTNode* second = phead->next->next;
  phead->next = second;
  second->prev = phead;  
  free(first);
}
void LTInsert(LTNode* pos,LTDataType x)//输入要删除的数的位置即可
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* prev = pos->prev;
  prev->next = newnode;
  newnode->next = pos;
  newnode->prev = prev;
  pos->prev = newnode;
}
//INsert尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead, x);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead->next);
  LTInsert(phead->next, x);
}
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
  free(pos);
}
//LTPopBack链表尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->prev);
}
//LTPopFront链表头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->next);
}
size_t LTSize(LTNode* phead)
{
  assert(phead);
  size_t n = 0; 
  LTNode * cur = phead->next;
  while (cur!=phead)
  {
    n++;
    cur = cur->next;
  }
  return n;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}


  本篇完毕，如有错误，欢迎大佬指正！✨

关键词：
数据结构链表
数据结构入门
数据结构双向循环链表
数据结构双向循环链表入门必备知识
数据结构链表入门
Dream_Chaser～
目录
相关文章
老秦包你会
|
1天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
21 0
Bigcrab__
|
1天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
Bigcrab__
11 0
菜菜的后端私房菜
|
1天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
菜菜的后端私房菜
6 0
天玑y
|
1天前
|
C++
数据结构（双链表
数据结构（双链表
天玑y
9 1
Yawesh
|
1天前
|
存储 数据库 C++
高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
Yawesh
15 0
小蜗牛~向前冲
|
1天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1）
[数据结构]~双向+循环链表从(0~1）
小蜗牛~向前冲
17 2
老秦包你会
|
1天前
|
存储
数据结构第三课 -----线性表之双向链表
数据结构第三课 -----线性表之双向链表
老秦包你会
12 0
皮牙子抓饭
|
1天前
|
存储 机器学习/深度学习 算法
数据结构算法入门指南：常见算法解析与应用
【4月更文挑战第28天】
皮牙子抓饭
9 0
小谢在努力
|
1天前
|
存储 Java
数据结构奇妙旅程之顺序表和链表
数据结构奇妙旅程之顺序表和链表
小谢在努力
6 0
请回答1024
|
1天前
|
存储 NoSQL 算法
Redis入门到通关之Redis数据结构-Hash篇
Redis入门到通关之Redis数据结构-Hash篇
请回答1024
23 1

热门文章

最新文章

  • 1
    python学习-函数模块，数据结构，字符串和列表（下）
  • 2
    Redis入门到通关之Redis数据结构-String篇
  • 3
    Redis入门到通关之Redis数据结构-List篇
  • 4
    Redis入门到通关之数据结构解析-SkipList
  • 5
    Pandas数据结构详解：Series与DataFrame的奥秘
  • 6
    Redis入门到通关之Redis数据结构-Hash篇
  • 7
    二叉树和数据结构
  • 8
    数据结构---B+Tree
  • 9
    Redis入门到通关之数据结构解析-Dict
  • 10
    单链表——“数据结构与算法”
  • 1
    Redis入门到通关之Redis数据结构-Hash篇
    23
  • 2
    Redis入门到通关之Redis数据结构-List篇
    33
  • 3
    Redis入门到通关之Redis数据结构-String篇
    35
  • 4
    Redis入门到通关之数据结构解析-SkipList
    30
  • 5
    Redis入门到通关之数据结构解析-动态字符串SDS
    18
  • 6
    Redis入门到通关之数据结构解析-Dict
    20
  • 7
    Java并发编程中的高效数据结构：ConcurrentHashMap解析
    14
  • 8
    数据结构开篇（普普通通浅浅聊数据结构）什么是数据结构 、什么是算法、重要性、如何学好数据结构呢
    16
  • 9
    数据结构基础：双链表结构、实现
    16
  • 10
    C语言进阶：顺序表（数据结构基础） （以通讯录项目为代码练习）
    15

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考