[数据结构与算法]线性表--双向链表

双向链表:相比于单链表，双向链表有两个指针域，既可以保存右边的节点地址(后继)，也可以保存左边的节点地址(前驱)。如果指针域指向一个不存在的节点，则将其指针置为NULL。

。

如果一个空的双向链表，则它的next和prior同时指向NULL即可。

双向链表结构体设计：

typedef int ELEM_TYPE;

typedef struct Dlist
{
    ELEM_TYPE data;//数据域    保存有效值
    struct Dlist* next;//指针域  保存下一个节点的地址（后继）
    struct Dlist* prior;//指针域 保存上一个节点的地址（前驱）
}Dlist, * PDlist;

双向链表主要实现的函数功能方法：

?1.头插

?双向链表的头插需要首先改变新节点pnewnode自身两条线的指向，然后修改后一个节点的前驱，在修改前一个节点的后继。

bool Insert_head(PDlist plist, ELEM_TYPE val)
{
	//判空
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	//购买新节点
	struct Dlist* pnewnode = BuyNode(val);
	//插入  首先修改pnewnode的指向,其次修改后一个节点前驱和前一个节点后继
	pnewnode->next = plist->next;
	pnewnode->prior = plist;
	if (plist->next != NULL)
	{
		plist->next->prior = pnewnode;
	}
	plist->next = pnewnode;
	return true;
}

2.尾插

?

//尾插
bool Insert_tail(PDlist plist, ELEM_TYPE val)
{
	//判空
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	//购买新节点一个
	struct Dlist* pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if (pnewnode == NULL)
	{
		return false;
	}
	//寻找合适的插入位置
	struct Dlist* p = plist;
	for (p; p->next != NULL; p = p->next);
	//插入先动pnewnode自身指向，再修改前一个节点的后继
	pnewnode->next = NULL;
	pnewnode->prior = p;
	p->next = pnewnode;

	return true;
}

?

?

?3.按位置插入

?

bool Insert_pos(PDlist plist, int pos, ELEM_TYPE val)
{
	assert(plist != NULL);
	//购买新节点
	PDlist pnewnode = BuyNode(val);
	//寻找合适插入位置
	PDlist p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	pnewnode->next = p->next;
	pnewnode->prior = p;
	if (pos != Get_length(plist) && !IsEmpty(plist)) //排除尾插和头插的风险
	{
		p->next->prior = pnewnode;
	}
	p->next = pnewnode;
}

4.头删

?

?

?先用一个临时指针p指向待删除节点位置，在修改后一个节点的前驱和前一个节点的后继，最后释放指针p

bool Del_head(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	if (IsEmpty(plist))  //判断是否为空链表
	{
		return false;
	}
	//寻找待删除节点位置
	struct Dlist* p = plist->next;
	 
	plist->next = p->next;
	if (p->next != NULL)
	{
		p->next->prior = plist;
	}
	free(p);
	return true;

?注：删除一定要判断是否为空链表

5.按位置删除

用一个指针p指向待删除节点位置，用另一个临时指针q指向待删除节点的前一个节点的地址

?修改待删除节点后一个节点的前驱和待删除节点前一个节点的后继，最后释放p

bool Del_pos(PDlist plist, int pos)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	assert(pos >= 0 && pos <= Get_length(plist));
	if (pos == 0)
	{
		return Del_head;
	}
	if (pos == Get_length(plist))
	{
		return Del_tail;
	}
	//判断是否空链表
	if (IsEmpty(plist))
	{
		return false;
	}
	//寻找待删除节点位置
	struct Dlist* q = plist;
	for (int i = 0; i < pos; i++)
	{
		q = q->next;
	}
	struct Dlist* p = q->next;

	q->next = p->next;
	p->next->prior = q;

	free(p);
	return true;
}

双向链表实现完整代码：

Dlist.h

#pragma once

//双向链表结构体设计：
typedef int ELEM_TYPE;

typedef struct Dlist
{
    ELEM_TYPE data;//数据域    保存有效值
    struct Dlist* next;//指针域  保存下一个节点的地址（后继）
    struct Dlist* prior;//指针域 保存上一个节点的地址（前驱）
}Dlist, * PDlist;

//双向链表可执行函数声明：
//初始化
void Init_dlist(struct Dlist* plist);

//购买新节点
struct Dlist* BuyNode(ELEM_TYPE val);

//头插
bool Insert_head(PDlist plist, ELEM_TYPE val);

//尾插
bool Insert_tail(PDlist plist, ELEM_TYPE val);

//按位置插
bool Insert_pos(PDlist plist, int pos, ELEM_TYPE val);

//头删
bool Del_head(PDlist plist);

//尾删
bool Del_tail(PDlist plist);

//按位置删
bool Del_pos(PDlist plist, int pos);

//按值删除
bool Del_val(PDlist plist, ELEM_TYPE val);

//查找（如果值重复，返回第一次出现的节点地址）
struct Dlist* Search(PDlist plist, ELEM_TYPE val);

//判空
bool IsEmpty(PDlist plist);
//判满（链表不用实现）

//获取有效长度
int Get_length(PDlist plist);

//清空
void Clear(PDlist plist);

//销毁1
void Destroy(PDlist plist);

//销毁2
void Destroy2(PDlist plist);

//打印
void Show(PDlist plist);

Dlist.cpp

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include "dlist.h"



//初始化
void Init_dlist(struct Dlist* plist)  //排除两个野指针的风险
{
	plist->next = NULL;
	plist->prior = NULL;

}


//购买新节点
struct Dlist* BuyNode(ELEM_TYPE val)
{
	struct Dlist* pnewnode = (struct Dlist*)malloc(1 * sizeof(struct Dlist*));
	assert(pnewnode != NULL);
	if (pnewnode == NULL)
	{
		return NULL;
	}
	pnewnode->data = val;
	pnewnode->next->prior = NULL;
	return pnewnode;
}

//头插
bool Insert_head(PDlist plist, ELEM_TYPE val)
{
	//判空
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	//购买新节点
	struct Dlist* pnewnode = BuyNode(val);
	//插入  首先修改pnewnode的指向,其次修改后一个节点前驱和前一个节点后继
	pnewnode->next = plist->next;
	pnewnode->prior = plist;
	if (plist->next != NULL)
	{
		plist->next->prior = pnewnode;
	}
	plist->next = pnewnode;
	return true;
}

//尾插
bool Insert_tail(PDlist plist, ELEM_TYPE val)
{
	//判空
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	//购买新节点一个
	struct Dlist* pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if (pnewnode == NULL)
	{
		return false;
	}
	//寻找合适的插入位置
	struct Dlist* p = plist;
	for (p; p->next != NULL; p = p->next);
	//插入先动pnewnode自身指向，再修改前一个节点的后继
	pnewnode->next = NULL;
	pnewnode->prior = p;
	p->next = pnewnode;

	return true;
}


//按位置插
bool Insert_pos(PDlist plist, int pos, ELEM_TYPE val)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	assert(pos >= 0 && pos <= Get_length(plist));
	if (pos == 0)
	{
		return Insert_head(plist, val);
	}
	else if (pos == Get_length(plist))
	{
		return Insert_tail(plist, val);
	}
	//购买新节点
	PDlist pnewnode = BuyNode(val);
	//寻找合适插入位置
	PDlist p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	pnewnode->next = p->next;
	pnewnode->prior = p;
	if (pos != Get_length(plist) && !IsEmpty(plist)) //排除尾插和头插的风险
	{
		p->next->prior = pnewnode;
	}
	p->next = pnewnode;
}

//头删
bool Del_head(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	if (IsEmpty(plist))  //判断是否为空链表
	{
		return false;
	}
	//寻找待删除节点位置
	struct Dlist* p = plist->next;
	 
	plist->next = p->next;
	if (p->next != NULL)
	{
		p->next->prior = plist;
	}
	//释放p
	free(p);
	return true;
	
}

//尾删
bool Del_tail(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	if (IsEmpty(plist))
	{
		return false;
	}
	struct Dlist* p = plist;
	for (p; p->next != NULL; p = p->next);
	free(p);
}

//按位置删
bool Del_pos(PDlist plist, int pos)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	assert(pos >= 0 && pos <= Get_length(plist));
	if (pos == 0)
	{
		return Del_head;
	}
	if (pos == Get_length(plist))
	{
		return Del_tail;
	}
	//判断是否空链表
	if (IsEmpty(plist))
	{
		return false;
	}
	//寻找待删除节点位置
	struct Dlist* q = plist;
	for (int i = 0; i < pos; i++)
	{
		q = q->next;
	}
	struct Dlist* p = q->next;

	q->next = p->next;
	p->next->prior = q;

	free(p);
	return true;
}

//按值删除
bool Del_val(PDlist plist, ELEM_TYPE val)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	struct Dlist* p = Search(plist, val);
	if (p == NULL)
	{
		return false;
	}

	//在申请一个指针q，指向p的前一个节点
	struct Dlist* q = plist;
	for (q; q->next != p; q = q->next);
	//此时 q在p前面

	//跨越指向  +  释放内存
	q->next = p->next; //ok
	if (p->next != NULL)
	{
		p->next->prior = q;//特殊情况：如果你找的val值 在尾结点找到了  这行代码就会失败
	}

	free(p);
	return true;
}

//查找（如果值重复，返回第一次出现的节点地址）
struct Dlist* Search(PDlist plist, ELEM_TYPE val)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	for (struct Dlist* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//判空
bool IsEmpty(PDlist plist)
{
	return plist->next == NULL;
}
//判满（链表不用实现）

//获取有效长度
int Get_length(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}
	int count = 0;
	for (struct Dlist* p = plist->next; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

//清空
void Clear(PDlist plist)
{
	Destroy(plist);
}

//销毁1
void Destroy(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return ;
	}
	while (plist->next != NULL)
	{
		struct Dlist* p = plist->next;
		plist->next = p->next;//这里只需要上一个节点 指向下一个节点即可
		free(p);
	}
	plist->next = plist->prior = NULL;
}

//销毁2
void Destroy2(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return ;
	}
	struct Dlist* p = plist->next;
	struct Dlist* q = NULL;

	plist->next = plist->prior = NULL;

	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

//打印
void Show(PDlist plist)
{
	assert(plist != NULL);
	if (plist == NULL)
	{
		return ;
	}
	for (struct Dlist* p = plist->next; p != NULL; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}