数据结构之“双向链表”

前言

前面我们介绍了单向链表，我们这里的双向链表是为了弥补单向链表只能从头节点开始单向遍历，插入和删除节点时需要更多的操作，因为无法直接访问前一个节点。

前言

一、双向链表的结构

二、实现双向链表

2.1符号定义

2.2节点创建

2.3初始化

2.4尾插

2.5头插

2.6打印

2.7尾删

2.8头删

2.9指定位置之后插入数据

2.10在指定位置的删除

2.11查找

2.12销毁

三、双向链表和单向链表的分析

四、完整代码

总结

一、双向链表的结构

这里双向链表是带头双向循环的链表，大致是下面这样的。

二、实现双向链表

2.1符号定义

这里结构体里面有两个指针，分别指向前一个节点和下一个节点。

typedef int STLDataType;
typedef struct ListNode ListNode;
typedef struct ListNode//双向链表是（带哨兵位双向循环链表）    单链表是（不带哨兵位单向不循环链表）
{
	STLDataType data;//节点存放的数据
	ListNode* next;//指向下个节点的指针
	ListNode* prev;//指向上个节点的指针
};

2.2节点创建

这里和单链表类似，通过malloc来开辟动态空间。这里要注意一下这两个指针要指向空。

ListNode* STLBuyNode(STLDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;//next 表示为指向下一个节点的指针
	newnode->prev = NULL;//prev 表示为指向上一个节点的指针
	return newnode;
}

2.3初始化

初始化也就是创建一个哨兵位，因为是循环所以要把指针指向自己。

ListNode* STLInit()
{
	ListNode* head = STLBuyNode(-1);
	head->next = head;
	head->prev = head;
	return head;
}

2.4尾插

尾插我们要改变p3、p4、head这三个节点的指针，我们先把新节点的next指针指向head，新节点的prev指针指向head的prev指针指向的节点。（也就是p4next指针指向head，prev指向p3），再来改变p3的next指针指向p4和head的prev指针指向p4。

那能不能颠倒一下顺序呢？改变了顺序（这里的顺序是指先改变新节点还是p3），就会找不到p3,找不到p3就改变不了p3的next指针指向，所以不可以颠倒顺序。我们还要判断一下这个是不是空指针，空指针不可以进行解引用操作。

//尾插
void STLPushBlack(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

2.5头插

和尾插原理相似，我们就先改变新节点的两个指针，然后再来改变head指针和p1指针。不要忘了判空。

//头插
void STLPushFront(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead->prev;

	phead->next->prev = newnode;
	phead->next = newnode;
}

2.6打印

我们打印双向链表，因为第一个是哨兵位不储存有效的值，所以要从下一个开始打印（我们就用temp指针来指向phead->next指针）。因为双向链表具有循环的特定，所以我们要找一下结束顺序的条件（当temp！=head位为顺序条件），还要让temp移动，还要判空别忘了。

//打印
void STLPrint(ListNode* phead)
{
	assert(phead);
	ListNode* temp = phead->next;
	while (temp != phead)
	{
		printf("%d->", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

2.7尾删

我们这里通过指针del来删除尾节点，我们不引进这个新指针的话指针就会显示的很长容易写错，

例如phead->prev->prev->next=phead;很长很繁琐。我们释放了这个节点不要忘了指向空指针（防止出现空指针），判空要有一点改变因为我们用到是第一个有效节点所以第一个有效节点也不可以是空指针。

//尾删
void STLPopBlcak(ListNode* phead)
{
	assert(phead && phead->prev);
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

2.8头删

与尾删同理可知，大家自己画图试试，这里就不讲了。

//头删
void STLPopFront(ListNode* phead)
{
	assert(phead && phead->next);
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

2.9指定位置之后插入数据

首先传一个地址，用pos指针来接受，受影响的指针有p2、p3、p4还是按照之前的思路先改变要插入的数据，让p4的指针next指向p3，指针prev指p2。在来改变p2的next指针和p3的prev指针。

然后还要判空。

//在指定位置之后插入数据
void STLInsert(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	ListNode* pos = phead;//指定位置的指针
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}

2.10在指定位置的删除

删除这个p2位置的节点会影响到p1、p3。直接修改了p1的next指针指向p3，p3的prev指针指向p1后会导致找不到p2节点，也就释放不了了。所以我们要找一个指针储存它，方便释放动态空间。

//在指定位置的删除
void STLErase(ListNode* phead)
{
	assert(phead);
	ListNode* pos = phead;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

2.11查找

遍历链表，判断是否相同，里面的循环和打印类似。

//查找
ListNode* STLFind(ListNode* phead,STLDataType x)
{
	ListNode* pucr = phead->next;
	while (pucr != phead)
	{
		if (pucr->data == x)
		{
			return pucr;
		}
		pucr = pucr->next;
	}
	return NULL;
}

2.12销毁

销毁表，这里要先从第一个有效节点开始释放，释放之前要先储存起来下一个节点的指针，这样方便写循环条件。最后再来释放哨兵位。

//销毁双向链表
void STLDesTroy(ListNode* phead)
{
	assert(phead);
	ListNode* pucr = phead->next;
	while (pucr != phead)
	{
		ListNode* temp = pucr->next;
		free(pucr);
		pucr = temp;
	}
	free(phead);
	phead = NULL;
	pucr = NULL;
}

三、双向链表和单向链表的分析

四、完整代码

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


typedef int STLDataType;
typedef struct ListNode ListNode;
typedef struct ListNode//双向链表是（带哨兵位双向循环链表）    单链表是（不带哨兵位单向不循环链表）
{
	STLDataType data;//节点存放的数据
	ListNode* next;//指向下个节点的指针
	ListNode* prev;//指向上个节点的指针
};

//初始化双向链表
ListNode* STLInit();
//打印
void STLPrint(ListNode * phead);
//尾插
void STLPushBlack(ListNode* phead, STLDataType x);
//头插
void STLPushFront(ListNode* phead, STLDataType x);
//尾删
void STLPopBlcak(ListNode* phead);
//头删
void STLPopFront(ListNode* phead);
//在指定位置之后插入数据
void STLInsert(ListNode* phead, STLDataType x);
//在指定位置的删除
void STLErase(ListNode* phead);//原本应该是要传二级指针的，
//因为要通过形参影响实参所以要传地址！！,但是为了统一接口
// 所以传一级指针

//查找
ListNode* STLFind(ListNode* phead,STLDataType x);

//销毁双向链表
void STLDesTroy(ListNode* phead);

STL List.c
#define _CRT_SECURE_NO_WARNINGS
#include"STL List.h"
//节点创建
ListNode* STLBuyNode(STLDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

//初始化
ListNode* STLInit()
{
	ListNode* head = STLBuyNode(-1);
	head->next = head;
	head->prev = head;
	return head;
}

//尾插
void STLPushBlack(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void STLPushFront(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead->prev;

	phead->next->prev = newnode;
	phead->next = newnode;
}

//打印
void STLPrint(ListNode* phead)
{
	assert(phead);
	ListNode* temp = phead->next;
	while (temp != phead)
	{
		printf("%d->", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

//尾删
void STLPopBlcak(ListNode* phead)
{
	assert(phead && phead->prev);
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void STLPopFront(ListNode* phead)
{
	assert(phead && phead->next);
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

//在指定位置之后插入数据
void STLInsert(ListNode* phead, STLDataType x)
{
	assert(phead);
	ListNode* newnode = STLBuyNode(x);
	ListNode* pos = phead;//指定位置的指针
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}

//在指定位置的删除
void STLErase(ListNode* phead)
{
	assert(phead);
	ListNode* pos = phead;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//查找
ListNode* STLFind(ListNode* phead,STLDataType x)
{
	ListNode* pucr = phead->next;
	while (pucr != phead)
	{
		if (pucr->data == x)
		{
			return pucr;
		}
		pucr = pucr->next;
	}
	return NULL;
}

//销毁双向链表
void STLDesTroy(ListNode* phead)
{
	assert(phead);
	ListNode* pucr = phead->next;
	while (pucr != phead)
	{
		ListNode* temp = pucr->next;
		free(pucr);
		pucr = temp;
	}
	free(phead);
	phead = NULL;
	pucr = NULL;
}

test.c //测试文件
#define _CRT_SECURE_NO_WARNINGS
#include"STL List.h"

void Test1()
{
	ListNode* phead = STLInit();
	STLPushFront(phead, 1);//头插
	STLPushBlack(phead, 2);//尾插
	STLPushBlack(phead, 3);
	STLPushBlack(phead, 4);
	STLPushBlack(phead, 5);
	STLPrint(phead);//打印
	STLPopFront(phead);//头删
	STLPopBlcak(phead);//尾删
	STLPrint(phead);//打印
	ListNode* pos = STLFind(phead,4);
	/*if (pos == NULL)
	{
		printf("查找失败！\n");
	}
	else
	{
		printf("找到了！\n");
	}*/
	STLInsert(pos, 5);//指定位置以后的删除
	STLPrint(phead);//打印
	STLErase(pos);//指定位置的删除
	STLPrint(phead);//打印
	STLDesTroy(phead);//销毁
	phead = NULL;
	//STLPrint(phead);//打印
}

int main()
{
	Test1();
	return 0;
}