【数据结构】带头双向循环链表（小白入门必备知识）(下）-阿里云开发者社区

7.链表尾删节点

图解:

当链表不止一个节点时:

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

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

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

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;
}

代码执行:

8.链表头删节点

链表不止一个结点时:

图解:

数字代表顺序

链表为一个结点时:

数字代表顺序

函数代码:

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);
}

代码执行:

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;
}

代码执行:

找到了:

找不到:

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

图解:

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;
}

代码执行:

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位置处删除此节点

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

代码执行:

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);
}

代码执行：

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);
}

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

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

7.链表尾删节点

8.链表头删节点

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

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

LTInsert实现尾插操作:

LTInsert实现头插操作:

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

LTErase实现尾删:

LTErase实现头删

12.求链表的长度函数

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

Test.c

List.h

List.c

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

7.链表尾删节点

8.链表头删节点

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

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

LTInsert实现尾插操作:

LTInsert实现头插操作:

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

LTErase实现尾删:

LTErase实现头删

12.求链表的长度函数

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

Test.c

List.h

List.c

热门文章

最新文章

相关课程

相关电子书