模板类—双向链表： doubly linked list

在循环链表中，从任意一个结点除法可以扫描到其他结点，但要找到其前序结点，则需要遍历整个循环链表。

双向链表

在单链表的基础上设置一个指向其前驱结点的指针域，这样就形成了双链表

1. 其中data为数据域
2. pre为前驱指针域，存放该结点的前驱结点地址
3. next为后继指针域，存放该结点后继结点的地址

顺序表和链表的比较

1. 元素的随机访问：顺序表>链表
2. 元素的插入和删除：链表>顺序表
3. 顺序表需要提前分配空间
4. 链表不需要提前分配空间-只要能够向内存中申请就可以

双链表的声明

//
// Created by HANWENKE on 2022/8/27.
//
#ifndef DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H
#endif //DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H
#include <iostream>
#include <vector>
#include <random>
using
namespace
std;
template <class
_Ty>
struct Node{
_Ty data;
Node<_Ty> *next;
Node<_Ty> *pre;
};
template <class _Ty>
class Doubly_Linked_List{
private:
Node<_Ty> *head;//链表的头指针
public:
Doubly_Linked_List();//无参构造
Doubly_Linked_List(const _Ty *const &a, int n);//有参构造,建立有n个元素的单链表
~Doubly_Linked_List();//析构函数
int length();//求单链表的长度
Node<_Ty>* Get(int t);//按位置查找，在双链表中查找第i个结点
int Locate(const _Ty &x);//按值查找。在单链表中查找值为x的元素序号
void Insert(int i,const _Ty &x);//插入操作，在第i个位置后插入元素值为x的结点
void Delete(int i);//删除单链表中第i个结点
void Print();//遍历操作，按序号输出各个元素
};

双向链表的实现

//
// Created by HANWENKE on 2022/8/27.
//
#include "doubly_linked_list.h"
template<class _Ty>
Doubly_Linked_List<_Ty>::Doubly_Linked_List() {
head=new Node<_Ty>;
head->next= nullptr;
head->pre= nullptr;
}
template<class _Ty>
//双向链表--头插有参构造
Doubly_Linked_List<_Ty>::Doubly_Linked_List( const _Ty *const &a, int n) {
head=new Node<_Ty>;
head->next= nullptr;
head->pre= nullptr;
for(int i=0;i<n;i++){
if(head->next== nullptr){
auto *s=new Node<_Ty>;
s->data=a[i];
s->pre=head;
s->next=head->next;
head->next=s;
}else{
auto *s=new Node<_Ty>;
s->data=a[i];
s->pre=head;
s->next=head->next;
head->next->pre=s;
head->next=s;
}
}
}
template<class _Ty>
Doubly_Linked_List<_Ty>::~Doubly_Linked_List() {
Node<_Ty> *p=head->next;
Node<_Ty> *q=p;
while(p){
q=p->next;
delete p;
p=q->next;
}
delete head;
p= nullptr;
q= nullptr;
head= nullptr;
}
template<class _Ty>
int Doubly_Linked_List<_Ty>::length() {
Node<_Ty> *p;
p=head->next;
int count=0;
while (p){
++count;
p=p->next;
}
return count;
}
template<class _Ty>
//按位置查找
Node<_Ty>* Doubly_Linked_List<_Ty>::Get(int t) {
Node<_Ty> *p=head->next;
int count=1;
while(p&&count<t){
p=p->next;
count++;
}
if (p == nullptr){
cout<<"位置异常"<<endl;
return nullptr;
}
else
return p;
}
//按值查找--如果找到返回元素的序号，如果查找不成功返回0表示失败
template<class _Ty>
int Doubly_Linked_List<_Ty>::Locate(const _Ty &x) {
Node<_Ty> *p=head->next;
int count=1;
while(p){
if(p->data==x) return count;
p=p->next;
count++;
}
return 0;
}
template<class _Ty>
void Doubly_Linked_List<_Ty>::Insert(int i, const _Ty &x) {
Node<_Ty> *temp= Get(i);
auto *newNode=new Node<_Ty>;
newNode->data=x;
newNode->pre=temp;
newNode->next=temp->next;
temp->next->pre=newNode;
temp->next=newNode;
}
template<class _Ty>
void
Doubly_Linked_List<_Ty>::Delete(int i) {
if(i<0||i>length()){
cout<<"删除位置不合法"<<endl;
return;
}
auto temp= Get(i);
temp->pre->next=temp->next;
temp->next->pre=temp->pre;
delete temp;
temp= nullptr;
}
template<class _Ty>
/*遍历操作：
* 临时结点指向第一个结点
* 重复执行以下操作，直到p为空：
*
输出结点p的数据域
*
指针后移*/
void Doubly_Linked_List<_Ty>::Print() {
Node<_Ty> *p=head->next;
while(p!= nullptr){
cout<<p->data<<"
";
p=p->next;
}
cout<<endl;
}
int main(){
vector<char>res(20);
for (int i = 0; i < res.size(); i++)
res[i]=i+'A';
Doubly_Linked_List<char> l(&res[0],res.size());
l.Print();
cout<<l.length()<<endl;
//cout<<l.Get(100)->data<<endl;
l.Insert(0,'W');
l.Print();
l.Delete(3);
l.Print();
return 0;
}

最后

以上就是标致皮卡丘为你收集整理的C++ 模板实现—双向链表： doubly linked list模板类—双向链表： doubly linked list的全部内容，希望文章能够帮你解决C++ 模板实现—双向链表： doubly linked list模板类—双向链表： doubly linked list所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。