首页 > 其他分享 >【链表】双向循环带头链表-增-删-查(C语言)

【链表】双向循环带头链表-增-删-查(C语言)

时间：2022-11-17 21:39:14浏览次数：41  
标签：结点 cur DBLSTNode next 链表 phead 双向 newnode C语言


我的小站——半生瓜のblog——同步更新

单链表存在的缺陷：

不能从后往前走,

找不到他的前驱,

指定位置 删除 增加 尾删 都要找前一个，时间复杂度都是O(n)

针对上面的这些缺陷的解决方案——双向链表。

双向循环带头链表

  • ​​带头双向循环链表​​
  • ​​结构体创建​​
  • ​​创建结点​​
  • ​​初始化​​
  • ​​销毁​​
  • ​​打印​​
  • ​​尾插​​
  • ​​头插​​
  • ​​头删​​
  • ​​尾删​​
  • ​​查找位置​​
  • ​​删除pos位置的值​​
  • ​​在pos前插入x​​
  • ​​返回链表的结点数量​​
  • ​​判断链表是否为空​​
  • ​​优化​​
  • ​​总结​​
  • ​​全部代码​​

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向、双向
  2. 带头、不带头——带哨兵位的头结点，这个结点不存储有效数据，好处是什么？尾插的判断更方便简单，带头就不需要二级指针了，（带头结点，不需要改变穿过来的指针，也就是意味着不需要传二级指针了。）
  3. 循环、非循环
  1. 无头单向非循环：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等，另外这种数据结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头循环双向链表，另外，这个结构虽然复杂，但是使用代码代码实现的以后会发现结构带来许多优势，实现反而简单了。

带头双向循环链表

【链表】双向循环带头链表-增-删-查(C语言)_数据结构

结构体创建

typedef int LSTNodeData;
typedef struct ListNode
{
  LSTNodeData data;
  struct ListNode* next;
  struct ListNode* prev;
}LSTNode;

创建结点

DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
  DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}

初始化

有个小哨兵位的头结点，并且是一个循环状态。

DBLSTNode* DBLSTInit()
{
  //用一个返回值可以 替代二级指针
  DBLSTNode* phead = DBLSTCreat(0);
  //循环
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

销毁

void DBLSTDestory(DBLSTNode* phead)
{
  //找到第一个结点
  DBLSTNode* cur = phead->next;
  while (cur !=phead)
  {
    //保存下一个结点
    DBLSTNode* curNext = cur->next;
    free(cur);
    cur = curNext;
  }
  free(phead);
}

画图有利于双向链表的理解。

【链表】双向循环带头链表-增-删-查(C语言)_指针_02

打印

void DBLSTPrint(DBLSTNode* phead)
{
  //如果链表是空的会发生错误吗?
  //不会。因为phead->next还是自己。
  DBLSTNode* cur = phead->next;//这里我容易忘记指向next
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

尾插

双向带头循环链表，结构虽然复杂了，但是更容易操作了。

这就是结构设计的优势。

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //找到尾结点
  DBLSTNode* tail = phead->prev;
  //插入-链接
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

头插

如果插入的时候链表是空的同样不会有影响。

有first这几个指针先动谁都行，没有first也可以，就是会有顺序要求。

示例：

【链表】双向循环带头链表-增-删-查(C语言)_数据结构_03

newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //拿到第一个结点
  DBLSTNode* first = phead->next;
  //插入-链接
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}

头删

void DBLSTPopFront(DBLSTNode* phead)
{
  //保存第一个和第二个结点
  DBLSTNode* first = phead->next;
  DBLSTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
  first = NULL;
}

尾删

void DBLSTPopBack(DBLSTNode* phead)
{
  //找到最后的一个结点
  DBLSTNode* tail = phead->prev;
  //找到最后一个结点的前一个结点
  DBLSTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
  tail = NULL;
}

查找位置

DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
  //从第一个结点开始往下寻找，找到返回结点
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

使用：

DBLSTNode* pos = DBLSTFind(phead,x);
if(pos)
{
  printf("找到了");
}
else
{
  printf("没找到");
}

删除pos位置的值

void DBLSTErase(DBLSTNode* pos)
{
  //找到pos的前一个
  DBLSTNode* posPrev = pos->prev;
  //找到pos的后一个
  DBLSTNode* posNext = pos->next;
  //链接pos的前一个和pos的后一个
  posPrev->next = posNext;
  posNext->prev = posPrev;
  //释放pos
  free(pos);
  pos = NULL;
}

在pos前插入x

void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
  //知道pos前的一个结点
  DBLSTNode* posPrev = pos->prev;
  //创建新的结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //将新的结点插入
  newnode->data = x;
  newnode->prev = posPrev;
  posPrev->next = newnode;
  newnode->next = pos;
  pos->prev = newnode;
}

返回链表的结点数量

int DBLSTSize(DBLSTNode* phead)
{
  //其实就是遍历一遍，找一个计数的
  int count = 0;
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    count++;
    cur = cur->next;
  }
  return count;
}

判断链表是否为空

bool DBLSTEmpty(DBLSTNode* phead)
{
  //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
  DBLSTNode* cur = phead->next;
  if (phead == cur)
  {
    //空
    return true;
  }
  else
  {
    //不为空
    return false;
  }
}

优化

为了更快的实现一个双向循环的带头链表，我们可以直接利用Insert和Erase。

如果Erase的pos位置是第一个结点，那就代表着头删，如图：

【链表】双向循环带头链表-增-删-查(C语言)_链表_04


所以头删还可以这样写：

void DBLSTPopFront(DBLSTNode* phead)
{
    DBLSTErase(phead->next);
}

尾删同理：

void DBLSTPopBack(DBLSTNode* phead)
{
  DBLSTErase(phead->prev);
}

头插：

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  DBLSTInsert(phead->next,x);
}

尾插：

其实就是插到头结点phead的前面。

【链表】双向循环带头链表-增-删-查(C语言)_链表_05

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  DBLSTInsert(phead, x);
}

总结

带头双向循环链表，任意位置插入和删除数据，时间复杂度都是O(1)。

查找最优的结构不是这个，查找就得遍历，时间复杂度还是O(N)。

查找的最优结构有三种：

  • 平衡搜索树（AVL树和红黑树）
  • 哈希表
  • B树 & B+树系列 (数据库底层核心引擎)

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DoubleListDataType;
typedef struct DoubleListNode
{
  DoubleListDataType data;
  struct DoubleListNode* next;
  struct DoubleListNode* prev;
}DBLSTNode;
//创建结点
DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
  DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//初始化
DBLSTNode* DBLSTInit()
{
  //用一个返回值可以 替代二级指针
  DBLSTNode* phead = DBLSTCreat(0);
  //循环
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//销毁链表
void DBLSTDestory(DBLSTNode* phead)
{
  //找到第一个结点
  DBLSTNode* cur = phead->next;
  while (cur !=phead)
  {
    //保存下一个结点
    DBLSTNode* curNext = cur->next;
    free(cur);
    cur = curNext;
  }
  free(phead);
}
//打印结点
void DBLSTPrint(DBLSTNode* phead)
{
  //如果链表是空的会发生错误吗?
  //不会。因为phead->next还是自己。
  DBLSTNode* cur = phead->next;//这里我容易忘记指向next
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//尾插
void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //找到尾结点
  DBLSTNode* tail = phead->prev;
  //插入-链接
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
  //或者
  //DBLSTInsert(phead, x);
}
//头插
void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
  //创建新结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //拿到第一个结点
  DBLSTNode* first = phead->next;
  //插入-链接
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
  //或者
  //DBLSTInsert(phead->next,x);
}
//头删
void DBLSTPopFront(DBLSTNode* phead)
{
  //保存第一个和第二个结点
  DBLSTNode* first = phead->next;
  DBLSTNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
  first = NULL;
  /或者
  //DBLSTErase(phead->next);
}
//尾删
void DBLSTPopBack(DBLSTNode* phead)
{
  //找到最后的一个结点
  DBLSTNode* tail = phead->prev;
  //找到最后一个结点的前一个结点
  DBLSTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
  tail = NULL;
  //或者
  //DBLSTErase(phead->prev);
}
//查找位置
DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
  //从第一个结点开始往下寻找，找到返回结点
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//删除pos位置的值
void DBLSTErase(DBLSTNode* pos)
{
  //找到pos的前一个
  DBLSTNode* posPrev = pos->prev;
  //找到pos的后一个
  DBLSTNode* posNext = pos->next;
  //链接pos的前一个和pos的后一个
  posPrev->next = posNext;
  posNext->prev = posPrev;
  //释放pos
  free(pos);
  pos = NULL;
}
//在pos前插入x
void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
  //知道pos前的一个结点
  DBLSTNode* posPrev = pos->prev;
  //创建新的结点
  DBLSTNode* newnode = DBLSTCreat(x);
  //将新的结点插入
  newnode->data = x;
  newnode->prev = posPrev;
  posPrev->next = newnode;
  newnode->next = pos;
  pos->prev = newnode;
}
//返回链表的结点数量
int DBLSTSize(DBLSTNode* phead)
{
  //其实就是遍历一遍，找一个计数的
  int count = 0;
  DBLSTNode* cur = phead->next;
  while (cur != phead)
  {
    count++;
    cur = cur->next;
  }
  return count;
}
//判断链表是否为空
bool DBLSTEmpty(DBLSTNode* phead)
{
  //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
  DBLSTNode* cur = phead->next;
  if (phead == cur)
  {
    //空
    return true;
  }
  else
  {
    //不为空
    return false;
  }
}
void Test1()
{
  DBLSTNode* phead = DBLSTInit();
  DBLSTPushBack(phead, 1);
  DBLSTPushBack(phead, 2);
  DBLSTPushBack(phead, 3);
  DBLSTPushBack(phead, 4);
  DBLSTPushFront(phead, 0);
  DBLSTPrint(phead);
  //DBLSTNode* pos = DBLSTFind(phead, 3);
  //if (pos)
  //{
  //  DBLSTErase(pos);
  //}
  DBLSTPrint(phead);
  int Count = DBLSTSize(phead);
  printf("%d", Count);
  DBLSTEmpty(phead);
  if (DBLSTEmpty(phead) == 0)
  {
    printf("不为空\n");
  }
}

int main(void)
{
  Test1();
  return 0;
}


标签：结点,cur,DBLSTNode,next,链表,phead,双向,newnode,C语言
From： https://blog.51cto.com/u_15333750/5866179

相关文章

  • 【链表】单链表-增-删-查(C语言)
    我的小站——半生瓜のblog单链表​​结构体定义​​​​打印​​​​创建结点​​​​尾插​​​​头插​​​​尾删​​​​头删​​​​查找​​​​在指定位置前插入某个......
  • 【线性表】之顺序表(C语言)
    【线性表】之顺序表​​线性表​​​​顺序表​​​​结构定义​​​​初始化​​​​销毁​​​​打印​​​​扩展空间​​​​尾插​​​​头插​​​​尾删​​​​头删......
  • LeetCode刷题(4)【移除元素&合并两个有序数组】(C语言)(含图解)
    移除元素典型双指针玩法。27.移除元素-力扣（LeetCode）(leetcode-cn.com)我们都会想到这样的解法：从前面依次往后推，是val就将该数据后面的元素依次覆盖上来，但是这样的时间复......
  • LeetCode刷题(5)【链表】【环形链表II】(C语言)
    环形链表I​​LeetCode刷题(3)【链表】【环形链表】&扩展_半生瓜のblog-CSDN博客​​环形链表II142.环形链表II-力扣（LeetCode）(leetcode-cn.com)这个题写起来不难，但是证......
  • 【线性表】之栈(C语言)
    栈​​回顾​​​​栈​​​​结构定义​​​​初始化​​​​销毁​​​​入栈​​​​出栈​​​​返回栈顶元素​​​​返回栈中元素个数​​​​判断栈是否为空​​​​......
  • 【线性表】之队列(C语言)
    队列​​队列的概念​​​​结构定义​​​​初始化​​​​销毁​​​​队尾入​​​​队头出​​​​队头出​​​​队头数据​​​​队尾数据​​​​是否为空​​​​返......
  • LeetCode刷题(7)【栈&队列】用队列实现栈(C语言)
    用队列实现栈225.用队列实现栈-力扣（LeetCode）(leetcode-cn.com)目的：用队列实现栈，从先进先出——>先进后出，1234这四个数据依次从队列1的队尾进入，要让4先出，一个队列是无法......
  • LeetCode刷题(2)【链表】【合链表&链表的中间结点】(C语言)
    我的小站——半生瓜のblog快慢指针问题：思路：定义一个快指针和一个慢指针，快指针走到结束的时候，慢指针刚好走到一半。链表的中间结点。876.链表的中间结点-力扣（LeetCode）(le......
  • LeetCode刷题(3)【链表】【环形链表】&扩展(C语言)
    我的小站——半生瓜のblog环形链表141.环形链表-力扣（LeetCode）(leetcode-cn.com)什么是链表带环：链表的最后一个元素不指向空而指向前面的某个结点。思路：快慢指针，慢指针走......
  • C语言二级错题积累(4)
    在栈中，栈项指针的动态变化决定栈中元素的个数。详细设计的人物是为软件结构体中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。扇......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99