1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
// 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();//遍历操作，按序号输出各个元素
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//
// 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;
}