C语言中带头双向循环链表基本操作的实现详解

2022-12-02 14:03 开发作者：蜗牛牛啊

一、概念与结构

无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表，虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。

二、基本操作的实现

1.创建结点

LTNode* BuyListNode(ListDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    newnode->val = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

2.初始化链表

void ListInit(LTNode** pphead)//初始化
{
    *pphead = (LTNode*)malloc(sizeof(LTNode));
    *pphead = BuyListNode(-1);
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//    LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//    phead->next = phead;
//    phead->prev = phead;
//    return phead;
//}

初始化链表有两种方式，一种是有返回类型（注释部分），另一种是在初始化函数中给结构体开辟空间（不过注意参数要为二级指针）。因为是带头结点的循环链表，所以prev和next指针都指向自己。

3.打印链表

void ListPrint(LTNode* phead)//打印
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->val);
       python cur = cur->next;
    }
    printf("\n");
}

注意while循环的结束条件，保证能够打印链表中的所有有效值。要对头结点进行assert判断，不能为空。

4.尾插

void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    newnode->next = tail->next;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;
    //ListInsert(phead, x);
}

5.尾删

void ListPopBack(LTNode* phead)//尾删
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* prevnode = phead->prev;
    prevnode->prev->next = phead;
    phead->prev = prevnode->prev;
    free(prevnode);
    //ListErase(phead->prev);
}

尾删时要注意判断phead->next != phead，不能删除头结点，同时记得要free(prevnode)释放删除后的空间。

6.头插

void ListPushFront(LTNode* phead, ListDataType x)//头插
{
    assert(phead);
    LTNode* tail = phead->next;
    LTNode* newnode = BuyListNode(x);
    tail->prev = newnode;
    newnode->next = tail;
    newnode->prev = phead;
    phead->next = newnode;
    //ListInsert(phead->next,x);
}

7.头删

void ListPopFront(LTNode* phead)//头删
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* tail = phead->next;
    phead->next = tail->next;
    tail->next->prev = phead;
    //ListErase(phead->next);
}

8.查找某个数并返回其指针

LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->val == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

9.在某个位置之前插入

void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = pos->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = pos;
    pos->prev = newnode;
}

10.删除某个位置

void ListErase(LTNode* pos)//删除pos位置
{
    assert(pos);
    LTNode* prevnode = pos->prev;
    LTNode* nextnode = pos->next;
    free(pos);
    prevnode->next = nextnode;
    nextnode->prev = prevnode;
    /*pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);*/
}

11.判断链表是否为空

boo编程客栈l ListEmpty(LTNode* phead)//判断是否为空,如果是空，返回true
{
    assert(phead);
    return phead->next == phead;
}

12.计算链表中有效值的个数

size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
    assert(phead);
    size_t size = 0;
    LTNode* tail = phead->next;
    while (tail != phead)
    {
        size++;
        tail = tail->next;
    }
    return size;
}

13.销毁链表

void ListDestroy(LTNode* phead)//销毁链表 
{
    assert(phead);
    LTNode* tail = phead->next;
    while (tail != phead)
    {
        LTNode* nextnode = tail->next;
        free(tail);
        tail = nextnode;
    }
    free(phead);
}

销毁链表时要注意要保证每个结点都释放，同时最后也要将头结点释放free(phead)。

三、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int ListDataType;
typedef struct ListNode {
	ListDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
LTNode* BuyListNode(ListDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
void ListInit(LTNode** pphead)//初始化
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	*pphead = BuyListNode(-1);
	(*pphead)->next = *pphead;开发者_JAVA开发
	(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//	LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//	phead->next = phead;
//	phead->prev = phead;
//	return phead;
//}

void ListPrint(LTNode* phead)//打印
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;
	//ListInsert(phead, x);
}
void ListPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* prevnode = phead->prev;
	prevnode->prev->next = phead;
	phead->prev = prevnode->prev;
	free(prevnode);
	//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, ListDataType x)//头插
{
	assert(phead);
	LTNode* tail = phead->next;
	LTNode* newnode = BuyListNode(x);
	tail->prev = newnode;
	newnode->next = tail;
	newnode->prev = phead;
	phead->next = newnode;
	//ListInsert(phead->next,x);
}
void ListPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->next;
	phead->next = tail->next;
	tail->next->prev = phead;
	//ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = pos->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(LTNode* pos)//删除pos位置
{
	assert(pos);
	LTNode* prevnode = pos->prev;
	LTNode* nextnode = pos->next;
	free(pos);
	prevnode->next = nextnode;
	nextnode->prev = prevnode;
	/*pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);*/
}
bool ListEmpty(LTNode* phead)//判断是否为空,如果是空，返回true
{
	assert(phead);
	return phead->next == phead;
}
size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
	assert(phead);
	size_t size = 0;
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		size++;
		tail = tail->next;
	}
	return size;
}
void ListDestroy(LTNode* phead)//销毁链表 
{
	assert(phead);
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		LTNode* nextnode = tail->next;
		free(tail);
		tail = nextnode;
	}
	free(phead);
}
void TestList()
{
	//LTNode* plist = ListInit(&plist);
	LTNode* plist = NULL;
	ListInit(&plist);
	ListPushBack(plist, 100);
	ListPushBack(plist, 200);
	ListPushBack(androidplist, 300);
	ListPushBack(plist编程客栈, 400);
	ListPushBack(plist, 500);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 1000);
	ListPushFront(plist, 2000);
	ListPushFront(plist, 3000);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	LTNode* pos = ListFind(plist, 1000);
	if (pos != NULL)
	{
		ListInsert(pos, 500);
		ListErase(pos);
	}
	ListPrint(plist);
	if (!ListEmpty(plist))
		printf("%d\n", ListSize(plist));
}
int main()
{
	TestList();
	return 0;
}

以上就是C语言中带头双向循环链表基本操作的实现详解的详细内容，更多关于C语言带头双向循环链表的资料请关注我们其它相关文章！

继续阅读：C语言双向循环链表 C语言带头双向循环链表 C语言循环链表

C语言中带头双向循环链表基本操作的实现详解

目录

一、概念与结构

二、基本操作的实现

1.创建结点

2.初始化链表

3.打印链表

4.尾插

5.尾删

6.头插

7.头删

8.查找某个数并返回其指针

9.在某个位置之前插入

10.删除某个位置

11.判断链表是否为空

12.计算链表中有效值的个数

13.销毁链表

三、测试代码

更多精彩内容

精彩评论

最新开发

SpringBoot整合Liquibase实现对数据库管理和迁移

java8升级java21方法步骤(完整pom文件升级及代码修改)

javacv ffmpeg使用原生ffmpeg命令方式

golang进行xml文件解析的操作方法

如何使用go实现创建WebSocket服务器

开发排行榜

springboot后端存储富文本内容的思路与步骤(含图片内容)

PyCharm运行python测试,报错“没有发现测试”/“空套件”的解决

return base64.b64encode(b).decode(

基于C语言实现钻石棋游戏的示例代码

Sublime Text 3解决中文乱码问题（实测可用）