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

【数据结构初阶】双链表

双链表

    • 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/a/135655.html

相关文章:

  • 第二天python笔记
  • wordpress实用功能A5资源网同款 隐藏下载框 支付框 需要登录才能查看隐藏的内容
  • 如何选择最适合的自闭症干预机构?
  • ctfshow-web入门-反序列化(web271-web278)
  • 权限管理练习2
  • 丹韵红墙成红毯至美背景!冠珠华脉「雍华京韵」于M essential大秀绽放京韵时尚
  • 多因素方差分析(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酒店信息管理系统【程序源码+文档+调试运行】