c语言单链表

1. 链表概述

   链表是一种常见的重要的数据结构，它是动态的进行存储分配的一种结构。先说一个场景的应用，假设有若干位同学的信息需要保存，每位同学包含编号、年龄、分数。虽然对每位同学来讲可以用结构体类型的数据表示，但是对于多为同学而言能否用结构体数组表示呢？如果同学的具体数量不知道定义大了，浪费空间，定义小了则不够用，因此排除掉结构体数组。此时我们的链表就派上用场了。
   

head表示链头指针，指向链表的第一个元素，存放第一个元素的地址（1010），链表中每个节点都包括两个部分：一为用户所需要的实际数据（如第一个节点中的01，zhang,80）,二为下一节点的地址（如：1210），链表最后一个元素不在指向其他元素，称为“链尾”，它的地址部分存放的是NULL（表示空地址）。

链表中各元素在内存中不一定是连续存放的，要寻找链表中某一元素，必须先找到上一个元素，根据它提供的下一元素的地址才能找到下一个元素。如无head，则整个链表无法访问。

2 , 动态链表
2.1,建立动态链表

尾插法建立单链表的C语言源程序如下：

#include "stdafx.h"
#include "stdlib.h"

#define LEN  sizeof(struct student)

struct student {

    long int num;
    char name[10];
    float score;
    struct student *next;
};


/**尾插法建立单链表*/
struct student *creatail() {

    struct student *head, *p1, *p2;
    p1 = (struct student *)malloc(LEN);//开辟第一个节点
    scanf("%ld%s%f",&p1->num,p1->name,&p1->score);//输入第一个结点的值
    head = NULL;
    while (p1->num != 0)//学号不为零，执行循环操作
    {
        if (head == NULL) head = p1;
        else
            p2->next = p1;
            p2 = p1;
            p1 = (struct student *)malloc(LEN);
            scanf("%ld%s%f", &p1->num, p1->name, &p1->score);//输入结点的值
    }
    p2->next = NULL;
    return head;

}

指针变量head,p1,p2用来指向struct student 类型数据。head表示头指针，p1指向新开辟的结点，p2指向链表末尾，最初链表中无结点，因此，head的值为NULL，此时开辟第一个结点，使p1,p2指向它，并输入数据，因为开辟的是第一个结点，因此将p1赋给head,则将p1所指结点连入了链表。此时链表状态只有一个结点。因此p2也指向它。

继续开辟结点使p1指向它，输入学生数据，如果输入学号不为零，则将刚开辟的结点接入p2所指结点的后面，然后p2移到表尾。重复上述工作，知道输入学号为零，不再执行循环。此时。新开辟的结点不连入链表，而p2.next的值应为NULL，链表建立到此结束。

2.2单链表的上的访问：
2.2.1，输出链表各结点的某成员域
这个简单不细说，看代码：

void print(struct student *head) {

    struct student *p;
    p = head;
    if (head!=NULL)
    {
        printf("output records:");
    }
    do
    {
        printf("%ld %s %5.1f\n", p->num, p->name, p->score);
        p = p->next;
    } while (p!=NULL);
}

2.2.2 统计单链表中结点个数

int count(struct student *head) {

    struct student *p;
    int n = 0;
    p = head;
    while (p!=NULL)
    {
        n++;
        p = p->next;
    }
    return (n);
}

2.2.3 根据条件查找结点
如果要在链表中查找符合条件的数据，则需要从表头开始查找直至表尾.
例如：输出学生链表中成绩大于90分的所有学生姓名。

void find(struct student *head) {

    struct student *p;
    p = head;
    printf("Name Score\n");
    while (p!=NULL)
    {
        if (p->score > 90) {
            printf("%s,%5.1f\n", p->name, p->score);
        }
        p = p->next;
    }
}

3.链表上的插入
对链表的插入是指将一个结点插入到一个已有的链表中。
例如，有一个学生链表，要在姓名为Wang的学生结点后面插入一个新节点。
要到达这一目的，应解决两个问题。第一是怎样找到插入的位置，第二是怎样实现插入。
插入的位置有三种情况：
1.链表为空。此时只需要将新节点直接连入链表中。

用q指向新结点，q赋给head，NULL赋给q->next 便可实现插入。

2，链表不为空。则需要从头至表尾查找姓名为“Wang”的学生结点。

用p1指向第一个结点。p1->name与“Wang”相比较，如果p1->不等于“Wang”则将p1后移，并使p2指向p1刚才指向的结点。再将p1->name与“Wang”相比较，如果仍然不相等，则应使p1继续后移，p2指向刚才的结点，直到p1->name与“Wang”相等为止。这时将q所指结点插入p1所指结点后。此时只需将p1->next 赋给q->next,q赋给p1->next即可。

3，从表头到表尾都没有找到。此时只需要将q赋给p2->next,NULL赋给q->next即可。很简单图就不画了

综上分析，代码就出来了：

struct student * insafter(struct student *head, struct student *q) {

    struct student *p1, *p2;
    if (head==NULL)//原来链表为空
    {
        head = q;
        q->next = NULL;

    }
    else
    {
        p1 = head;
        while (p1!=NULL&&strcmp(p1->name,"Wang")!=0)
        {  //没有找到
            p2 = p1;
            p1 = p1->next;
        }
        //已到表尾,没有找到所需结点
        if (p1==NULL)
        {
            p2->next = q;
            q->next = NULL;
        }
        else {
            // 找到了便插入
            q->next = p1->next;
            p1->next = q;
        }
    }
}

4.链表上的删除
删除链表中的某个结点，并非将改结点从内层中抹掉，而是把它从链表中分离出来，撤销原来的链接关系即可。
同样以”Wang”姓学生为例。
删除也分两种情况：
如果链表为空，即头指针head等于NULL，则不能删除。
如果链表不为空。设一指针p1指向链表第一个结点。检查该节点中的name值是否等于“Wang”。如果相等就将该节点删除，如不相等，就将p1后移一个结点。再如此进行下去，直到表尾为止。对于结点不为空又可分为下面两种情况讨论。

第一种情况是要删除的结点在链表中：
（1）如果要删除的是第一个结点，则将p1->next 赋给head.此时head指向原来的第二个结点。第一个结点虽然仍然存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它。虽然p1还指向它，它仍然指向第二个结点，但无济于事，现在链表的第一个结点是原来的第二个结点，原来的第一个结点“丢失”。即不再是链表的一部分了。

（2）如果要删除的不是第一个结点。设两个指针变量p1,p2先使p1指向第一个结点，因为删除的不是第一个结点，则使p1指向下一个节点。即p1->next赋给p1,在此之前应将p1的值赋给p2，使p2指向刚才检查的那个结点。如此一次一次的是p后移，直到找到所要删除的结点或检查完全部链表都找不到所要删除的结点为止。如果找到了所要删除的结点。则将p1->next赋给p2->next.即p2所指向结点的下一节点不是p1所指向的结点了，而是p1所指向结点的下一节点。

第二种情况是检查到表尾还没找到所要删除的结点，则不能删除。
综上分析代码如下：

struct student *del(struct student *head, char *del_name) {

    struct student *p1, *p2;
    if (head==NULL)
    {
        printf("链表为空，不能删除\n");
    }
    else {
        p1 = head;
        while (strcmp(p1->name,del_name)!=0&&p1->next!=NULL)
        {
            p2 = p1;
            p1 = p1->next;
        }
        if (strcmp(p1->name,del_name)==0)
        {
            if (p1==head)//所需结点为第一个结点
            {
                head = p1->next;//删除第一个结点
            }
            else//所需删除的结点不为第一个结点
            {
                p2->next = p1->next;//将下一节点的地址赋给前一节点；
            }

        }
        else
        {
            printf("找不到要删除的结点\n");
        }
    }
    return (head);
 }

上面已经对单链表的建立、输出、统计、查找、插入、删除做了详细的分析与编码。当然除了单链表为还有环形链表、双向链表。