当前位置： 首页 > news >正文

【数据结构初阶】双链表

news 2025/8/25 4:44:34

双链表

    • 1.双链表的实现
      • 1.1结口实现
      • 1.2申请结点
      • 1.3初始化双链表
      • 1.4打印双链表
      • 1.5尾插
      • 1.6尾删
      • 1.7头插
      • 1.8头删
      • 1.9计算大小
      • 1.10查找
      • 1.11pos位置插入
      • 1.12删除pos位置
      • 1.12删除双链表
    • 全部码源

1.双链表的实现

1.1结口实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDateType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDateType date;
}LTNode;//创造结点
LTNode* BuyLTNode(LTDateType x);//初始化双链表
LTNode* LTInit();//打印双链表
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDateType x);//尾删
void LTPopBack(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDateType x);//头删
void LTPopFront(LTNode* phead);//计算
int LTSize(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDateType x);//pos位置插入
void LTInsert(LTNode* pos, LTDateType x);//删除pos位置
void LTErase(LTNode* pos);//销毁双链表
void LTDestroy(LTNode* phead);

1.2申请结点

//创造结点
LTNode* BuyLTNode(LTDateType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->date = x;node->next = NULL;node->prev = NULL;return node;
}

1.3初始化双链表

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

1.4打印双链表

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

1.5尾插

在这里插入图片描述

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

1.6尾删

在这里插入图片描述

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

1.7头插

在这里插入图片描述

//头插
void LTPushFront(LTNode* phead, LTNode* x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

1.8头删

在这里插入图片描述

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

1.9计算大小

//计算
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}

1.10查找

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->date == x)return cur;cur = cur->next;}return NULL;
}

1.11pos位置插入

在这里插入图片描述

//在pos位置插入
void LTInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

1.12删除pos位置

在这里插入图片描述

//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posNext = pos->next;LTNode* posPrev = pos->prev;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

1.12删除双链表

//销毁双链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = cur->next;}free(phead);
}

全部码源

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDateType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDateType date;
}LTNode;//创造结点
LTNode* BuyLTNode(LTDateType x);//初始化双链表
LTNode* LTInit();//打印双链表
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDateType x);//尾删
void LTPopBack(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDateType x);//头删
void LTPopFront(LTNode* phead);//计算
int LTSize(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDateType x);//pos位置插入
void LTInsert(LTNode* pos, LTDateType x);//删除pos位置
void LTErase(LTNode* pos);//销毁双链表
void LTDestroy(LTNode* phead);

List.c

#include"List.h"//创造结点
LTNode* BuyLTNode(LTDateType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->date = x;node->next = NULL;node->prev = NULL;return node;
}//初始化双链表
LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}//打印双链表
void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->date);cur = cur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDateType 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->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}//头插
void LTPushFront(LTNode* phead, LTNode* x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}//计算
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->date == x)return cur;cur = cur->next;}return NULL;
}//在pos位置插入
void LTInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posNext = pos->next;LTNode* posPrev = pos->prev;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//销毁双链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = cur->next;}free(phead);
}

test.c

#include"List.h"void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 20);LTPrint(plist);
}void TestList2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTSize(plist);
}void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTNode* pos = LTFind(plist, 3);LTInsert(pos, 20);LTPrint(plist);
}void TestList4()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTNode* pos = LTFind(plist, 3);LTErase(pos);LTPrint(plist);
}int main()
{TestList4();return 0;
}

💘不知不觉，【数据结构初阶】双链表 以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!

http://www.lryc.cn/news/237527.html

相关文章：

  • Django实战：从零到一构建安全高效的Web应用
  • Docker build报错总结，版本过新大避雷！
  • spider 网页爬虫中的 AWS 实例数据获取问题及解决方案
  • flink的window和windowAll的区别
  • 【机器学习】特征工程：特征选择、数据降维、PCA
  • 短视频账号矩阵系统saas管理私信回复管理系统
  • 利用ETLCloud自动化流程实现业务系统数据快速同步至数仓
  • 学习c#的第十六天
  • 【论文阅读笔记】Deep learning for time series classification: a review
  • 如何将vscode和Linux远程链接：
  • 快速傅立叶卷积(FFC)
  • 藏头诗（C语言）
  • 适合您的智能手机的 7 款优秀手机数据恢复软件分享
  • uniapp APP下载流文件execl 并用WPS打开
  • 【Python】 Python 操作PDF文档
  • vue3-响应式核心
  • 人工智能的广泛应用与影响
  • SAP创建权限对象、角色、并分配角色
  • [uni-app]记录APP端跳转页面自动滚动到底部的bug
  • 应用软件安全编程--23避免使用不安全的操作模式
  • 国产高云FPGA：纯verilog实现视频图像缩放，提供6套Gowin工程源码和技术支持
  • python操作windows窗口，python库pygetwindow使用详解
  • 手写消息队列（基于RabbitMQ）
  • kafka本地安装报错
  • 王者荣耀游戏
  • MobaXterm如何连接CentOS7的Linux虚拟机？Redis可视化客户端工具如何连接Linux版Redis？
  • python实现炫酷的屏幕保护程序
  • java学习part06数组
  • Java 的异常体系
  • V100 GPU服务器安装CUDA教程