第4周：链表——4.2 链表

1.可变数组的缺陷

每次成长需要分配新的内存，需要时间拷贝元素，申请内存是连续的，有可能会出现内存充足却分配不到内存的情况。

假如我们有一个办法，原来内存放着不动，就申请一块 BLOCK 那么大的内存后，把他们链接起来，不需要拷贝。这一个 BLOCK 走完告诉你下一个在哪里，到那里去访问它。避免拷贝，节约时间，可充分利用这块内存的每个角落。

2.链表

让这个数组指向下一个数组。

有那么一种东西分为两个部分，一部分为数据，一部分为指针。指针指向下一个同样的东西，最后一个指针用符号 NULL 代替表示没有这个东西了。还需要有一个指针指向第一个东西（头指针 head）。——链表

带着数据和指针的东西叫结点。

3.结点定义

结点Node定义

4.创建（添加）节点

写在main函数里的添加节点方法，else为特殊情况，头指针为空

创建新的节点挂到链表尾巴上，如果把它抽出来作为一个函数 void add(Node *head,int number)。

在 head = p 时为特殊情况，链表为空。在函数里会改 head ，传入的 head 在函数里的修改对 main 中的 head 没有作用，传进函数的 head 不会被修改，为本地变量。

如何解决？

1.全局变量

全局变量是有害的。定义全局变量使得程序为一次性的，add() 函数只能对这个函数变量起作用。

2.函数改为 Node *add( Node *head,int number){ ... return head;}

要求使用 add() 的程序员必须把代码写成 head = add (head , number); 如果忘记这样写，对空链表的 add() 函数就是错误的。

3.传 head 的指针 Node*add( Node**pHead,int number)

可对指针的值做修改，head 改为 pHead。传入&head 。

4.创建新的数据结构 List

好处：我们用了自己定义的数据结构代表整个链表，以后可以有各种扩充。可加 Node *tail 表示链表末尾，给将来升级改进 List 带来可能。

5.链表的搜索

链表中的遍历

main 函数中的遍历

for ( p=list.head;p;p->next){} 链表操作中的经典写法。

写为函数print()

在 main() 函数中调用时写为 print(&list)。

让用户输入一个数字，在链表中找到数字。

一定要记得break！！

6.链表的删除

删除结点

首先，让这个要删除的结点的前一个结点的指针，指向这个结点的下一个结点。然后，free 指向要删除的结点的指针。

问题：要删除的结点前一个结点是什么？

如果有另外一个指针指向前一个结点，设为 q。q->next = p->next; free(p);

如果不是要删除的节点， q=p; p=p->next;

特殊情况（识别边界情况）

当你在用指针时，识别边界的一种非常机械的做法是：什么时候你的指针变量出现在箭头（->）的左边了，意味着你要用到指针所指的东西，意味着这个时刻这个指针不能是 NULL 。

for (q = NULL,p=head; p ; q=p;p=p->next){ if ( p->value == number) q->next = p-> next; }

在上面的代码中，for 中的第二个条件 p 有起到判断 p 是否是 NULL 的作用。而 q->next 不安全，如果我们要找的是第一个元素，q 为 NULL。这时候应该让 head 等于 p 所指的 next 。

我们有没有足够的代码判断要用到的指针（-> 左边的指针）是不是 NULL？

结点的删除

链表的清除

链表中所有的结点都是 malloc 出来的，需要把链表清除干净。有一个指针指向 head ，先让指针 q 指向 p 的 next。删除 p ，再让 p 等于 q .

q = p->next; free(p); p=q ; p 为 NULL 结束。