【数据结构】‘双向链表’冲冲冲-阿里云开发者社区

【数据结构】‘双向链表’冲冲冲

2023-10-09 48

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 文章目录构建节点初始化打印尾插尾删头插头删

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤

📃个人主页：阿然成长日记 👈点击可跳转

📆 个人专栏： 🔹数据结构与算法🔹C语言进阶

🚩 不能则学，不知则问，耻于问人，决无长进

🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录

构建节点

//构建节点
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("newnode fail");
    exit(-1);
  }
  newnode->data = x;
  return newnode;
}

初始化

我们的节点是双向循环链表

//初始化
LTNode* LTInit()
{
  LTNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

打印

//打印
void print(LTNode* phead)
{
  assert(phead);
  printf("phead<=>");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d<=>", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

尾插

思路：

代码：

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* newnode = BuyLTNode(x);
  newnode->prev = tail;
  tail->next = newnode;
  newnode->next = phead;
  phead->prev = newnode;
}

尾删

思路：

代码：

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->prev!=phead);
  LTNode* cur = phead->prev->prev;
  free(cur->next);
  cur->next = phead;
  phead->prev = cur;
}

运行结果：

头插

思路:

代码;

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyLTNode(x);
  //先改newnode节点后
  newnode->next = phead->next;
  phead->next->prev = newnode;
  //在改前
  newnode->prev = phead;
  phead->next = newnode;
}

运行结果：

头删

思路：

代码：

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* cur = phead->next->next;
  free(phead->next);
  //链接顺序不能变
  phead->next = cur;
  phead = cur->prev;
}

运行结果：

计算链表长度

//如果让哨兵节点的内容是链表长度，那么，data的数据类型必须是int型。

//链表长度
//如果让哨兵节点的内容是链表长度 ，那么，data的数据类型必须是int型。
int LTSize(LTNode* phead)
{
  int size = 0;
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

查找

pos位置插入（一般都是pos之前）

思路：

代码：

//pos位置插入（一般都是pos之前）
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* cur = pos->prev;
  //先链接newnode后
  newnode->next = pos;
  pos->prev = newnode;
  //再链接newnode前
  cur->next = newnode;
  newnode->prev = cur;
}

删除pos位置

思路: 代码：

//删除pos位置
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* posnext = pos->next;
  free(pos);
  //链接顺序不能变
  posprev->next = posnext;
  posnext->prev = posprev;
}