一：单链表介绍
为什么需要链表？
我们在使用数组存放数据是非常方便，但是由于数组的长度是固定的，所以当存储不同的元素数量时，就很容易出现问题。如果向数组中添加的数量大于数组大小时候，信息无法完全被保存。所以我们需要另一种存储方式来存储数据，其中存储的元素的个数不受限制。这种存储方式就是链表。
链表结构示意
链表的基础知识：
每一个结点包含数据域和指针域：
数据域：存放用户需要的数据信息
指针域：指向下一个结点的地址
头指针：head就是头指针变量，我们把指向第一个结点的指针成为头指针
（无论链表是不是空，头指针是必不可少的）
头结点：第一个结点前可以虚加一个头结点，头指针指向头结点，头结点的指针域（head->next）指向第一个实际有效的结点（即首元结点），头结点的数据域可以不使用，在单链表中可以不添加头结点
首元结点：第一个实际有效的结点
链表是环环相扣的，head头指针指向头结点，头结点指向首元结点，首元结点指向第二个结点……直到最后的结点。
二：单链表的建立
单链表的建立即从无到有创建一个链表，一个一个的分配结点的储存空间，然后输出每一个结点的数据域，然后建立结点之间的关系。
单链表的建立可以分为两种方法，（1）头插法，（2）尾插法(更易理解)
头插法
即在单链表的头部插入新的结点的方法成为头插法。
数据读入顺序和链表的结点顺序正好相反。
==图解：==
结点的结构体类型定义如下：
1
2
3
4
5
6
| struct Student
{
char name[100];
int number;
struct Student *next;
};
|
头插法创建链表的函数代码如下：
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
| struct Student* Create()
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student));
Head->next = NULL;
struct Student *s;
int num;
char a[20];
while(1)
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Stduent *)malloc(sizeof(struct Student));
s->number = num;
strcpy(s->name,a);
s->next = Head->next;
Head->next = s;
}
return Head;
}
|
==运行结果==：
倒序输出
==步骤==：
1.对头指针进行初始化，对其开辟动态空间，并且将头结点的指针域置空(顺序不要弄反)
2.定义指针变量s,用来指向新创建的结点
3.循环，在循环中开辟s（新结点）的动态空间，并赋予新结点数据域的信息
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
| struct Student *Creat()
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student));
Head->next = NULL;
struct Student *r,*s;
r = Head;
int num;
char a[20];
while(1)
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Student *)malloc(sizeof(struct Student));
strcpy(s->name ,a);
s->number = num;
r->next = s;
r = s;
}
s->next = NULL;
return Head;
}
|
正序输出
==运行结果==：
相较于头插法创立链表，尾插法更易于结合图解理解
==步骤注意点==：
1.在空链表时候，r指针指向头结点
2.尾插法的关键两行代码也不可以互相调换顺序，调换顺序的结果并不会循环输出，而是无法读取存储的信息，即输入了5个姓名，输出0个信息
3.注意的是，在循环结束时，新结点的指针域一定要指向空
三：单链表的遍历
==代码实现==：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void print(struct Student *Head)
{
struct Student *Temp = Head->next ;
printf("****学生信息如下*****\n");
while(Temp!=NULL)
{
printf("姓名: %s\n",Temp->name );
printf("学号: %d\n",Temp->number );
printf("\n");
Temp = Temp->next ;
}
}
|
==步骤注意点==：
1.定义临时指针变量Temp指向首元结点
2.循环输出
3.关键：每输出一个结点的内容，就移动Temp指针到下一个结点的地址，如果是最后一个结点，指针指向NULL，循环结束
四：单链表结点数目判断
==代码实现==:
1
2
3
4
5
6
7
8
9
10
11
12
| int length(struct Student *Head)
{
struct Student *p = Head->next ;
int iCount = 0;
while(p!=NULL)
{
iCount++;
p = p->next ;
}
return iCount;
}
|
==运行结果==：
==步骤注意点==:
定义iCount计数器，每移动一次p指针且p指向不为空，iCount++;
五：单链表的插入
链表的插入，有三种方式，可以从链表的头部插入，可以从链表的尾部插入，也可以在指定位置进行插入。
链表头插入
==图解==：
==代码实现==：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void insert(struct Student *Head)
{
struct Student *s;
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
s->next = Head->next ;
Head->next = s;
}
|
==步骤注意点==：
1.首先为插入的新结点分配内存
2.首先将新结点的指针指向链表的首元结点(s->next = Head->next)
3.将头结点的指针指向新结点(Head->next = s)
任意结点插入
==图解==：
==代码实现==：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void insert(struct Student *Head,int i)
{
struct Student *p = Head;
struct Student *s;
int j = 0;
while(j<i-1 && p != NULL)
{
p = p->next ;
j++;
}
if(p != NULL)
{
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
s->next = p->next ;
p->next = s;
}
}
|
==步骤注意点==:
1.首先找到链表第i-1个结点的地址p，如果存在，则在i-1后面插入第i个结点
2.为插入的新结点分配空间
3.注意插入的两行代码联系图解理解
链表尾部插入
==图解==：
==代码实现==：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void insert(struct Student *Head)
{
struct Student *p,*s;
p = Head;
while(p && p->next )
{
p = p->next ;
}
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
p->next = s;
s->next = NULL;
}
|
（尾部插入较好理解）
==步骤注意点==：
1.首先找到尾结点，即循环中的条件，每一次p指针移动到下一个结点的地址
2.插入时为新插入的结点分配空间
3.尾部插入的两行代码联系图解理解，新结点指针指向空
六：单链表的删除
==图解==：
==代码实现==：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void Delete(struct Student *Head,int pos)
{
int j = 1;
struct Student *p,*q;
p = Head;
while(j < pos && p)
{
j++;
p = p->next ;
}
if(p== NULL || p->next == NULL)
{
printf("ERROR!\n");
}
else
{
q = p->next ;
p->next = q->next ;
free(q);
}
}
|
==运行结果==:
==步骤注意点==：
1.pos表示的是需要删除结点的位置，定义j用来控制循环次数
2.定义指针q和p，利用循环找到要删除结点之前的结点p，然后让q指向准备删除的结点即(q = p->next)
3.连接删除结点两边的结点(p->next = q->next)
4.用free(q)释放q指向的内存空间达到删除的目的
七 ：单链表的查询
==代码实现==：
相当于遍历查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| struct Student *search(struct Student *Head,char name[])
{
struct Student *p = Head->next ;
while(p!=NULL)
{
if(strcmp(p->name ,name) != 0)
{
p = p->next ;
}
else
{
break;
}
}
if(p == NULL)
{
printf("没有查到该学生的信息\n");
}
return p;
}
|
==步骤注意点==：
1.定义指针变量p，使其从首元结点开始到链表结束
2.利用字符串函数strcmp来查询
增删改查完整代码如下：
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
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Student
{
int number;
char name[20];
struct Student *next;
};
struct Student *Creat()
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student));
Head->next = NULL;
struct Student *r,*s;
r = Head;
int num;
char a[20];
while(1)
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Student *)malloc(sizeof(struct Student));
strcpy(s->name ,a);
s->number = num;
r->next = s;
r = s;
}
s->next = NULL;
return Head;
}
int length(struct Student *Head)
{
struct Student *p = Head->next ;
int iCount = 0;
while(p!=NULL)
{
iCount++;
p = p->next ;
}
return iCount;
}
void insert(struct Student *Head)
{
struct Student *p,*s;
p = Head;
while(p && p->next )
{
p = p->next ;
}
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
p->next = s;
s->next = NULL;
}
void Delete(struct Student *Head,int pos)
{
int j = 1;
struct Student *p,*q;
p = Head;
while(j < pos && p)
{
j++;
p = p->next ;
}
if(p== NULL || p->next == NULL)
{
printf("ERROR!\n");
}
else
{
q = p->next ;
p->next = q->next ;
free(q);
}
}
void print(struct Student *Head)
{
struct Student *Temp = Head->next ;
printf("****学生信息如下*****\n");
while(Temp!=NULL)
{
printf("姓名: %s\n",Temp->name );
printf("学号: %d\n",Temp->number );
printf("\n");
Temp = Temp->next ;
}
}
struct Student *search(struct Student *Head,char name[])
{
struct Student *p = Head->next ;
while(p!=NULL)
{
if(strcmp(p->name ,name) != 0)
{
p = p->next ;
}
else
{
break;
}
}
if(p == NULL)
{
printf("没有查到该学生的信息\n");
}
return p;
}
int main()
{
int n;
struct Student *Head;
Head = Creat();
print(Head);
printf("一共有%d个学生信息\n",length(Head));
insert(Head);
print(Head);
printf("please input the delete the number:\n");
scanf("%d",&n);
Delete(Head,n);
print(Head);
char name[20];
printf("please input the search name:\n");
scanf("%s",&name);
struct Student *p = search(Head,name);
printf("***查询信息如下:****\n");
printf("姓名:%s\n",p->name );
printf("学号:%d\n",p->number );
}
|
