索取营销诊断书
021-80394720QQ
    您的位置：上海毫米网络优化公司 > 网站优化分享 >
    相关推荐recommended
    数据结构——双向链表（保姆级教程，包学包会）
    作者：mmseoamin日期：2024-03-04

    1.双向链表的概念

    双向链表就是带头双向循环链表

    我们在学完单链表之后，就感觉这个非常简单了，他的主要表现就是拥有头节点，链表永不为空，不需要二级指针；可以通过一个节点找到上一个或者下一个节点；头尾相连呈环状。

    他主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next就不用多说了。

    如图所示

    数据结构——双向链表（保姆级教程，包学包会）,第1张

     不多废话，直接上代码

    2.双向链表的实现

    2.1 结构设计

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

    2.2 接口总览

    实现一个双向链表的各个接口

    typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
LTNode* LTInit();
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

    注意看一下啊我们的初始化的时候，这里是不带参数的，是为什么呢？

    双向链表是带头的，有头节点，就是我们说的哨兵位，哨兵位不存储有效数据，所以链表的第一个节点就是哨兵位后面的第一个节点。

    注意：这里面我们用二级指针也可以操作，但是我们在以后的代码中二级指针太麻烦而且容易用错，所以我们直接用哨兵位的办法来解决，不需要用二级指针。

    2.3 初始化

    创建一个哨兵位，让他自己变成一个环形链表

    只需要让他自己指向自己就可以

    数据结构——双向链表（保姆级教程，包学包会）,第2张

     

    LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

     2.4 创建节点

    当我们需要插入元素是，只需要创建节点，然后直接把值存入，两个指针置为空，返回该节点的地址就可。

    LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
	
}

    2.5 尾插

    直接图片更清晰观赏，我们思路是：将tail->next的链接直接连接到newnode，然后将newnode->prev连接到tail。最后phead的prev和next连接即可。

    数据结构——双向链表（保姆级教程，包学包会）,第3张

     

    void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

    2.6 头插

    头插就是将链表上的第一个节点与哨兵位的链接断开，但是在断开之前我们一定要先保存好将要断开的data，在去改变你将要头插的newnode

    数据结构——双向链表（保姆级教程，包学包会）,第4张

    void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

     2.7 尾删

    这里我们还是一样的要找到tail前一个节点tailprev，然后直接释放掉尾节点就好

    这里面注意一下，要是只有哨兵位就不能删除

    数据结构——双向链表（保姆级教程，包学包会）,第5张

     

    void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;
}

    2.8 头删

    对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。

    数据结构——双向链表（保姆级教程，包学包会）,第6张

     

    void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);
	firstnext->prev = phead;
	phead->next = firstnext;
}

    2.9 查找

    对于 双向链表 来说，它是没有指向NULL的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 ! = phead，这个条件就表示，已经遍历过一遍链表了

    LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

    2.10 在pos之前插入

    通过 pos 的 prev 找到 pos 位置的上一个节点 posprev ，然后改变 posprev 和 新节点 newnode  之间的链接和 newnode 和 pos 之间的链接

    数据结构——双向链表（保姆级教程，包学包会）,第7张

     

    void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->prev = posprev;
	posprev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

    2.11 在pos之前插入

    在pos位置删除，我们只需找到pos前一个节点posprev，和后一个节点posnext，将prev和next的链接接好，释放pos节点

    数据结构——双向链表（保姆级教程，包学包会）,第8张

    void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

     

    2.12 判断是否为空

    这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己，那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言

    bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

    这里我们也可以简写成：

    void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
	LTInsert(phead->next, x);
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);
}

    2.13 打印

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

    2.14 销毁

    我们这时直接把链表节点全部删除，在删除过程中记住我们下一个节点以便于循环

    注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空

    void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

    完整代码

    List.h

    #pragma once
#include
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
LTNode* LTInit();
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

    List.c

    #include "List.h"
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
	
}
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);
	firstnext->prev = phead;
	phead->next = firstnext;
}
LTNode* LTFind(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 LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->prev = posprev;
	posprev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	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 = next;
	}
	free(phead);
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

    Test.c

    #include"List.h"
void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
void TestList2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	/*LTPopFront(plist);
	LTPrint(plist);*/
	LTDestroy(plist);
	plist = NULL;
}
void TestList3()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
int main()
{
	TestList3();
	return 0;
}

    以上就是今天的分享喜欢的话请三联支持一下我们下期再见哦

     

    上一篇：算法介绍及实现——基于遗传算法改进的BP神经网络算法（附完整Python实现）

    下一篇：【数据结构】二叉树——堆（开篇）

    网站优化运营
    整站seo优化
    网络营销运营
    成功案例
    品牌创意网站
    营销型网站
    小程序
    微信小程序
    微信公众号
    百度熊掌号
    网站优化分享
    关于我们
    公司概况
    公司新闻
    公司文化
    结构体系
    企业资质
    加入我们
    关注我们
    扫描二维码
    获取更多信息
    精彩一手掌握
    Copyright © 2014-2019 seo,上海网站优化_网络制作_网站seo排名_网站建设推广_上海网络公司 版权所有 沪ICP备19022315号