vlambda博客
学习文章列表

好久没更新了，因为我太懒了

今天我们介绍链表。

当然，前提是你必须要懂得什么是结构体，以及知道如何分配内存(malloc)

当然不知道也没关系，逻辑上我还是会帮你理清楚的。

讲链表之前，我们需要先回忆一下数组。

比如这么一个数组：

float a[3] = {1, 2, 3};

那么，这个数组有三个数：1， 2， 3。

通过之前的学习我们知道，假设数组的数据是无序的，我们也依然可以对它进行排序。

但，假设我们有一个新的数字：1.5

请问我们怎么放进去？

(不考虑数据类型)这个数组的大小只有3个float的字节，而我们想把1.5放到数组里面。让a[]存储4个float字节。请问能做到吗？

显而易见，做不到。

试想一下，一个书架最多只能放三本书，你想把第四本书插进去，能做到吗？

肯定做不到。

当然，如果你是书架的主人，你也许会买一个能放4本书的书架。这样，就能把第四本书插进去。

所以在数组里面，我们需要重新声明一个数组。然后将之前数组里面的数据存进去，并且把第4个数据插进去。

这或许是个不错的办法。但如果过了段时间，你又有第5本书了，于是你又要买一个新的书架。随后的第6本，第7本……买书架的钱比买书的钱还多。

如果我们一直修改数组的大小，那么就会造成大量的内存被浪费。这肯定是不好的事。

一个正常的人，都不会每买一本书，都换一个书架。那么他会怎么做？

买一个大一点的书架

所以对于数据而言，我们也可以声明一个大一点的数组

float[200]

直接存放200个数据。

问题解决？

当然没有！试想一下，当你有好几百本书，你要想其中插入一本书。你必须把后面的书都诺一位。假设你要插入到第一本书的前面，那意味着你要把后面几百本书都要挪一个位置！

用数组进行这个操作，过程可是相当麻烦的。

看来参考书架无法解决我们的问题。

也许我们应该换个思路？

此时不妨想一想，我们要在一堆数据中插入一个数据。这件事到底怎么做？

如图所示，我们需要让原来的2号位置变成3号位置，3号位置变成4号位置。而2号位置则插入了新的数据。

那么在这个过程中，原来的2号位是2，它的下一位是3。改变了以后，3号位的2下一位依然是3。

但是原来的1号位是1，它的下一位是2，而改变以后，1号位是1但下一位却变成了1.5

所以我们可以看到，插入的本质就是改变"下一位"！，没有进行修改的地方，其"下一位"的数据不变。

可是，如何确定"下一位"呢？

这就是在数组当中，寻找下一位的方法。

所以我们完全不需要把数据这样线性的排列。我们完全可以告诉这个数据，你的下一位不是你的"邻居"，你的下一位，我来告诉你。

如果我们告诉1号位的数据，你的"下一位"不是61FF20，而是87FC30。告诉2号位，你的"下一位"不是87FC34,而是313FE1……

这虽然让数据存储的空间不再连续，但确实为我们省了不少的事情！

这个时候，如果我们需要插入一个数据，我们不需要经过其他数据的同意，我们只需要改变先前一个数的"下一位"。

比如我们要在1.5和2之间插入一个1.75

如法炮制，我们可以进行插入，我们同样也可以进行删除。

我们只需要删除一个数据，并且让前一个数的"下一位"指向下一个数。

比如我们要删除2

这样，我们可以用最方便的方式修改数据。

而这，就是链表！

(如果你不知道的话，结构体是可以自己DIY里面的参数，你可以声明一个数据，还可以声明一个结构体类型的指针！)

同时我们还有些问题要处理。

我们如何插入第一个数据？

我们最后一个数据的"下一位"是几？

在上文图中，我们能很清晰的看到，处在中间的数据都是被两条线相连的。一条是从上一个数据过来，另一个是指向下一个数据。

但是第一个数据没有上一个数据，最后一个也没有下一位。

所以得给这个表做一些修改，给这些数据标记一下开头和结尾。

这样，一个有头有尾的链表就完成了！

一下是源代码：

#include <stdio.h>#include <stdlib.h>
typedef struct list { float number; struct list * next;} LIST;
int main(void) { LIST * head, * p1, * p2; float i; head = NULL;
 while (scanf("%f", &i) != 0) { p1 = (LIST *)malloc(sizeof(LIST)); p1->number = i; if (head == NULL) { head = p1; p2 = p1; } else { p2->next = p1; p2 = p1; } } p2->next = NULL;  return 0;}

首先，我们线声明一个结构体，里边有两中数据类型，一个是浮点数，另一个是指向该结构体的指针类型。并且我们给它一个名字:LIST

有了结构体以后，我们还需要结构体变量的指针，一个作为头指针，代表开头。一个用来作为结尾。还有一个用来分配内存，修改数据。

在最开始，没有数据，所以头指针需要指向NULL，代表没指向任何地方。

随后我们用一个循环while(scanf("%lf", &i) != 0)(如果scanf需要输入的值和实际需要输入的值类型不匹配的话，就会输出0)循环执行就代表有值需要存储在链表里，输入不需要输入的话，就输入任意一个非数字的字符(例如"!")

在循环中，我们利用malloc来分配一个内存，用来存储i的数值。

随后进行判断，如果头指针不指向任何数值，就代表p1指向的数值是这个链表的第一个数值，所以我们要让头指针指向这个结构体，并且我们还要让p2指向结构体，代表此时这个数也是结尾。

如果head此时不是NULL，就代表输入的数不是第一个，所以我们直接让p2指向的结构体的指针指向p1所指的值(也就是"下一位")，并且让p2等于p1，代表此时为结束。

循环执行到输入一个非数字的字符，结束时让p2指向的结构体的指针指向NULL代表整个链表完成！

链表的用法还有很多，我们以后再讲。

本期推送主要告诉大家如何使用结构体指针。