您现在的位置是：首页 > 后端

当前栏目

带头双向循环链表增删查改实现（C语言）

C语言循环链表实现增删双向查改带头

2023-06-13 09:17:43 时间

带头双向循环链表

结点结构与头结点的创建

创建两个源文件和一个头文件

test.c linked_list.c linked_list.h

带头双向循环链表，那么，结点的结构就要有两个指针域，分别指向前一个结点和后一个结点。

整个链表大概就是这样一个结构。

#define TYPE int 
typedef struct Linked_list//结点的内部结构
{
	struct Linked_list* prev;//前指针
	struct Linked_list* next;//后指针
	TYPE data;
}LL;

创建头结点时要注意，我们要的时循环结构，所以也要让头结点的前指针和后指针都指向自己才符合循环结构。（在后面的操作也是比较方便的）

LL* ListCreate()//创建头结点
{
	LL* head = (LL*)malloc(sizeof(LL));
	if (head == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	head->next = head;
	head->prev = head;
	return head;
}

头插尾插

因为有头结点的关系，就不需要判断是否是第一个结点的问题了。这里尾插就很方便了，不像之前需要遍历找尾，因为是循环链表，尾的next就是头结点。当然这里要先写一个创建新结点的函数。

//linked_list.c
LL* BuyLisNode(TYPE x)
{
	LL* newnode = (LL*)malloc(sizeof(LL));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;//因为是要链接进链表的结点，所以指向空就可以了
	newnode->prev = NULL;
	return newnode;//返回新结点的地址
}

尾插

void ListPushBack(LL* phead, TYPE x)//尾插
{
	assert(phead);
	LL* newnode = BuyLisNode(x);
	LL* tail = phead->prev;//储存尾结点
	tail->next = newnode;//让尾的next指向新节点
	newnode->prev = tail;//新结点的prev指向尾
	newnode->next = phead;//新节点的next指向头结点
	phead->prev = newnode;//头结点的prev指向新结点
}

头插

void ListPushFront(LL* phead, TYPE x)//头插
{
	assert(phead);
	LL* newnode = BuyLisNode(x);
	LL* head = phead->next;//储存头结点的下一个结点
	phead->next = newnode;//让头结点的next指向新结点
	newnode->prev = phead;//新结点的prev指向头结点
	newnode->next = head;//新结点next指向头结点的下一个结点
	head->prev = newnode;//头结点的下一个结点指向新结点
}

打印链表

这里就要遍历链表了，因为是循环结构，所以结尾就不用空指针进行判断了。

void ListPrint(LL* phead)//打印链表
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)//遍历链表，结尾是cur指向的的如果是phead就说明上一个结点就是尾
	{
		printf("%d ", cur->data);//打印
		cur = cur->next;
	}
	printf("\n");
}

头删与尾删

删除的话，我们需要写一个函数判断链表中是否还有数据，如果只剩一个头结点就不能继续删除了。

bool estimate(LL* phead)//判断是否还有数据
{
	return phead->next == phead;//这里要注意，相等返回1，不相同返回0
}

尾删删除尾结点的时候要将倒数第二个结点与头结点进行连接。

void ListPopBack(LL* phead)// 尾删
{
	assert(phead);
	assert(!estimate(phead));//判断是否还有数据，这里别忘记用!号
	LL* cur = phead->prev;//储存要删除的尾结点
	phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点
	cur->prev->next = phead;//让倒是第二个结点的next指向头结点
	free(cur);//释放
}

头删删除第一个结点也要注意判断是否还有数据和第二个结点与头结点的连接。

void ListPopFront(LL* phead)//头删
{
	assert(phead);
	assert(!estimate(phead));
	LL* cur = phead->next;//储存要删除的第一个结点
	phead->next = cur->next;//头结点的next指向第二个结点
	cur->next->prev = phead;//第二个结点的prev指向头结点
	free(cur);//释放
}

链表的查找

LL* ListFind(LL* phead, TYPE x)//查找
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;//找到返回当前地址
		}
		cur = cur->next;
	}
	return NULL;//找不到返回空指针
}

在pos的前面进行插入与删除pos位置的结点

pos是配合查找的，如果pos传错了也没办法。插入

void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入
{
	LL* cur = BuyLisNode(x);// 创建新结点
	LL* prev = pos->prev;//找到pos前面的结点
	pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系
	cur->next = pos;
	cur->prev = prev;
	prev->next = cur;
}

删除

void ListErase(LL* pos)//删除pos位置的结点
{
	LL* prev = pos->prev;//储存pos前面的结点
	LL* next = pos->next;//储存pos后面的结点
	prev->next = next;//让pos前后结点建立联系
	next->prev = prev;
	free(pos);//释放
}

销毁链表

这里注意，头结点也要释放掉。

void ListDestory(LL* phead)//销毁链表
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)//释放除了头结点以外的结点
	{
		LL* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);//释放头结点
}

完整代码

linked_list.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int TYPE;
typedef struct Linked_list//结点的内部结构
{
	struct Linked_list* prev;//前指针
	struct Linked_list* next;//后指针
	TYPE data;
}LL;

LL* ListCreate();//创建头结点
void ListPushBack(LL* phead, TYPE x);//尾插
void ListPushFront(LL* phead, TYPE x);//头插
void ListPrint(LL* phead);//打印链表
void ListPopBack(LL* phead);// 尾删
void ListPopFront(LL* phead);//头删
LL* ListFind(LL* phead, TYPE x);//查找
void ListInsert(LL* pos, TYPE x);//在pos的前面进行插入
void ListErase(LL* pos);//删除pos位置的结点
void ListDestory(LL* phead);//销毁链表

linked_list.c

#include "linked_list.h"
LL* ListCreate()//创建头结点
{
	LL* head = (LL*)malloc(sizeof(LL));
	if (head==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	head->next = head;
	head->prev = head;
	return head;
}

LL* BuyLisNode(TYPE x)//创建新结点
{
	LL* newnode = (LL*)malloc(sizeof(LL));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;//因为是链接进链表的结点，所以指向空就可以了
	newnode->prev = NULL;
	return newnode;
}

void ListPushBack(LL* phead, TYPE x)//尾插
{
	assert(phead);
	LL* newnode = BuyLisNode(x);//创建新结点
	LL* tail = phead->prev;//储存尾结点
	tail->next = newnode;//让尾的next指向新节点
	newnode->prev = tail;//新结点的prev指向尾
	newnode->next = phead;//新节点的next指向头结点
	phead->prev = newnode;//头结点的prev指向新结点
}

void ListPushFront(LL* phead, TYPE x)//头插
{
	assert(phead);
	LL* newnode = BuyLisNode(x);
	LL* head = phead->next;//储存头结点的下一个结点
	phead->next = newnode;//让头结点的next指向新结点
	newnode->prev = phead;//新结点的prev指向头结点
	newnode->next = head;//新结点next指向头结点的下一个结点
	head->prev = newnode;//头结点的下一个结点指向新结点
}
bool estimate(LL* phead)//判断是否还有数据
{
	return phead->next == phead;//这里要注意，相等返回0，不相同返回1
}
void ListPrint(LL* phead)//打印链表
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)//遍历链表
	{
		printf("%d ", cur->data);//打印
		cur = cur->next;
	}
	printf("\n");
}

void ListPopBack(LL* phead)// 尾删
{
	assert(phead);
	assert(!estimate(phead));//判断是否还有数据
	LL* cur = phead->prev;//储存要删除的尾结点
	phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点
	cur->prev->next = phead;//让倒是第二个结点的next指向头结点
	free(cur);//释放
}

void ListPopFront(LL* phead)//头删
{
	assert(phead);
	assert(!estimate(phead));
	LL* cur = phead->next;//储存要删除的第一个结点
	phead->next = cur->next;//头结点的next指向第二个结点
	cur->next->prev = phead;//第二个结点的prev指向头结点
	free(cur);//释放
}

LL* ListFind(LL* phead, TYPE x)//查找
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;//找到返回当前地址
		}
		cur = cur->next;
	}
	return NULL;//找不到返回空指针
}

void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入
{
	LL* cur = BuyLisNode(x);// 创建新结点
	LL* prev = pos->prev;//找到pos前面的结点
	pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系
	cur->next = pos;
	cur->prev = prev;
	prev->next = cur;
}

void ListErase(LL* pos)//删除pos位置的结点
{
	LL* prev = pos->prev;//储存pos前面的结点
	LL* next = pos->next;//储存pos后面的结点
	prev->next = next;//让pos前后结点建立联系
	next->prev = prev;
	free(pos);//释放
}

void ListDestory(LL* phead)//销毁链表
{
	assert(phead);
	LL* cur = phead->next;
	while (cur != phead)//释放除了头结点以外的结点
	{
		LL* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);//释放头结点
}

test.c

#include "linked_list.h"
void test()
{
	LL* head = NULL;
	head = ListCreate();//创建头结点
	ListPushBack(head, 5);//尾插
	ListPushBack(head, 7);//尾插
	ListPushFront(head, 8);//头插
	ListPushFront(head, 6);//头插
	ListPopBack(head);//尾删
	ListPopFront(head);//头删
	ListPrint(head);//打印链表

	LL* pos = ListFind(head, 5);//查找
	if (pos != NULL)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	ListInsert(pos, 3);//在pos的前面进行插入
	ListPrint(head);//打印链表

	ListErase(pos);//删除pos位置的结点
	ListPrint(head);//打印链表

	ListDestory(head);//销毁链表
	ListPrint(head);//打印链表
	
}
int main()
{
	test();
	return 0;
}

运行结果：

猜你喜欢

Linux操作系统发展简史
普京年度电话直播遭黑客攻击
自动更新网站底部 Copyright © 年份
PrototypeDate对象学习
使用jqMobi开发app基础：Toggle Switches开关按钮详解手机开发
单点登录(SSO)及实现方案
Django REST Framework-基于Oauth2的身份验证（一）
ORA-02788: Unable to find kernel process pointer in async process array ORACLE 报错故障修复远程处理
Linux系统yum命令的使用语法及详细用法
java作用域-翻译：⚡⛓️可视化的 JavaScript作用域（链）
Oracle 11g安装指南：轻松安装，快乐畅玩（oracle11g安装教程）
Oracle中使用RAW类型的字段（oracle的raw字段）
憨批的语义分割重制版5——Keras 搭建自己的Unet语义分割平台
基于vim思想开发出来的那些编辑器
React生态单元测试框架对比
数据解决Redis中 Java的过期数据问题（redisjava过期）

zl程序教程