|
?目录
?初识链表
链表的增加
链表的函数
代码细节分析
链表的搜索，删除，清除。
链表的搜索
链表的删除
链表的清除
MOOC原视频地址：C语言程序设计进阶_浙江大学_中国大学MOOC(慕课)
?初识链表
typedef struct _node{
int value;
struct _node *next;
}Node;
简单来说，一个结点（note）由两部分组成，分别是value和point。其中point指向另一结点。?
链表的增加
这个部分如果有不懂的请结合注释或者私信我哦。（其实更推荐看更下面一段代码，更加工程化。）
typedef struct _note {
int value;
struct _note *next;
}Note;
#include <stdio.h>
#include <stdlib.h>
int main() {
int number;
do {
Note* head = NULL; //假设初始为空链表
Note* last = NULL; //链表的最后
scanf_s("%d", &number);
Note* p = (Note*)malloc(sizeof(Note)); //定义出新的结点
p->value = number; //注意，此时并没有连接进链表
p->next = NULL;
if (last) {
while (last->next) { //找到最后一个结点
last = last->next; //让last等于最后结点的指针
}
last->next = p; //连接新结点
}
else {
head = p; //刚开始是空链表，先让head等于新的结点
}
} while (number != -1);
}
链表的函数
让我们来封装一下上面的函数吧！我们可以把加入新的结点作为一个函数封装。注意，这里我们新建了一个结构List，用来使传入函数的结构返回。
typedef struct _note {
int value;
struct _note* next;
}Note;
typedef struct _list {
Note* head; //在该结构里存在Note结构的指针。
}List;
void add(List* pList, int number);
#include <stdio.h>
#include <stdlib.h>
int main() {
List list; //定义结构变量。
list.head = NULL; //开始是空的链表。
int number;
do {
scanf_s("%d", &number);
if(number!=-1){
add(&list, number); //传给add函数List结构的指针。
}
} while (number != -1);
return 0;
}
void add(List* pList, int number) {
Note* last = pList->head; //初始last是List结构中指向head的指针。
Note* p = (Note*)malloc(sizeof(Note));
p->value = number;
p->next = NULL;
if (last) {
while (last->next) {
last = last->next; //指向链表中的下一个指针
}
last->next = p; //连接新结点。
}
else {
pList->head = p; //如果head=NULL，使head等于第一个结点。
}
}
代码细节分析
注意这两个语句经常在循环中使用，表示last/p指向链表中的下一个结点。
last=last->next;
p=p->next;
链表的搜索，删除，清除。
链表的搜索
好了，现在我们已经可以把新的number放入链表中，现在该想一想，我们如何输出这个链表呢？
Note* p;
for (p=list.head; p; p=p->next) { //遍历链表
printf("%d\t", p->value);
}
只需要在主函数中加入上面这一段代码就可以了。这是一种常用的遍历链表的方法。
链表的删除
搜索一个链表中的某个数，之后将其删除，如何实现呢？前面已经提到了如何搜索一个链表。不妨在这基础上在加一个指针q指向p之前的一个结点。
Note* p;
Note* q;
for (q = NULL, p = list.head; p; q = p, p = p->next) {
if (p->value == number) {
if (q) {
q->next = p->next; //q的指针指向p的下一结点。
}
list.head = p->next; //当第一个就是要删除的数字时，此时q=NULL。
free(p);
break;
}
判断边界条件的技巧：当指针变量在->的左边，此时的指针不能是NULL。此时我们无法判断q是不是NULL，需要if语句判断。
例如：第一个就是我要删除的数字，此时q是NULL，程序会出错。（野指针）
链表的清除
q等于p指针指向的结点。删除p结点。重复循环即可。
Note* p;
Note* q;
for (p = list.head; p; p = q) {
q = p->next;
free(p);
}
?
如果这篇文章对你有帮助的话，请给作者一个点赞或者关注一下，谢谢大家了！
（作者也是一边学习一边分享，如有错误欢迎指出！持续更新中......）
|