1. 链表基础知识

1.1 定义：

1. n个节点离散分配
2. 彼此通过指针相连
3. 每个节点只有一个前驱节点，每个节点只有一个后续节点
4. 首节点没有前驱节点，尾节点没有后续节点

1.2 专业术语：

1. 首节点：第一个有效节点
2. 尾节点：最后一个有效节点
3. 头结点：头结点的数据类型和首节点数据类型一样
   第一个有效节点之前的那个节点；
   头结点并不存放有效数据
   加结点的目的主要是为了方便对链表的操作
4. 头指针：指向头结点的指针变量
5. 尾指针：指向尾节点的指针变量

1.3 确定一个链表需要几个参数

1. 只需要一个参数：头指针
2. 因为我们通过头指针可以推算出链表的其他所有信息

1.4 分类

1. 单链表
2. 双链表：每一个节点有两个指针域
3. 循环链表：能通过任何一个节点找到其他所有的节点
4. 非循环链表

2. 链表的定义和设计的相关操作

1. 链表的定义
2. 链表的遍历输出
3. 判断链表是否为空
4. 确定链表的长度
5. 对链表进行排序（冒泡排序）
6. 在链表的指定位置前插入节点
7. 删除指定位置的节点

3. 具体代码实现

#include
using namespace std;


struct Node
{
	int data;
	Node* pNext;
};

Node* create_list(void);
void traverse_list(Node* pHead);
bool judge_empty(Node* pHead);
int length_list(Node* pHead);
void sort_list(Node* pHead);
bool plug_list(Node* pHead, int pos, int val);
bool delete_list(Node* pHead, int pos, int* pVal);



int main()
{
	Node* pHead;
	int val;

	pHead = create_list();					// 功能：创建一个非循环单链表，并将该链表的头节点的地址赋给pHead;


	traverse_list(pHead);					// 遍历



	//if (judge_empty(pHead))
	//{
	//	cout << "链表为空！" << endl;
	//}
	//else
	//{
	//	cout << "链表不为空！" << endl;
	//}

	//int len = length_list(pHead);
	//cout << "链表的长度是：" << len << endl;

	//sort_list(pHead);
	//traverse_list(pHead);

	plug_list(pHead, 4, 33);
	traverse_list(pHead);

	if (delete_list(pHead, 4, &val))
	{
		cout << "删除成功，删除的元素是：" << val << endl;
	}
	else
	{
		cout << "删除失败！" << endl;
	}
	traverse_list(pHead);



	system("pause");
	return 0;
}


Node* create_list(void)
{
	int len;				// 用来存放有效节点的个数
	int i;					
	int val;				// 用来临时存放用户输入的节点的值

	Node* pHead = new(Node);
	if (NULL == pHead)
	{
		cout << "分配失败，程序终止！" << endl;
		exit(-1);
	}
	Node* pTail = pHead;
	pTail->pNext = NULL;

	cout << "请输入您需要生成的链表节点的个数：len = " << endl;
	cin >> len;

	for (i = 0; i < len; i++)
	{
		cout << "请输入第" << i + 1 << "个节点的值：" << endl;
		cin >> val;

		Node* pNew = new(Node);
		if (NULL == pNew)
		{
			cout << "分配失败，程序终止！" << endl;
			exit(-1);
		}
		pNew->data = val;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}

	return pHead;

}

void traverse_list(Node* pHead)
{
	Node* p = pHead->pNext;

	cout << "遍历的链表内容如下：" << endl;
	while (p != NULL)
	{
		cout << p->data<<"\t";
		p = p->pNext;
	}
	cout << endl;
	return;
}

bool judge_empty(Node* pHead)
{
	if (pHead->pNext == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int length_list(Node* pHead)
{
	Node* p = pHead->pNext;
	int len = 0;

	while (NULL != p)
	{
		len++;
		p = p->pNext;
	}
	return len;
}

// 在pHead所指向的链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值是从1开始的
bool plug_list(Node* pHead, int pos, int val)
{
	int i = 0;
	Node* p = pHead;

	while (NULL != p && i < pos - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > pos - 1 || NULL == p)
	{
		return false;
	}

	Node* pNew = new(Node);
	if (NULL == pNew)
	{
		cout << "动态内存分配失败！" << endl;
		exit(-1);
	}
	pNew->data = val;
	Node* q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;

	return true;
}


bool delete_list(Node * pHead, int pos, int * pVal)
{
	int i = 0;
	Node* p = pHead;

	while (NULL != p->pNext && i < pos - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > pos - 1 || NULL == p->pNext)
	{
		return false;
	}

	Node* q = p->pNext;
	*pVal = q->data;

	// 删除p节点后面的节点
	p->pNext = p->pNext->pNext;
	delete q;
	q = NULL;

	return true;
}

void sort_list(Node * pHead)
{
	int i, j;
	int len = length_list(pHead);
	Node* p;
	Node* q;

	// 冒泡排序实现
	for (i = 0; i < len - 1; i++)
	{
		for (j = 0, q = pHead->pNext; j < len - i - 1; j++,q = q->pNext)
		{
			if (q->data > q->pNext->data)
			{
				int temp = q->data;
				q->data = q->pNext->data;
				q->pNext->data = temp;
			}
		}
	}
}


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