插入
头插法
首先需要知道 c 语言的值传递机制：把一个变量传给函数时，函数拿到的只是这个变量的一个 副本，在函数中对这个变量进行涂涂改改，并不影响 原件
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
| # define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_s{
// 数据域
int data;
//指针域
struct node_s* next;
}node_t;
//传入的是 node_t 的地址
node_t* head_insert(node_t* phead, int data) {
// 1.在内存的堆空间中给新结点申请内存 && 初始化
node_t* pnew_node = (node_t *)malloc(sizeof(node_t));
pnew_node->data = data;
pnew_node->next = NULL;
// 2.插入
pnew_node ->next = phead;
phead = pnew_node;
//把新节点的地址甩回去，否则主函数中phead中存的地址不会变
return pnew_node;
}
int main() {
node_t* phead = NULL; // phead是一个指向node_t数据类型的指针
phead = head_insert(phead, 1); // &phead 是将指针再取地址
phead = head_insert(phead, 2);
phead = head_insert(phead, 3);
node_t* temp = phead;
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
return 0;
}
|
尾插法
首先搞清楚 指针 、 解引用、取地址 之间的关系：
指针变量 存储的是一个地址（就像是一个写着地址的纸条）
*解引用 就是 根据 指针变量中存的地址 去访问该地址处的数据（就像是要知道纸条上地址处到底存了什么，远程操控，见字如面）
对一级指针取地址，得到的就是二级指针
1
2
3
4
5
6
7
8
9
10
| node_t* tail_insert(node_t* ptail, int data) {
// 1.在内存的堆空间中给新结点申请内存 && 初始化
node_t* pnew_node = (node_t*)malloc(sizeof(node_t));
pnew_node->data = data;
pnew_node->next = NULL;
// 分情况讨论
ptail->next = pnew_node;
return pnew_node;
}
|
头插与尾插：
代码中包含头结点
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
| # define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_s {
// 数据域
int data;
//指针域
struct node_s* next;
}node_t;
//头插法：传入的是 node_t 的地址
void head_insert(node_t* L1, int data) {
// 1.在内存的堆空间中给新结点申请内存 && 初始化
node_t* pnew_node = (node_t*)malloc(sizeof(node_t));
pnew_node->data = data;
// 2.插入
pnew_node->next = L1 ->next;
L1->next = pnew_node;
}
//尾插法
//传入的是 node_t 地址
node_t* tail_insert(node_t* ptail, int data) {
// 1.在内存的堆空间中给新结点申请内存 && 初始化
node_t* pnew_node = (node_t*)malloc(sizeof(node_t));
pnew_node->data = data;
pnew_node->next = NULL;
// 分情况讨论
ptail->next = pnew_node;
return pnew_node;
}
// 打印链表
void print_list(node_t* L) {
L = L->next;
while (L != NULL) {
printf("%d ", L->data);
L = L->next;
if (L != NULL) {
printf(" ");
}
}
printf("\n");
}
int main() {
int i = 0;
//--头插--
// 创建头结点L1
node_t* L1 = (node_t*)malloc(sizeof(node_t));
L1->next = NULL;
while (scanf("%d", &i) != EOF && i!=9999) {
head_insert(L1, i);
}
//---尾插---
//创建头结点L2
node_t* L2 = (node_t*)malloc(sizeof(node_t));
L2->next = NULL;
node_t* ptail = L2;
while (scanf("%d", &i) != EOF && i != 9999) {
ptail= tail_insert(ptail, i);
}
print_list(L1);
print_list(L2);
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
| # define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 需求：
// 1.在指定位置插入
// 2.在指定位置删除
typedef struct node_s {
int data;
struct node_s* next;
}node_t;
//初始化
node_t* _Init(node_t* ptail, int data) {
node_t* new_node = (node_t*)malloc(sizeof(node_t));
new_node->data = data;
new_node->next = NULL;
ptail->next = new_node;
return new_node;
}
//打印
void print_list(node_t* L) {
L = L->next;
while (L != NULL) {
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
//在指定 位置2 插入 i
void insert_i(node_t* L1, int pos, int i) {
node_t* pre = L1;
//找到前驱节点
for (int k = 1; k < pos && pre != NULL; k++) {
pre = pre->next;
}
node_t* new_node = (node_t*)malloc(sizeof(node_t));
new_node->data = i;
new_node->next = pre->next;
pre->next = new_node;
}
//
void delete_pos(node_t* L1, int pos) {
if (pos < 1) {
printf("false\n");
return;
}
node_t* pre = L1;
for (int i = 1; i < pos && pre->next != NULL; i++) {
pre = pre->next;
}
if (pre->next == NULL) {
printf("false\n");
return;
}
node_t* pdelete = pre->next;
pre->next = pdelete->next;
free(pdelete);
print_list(L1);
}
int main() {
//申请一个空白头节点
node_t* L1 = (node_t*)malloc(sizeof(node_t));
L1->next = NULL;
node_t* ptail = L1;
ptail = _Init(ptail, 1);
ptail = _Init(ptail, 2);
ptail = _Init(ptail, 3);
/*print_list(L1);*/
//在指定位置2插入指定数i
int i = 0;
scanf("%d", &i);
insert_i(L1, 2, i);
print_list(L1);
//在指定位置 pos 删除结点
int pos = 0;
scanf("%d", &pos);
delete_pos(L1, pos);
return 0;
}
|