【数据结构】双链表完整代码实现双向链表的代码实现

48 阅读 0 评论 32 点赞

我是靠谱客的博主单薄心锁，最近开发中收集的这篇文章主要介绍【数据结构】双链表完整代码实现双向链表的代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

双向链表的代码实现

前置文章：单链表完整代码实现

1、前言

上一篇文章，对单链表进行了总结，并实现了单链表的完整代码，并通过实践验证，已成功跑通。欢迎点击前置文章前往查看。
本章主要总结双向链表的知识点，并在C++环境下对双向链表进行了实现。

2、双向链表存储结构

typedef struct DuLNode
{
ElemType data; //数据域
struct DuLNode* prior; //直接前驱
struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;

3、双向链表与单链表的区别

区别：

比单链表多了个头结点，因此可以从最后一个结点往前遍历
与单链表主要区别在存储结构、初始化、插入和删除的方法上，其他的可通用

与单链表代码不同的地方：

/* 双向链表结构 */
typedef struct DuLNode
{
ElemType data; //数据域
struct DuLNode* prior; //直接前驱
struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;
//初始化双链表 有头结点
Status InitList(DuLinkList& L)
{
L = new DuLNode;
L->prior = NULL;
L->next = NULL;
return 1;
}
/*
双链表的取址（按位查找）: 时间复杂度O(n)
参数一：要取址的双链表
参数二：要取址的位置
这是获取插入位置前一个的地址
如果想把数据插入1号位置，就返回第1-1号位置的地址
*/
DuLNode* GetElem_Dul(DuLinkList L, int i)
{
DuLNode* p = L;
//if (p->next == NULL)//如果头结点L的后继为空，则返回头结点L的地址
//{
//	return p;
//}
int j = 0;
while (p && j < i-1)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return 0;
}
return p;
}
/*
双链表的插入（按位序前插入）:时间复杂度O(n)
参数一：要插入的双链表
参数二：要插入的位置
参数三：要插入的数据
注意：成功：返回1；失败：返回0。
*/
Status ListInsert(DuLinkList& L, int i, ElemType e)
{
DuLNode* p = GetElem_Dul(L, i);//获取插入位置的前驱结点
DuLNode* s = new DuLNode; //创建新结点
s->data = e;//新结点存放新数据e
s->next = p->next;//改s的前驱和后继
if (p->next != NULL)
{
p->next->prior = s;//p的指针指向新节点s
}
s->prior = p;//将p的指针指向的下一个数据地址赋值给新结点s的指针
p->next = s;
return 1;
}
/*
双链表的删除:
时间复杂度O(n)
参数一：要删除的双链表
参数二：要删除的位置
注意：成功：返回1；失败：返回0。
*/
Status ListDelete(DuLinkList& L, int i)
{
DuLNode* p = L;//创建临时结点指向头结点，头结点不存数据
int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
while (p->next && (j < i - 1))//循环找到第i-1个结点的前一个结点
{
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
{
return 0;
}
DuLNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
p->next->next->prior = p;//修改q->next的前驱
p->next = p->next->next;//修改p的后继
delete q;//释放q结点
return 1;
}

4、双向链表的完整代码实现

#include<iostream>
#include<string>
using namespace std;
/*
双链表 Double Link List
比单链表多了个头结点，因此可以从最后一个结点往前遍历
与单链表主要区别在 存储结构、插入和删除的方法上，其他的可通用
*/
typedef int ElemType;
typedef int Status;
typedef struct DuLNode
{
ElemType data; //数据域
struct DuLNode* prior; //直接前驱
struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;
//初始化双链表 有头结点
Status InitList(DuLinkList& L)
{
L = new DuLNode;
L->prior = NULL;
L->next = NULL;
return 1;
}
/*
双链表的取值（按位查找）: 时间复杂度O(n)
参数一：要取值的双链表
参数二：要取值的位置
参数三：待保存的对象
注意：成功：返回1；失败：返回0。
*/
Status GetElem(DuLinkList L, int i, ElemType& e)
{
DuLNode* p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return 0;
}
e = p->data;
return p->data;
}
/*
双链表的取址（按位查找）: 时间复杂度O(n)
参数一：要取址的双链表
参数二：要取址的位置
这是获取插入位置前一个的地址
如果想把数据插入1号位置，就返回第1-1号位置的地址
*/
DuLNode* GetElem_Dul(DuLinkList L, int i)
{
DuLNode* p = L;
//if (p->next == NULL)//如果头结点L的后继为空，则返回头结点L的地址
//{
//	return p;
//}
int j = 0;
while (p && j < i-1)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return 0;
}
return p;
}
/*
双链表的查找（按值查找）:
时间复杂度O(n)
参数一：要查找的双链表
参数二：要查找的数据
注意：成功：返回下标地址；失败：返回NULL。
*/
DuLNode* LocateElem(DuLinkList L, ElemType e)
{
DuLNode* p = L->next;//创建新结点，并指向第一块数据
while (p && p->data != e)//如果p不为空且data != e,指向下一个
{
p = p->next;
}
return p;//找到e返回p的地址，没找到返回NULL
}
/*
双链表的插入（按位序前插入）:时间复杂度O(n)
参数一：要插入的双链表
参数二：要插入的位置
参数三：要插入的数据
注意：成功：返回1；失败：返回0。
*/
Status ListInsert(DuLinkList& L, int i, ElemType e)
{
DuLNode* p = GetElem_Dul(L, i);//获取插入位置的前驱结点
DuLNode* s = new DuLNode; //创建新结点
s->data = e;//新结点存放新数据e
s->next = p->next;//改s的前驱和后继
if (p->next != NULL)
{
p->next->prior = s;//p的指针指向新节点s
}
s->prior = p;//将p的指针指向的下一个数据地址赋值给新结点s的指针
p->next = s;
return 1;
}
/*
双链表的删除:
时间复杂度O(n)
参数一：要删除的双链表
参数二：要删除的位置
注意：成功：返回1；失败：返回0。
*/
Status ListDelete(DuLinkList& L, int i)
{
DuLNode* p = L;//创建临时结点指向头结点，头结点不存数据
int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
while (p->next && (j < i - 1))//循环找到第i-1个结点的前一个结点
{
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
{
return 0;
}
DuLNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
p->next->next->prior = p;//修改q->next的前驱
p->next = p->next->next;//修改p的后继
delete q;//释放q结点
return 1;
}
int main()
{
DuLinkList L;
//初始化双链表
InitList(L);
//插入双链表
for (int i = 1; i < 6; i++)
{
ListInsert(L, i, i);
}
//取值
int e;
for (int i = 1; i <= 5; i++)
{
cout << GetElem(L, i, e) << endl;
}
//查找
cout << "5的地址为：" << LocateElem(L, 1) << endl;
//删除
ListDelete(L, 2);
cout << "删除第一个元素1：" << endl;
for (int i = 1; i < 5; i++)
{
cout << GetElem(L, i, e) << endl;
}
return 1;
}