14.2.1 可变数组的缺陷

每次长大，都可能会重新申请新的内存空间。

每次都要拷贝，很花时间
每次都是在之前的内存结尾申请空间，不断往后排，所以最后其实我们不需要那么多内存空间，但我们的内存空间不够了。
如果我们每次都只申请一块block大的内存，把他们链起来，不需要拷贝了节约时间，也可以充分利用给内存的每一块。

14.2.2 链表

在这里插入图片描述
实际上的解决方法是每一块都分为两部分，前一块是数据，后一块是指针，指向下一块。然后还需要指向开头的head，以及结尾不指向任何东西(NULL)。这就是链表（linked-list）。每个块就是结点。

typedef struct _node{int value;struct _node *next;
}Node;

第一个例子：像可变数组一样，不停读入数字直到-1为止。
这件事回想起来，从平均数就开始做了。一开始我们不需要记录每一个数，只需要求平均数即可。后来讲到数组，需要输出比平均数大的数，就需要记录输入的每一个数，用到数组了。不过数组大小需要用户事先告诉我们。但现在是不知道会读入多少个数。

do{scanf("%d",&number);if(number!=-1)//add to linked-list
}while(number!=-1);

首先我们需要有head开头的指针。一开始head指针是NULL，不停往后挂结点

Node *head=NULL;

Node *p=(Node*)malloc(sizeof(Node));
p->value=number;
p->next=NULL;
//find the last, attach
Node *last=head;
if(last)//判断head是否为空
{while(last->next)last=last->next;last->next=p;
}else head=p;//即：p就是第一个结点

14.2.3 链表的函数

上面的这些操作（把新的结点挂到上一个结尾）尝试拿出来单独写成一个add函数。
函数的参数应该有什么？head头指针，以及每次要传入的数据data。

错误的方案1：
void add(Node *head,int number);
每次新定义一个临时结点p，p->last=number，p->next=NULL;然后我们把这个结点挂在链表的末尾。
有两种情况：1、p是链表的第一个元素，即head=NULL，那直接令head=p完事。
2、p不是第一个元素，我们现在只知道链表头是head，我们要先找到last链表的结尾结点，然后把p挂在结尾。

last=head;
while(last->next)last=last->next;//找到结尾last结点
last->next=p;

但是head=p是有问题的，head的值并没有得到修改。如果想不通，可以阅读作者的另一篇文章，里面有写作者自己的一些理解。
如果我们把head放在外面作为一个全局变量？不好，在全局变量时讲过，不要用head做全局变量。因为add只能对这个链表的head起作用，如果程序中出现其他链表，不能再做操作。
方案2：如果add函数返回指针，然后return 理想的head指针，在函数中令head=add函数呢？不错。
方案3：传给add的参数不再是head，而是head的地址。我们知道通过指针可以直接修改该地址中的值。
在这里插入图片描述
方案4：我们定义一个结构list，其中包含*head。在原函数中定义list，list.head=NULL；然后把list的指针&list传入add函数，add的参数是list的指针，在函数中就可以对list->head进行修改。

方案4的好处在于我们用自己定义的list结构来代表整个链表。除了定义的这个head，还可以有tail指向结尾，这样每次last不用遍历整个链表才能找到结尾；等等。
这里讲的比较细，是因为链表的放入东西、插入东西都是比较简单的。对于工程化的东西，我们要深究。

14.2.4 链表的搜索

输出链表中读到的所有东西

node *p;
for(p=list.head;p;p=p->next)printf("%d\t",p->value);//遍历

则这一段可以单独拿出来写作函数，称之为print，参数为list的指针。
可见for循环不一定非要是++。
然后进一步，我们希望能实现搜索的功能：输入一个数字，在链表中寻找这个数字，如果找到了就将其删除。

for(p=list.head;p;p=p->next)
{if(p->value==number)printf("找到了！");
}

14.2.5 链表的删除

删除某个值，我们要做两件事。
第一，前面的指针指向他后面的值。
第二，free it.
也就是说，如果前面的指针是q，我们要删除的部分指针是p，则要q=p,p=p->next。
在这里插入图片描述

怎么考虑到边界情况？
一个很重要的思想：
判断出现在arrow箭头左边的指针变量是否是NULL。如图中for循环内出现了p->next，p->value，q->next.因为在for循环中判断了p会不会是空指针，所以p->是安全的。但是q->next就不安全了，没有判断q是否是NULL。
也就是说当要删除的节点p是第一个时，q=NULL，这就是边界情况。这时可以让head等于所指的next。
在这里插入图片描述
最后别忘记free(p).