虫子 双链表 内核必备，基本算法，linux二次发育，项目远见

举报
虫子VV 发表于 2022/04/21 13:50:27 2022/04/21
【摘要】 双链表 双链表结构图 双链表节点 双链表初始化函数ListInit 双链表尾插函数ListPushBack 双链表打印函数ListPrint 双链表尾删函数ListPopBack 双链表头插函数ListPushFront 获得双链表节点函数BuyListNode 双链表头删函数ListPopFront 双链表查找函数ListFind 双链表插入函数ListInsert（pos之前插入因为c...

双链表

双链表结构图

image-20211028225455233

双链表节点

typedef int LTDataType;  //C++中的双链表是用list表示的

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

双链表初始化函数ListInit

//双链表初始化函数
LTNode* ListNodeInit()
{
	//创建一个双链表哨兵位头结点  不存储有效数据  循环
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

image-20211028230625085

双链表尾插函数ListPushBack

image-20211029001350843

//双链表尾插函数
void ListNodePushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//实际上phead永远也不可能是NULL
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

双链表打印函数ListPrint

image-20211029070928255

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

双链表尾删函数ListPopBack

image-20211029072838324

//双链表尾删函数
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

双链表头插函数ListPushFront

image-20211029080341212

//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中间插一个节点
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

==既然我们头插尾插都遇到了添加节点，所以我们把添加节点的部分抽离出来重新封装一下==

获得双链表节点函数BuyListNode

image-20211029191337400

//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

双链表头删函数ListPopFront

image-20211029193358759

//双链表头删函数
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

双链表查找函数ListFind

==这个一般是和插入，删除配合使用==

//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

双链表插入函数ListInsert（pos之前插入因为c++中就是之前插入的）

image-20211029204212625

//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}

双链表删除函数ListErase（删除pos）

image-20211029205627363

//双链表删除函数
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}

双链表销毁函数ListDestroy(实际上我在这里写报错了，前面一个函数有bug，但是找到了)

//双链表销毁函数
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

代码

DoubleList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;  //C++中的双链表是用list表示的

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//双链表初始化函数
extern LTNode* ListInit();
//双链表销毁函数
extern void ListDestroy(LTNode* phead);
//双链表尾插函数
extern void ListPushBack(LTNode* phead, LTDataType x);
//双链表打印函数
extern void ListPrint(LTNode* phead);
//双链表尾删函数
extern void ListPopBack(LTNode* phead);
//获得双链表节点函数
extern LTNode* BuyListNode(LTDataType x);
//双链表头插函数
extern void ListPushFront(LTNode* phead, LTDataType x);
//双链表头删函数
extern void ListPopFront(LTNode* phead);
//双链表查找函数
extern LTNode* ListFind(LTNode* phead, LTDataType x);
//双链表插入函数
extern void ListInsert(LTNode* pos, LTDataType x);
//双链表删除函数
extern void ListErase(LTNode* pos);

DoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "DoubleList.h"

//双链表初始化函数
LTNode* ListInit()
{
	//创建一个双链表哨兵位头结点  不存储有效数据  循环
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//双链表尾插函数
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//实际上phead永远也不可能是NULL
	LTNode* tail = phead->prev;
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//双链表打印函数
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//双链表尾删函数
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中间插一个节点
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

//双链表头删函数
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}
//双链表删除函数
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}
//双链表销毁函数
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"
void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPrint(plist);
	LTNode* p1 = ListFind(plist, 10);
	if (p1)
	{
		ListInsert(p1, 100);
	}
	ListPrint(plist);
	LTNode* p2 = ListFind(plist, 20);
	if (p2)
	{
		ListErase(p2);
	}
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}


int main()
{
	TestList1();
	return 0;
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入