单链表（建立、插入、删除、打印）

单向链表创建

链表是动态分配存储空间的链式存储结构。

其包括一个“头指针”变量，其中第0个结点称为整个链表的头结点，头结点中存放一个地址，该地址指向一个元素，头结点一般不存放具体数据，只是存放第一个结点的地址。

链表中每一个元素称为“结点”，每个结点都由两部分组成：存放数据元素的数据域和存储直接后继存储位置的指针域。指针域中存储的即是链表的下一个结点存储位置，是一个指针。多个结点链接成一个链表。

最后一个结点的指针域设置为空(NULL)，作为链表的结束标志，表示它没有后继结点。

使用结构体变量作为链表中的结点，因为结构体变量成员可以是数值类型，字符类型，数组类型，也可以是指针类型，这样就可以使用指针类型成员来存放下一个结点的地址，使其它类型成员存放数据信息。

当一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。

       单链表的示意图如下：

Head指针为单链表的头指针，单链表L：L既是单链表的名字，也是其头指针。链表中的最后一个结点的指针域定义为空指针(NULL)。

在创建列表时要动态为链表分配空间，C语言的库函数提供了几种函数实现动态开辟存储单元。

malloc()函数实现动态开辟存储单元：

      malloc函数原型为：void *malloc(unsigned int size);

      其作用是在内存的动态存储区中分配一个长度为size的连续空间，函数返回值是一个指向分配域起始地址的指针（类型为void）。如果分配空间失败（如，内存空间不足），则返回空间指针（NULL）

单链表的求表长操作需要设定当前指针p和一个计数器j，初始时p指向链表中的第一个结点，p每向下移动一个结点时，j就加1，直到到达p链表的尾部。带头结点的链表，链表长度不包括头结点。

设定p为当前结点，初始时p指向链表的第一个结点，然后向下移动i，此时p所指向的元素就是需要查找的第i个结点元素。

    查找元素e第一次出现的位置。从链表的第一个结点开始，判断当前结点的值是否等于e，等于则返回该结点的指针，否则继续向后查找，直至到达链表的最后。

    在结点p之前插入一个新的结点q:对于不带头结点的单链表，结点p的位置有所不同，插入操作有以下两种情况：  

    1)在链表的表头插入：

     (1)创建一个新的结点q。

     (2)将此结点的数据域赋值为e，并将它的next指针指向第一个结点，即L。

     (3)将L修改为指向新的结点q。        

    操作示意图如下：

 2)在链表的中间插入       (1)创建一个新的结点q。       (2)将此结点的数据域赋值为e，并将它的next指针指向p。       (3)查找到p的前驱结点pre。       (4)将pre的next指针指向新创建的结点q。      操作示意图如下：

   删除链表中的某个元素e，如果e在链表中出现不止一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：      

     1)p是链表中的第一个结点            

        (1)将L指向p->next。            

        (2)释放p。          

    示意图如下：

 2)p是链表中的其他结点         (1)找到p的前驱结点pre。         (2)将pre->next指向p->next。         (3)释放p。      示意图如下：

    单链表的创建方法有两种：头插法和尾插法。        

    头插法是将新增结点插入第一个结点之前，示意图如下：

       尾插法是将新增结点插入最后一个结点之后，示意图如下：

      首先设置3个指针pa、pb、pc, pa和pb分别指向链表La与Lb的当前待比较插入结点，pc指向链表Lc的最后一个结点。当pa->data≤pb->data时，将pa所指的结点插入到pc后面，否则就将pb所指的结点插入到pc后面。最后，当有一个表合并完，将另一个表剩余的结点全插入到pc。

代码如下：

/*-----------------------------------------------------------------------------时间:2011年9月28日

文件功能:实现了动态建立一个学生信息的链表包括链表的创建、插入、删除、和打印输出学生信息包括姓名和分数本链表是带有头结点的，头结点的内容为空内容-----------------------------------------------------------------------------*/