数据结构——单链表基本操作实现 (c++)_c++单链表

单链表定义

单链表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这里存储单元可以是连续的，也可以是不连续的），为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系，除了存储信息本身外还要存储一个指示其直接后继的信息（地址）.
这两部分信息组成数据元素a的存储映像称为结点，它包括两个域：存储信息的称为数据域，存储直接后继存储地址的域称为指针域，指针域中存储的信息称作指针或链.

单链表表示

可以参考下图：

三个需要理解的概念：

头指针：头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头节点；若链表没设头结点，则头指针所指结点为线性表的首元结点。

头结点：头结点是在首元结点之前附设的一个结点，该头结点指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储信息，设定头结点的目的是使链表中第一个数据(首元结点)的操作与其他数据元素的操作相同，无需进行特殊处理。

首元结点：首元结点是指链表中存储第一个数据元素a的结点。如上图所示的A。

代码实现

1.单链表存储结构和初始化操作

//单链表存储结构
struct LinkedList {
	int data;	//结点数据域（以下我用int型数据类型）
	LinkedList* next;	//结点指针域
};

//初始化操作（创建头节点）
void InitList(LinkedList*& L) {	//这里的 *& 表示对指针的引用
	L = new LinkedList;	//生成一个头节点，用头指针 L 指向头节点
	L->next = NULL;		//头指针置空（目的是为了不指向什么奇奇怪怪的地方，也为了方便对单链表基本操作实现）
}
1
2
3
4
5
6
7
8
9
10
11

1.单链表存储结构包括两个方面：一是该存储节点的数据域，二是该存储节点的指针域（用来指向直接后继结点的）.
2. 初始化的目的时为了生成一个头结点，上面代码InitList中的形参为指针的引用类型（*&）是对指针的一个引用操作。那么为什么这个地方要用引用指针？用指针不也行吗？肯定不行，这里简单表示为p1(形参) = p2(实参)，若用指针作为形参接收实参，在开辟空间 L = new LinkedList; 时，实际接收这个新开辟的空间的指针是p1而不是p2，总的来说就是我们想初始化的是实参，开辟的空间要作用于实参上就必须得用指针的引用类型.

2.前插法

//前插法（在头节点后插入 n 个结点）
void CreateList_H(LinkedList*& L, int n = 1) {	
//n 表示前插的结点数量，这里默认设置为 1
	if (n < 1){	//若传入的n小于1，出现错误
		cout << "ERROR" << endl;
		exit(0);
	}
	//逆位序插入结点
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;	//创建新结点
		cin >> p->data;
		
		//具体插入操作
		p->next = L->next; 	
		L->next = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

下图是单链表（c、d、e）前插过程，因为每次插入都在头结点后，所以为逆位序插入，插入顺序为e、d、c.

3.后插法

//后插法
void CreateList_R(LinkedList*& L, int n = 1) {
	LinkedList* r = L->next;	//创建指向尾部的指针
	while (r->next) {	//让尾指针指向链表尾部
		r = r->next;
	}
	if (n < 1) {	//若传入的n小于1，出现错误
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}		
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		
		//具体插入操作
		p->next =r->next;
		r->next = p;
		r = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

下图是单链表（a、b、c）后插过程，实现该过程需要一个尾指针 r 来指向链表尾部.

4.取值、查找和显示

//取值
void GetElem(LinkedList*& L, int i, int& e) {	
//在带头节点的单链表 L 中根据序号 i 获取元素的值，用 e 返回该值
	LinkedList* p = L->next;
	int j = 1;
	while (p && j < i) {	//p不为空 && j < i
		p = p->next;
		j++;
	}
	if (!p || j > i) {	//p为空 || i小于1
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}
	e = p->data;	//该函数形参为引用类型，所以这里的 e 改变实参也会改变
}

//查找
LinkedList* LocateElem(LinkedList*& L, int e) {	
//在带头结点的单链表 L 中查找值为 e 的元素并返回该结点地址
	LinkedList* p = L;
	while (p && p->data != e) {	//p不为空 && p数据域不等于e
		p = p->next;
	}
	return p;	//返回指针p，因为该函数返回值类型为 LinkedList* 类型
}

//显示
void ShowList(LinkedList*& L) {
	LinkedList* p = L->next;
	while (p){	//p为空时循环结束
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
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

5.插入（指定插入）

//插入
void ListInsert(LinkedList*& L, int i, int e) {	
//在带头节点的单链表 L 中第 i 个位置插入值为 e 的新结点
	LinkedList* p = L;
	int j = 1;	//用j来记录指针p向后移次数
	while (p && j < i) {	//p不为空 && j记录次数小于i
		p = p->next;
		j++;
	}
	if (!p || j > i) {	//p为空 || i大于1
		cout << "ERROR" << endl;
		exit(0);	//跳出程序
	}	
	LinkedList* s = new LinkedList;
	
	//具体插入操作
	s->data = e;
	s->next = p->next;
	p->next = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

可以参考下图：

6.删除

//删除
void ListDelete(LinkedList*& L, int i) {	
//在带头节点的单链表 L 中，删除第 i 个结点
	LinkedList* p = L;
	int j = 1;	//用j来记录指针p向后移次数
	while (p->next && j < i) {	//p->next不为空 && j<i
		p = p->next;
		j++;
	}
	if (!p->next || j > i) {	//p->next为空 || i大于1
		cout << "ERROR" << endl;
		exit(0);
	}
	
	//具体删除操作
	LinkedList* q = p->next;
	p->next = q->next;
	delete q;	//释放该段结点空间
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码源文件

下面是上诉代码集合 和 main函数测试：

#include <iostream>
using namespace std;

//单链表存储结构
struct LinkedList {
	int data;	
	LinkedList* next;	
};

//初始化操作（创建头节点）
void InitList(LinkedList*& L) {	
	L = new LinkedList;	
	L->next = NULL;		
}

//前插法（在头节点后插入 n 个结点）
void CreateList_H(LinkedList*& L, int n = 1) {	
	if (n < 1){	
		cout << "ERROR" << endl;
		exit(0);
	}
	//逆位序插入结点
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		p->next = L->next; 
		L->next = p;
	}
}

//后插法
void CreateList_R(LinkedList*& L, int n = 1) {
	LinkedList* r = L->next;	
	while (r->next) {	
		r = r->next;
	}
	if (n < 1) {	
		cout << "ERROR" << endl;
		exit(0);	
	}		
	for (int i = 0; i < n; i++) {
		LinkedList* p = new LinkedList;
		cin >> p->data;
		p->next =r->next;
		r->next = p;
		r = p;
	}
}

//取值
void GetElem(LinkedList*& L, int i, int& e) {	
	LinkedList* p = L->next;
	int j = 1;
	while (p && j < i) {	
		p = p->next;
		j++;
	}
	if (!p || j > i) {	
		cout << "ERROR" << endl;
		exit(0);
	}
	e = p->data;	
}

//查找
LinkedList* LocateElem(LinkedList*& L, int e) {	
	LinkedList* p = L;
	while (p && p->data != e) {	
		p = p->next;
	}
	return p;	
}

//插入
void ListInsert(LinkedList*& L, int i, int e) {	
	LinkedList* p = L;
	int j = 1;
	while (p && j < i) {	
		p = p->next;
		j++;
	}
	if (!p || j > i) {
		cout << "ERROR" << endl;
		exit(0);
	}
	LinkedList* s = new LinkedList;
	s->data = e;
	s->next = p->next;
	p->next = s;
}

//删除
void ListDelete(LinkedList*& L, int i) {	
	LinkedList* p = L;
	int j = 1;
	while (p->next && j < i) {
		p = p->next;
		j++;
	}
	if (!p->next || j > i) {
		cout << "ERROR" << endl;
		exit(0);
	}
	LinkedList* q = p->next;
	p->next = q->next;
	delete q;	
}

//显示
void ShowList(LinkedList*& L) {
	LinkedList* p = L->next;
	while (p){	
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}


int main() {
	//创建头指针
	LinkedList* L;

	//初始化（创建头节点，让头指针和头节点关联）
	InitList(L);

	cout << "前插：" << endl;
	CreateList_H(L, 2);
	ShowList(L);

	cout << "后插：" << endl;
	CreateList_R(L, 3);
	ShowList(L);
	
	cout << "插入元素：" << endl;
	ListInsert(L, 3, 9);
	ShowList(L);

	cout << "删除元素：" << endl;
	ListDelete(L, 2);
	ShowList(L);


	system("pause");
	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

下面是运行截图：