数据结构-双链表

标签：结点 LTNode next pcur phead 双链 newnode 数据结构

一.概念与结构

链表的结构丰富多样,基本分为以下的八种(2×2×2)

1.1 单项或双向

双向链表区别于单向链表的是,其多了一个指针区域,指向其前一个结点,这样就可以通过任意一个结点进行前后遍历.

1.2 带头或不带头

带不带头指的是其有无头结点,即下图的head结点,这个结点是一个特殊的结点,他不存放数据,只是存放指向头节点的地址,那么这样有什么好处呢,在为什么实现双向链表的过程中会有提及.

1.3 循环或不循环

循环或不循环指的是该链表的头尾是否相连接,如果这个链表为一个循环链表那么他的尾节点的next指针则不再是指向空,而是于指向了头结点,实现了头尾相连.

在上一篇博客中,我们论述的单链表,严谨的说法应该是单向不带头不循环链表,这是比较常用到的链表结构之一.

而在本篇章中,我们就要实现的双链表,即是另一个比较常用的链表结构:双向带头循环链表.

既然双链表的全称为双向带头循环链表,由此我们不难推断出他节点结构:一个数值域,两个指针域,分别是指向该节点的前驱节点prev与其后驱节点pcur.

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

二.双链表的实现

双链表的实现基本分为以下的三个部分

2.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

//创建结点
LTNode* LTCreat(LTDatatype x);
//初始化
LTNode* LTInit();

//打印
void LTPrint(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);
//指定位置之后插入
void LTInsert(LTNode* pos, LTDatatype x);
//指定位置删除
void LTErase(LTNode* pos);

//销毁
void LTDestroy(LTNode* pphead);

2.2 List.c

2.2.1 申请新节点

双链表的物理结构不一定连续，我们只需要创建一个节点就申请一块空间即可，因此我们使用malloc函数独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），比realloc动态增容消耗更低，也不会造成空间浪费。

所以实现这个函数，我们在创建节点时使用malloc函数开辟一个内存单元,接着将传递过来的参数放在newnode里。然后为newnode结点赋值,最后将创建好的结点返回.

LTNode* LTCreat(LTDatatype x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("newnode");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
	return newnode;
}

注：实现这个函数需要注意以下几点：

1.在申请内存时候，注意申请的内存大小应为(sizeof(LTNode)),并且将返回类型强制转换为LTNode*,并使用对应类型的指针newnode接收.

2.malloc的扩容用概率会失败,如果失败则会返回NULL,所以在使用之前需要写一个判断条件,判断newnode是否等于空指针

3.在在进行节点初始化的时候不要忘记,由于我们实现的链表为双向带头循环链表,那么申请的节点初始化因头尾链接形成循环,即自己指向自己,因此在初始化节点时我们要让其prev指针与pcur指针都指向自己形成自循环.

4.对新结点赋值完之后我们要返回这个这个结点，因此我们的函数返回类型为LTNode*

2.2.2 双链表的打印

LTPrint函数有助于我们在对后续函数实现的过程中更加清晰明了的反应链表中元素，可以帮助我们免去一些调试的过程，所以我们先实现这个函数。

这个函数的参数是一个结构体指针，我们只需要接受这个指针的值，创建while循环，定义一个指针指向链表的第一个节点:pcur=phead->next,并利用pcur=pcur- >next实现节点的遍历并打印

由于我们的链表为循环链表，因此while循环的结束条件应该是pcur不能到为我们的头节点(我们的pcur是从第一个节点开始遍历的,若pcur变为头节点说名已经遍历过一遍链表了)

但是需要注意的是,,在最后不要忘记printf（“\n”);

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

有了链表的打印与节点的申请,实现双链表的过程便会如鱼得水.

2.2.3 初始化

链表的初始化一般有两种方法:

1. 创捷头节点将其返回
        这样不需要传参,只需返回申请好的节点即可,需要注意的是,
        初始化的为头节点,其数据域为什么只需复制一个无意义的值即可

2. 在声明头节点之后传递其地址给LTInit初始化函数
        这样需要传递参数，且是二级指针，指向头节点的变量已经是一级指针，
        想要改变一级指针的内容必须取其地址，使用二级指针接收.
        而由于我们传递的是二级指针,在函数内对形参的开辟会影响到实参        
        因此不需要将地址返回。

void LTInit(LTNode** pphead)
{
	//创建一个头结点（哨兵位）
	*pphead = LTBuyNode(-1);
}

LTNode* LTInit()
{
	LTNode* phead = LTCreat(-1);
	return phead;
}

2.2.4 结点查询

在指定位置的插入删除时,我们需要用到一个方法,返回得到指定结点的位置,因次我们将其封装成一个函数.

而在双链表的结点查询时候,我们要注意循环的退出条件,由于我们的链表为循环链表，因此while循环的结束条件应该是pcur不能为我们的头节点(我们的pcur是从第一个节点开始遍历的,若pcur变为头节点说名已经遍历过一遍链表了)

若找到则返回该结点位置,若循环结束说明未找到该节点,则返回NULL

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

2.2.5 双链表的插入

双向链表拥有前驱指针跟后驱指针,因此在实现这一操作会相对便利许多

尾插

在实现尾插时候，首先创建一个新结点，而后通过链表找到最后一个结点，而由于双链表的结点是头尾相连的,因此我们要找的尾结点即是头结点的前驱结点phead->prev

将新结点的前驱指针指向链表原来的尾结点phead->prev后,再使新结点的后驱指针指向我们的为什么的头结点,从而达到头尾相连

而后使我们原先的为节点phead->prev的后驱指针指向新结点

再使头节点的前驱结点指向新结点,如此一来,便实现了尾插的操作.

void LTPushBack(LTNode* phead, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

头插

在实现了尾插之后,头插的实现自然是得心应手

同样的,首先创建一个新结点,使newnode的后驱结点指向原先的第一个结点,即head->next,再将newnode的p前驱结点指向链表的头节点

而后不要忘记使原先的第一个结点的前驱结点和头结点的后驱结点指向我们的newnode,这便实现了结点的头插.

void LTPushFront(LTNode* phead, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

指定位置之后插入

指定位置的插入与我们的头插其实十分类似,只是操作对象从phead变成了指定的结点pos,因此我们只需要把上图的head结点理解为pos结点即可

由于我们在测试函数时候,需要pos的结点位置,所以在测试函数时,我们就要用到封装好的一个的函数LTFind.

void LTInsert(LTNode* pos, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}

2.2.6 双链表的删除

尾删

由于我们的链表为双链表结构,因此与尾插类似的,我们不再需要遍历链表找尾结点,而由于双链表的结点是头尾相连的,因此我们要找的尾结点即是头结点的前驱结点phead->prev

由于尾删需要将该节点申请的内存释放掉,因此我们需要定义一个指针del指向要删除的尾节点,防止我们在断开尾节点之后无法再找到这片区域

尾删的操作如下

首先使我们链表的头节点的前驱指针指向尾节点的前一结点,如此一来这一节点便成为了新的尾节点,而后再使新的尾节点的后驱节点指向头节点,实现头尾相连.而后再将del指向的空间释放掉,最后不要忘记将del置为空,防止野指针的诞生.

void LTPopBack(LTNode* phead)
{
	assert(phead->next !=phead);
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}

头删

与尾插类似的,由于需要将该节点申请的内存释放掉,因此我们需要定义一个指针del指向要删除的尾节点

头删的操作如下

首先使我们的头节点hea的后驱节点指向del的后驱节点d2,如此d2便成了新的头节点,而后再使头节d2的前驱节点指向头节点,如此一来del指向的节点便被断开,而后再将del指向的空间释放掉,最后不要忘记将del置为空,防止野指针的诞生.

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

指定位置删除

指定位置的删除其实与头删十分类似,只是删除的对象变成了pos节点,其余基本一致,可以举一反三,因此不过多赘述,以下附图方便理解.

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

2.2.7 链表的销毁

链表的销毁大致步骤为:

首先创建pcur指向第一个节点,而后创建循环,在循环中创建next指针指向下一节点,而后将释放掉pcur当前节点的内存,随后使pcur指针后移一位,如此反复,使得最后若pcur指向了头节点说明链表中的节点全部释放,由此退出循环,最后不要忘记释放掉头节点并将pcur与phead都置为空;

销毁链表的函数既可以选择一级指针也可以选择二级指针,他们各有利弊

1.传参为一级指针
        若传参为一级指针,那么由于头节点本身就为一级指针,所以函数实现的为传值调用,因此在最后虽然释放掉了phead执向的地址的内存,但是phead=NULL这句话实际上只是改变了形参的值,实参并未发生改变,因此,在调用完这个函数还需手动将头节点的函数值置为空.

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

2.传参为二级指针
        若传参为二级地址,则避免了手动将头节点的函数值置为空的操作,但是由于我们上述实现的操作基本传参为一级地址,因此,为了保证接口的一致性,在双联的实现中尽量选择接口一致的方法.

void LTDesTroy(LTNode** pphead)
{
	assert(pphead && *pphead);
	LTNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

三.源码

Lish.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

//创建结点
LTNode* LTCreat(LTDatatype x);
//初始化
LTNode* LTInit();

//打印
void LTPrint(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);
//指定位置之后插入
void LTInsert(LTNode* pos, LTDatatype x);
//指定位置删除
void LTErase(LTNode* pos);

//销毁
void LTDestroy(LTNode* pphead);

Lish.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
LTNode* LTCreat(LTDatatype x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("newnode");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
LTNode* LTInit()
{
	LTNode* phead = LTCreat(-1);
	return phead;
}
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
void LTPushBack(LTNode* phead, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}
void LTPopBack(LTNode* phead)
{
	assert(phead->next !=phead);
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}
void LTPopFront(LTNode* phead)
{
	assert(phead->next != phead);
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = del->prev;
	free(del);
	del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
void LTInsert(LTNode* pos, LTDatatype x)
{
	LTNode* newnode = LTCreat(x);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}
void LTErase(LTNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
void LTDestroy(LTNode* phead)
{
	LTNode* pcur = (phead)->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pcur = NULL;
	free(phead);
	phead = NULL;
}

标签：结点,LTNode,next,pcur,phead,双链,newnode,数据结构
From： https://blog.csdn.net/2302_81813630/article/details/140530967