神马是链表

这一节要学习链表了, 要学习链表了, 要学习链表了 !!! 重要的事情说三遍。

链表是一种重要的数据结构，跟数组很相似。那为什么会出现链表呢？这就要从数组的缺点说起：

上图数组a前四个元素是从大到小排序的，要把a[2]和a[3]中的值往后挪，再把7赋值给a[2]才能5个元素都从大到小排列。操作将是：把a[2]的值临时存储在变量b中，把4赋值给a[4]，把6赋值给a[3]，把b（也就是8）赋值给a[2]。这里就可以看出来了，数组的插入和删除的操作需要移动其他的元素。当数组长度很大时，移动就很耗费时间了。用链表就不会这么麻烦了。下图展示了什么是链表：

链表也由多个结构变量组成，每个结构变量叫一个节点。重要的是每个节点中都有一个成员是指针，它指向下一个节点，这样就能串起来，像链子一样，所以叫做链表。

链表通常由一个称为头指针的指针变量指向首节点,首节点中有一个指针指向第2个节点，最后一个节点的指针为空指针NULL，表示链表结束了。

链表的插入操作，只需要改变指针的指向就行了。还是上例中的把节点5插入到节点2和节点3之间，操作如下图所示：

首先，把节点2的指针保存在临时指针变量p中，再让节点2指向节点5，把临时变量p赋值给节点5的指针，节点5的指针就指向节点3了，最后节点4的指针赋值为NULL，就完成了。不需要其他元素的移动。

链表的实现

按照上述说明，链表要包括两部分，一部分用来放数据，剩下一个是指针，指向下一个节点。下面我们就建立一个student类型的节点：

#include <iostream>
using namespace std;
struct student{
    int id;
    char name[20];
    float score;
    student \*next;
};
void main()
{
    student *head;
    student stu1={1,"xiaoming",59.5,NULL},stu2={2,"angelababy",61,NULL},stu3={3,"xiaohong",99,NULL};
    head=&stu1;
    stu1.next=&stu2;
    stu2.next=&stu3;
}

第3行开始是student类型的定义，注意第7行是指向student类型的指针，用于把节点串起来的。

第11行定义student类型的指针，从名字可以看出来我们把它作为头指针。第12行是新建了3个student类型的对象，把对象串起来之后，就成了链表，每个对象都叫做这个链表的一个节点。新建的3个student对象的指针成员都为NULL，这是链表还没串起来，我们只是把一个个节点做好了，下面就要将他们串起来了。

第13到15行就是串起来的操作，头指针指向第一个节点stu1，stu1的指针next指向第2个节点stu2，stu2的指针next指向第3个节点stu3，stu3的指针next还是NULL，说明链表到头了。

串起来之后，我们就可以通过head指针访问到链表的每个节点。