【看课必备】MOOC C语言进阶——翁恺链表笔记

初识链表

链表的增加

链表的函数

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);
	}

如果这篇文章对你有帮助的话，请给作者一个点赞或者关注一下，谢谢大家了！

（作者也是一边学习一边分享，如有错误欢迎指出！持续更新中......）