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

【数据结构初阶】双链表

article 2024/9/20 1:40:39

双链表

    • 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.kler.cn/news/135655.html

相关文章：

  • 多因素方差分析(Multi-way Analysis of Variance) R实现
  • 栈和队列知识点+例题
  • 中国农业开启加速度，龙江农业迎来黄金期
  • 二阶段提交
  • thonny的汉字编码是UTF-8，如何才能转为GB2312?
  • LeetCode - 622. 设计循环队列（C语言，顺序存储结构，配图）
  • 逻辑漏洞（越权）
  • MySQL 的执行原理（五）
  • AI 游戏工具收集
  • 设计模式（二）-创建者模式（1）-单例模式
  • uniapp Android如何授权打开系统蓝牙Bluetooth？
  • 【ES6标准入门】JavaScript中的模块Module语法的使用细节：export命令和imprt命令详细使用，超级详细！！！
  • vue统一登录
  • C# 依赖注入如何实现
  • 数据结构【DS】栈
  • 音视频项目—基于FFmpeg和SDL的音视频播放器解析（十三）
  • 二维偏序问题
  • 从傅里叶变换，到短时傅里叶变换，再到小波分析（CWT），看这一篇就够了（附MATLAB傻瓜式实现代码）
  • 多维时序 | MATLAB实现PSO-BiGRU-Attention粒子群优化双向门控循环单元融合注意力机制的多变量时间序列预测
  • 毕业设计ASP.NET 2368酒店信息管理系统【程序源码+文档+调试运行】
  • 腐蚀监测常用技术及作用
  • 解决word之间复制公式时，公式编辑器变成图片
  • 【算法】堆排序
  • （BMS）电池管理系统技术研究与仿真
  • Selenium安装WebDriver最新Chrome驱动(含116/117/118/119)
  • 为什么阿里推荐 LongAdder ，不推荐 AtomicLong ？？
  • 蓝桥杯每日一题2023.11.20
  • WPF Visual, UIElement, FrameworkElement, Control这些类的区别
  • 【论文阅读】基于隐蔽带宽的汽车控制网络鲁棒认证（二）
  • 力扣刷题-二叉树-二叉树最小深度