1. 首页
  2. 文章中心
  3. 数据结构

数据结构C++ 实现单链表

103 阅读 0 评论
我是靠谱客的博主 不安自行车，这篇文章主要介绍数据结构C++ 实现单链表，现在分享给大家，希望可以做个参考。

link.h

复制代码
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
#ifndef LINK_H
#define LINK_H
#pragma once
#include <iostream>
#define OK 1
#define fail 0
using namespace std;
template <class T>
class Node
{
public:
Node<T> *next;
T *data;
};
template <class T>
class Link
{
private:
Node<T> *head;
int length;
public:
// 构造函数，初始化链表
Link();
// 拷贝构造
Link(const Link<T> &ln);
// 析构
~Link();
// 指定位置添加节点
int link_insert(int pos, T *value);
// 遍历链表
void link_foreach(void(print)(T *));
// 删除尾结点
T *link_pop();
// 添加尾节点
int link_push(T *value);
// 删除头结点
T *link_shift();
// 添加头结点
int link_unshift(T *value);
// 输出指定位置节点
T * link_index(int index);
// 查找节点
T * link_find(bool(print)(T *));
// 翻转链表
int link_reverse();
// 获取链表长度
int link_length();
// 清空链表
int link_clear();
// 销毁链表
int link_destory();
// 连接链表
Link<T>& operator+(const Link<T> &plink);
};
#endif //TEST1_LIST_H

link.cpp

复制代码
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include "link.h"
// 初始化链表
template<typename T>
Link<T>::Link(){
this->head=new Node<T>;
this->head->next=NULL;
this->head->data=NULL;
this->length=0;
}
// 拷贝构造
template<typename T>
Link<T>::Link(const Link<T> &ln){
this->length=ln.length;
this->head=new Node<T>;
this->head->next=NULL;
Node<T> *p=this->head;
Node<T> *move=ln.head->next;
for(int i=0;i<this->length;++i){
Node<T> *newNode=new Node<T>;
newNode->data=move->data;
newNode->next=NULL;
p->next=newNode;
p=newNode;
move=move->next;
}
}
// 析构
template<typename T>
Link<T>::~Link(){
this->link_destory();
}
// 指定位置添加节点
template<typename T>
int Link<T>::link_insert(int pos,T *value){
if(!value){
return fail;
}
if(pos<0||pos>this->length){
pos=this->length;
}
Node<T> *pCur=this->head;
for(int i=0;i<pos;++i){
pCur=pCur->next;
}
Node<T> *newNode=new Node<T>;
newNode->next=pCur->next;
newNode->data=value;
pCur->next=newNode;
this->length++;
return OK;
}
// 遍历链表
template<typename T>
void Link<T>::link_foreach(void(print)(T *)){
if(!print){
return ;
}
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
print(pCur->data);
}
}
// 删除尾结点
template<typename T>
T* Link<T>::link_pop(){
if(this->length==0)
return NULL;
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
}
Node<T> *deleteNode=pCur;
T *value=deleteNode->data;
delete deleteNode;
pCur=pCur->next;
this->length--;
return value;
}
// 插入尾结点
template<typename T>
int Link<T>::link_push(T *value){
if(!value)
return fail;
Node<T> *pCur=this->head;
for(int i=0;i<this->length;i++){
pCur=pCur->next;
}
Node<T> *newNode=new Node<T>;
newNode->data=value;
newNode->next=NULL;
pCur->next=newNode;
this->length++;
return OK;
}
// 删除头结点
template<typename T>
T * Link<T>::link_shift(){
if(this->length==0)
return NULL;
Node<T> *pCur=this->head;
T *value=pCur->next->data;
Node<T> *deleteNode=pCur->next;
pCur->next=deleteNode->next;
delete deleteNode;
this->length--;
return value;
}
// 查找指定位置节点
template<typename T>
T * Link<T>::link_index(int index){
if(index>this->length||index<0)
return NULL;
Node<T> *pCur=this->head->next;
for(int i=0;i<index;++i){
pCur=pCur->next;
}
return pCur->data;
}
// 添加头结点
template<typename T>
int Link<T>::link_unshift(T *value){
if(!value)
return fail;
Node<T> *pCur=this->head;
Node<T> *newNode=new Node<T>;
newNode->data=value;
newNode->next=pCur->next;
pCur->next=newNode;
this->length++;
return OK;
}
// 查找节点
template<typename T>
T * Link<T>::link_find(bool(print)(T *)){
if(this->length==0||!print)
return NULL;
Node<T> *pCur=this->head->next;
for(int i=0;i<this->length;i++){
if(print(pCur->data)){
return pCur->data;
}
}
return NULL;
}
// 翻转链表
template<typename T>
int Link<T>::link_reverse(){
if(this->length==0)
return fail;
Node<T> *pHead=this->head;
Node<T> *pFont=NULL;
Node<T> *pNext=NULL;
while(pHead->next!=NULL){
pFont=pHead->next;
pHead->next=pFont->next;
pFont->next=pNext;
pNext=pFont;
}
this->head->next=pFont;
return OK;
}
// 获取链表长度
template<typename T>
int Link<T>::link_length(){
return this->length;
}
// 清空链表
template<typename T>
int Link<T>::link_clear(){
if(this->length==0)
return OK;
Node<T> *pCur=this->head->next;
for(int i=0;i<this->length;i++){
Node<T> *t=pCur->next;
if(!pCur)
break;
delete pCur;
pCur=t;
}
this->length=0;
return OK;
}
// 销毁链表
template<typename T>
int Link<T>::link_destory(){
this->link_clear();
if(this->head){
delete this->head;
}
return OK;
}
// 连接链表
template<typename T>
Link<T>& Link<T>::operator+(const Link<T> &plink){
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
}
// pCur->next=plink.head->next;
Node<T> *move=plink.head->next;
Node<T> *newHead=new Node<T>;
newHead->next=NULL;
Node<T> *p=newHead;
for(int i=0;i<plink.length;++i){
Node<T> *newNode=new Node<T>;
newNode->data=move->data;
newNode->next=NULL;
p->next=newNode;
p=newNode;
move=move->next;
}
pCur->next=newHead->next;
this->length+=plink.length;
delete newHead;
return *this;
}

test.cpp

复制代码
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
#include "link/link.cpp"
#include <iostream>
#include <string>
using namespace std;
struct person{
int id;
string name;
int age;
};
int maxValue=-99;
int minValue=99;
struct person *pMax;
struct person *pMin;
template<typename T>
void myPrint(T *value){
struct person *p=(struct person *)value;
if(maxValue<p->age){
maxValue=p->age;
pMax=p;
}
if(minValue>p->age){
minValue=p->age;
pMin=p;
}
cout<<"id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
}
template<typename T>
bool findPrint(T *value){
struct person *p1=(struct person *)value;
if(p1->age==20&&p1->id==3&&p1->name=="Sam"){
return true;
}else{
return false;
}
}
void test(){
struct person p1={1,"Andy",18};
struct person p2={2,"Tom",19};
struct person p3={3,"Sam",20};
struct person p4={4,"Tim",21};
struct person p5={5,"Jack",22};
Link<person> *k1=new Link<person>();
k1->link_insert(0,&p1);
k1->link_insert(0,&p2);
k1->link_insert(0,&p3);
k1->link_insert(0,&p4);
k1->link_insert(0,&p5);
k1->link_push(&p5);
k1->link_unshift(&p3);
// struct person *p=(struct person *)k1->link_shift();
// cout<<"111id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
k1->link_foreach(myPrint);
cout<<"max value. id:"<<pMax->id<<" name:"<<pMax->name<<" age:"<<pMax->age<<endl;
cout<<"min value. id:"<<pMin->id<<" name:"<<pMin->name<<" age:"<<pMin->age<<endl;
struct person *p=(struct person *)k1->link_find(findPrint);
if(p)
cout<<"find id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
cout<<k1->link_reverse()<<endl;
cout<<"------------------"<<endl;
k1->link_foreach(myPrint);
k1->link_clear();
k1->link_insert(0,&p1);
k1->link_insert(0,&p2);
k1->link_insert(0,&p3);
k1->link_insert(0,&p4);
k1->link_insert(0,&p5);
k1->link_foreach(myPrint);
cout<<k1->link_length()<<endl;
cout<<"-------------------------------------"<<endl;
Link<person> *k2=new Link<person>(*k1);
k2->link_insert(0,&p1);
k2->link_foreach(myPrint);
cout<<"-------------------------------------"<<endl;
k1->link_foreach(myPrint);
*k1=*k1+*k2;
cout<<"-------------------------------------"<<endl;
k1->link_foreach(myPrint);
k1->link_destory();
cout<<"-------------------------------------"<<endl;
cout<<"find id:"<<p5.id<<" name:"<<p5.name<<" age:"<<p5.age<<endl;
// k2->link_foreach(myPrint);
p=(struct person *)k2->link_index(0);
cout<<"index id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
k2->link_destory();
}
int main(){
test();
system("pause");
return EXIT_SUCCESS;
}

 运行结果

复制代码
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
id:3 name:Sam age:20
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
id:5 name:Jack age:22
max value. id:5 name:Jack age:22
min value. id:1 name:Andy age:18
find id:3 name:Sam age:20
1
------------------
id:5 name:Jack age:22
id:1 name:Andy age:18
id:2 name:Tom age:19
id:3 name:Sam age:20
id:4 name:Tim age:21
id:5 name:Jack age:22
id:3 name:Sam age:20
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
5
-------------------------------------
id:1 name:Andy age:18
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
id:1 name:Andy age:18
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
find id:5 name:Jack age:22
index id:1 name:Andy age:18
请按任意键继续. . .

 

最后

以上就是不安自行车最近收集整理的关于数据结构C++ 实现单链表的全部内容，更多相关数据结构C++内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(68)

相关文章

数据结构-线性表-顺序表
数据结构-线性表-顺序表
数据结构（c语言版）顺序表的建立、初始化、插入、删除、遍历等12个基本操作及测试
数据结构（c语言版）顺序表的建立、初始化、插入、删除、遍历等12个基本操作及测试
C语言实现顺序表的基本操作
C语言实现顺序表的基本操作
链表InitList传入双重指针分析
链表InitList传入双重指针分析
数据结构C++ 实现单链表
数据结构C++ 实现单链表
顺序表创建和就地逆置
顺序表创建和就地逆置
线性表
线性表
数据结构实验1_顺序表的操作
数据结构实验1_顺序表的操作

评论列表共有 0 条评论

立即
投稿
返回
顶部