数据结构（离散 | 链式存储--链表）_前驱结点和后继结点是什么

定义

n个结点离散分配，彼此通过指针相连，每个结点只有一个前驱结点，每个结点只有一个后继结点，首结点没有前驱结点，尾结点没有后继结点。

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

什么是结点：结点就是为数据元素开辟的内存空间，他包括两部分内容，一是该数据元素本身的内容，成为数据域，二是指向该数据元素直接后继数据元素的指针内容，成为指针域。
什么是前驱结点？什么是后继结点？：前驱结点就是，该结点的前面一个结点，后继结点就是该结点的后面一个结点。

如果希望通过一个函数来对链表进行处理，我们至少需要接收链表的那些参数：只需要一个参数（头指针），因为我们通过头指针可以推算出链表的其他所有信息。

分类

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

算法

（1）遍历
（2）查找
（3）清空
（4）销毁
（5）求长度
（6）排序
（7）插入结点

有两种方法可以实现在p结点后面插入一个新结点q
（一）

	r = p->Next;  
	p->Next = q;  
    q->Next = r;
1
2
3

首先定义一个临时指针变量r，用来存放p的指针域的数据，再把指针变量q的地址赋给p的指针域，最后把指针变量r的地址赋给q的指针域。
（二）

	q->Next = p->Next; 
    p->Next = q;
1
2

首先把p的指针域赋给q的指针域，然后把q的地址赋给p的指针域
（8）删除结点

把p的指针域指向删除元素的下一个地址就行了

	r = p->Next;
	p->Next = p->Next->Next;
	free(r);
1
2
3

注意：不能直接改变他的指向，这样的话会导致内存泄露，所有我们要把删除的内存手动释放。

算法：狭义的算法是与数据的存储方式密切相关，广义的算法是与数据的存储方式无关
泛型：利用某种技术达到的效果是不同的存储方式，执行的操作是一样的。

非循环单链表实现

# include <stdio.h>
# include <stdlib.h>

typedef struct Node {
	int data; // 数据域 
	struct Node * pNext; // 指针域 
}NODE, *PNODE;

//函数声明
PNODE create_list(void);
void traverse_list(PNODE);
bool is_empty(PNODE);
int length_list(PNODE);
bool insert_list(PNODE, int, int);
bool delete_list(PNODE, int, int *);
void sort_list(PNODE);

 
int main(void)
{
	int val;
	PNODE pHead = NULL;  // 等价于 struct Node * pHead = NULL;
	
	pHead = create_list(); // 创建一个非循环单链表，并将该链表的头结点的地址赋给pHead 
	traverse_list(pHead);  //遍历结点 
	
//	insert_list(pHead, 4, 33); 

	if (delete_list(pHead, 4, &val)) {
		printf("删除成功，您删除的元素是：%d\n", val);
	} else {
		printf("删除失败！您删除的元素不存在\n");
	}
	
	traverse_list(pHead);
	
/*	int len = length_list(pHead);
	printf("这个链表的长度为：%d\n", len);
	
	sort_list(pHead);
	traverse_list(pHead);
	
	if (is_empty(pHead))
		printf("链表为空！\n");
	else
		printf("链表不为空！\n"); */
	
	return 0; 
}

/*
	创建一个链表，并返回该链表的头指针 
*/ 
PNODE create_list(void)
{
	int len; // 存放有效结点的个数 
	int i;
	int val; // 临时存放用户输入的结点值 
	
	PNODE pHead = (PNODE)malloc(sizeof(NODE)); //分配了一个不存放数据的头结点， pHead为头指针 
	if (NULL == pHead) {
		printf("分配失败，程序终止！\n");
		exit(-1);
	}
	
	PNODE pTail = pHead; // 尾节点，用于指向链表的最后面 
	pTail->pNext = NULL;
	
	printf("请输入您需要生成的链表结点的个数：len = ");
	scanf("%d", &len);
	
	for (i=0; i<len; ++i) {
		printf("请输入第%d个结点的值：", i+1);
		scanf("%d", &val);
		
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew) {
			printf("分配失败，程序终止！\n");
			exit(-1);
		}
		pNew->data = val;
/*		pHead->pNext = pNew;
		pNew->pNext = NULL;   */
		
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	
	return pHead; 
}

/*
	遍历链表，参数为链表的头指针 
*/ 
void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	
	while(NULL != p) {
		printf("%d ", p->data);
		p = p->pNext; //指向下一个结点 
	}
	printf("\n");
	
	return;
}

/*
	判断链表是否为空，参数为链表头指针，返回一个bool类型的值
	true：为空，false：不为空 
*/ 
bool is_empty(PNODE pHead)
{
	if (NULL == pHead->pNext)
		return true;
	else
		return false;
}

/*
	返回链表的长度，参数为头指针 
*/
int length_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	int len = 0;
	
	while(NULL != p)
	{
		++len;
		p = p->pNext;
	}
	
	return len;
}

/*
	给链表排序 
*/ 
void sort_list(PNODE pHead)
{
	int i, j, t, len = length_list(pHead);
	PNODE p, q;
	
	for (i=0, p=pHead->pNext; i<len-1; ++i, p=p->pNext) {
		for (j=i+1, q=p->pNext; j<len; ++j, q=q->pNext) {
			if (p->data > q->data) {
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
	
	return;
}

/*
	在pHead所指向链表的第pos个结点的前面插入一个新的结点，该结点的值是val,并且pos的值从1开始 
*/ 
bool insert_list(PNODE pHead, int pos, int val)
{
	int i = 0;
	PNODE p = pHead;
	
	while (NULL != p && i<pos-1) { //防止插入结点的位置超出链表，并且把p的位置确定在pos-1的位置上 
		p = p->pNext;
		++i;
	}
	
	if (i>pos-1 || NULL == p)  
		return false;
		
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew) {
		printf("动态内存分配失败！\n");
		exit(-1);
	} 
	
	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	
	return true;
}
/*
	 删除指定位置的结点，pos从1开始，并且把删除元素的值返回 
*/
bool delete_list(PNODE pHead, int pos, int *pVal)
{
	int i = 0;
	PNODE p = pHead;
	
	while (NULL != p->pNext && i<pos-1) {
		p = p->pNext;
		++i;
	}
	
	if (i>pos-1 || NULL==p->pNext)
		return false;
	
	PNODE q = p->pNext; 
	*pVal = q->data; // 保存要删除结点的数据 
	
	p->pNext = p->pNext->pNext; // 删除p结点后面的结点 
	free(q); // 释放掉删除结点的内存 
	q = NULL;
}
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

链表的优缺点
优点：空间没限制，插入删除元素快
确定：存取速度慢