当前位置：网站首页>Addition, deletion, search and modification of doubly linked list

Addition, deletion, search and modification of doubly linked list

2022-08-07 08:24:00 【VisionaryHS】

目录

 There must be three elements in the struct type：1、指向前一个节点的指针prev.2、存储的数据val.3、指向后一个节点的指针next.Another point to note is that：头节点head和尾结点tail的关系,head->prev=tail,tail->next=head.

1.两个typedef,做好基础工作

2.Each function that needs to be defined

3.LTDinitDetails of the initialization function

4.BuyListNode申请空间函数

5.ListInsertInsert function function details（默认尾插）

 6.ListEraseRemove function details

7.About the head plug and tail plug,头删尾删

8.ListFind查找函数

9.ListDestory销毁函数

10.ListPrint打印函数

11.Complete program plus run

  •  There must be three elements in the struct type：1、指向前一个节点的指针prev.2、存储的数据val.3、指向后一个节点的指针next.Another point to note is that：头节点head和尾结点tail的关系,head->prev=tail,tail->next=head.

If a doubly linked list has only the head nodehead那么他的head->next=head;head->prev=head;

1.两个typedef,做好基础工作

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

It is convenient to modify the data type and simplify writing code later.

2.Each function that needs to be defined

LTNode* LTDinit();//初始化双向链表
LTNode* BuyListNode(LTDataType x);//申请新的节点
void ListPrint(LTNode* phead);//打印双向链表
void ListInsert(LTNode* pos, LTDataType x);//在任意位置插入
void ListPushBack(LTNode* phead, LTDataType x);//尾部插入
void ListPushFront(LTNode* phead, LTDataType x);//头部插入
void ListErase(LTNode* pos);//删除数据
void ListPopBack(LTNode* phead);//尾部删除
void ListPopFront(LTNode* phead);//头部删除
LTNode* ListFind(LTNode* phead, LTDataType x);//查找
void ListDestory(LTNode* phead);//销毁双向链表

3.LTDinitDetails of the initialization function

LTNode* LTDinit()
{
	LTNode* guard = NULL;//创建哨兵位节点,方便尾插
	guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail\n");
		exit;//If the development is successful, continue,失败则退出程序
	}
	else
	{
		guard->next = guard;
		guard->prev = guard;
	}
	return guard;
}

There is a sentinel bit node to facilitate subsequent insertion,Of course, you also need to pay attention to the sentinel position when destroying the doubly linked list

4.BuyListNode申请空间函数

Parameters are datax,The return value is the address of the newly opened space,After finding the address, you can easily insert the operation

LTNode* BuyListNode(LTDataType x)
{
	LTNode* cur = NULL;
	cur = (LTNode*)malloc(sizeof(LTNode));//mallocBe sure to check afterward
	if (cur == NULL)
	{
		perror("malloc fail\n");
	}
	cur->next = NULL;
	cur->prev = NULL;
	cur->data = x;
	return cur;
}

5.ListInsertInsert function function details（默认尾插）

The first parameter is the address of the insertion location,The second parameter is the data to be inserted

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* new =BuyListNode(x);
	if (new == NULL)
	{
		perror("malloc fail");
	}
	LTNode* next = pos->next;
	new->next = next;
	new->prev = pos;
	pos->next = new;
	next->prev = new;
}

 6.ListEraseRemove function details

需要传参pos,tell the location,删除数据,and relink the linked list

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;//记录pos前的数据,方便在posRelink after location data is destroyed
	LTNode* next = pos->next;//记录pos后的数据,方便在posRelink after location data is destroyed
	LTNode* cur = pos;//创建一个curThe new pointer is usedfree空间
	prev->next = next;
	next->prev = prev;
	free(cur);
}

The effect diagram of the function is as follows

7.About the head plug and tail plug,头删尾删

Just plug it inListInsert函数的特殊情况,Insert head and tail;

同理,Just delete the head and tailListErase函数的特殊情况,Delete at the head and tail;

So you can take advantage of these two already existing functions,You only need to pass in the address of the head and tail

void ListPopBack(LTNode* phead)//尾删
{
	assert(phead);
	LTNode* cur = phead->prev;
	ListErase(phead->prev);
	free(cur);
	cur = NULL;
}
void ListPopFront(LTNode* phead)//头删
{
	assert(phead);
	LTNode* cur = phead;
	ListErase(phead);
	free(cur);
	cur = NULL;
}
void ListPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);
	ListInsert(phead->prev, x);

}
void ListPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);
	ListInsert(phead, x);

}

8.ListFind查找函数

返回值是指针,If not found, put one backNULL.

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;//将head地址赋给cur,通过cur遍历
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}//当cur==headWhen it means that the doubly linked list has been traversed once,Not found yet,It means that the given address does not exist in this list
	return NULL;
}

9.ListDestory销毁函数

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//同上,用cur从头遍历
	while (cur != phead)
	{
		LTNode* next = cur->next;//用nextRemember the original next position,Convenient to iterate after destruction
		free(cur);
		cur = next;
	}
	free(phead);//最后把pheadThe memory of the location is freed
}

10.ListPrint打印函数

to the top node,Print in sequence

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
		printf("NULL\n");
}

11.Complete program plus run

LTNode* LTDinit()
{
	LTNode* guard = NULL;
	guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail\n");
		exit;
	}
	else
	{
		guard->next = guard;
		guard->prev = guard;
	}
	return guard;
}
LTNode* BuyListNode(LTDataType x)
{
	LTNode* cur = NULL;
	cur = (LTNode*)malloc(sizeof(LTNode));//mallocBe sure to check afterward
	if (cur == NULL)
	{
		perror("malloc fail\n");
	}
	cur->next = NULL;
	cur->prev = NULL;
	cur->data = x;
	return cur;
}
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
		printf("NULL\n");
}
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->prev, x);

}
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);

}
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* new =BuyListNode(x);
	if (new == NULL)
	{
		perror("malloc fail");
	}
	LTNode* next = pos->next;
	new->next = next;
	new->prev = pos;
	pos->next = new;
	next->prev = new;
}void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	LTNode* cur = pos;
	prev->next = next;
	next->prev = prev;
	free(cur);
	cur = NULL;
}
void ListPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->prev;
	ListErase(phead->prev);
	free(cur);
	cur = NULL;
}
void ListPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	ListErase(phead);
	free(cur);
	cur = NULL;
}
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 ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

头文件如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
LTNode* LTDinit();//初始化双向链表
LTNode* BuyListNode(LTDataType x);//申请新的节点
void ListPrint(LTNode* phead);//打印双向链表
void ListInsert(LTNode* pos, LTDataType x);//在任意位置插入
void ListPushBack(LTNode* phead, LTDataType x);//尾部插入
void ListPushFront(LTNode* phead, LTDataType x);//头部插入
void ListErase(LTNode* pos);//删除数据
void ListPopBack(LTNode* phead);//尾部删除
void ListPopFront(LTNode* phead);//头部删除
LTNode* ListFind(LTNode* phead, LTDataType x);//查找
bool ListEmpty(LTNode* phead);//判断双向链表是否为空
void ListDestory(LTNode* phead);//销毁双向链表

原网站

版权声明
本文为[VisionaryHS]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/219/202208070822331133.html

边栏推荐

猜你喜欢

随机推荐