单链表的基本操作代码（C++）

80 阅读 0 评论 53 点赞

我是靠谱客的博主义气蜜蜂，这篇文章主要介绍单链表的基本操作代码（C++），现在分享给大家，希望可以做个参考。

该代码解决的问题属于简单类型的;
如果同样的数值出现几次，执行删除或查询等会出现问题;
不过小编思考或许可以用数组存储地址，然后分别执行操作，目前还待实践。

复制代码

#include <iostream>
using namespace std;
typedef struct INode{
int data;
struct INode *next;
}INode, *LinkList;
//单链表长度
int Len(LinkList &L)
{
INode *p=L;
int k=0;
while(p!=NULL)
k++;
return k;
}
//头插
bool ListHeadInsert(LinkList &L,int e)
{
INode *h=(INode *)malloc(sizeof(INode));
h->data=e;
h->next=L;
L=h;//令头结点变为h
cout << "头插成功n";
return true;
}
//尾插
bool ListLastInsert(LinkList &L,int e)
{
INode *s=(INode *)malloc(sizeof(INode *));
s->data=e;
s->next=NULL;
if(L==NULL)
L=s;
else
{
INode *q;
q=L;
while(q->next!=NULL)
{
q=q->next;
}
q->next=s;
}
cout << "尾插成功n";
return true;
}
//在第i个位置插入e
bool ListInsert(LinkList &L, int i, int e)
{
INode *p;
int j = 1;
p = L;
while (p != NULL&&j<i-1)	//找到i-1的结点
{
p = p->next;
j++;
}
if (p == NULL)
return false;
INode *q = (INode *)malloc(sizeof(INode));
q->data = e;
q->next = p->next;
p->next = q;
cout << "插入成功n";
return true;
}
//头删
void ListHeadDelect(LinkList &L)
{
if(L==NULL)
return;
else
{
INode *p=(INode *)malloc(sizeof(INode));
p=L;
L=L->next;
free(p);
p=NULL;
cout << "头删成功n";
}
}
//尾删
(需要注意特殊情况！！！容易忽略)
void ListLastDelect(LinkList &L)
{
if(L==NULL)
return;
else if (L->next==NULL)
{
free(L);
L=NULL;
}
else
//temp:尾结点的前一个结点
{
INode *temp = NULL;
INode *last = L;
while (last->next != NULL)
{
temp = last;
last = last->next;
}
free(last);
last=NULL;
temp->next = NULL;
}
}
//删除结点p
bool ListDelect(LinkList &L,INode *p)
{
if (p == NULL)
return false;
INode *q = L;
while(q->next!=p)
q=q->next;
q->next=p->next;
free(p);
p=NULL;
cout << "删除成功n";
return true;
}
//按位查找
int ListReserch(LinkList L, int i)
{
if (i<1)
return 0;
INode *p;
int j = 1;
p = L;
while (p != NULL&&j<i)	//找到i的结点
{
p = p->next;
j++;
}
int e;
e = p->data;
return e;
}
//按值查找返回指针
INode* ListFind(LinkList L, int e)
{
INode *p;
p = L;
while (p != NULL)
{
if (p->data == e)
return p;
p = p->next;
}
return NULL;
}
//单链表输出
void ListPrintf(LinkList &L)
{
INode *r;
r = L;
while (r != NULL)
{
cout << r->data <<' ';
r = r->next;
}
cout<<endl;
}
//尾插法创建
void InitList(LinkList &L)
{
int x;
INode*newnode = (LinkList)malloc(sizeof(INode));
cout << "请输入单链表中的数值：n";
cin >> x;
newnode->data = x;
newnode->next = NULL;
if (L == NULL)
{
L = newnode;
}
else
{
INode*r = L;
while (r->next!=NULL)
{
r = r->next;
}
r->next = newnode;
}
}
//判断是否为空链表
bool IsEmptyList(LinkList &L)
{
int l=Len(L);
if(l==0)
return true;
else
return false;
}
//初使化
void action1(LinkList &L)
{
cout<<"初使化长度：n";
int m;
cin>>m;
while (m--)
{
InitList(L);
}
cout<<"原始单链表：n";
ListPrintf(L);
}
//删除
void action2(LinkList &L)
{
int m;
cout<<"输入想要删除的元素：n";
cin>>m;
//测试可以选择是那种删除方式
//ListHeadDelect(L);
//ListLastDelect(L);
//删除指定结点需要先查找到结点
INode *q=ListFind(L,m);
ListDelect(L,q);
cout<<"删除结点后的单链表：n";
ListPrintf(L);
}
//查询
void action3(LinkList &L)
{
int n;
cout<<"输入想要查询的位置：n";
cin>>n;
cout<<"查询第"<<n<<"个数值为："<<ListReserch(L,n)<<endl;
}
//插入
void action4(LinkList &L)
{
int i,e;
cout<<"输入位置n";
cin>>i;
cout<<"输入数值n";
cin>>e;
//测试可以选择是那种插入方式
//ListHeadInsert(L,e);
//ListLastInsert(L,e);
ListInsert(L,i,e);
cout<<"插入数值后的单链表：n";
ListPrintf(L);
}
//可以需求选择对单链表的操作
int main()
{
LinkList L=NULL;
action1(L);
action2(L);
//action3(L);
//action4(L);
//IsEmptyList(L);
return 0;
}

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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <iostream>
using namespace std;
typedef struct INode{
int data;
struct INode *next;
}INode, *LinkList;
//单链表长度
int Len(LinkList &L)
{
INode *p=L;
int k=0;
while(p!=NULL)
k++;
return k;
}
//头插
bool ListHeadInsert(LinkList &L,int e)
{
INode *h=(INode *)malloc(sizeof(INode));
h->data=e;
h->next=L;
L=h;//令头结点变为h
cout << "头插成功n";
return true;
}
//尾插
bool ListLastInsert(LinkList &L,int e)
{
INode *s=(INode *)malloc(sizeof(INode *));
s->data=e;
s->next=NULL;
if(L==NULL)
L=s;
else
{
INode *q;
q=L;
while(q->next!=NULL)
{
q=q->next;
}
q->next=s;
}
cout << "尾插成功n";
return true;
}
//在第i个位置插入e
bool ListInsert(LinkList &L, int i, int e)
{
INode *p;
int j = 1;
p = L;
while (p != NULL&&j<i-1)	//找到i-1的结点
{
p = p->next;
j++;
}
if (p == NULL)
return false;
INode *q = (INode *)malloc(sizeof(INode));
q->data = e;
q->next = p->next;
p->next = q;
cout << "插入成功n";
return true;
}
//头删
void ListHeadDelect(LinkList &L)
{
if(L==NULL)
return;
else
{
INode *p=(INode *)malloc(sizeof(INode));
p=L;
L=L->next;
free(p);
p=NULL;
cout << "头删成功n";
}
}
//尾删
(需要注意特殊情况！！！容易忽略)
void ListLastDelect(LinkList &L)
{
if(L==NULL)
return;
else if (L->next==NULL)
{
free(L);
L=NULL;
}
else
//temp:尾结点的前一个结点
{
INode *temp = NULL;
INode *last = L;
while (last->next != NULL)
{
temp = last;
last = last->next;
}
free(last);
last=NULL;
temp->next = NULL;
}
}
//删除结点p
bool ListDelect(LinkList &L,INode *p)
{
if (p == NULL)
return false;
INode *q = L;
while(q->next!=p)
q=q->next;
q->next=p->next;
free(p);
p=NULL;
cout << "删除成功n";
return true;
}
//按位查找
int ListReserch(LinkList L, int i)
{
if (i<1)
return 0;
INode *p;
int j = 1;
p = L;
while (p != NULL&&j<i)	//找到i的结点
{
p = p->next;
j++;
}
int e;
e = p->data;
return e;
}
//按值查找返回指针
INode* ListFind(LinkList L, int e)
{
INode *p;
p = L;
while (p != NULL)
{
if (p->data == e)
return p;
p = p->next;
}
return NULL;
}
//单链表输出
void ListPrintf(LinkList &L)
{
INode *r;
r = L;
while (r != NULL)
{
cout << r->data <<' ';
r = r->next;
}
cout<<endl;
}
//尾插法创建
void InitList(LinkList &L)
{
int x;
INode*newnode = (LinkList)malloc(sizeof(INode));
cout << "请输入单链表中的数值：n";
cin >> x;
newnode->data = x;
newnode->next = NULL;
if (L == NULL)
{
L = newnode;
}
else
{
INode*r = L;
while (r->next!=NULL)
{
r = r->next;
}
r->next = newnode;
}
}
//判断是否为空链表
bool IsEmptyList(LinkList &L)
{
int l=Len(L);
if(l==0)
return true;
else
return false;
}
//初使化
void action1(LinkList &L)
{
cout<<"初使化长度：n";
int m;
cin>>m;
while (m--)
{
InitList(L);
}
cout<<"原始单链表：n";
ListPrintf(L);
}
//删除
void action2(LinkList &L)
{
int m;
cout<<"输入想要删除的元素：n";
cin>>m;
//测试可以选择是那种删除方式
//ListHeadDelect(L);
//ListLastDelect(L);
//删除指定结点需要先查找到结点
INode *q=ListFind(L,m);
ListDelect(L,q);
cout<<"删除结点后的单链表：n";
ListPrintf(L);
}
//查询
void action3(LinkList &L)
{
int n;
cout<<"输入想要查询的位置：n";
cin>>n;
cout<<"查询第"<<n<<"个数值为："<<ListReserch(L,n)<<endl;
}
//插入
void action4(LinkList &L)
{
int i,e;
cout<<"输入位置n";
cin>>i;
cout<<"输入数值n";
cin>>e;
//测试可以选择是那种插入方式
//ListHeadInsert(L,e);
//ListLastInsert(L,e);
ListInsert(L,i,e);
cout<<"插入数值后的单链表：n";
ListPrintf(L);
}
//可以需求选择对单链表的操作
int main()
{
LinkList L=NULL;
action1(L);
action2(L);
//action3(L);
//action4(L);
//IsEmptyList(L);
return 0;
}