1，为什么要用到链表
数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。
我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。
链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。
2，单向链表
单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。
如图所示：
上图还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。
3，单向链表程序的实现
（1），链表节点的数据结构定义
|
1
2
3
4
5
|
struct node { int num; struct node *p; } ; |
在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。
在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。
（2），链表的创建、输出步骤
单链表的创建过程有以下几步：
1 ) 定义链表的数据结构;
2 ) 创建一个空表;
3 ) 利用malloc ( )函数向系统申请分配一个节点;
4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
节点接到表尾;
5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
单链表的输出过程有以下几步
1) 找到表头;
2) 若是非空表，输出节点的值成员，是空表则退出;
3 ) 跟踪链表的增长，即找到下一个节点的地址;
4) 转到2 ).
（3），程序代码例子：
创建一个存放正整数单链表，输入0或小于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
|
#include <stdlib.h> /*含ma l l o c ( ) 的头文件*/ #include <stdio.h> //①定义链表数据结构 struct node { int num; struct node *next; }; //函数声明 struct node *creat(); void print(); main( ) { struct node *head; head=NULL; //②建一个空表 head=creat(head);/*创建单链表*/ print(head);/*打印单链表*/} /******************************************/struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/{ struct node*p1,*p2; int i=1; //③利用malloc ( )函数向系统申请分配一个节点 p1=p2=(struct node*)malloc(sizeof(struct node));/*新节点*/ printf("请输入值，值小于等于0结束，值存放地址为：p1_ADDR= %d\n",p1); scanf("%d",&p1->num);/*输入节点的值*/ p1->next=NULL;/*将新节点的指针置为空*/ while(p1->num>0)/*输入节点的数值大于0*/ { //④将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾; if(head==NULL) head=p1;/*空表，接入表头*/ else p2->next=p1;/*非空表，接到表尾*/ p2=p1; p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/ i=i+1; printf("请输入值，值小于等于0结束，值存放地址为：p%d_ADDR= %d\n",i,p2); scanf("%d",&p1->num);/*输入节点的值*///⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束; } //==============原来程序更正部分：（多谢@daling_datou提醒）================================ free(p1); //申请到的没录入，所以释放掉 p1=NULL; //使指向空 p2->next = NULL; //到表尾了，指向空 printf("链表输入结束（END）\n"); //============================================== return head;/*返回链表的头指针*/} /*******************************************/void print(struct node*head)/*出以head为头的链表各节点的值*/{ struct node *temp; temp=head;/*取得链表的头指针*/ printf("\n\n\n链表存入的值为：\n"); while(temp!=NULL)/*只要是非空表*/ { printf("%6d\n",temp->num);/*输出链表节点的值*/ temp=temp->next;/*跟踪链表增长*/ } printf("链表打印结束!!"); } |
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。
程序执行流程：
4，单链表操作基础示例
|
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
|
#include <stdio.h> #include <malloc.h> #define LEN sizeof(NODE) typedef struct _NODE//节点声明 { int val; struct _NODE* next; } NODE, *PNODE; void print(PNODE head){//打印所有节点 while (head) { printf("%3d",head->val); head = head->next; } printf("\n"); } void insertHead(PNODE *pHead, int val){//头插法 PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = *pHead; *pHead = n; } void insertTail(PNODE *pHead, int val){//尾插法 PNODE t = *pHead; PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = NULL; if (*pHead == NULL) { n->next = *pHead; *pHead = n; }else{ while (t->next) { t = t->next; } t->next = n; } } void deleteHead(PNODE *pHead){//删除头 if (*pHead == NULL) { return; } else { PNODE t = *pHead; *pHead = (*pHead)->next; free(t); } } void deleteTail(PNODE *pHead){//删除尾 PNODE t = *pHead; if (t == NULL) { return; } else if (t->next == NULL) { free(t); *pHead = NULL; } else{ while (t->next->next != NULL) { t = t->next; } free(t->next); t->next = NULL; } } PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点 while (head != NULL && head->val != val) { head = head->next; } return head; } PNODE findByIndex(PNODE head, int index){//根据索引找节点 if (index == 1) { return head; } else { int c = 1; while (head != NULL && index != c) { head = head->next; c++; } } return head; } void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点 if (index == 1) { insertHead(pHead, val); } else { PNODE t = findByIndex(*pHead,index - 1); if (t == NULL) { return; } else { PNODE n = t->next; t->next = (PNODE)malloc(LEN); t->next->next = n; t->next->val = val; } } } void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点 { if (index == 1) { deleteHead(pHead); } else { PNODE t= findByIndex(*pHead, index - 1); if (t == NULL || t->next == NULL) { return; }else{ PNODE n = t->next->next; free(t->next); t->next = n; } } } void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的 { if (*pHead == NULL)//如果空表退出 { return; } else { if ((*pHead)->val == val)//如果第一个就是，删头 { deleteHead(pHead); } else { PNODE t = *pHead; while (t->next != NULL && t->next->val != val)//遍历，若t的next为空或者next是要找的节点则退出 { t = t->next; } if (t->next)//如果t指向要找的结点的上一个节点 { PNODE n = t->next->next;//删除要找的结点 free(t->next); t->next = n; } } } } void clear(PNODE *pHead)//清除链表 { while ((*pHead) != NULL) { deleteHead(pHead);//从头删除 } } void main() { PNODE head = NULL; insertTail(&head,1); deleteHead(&head); insertTail(&head,2); insertTail(&head,3); insertTail(&head,4); insertTail(&head,5); insertTail(&head,6); print(head); insertByIndex(&head, 6, 9); print(head); //deleteByIndex(&head,3); deleteByVal(&head, 2); print(head); clear(&head); print(head); insertByIndex(&head,1,12); print(head); } |
