1. AI技术聚合首页
  2. IT

【数据结构初阶】双链表

xiaoxingxing • • IT • 阅读 45

双链表

    • 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;
}

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

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月8日
下一篇 2023年12月8日

相关推荐