链表的创建和基本操作（C语言实现）

假设需要登记每个班级的学生姓名，有的班级总人数为 35，有的班级总人数为 90，则用数组存放数据时，需要将数组的大小设为 90。若班级的人数无法确定，则需要将数组的大小设的足够大，但这样会浪费内存空间。

相比数组，链表就没有这种缺点，链表可以根据需要开辟内存空间。与数组不同的是，数组在内存中按顺序依次存储（线性），而链表在内存中是非线性存储的。

链表的创建

链表是一种数据结构，一般使用结构体变量作为链表的元素，也叫节点（Node）。因此，链表的基本构成包含指针变量和结构体变量。

在 int main() 函数外，先创建结构体类型，代码如下：

struct int_node {
    int val;
    struct int_node *next; //next是结构体指针变量，指向下一个结构体变量
};

这样创建了 int_node 结构体类型，这个结构体类型与之前的结构类型体不同，这个结构体类型有一个指向结构体变量的成员，这个成员是指针变量，用于存储下一个结构体变量的位置，该成员是创建链表最重要的部分。

在 int main() 函数里，创建头指针变量 head，指针变量 p 和结构体变量 a、b、c 代码如下：

struct int_node *head,*p,a,b,c;

对结构体变量 a、b、c 的 val 成员分别赋值 1、2、3，代码如下：

a.val = 1;
b.val = 2;
c.val = 3;

代码运行后，形成的数据初始结构如下图所示。


接下来做以下几步操作：

• 将结构体变量 a 的起始地址赋给头指针变量 head；
• 结构体变量 b 的起始地址赋给结构体变量 a 的 next 成员；
• 将结构体变量 c 的起始地址赋给结构体变量 b 的 next 成员；
• 为结构体变量 c 的 next 成员赋值为 NULL。

具体代码如下：

head = &a;
a.next = &b;
b.next = &c;
c.next = NULL; //指向空

到这一步，已经创建好了链表。指针变量 head 指向结构体变量 a 的地址，然后通过 a.next 指向结构体变量 b 的地址，再通过 b.next 指向结构体变量 c 的地址，最后 c.next 指向空。这样就将 3 个结构体变量串连起来，形成了链表其数据结构如下图所示。


下面进行遍历链表操作，先将指针变量 p 指向链表的首地址，代码如下：

p = head;

从头到尾，对链表进行访问，依次输出链表中 val 的值，代码如下：

do
{
    printf("%d\n",p->val);
    p = p->next;
}while(p! = NULL);

创建链表的完整代码如下：

#include <stdio.h>
　
struct int_node {
    int val;
    struct int_node *next;
};
　
int main()
{
    struct int_node *head,*p,a,b,c;
    a.val = 1;
    b.val = 2;
    c.val = 3;
　
    head = &a;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    p = head;
    while(p != NULL)
    {
        printf("%d\n",p->val);
        p = p->next;
    }
　
    return 0;
}

编译运行，结果如下：

1 2 3

注意，上面创建的是静态链表，即所有节点（也就是结构体变量）都已在程序中事先定义好的，而不是根据需要动态定义的。

链表的基本操作

接下来我们创建的链表，是在程序运行过程中从无到有地建立链表，也就是根据需要申请新节点，并将新节点从头到尾链接起来。

1) 创建链表

创建动态单向链表，能够输入学生的学号、成绩。代码如下：

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct stu) //获取字节数
//构造节点
struct stu
{
    long id; //学号
    float score; //成绩
    struct stu *next;
};
　
int n; //全局变量n，保存节点总数
　
//创建链表
struct stu *create(void)
{
    struct stu *head = NULL, *p1, *p2;
    n = 0;
    p1 = p2 = (struct stu*)malloc(LEN); //申请新节点
    scanf("%ld %f",&p1->id,&p1->score); //输入学生的学号和成绩
    while(p1->id != 0) //学号不等于0继续创建
    {
        n = n+1;
        if(n == 1) head = p1; //head指向第一个节点
        else p2->next = p1;
        p2 = p1;
        p1 = (struct stu*)malloc(LEN); //继续申请新节点
        scanf("%ld %f",&p1->id,&p1->score);
    }
    p2->next = NULL; //指向空
    return(head); //返回头节点
}
　
int main()
{
    struct stu *pt;
    pt = create();
    return 0;
}

编译运行，结果如下：

1 80
2 90
3 70
4 86
5 78
0 0

可以看出，程序的第 3 行定义 LEN 存储 struct stu 类型数据的字节数，sizeof 是“字节数运算符”。

下面对 create() 函数进行解析：
1) 先定义指向 struct stu 类型数据的指针变量 head、p1、p2。n 赋值为 0，表示没有节点。

2) create() 函数中的第 4 行，malloc(LEN) 的作用是开辟一个长度为 LEN 字节的内存空间。malloc() 函数返回的是不指向任何类型数据的指针（void 型），而 p1 和 p2 是指向 struct stu 类型数据的指针变量，因此在 malloc(LEN) 之前添加“(struct stu *)”，对其类型进行强制转换。

3) malloc() 函数开辟第一个节点后，用 p1 和 p2 指向它，如下图所示。


4) 从键盘输入一个学生的学号、成绩给 p1 所指的节点。如果输入的学号不为 0，则执行 n = n+1，n 的值为 1。如果判断出 n==1，即判断是第一个节点，则 head = p1，即将 head 指向第一个节点如图 3 所示（程序中始终将 head 指向第一个节点）。执行 p2 = p1，让 p2 也指向第一个节点。用 malloc() 函数开辟第二个节点，并将 p1 指向它（图 4 所示的第一步）。然后从键盘输入一个学生的学号、成绩给 p1 所指向的新节点。


5) 若学号为 0，则退出循环，执行 p2−>next=NULL（让链表最后的节点指向空），执行 return 语句返回链表的头指针 head。这样 p1 开辟的新节点不会链接到链表中。至此，完成了动态单向链表的创建。

创建的链表如图 3（只有一个节点）和图 4 所示（包含 5 个节点）。

与 malloc() 函数不同的是，calloc() 函数进行了初始化，calloc() 函数分配的空间全部初始化为 0。

char* p;
p=(char*)calloc(40,sizeof(char));

realloc() 函数用法为 realloc(void *p,unsigned size)，将指针变量 p 指向的已分配的内存空间的大小改为 size。

p=(char*)realloc(p,20);

2) 遍历链表

在前面程序的基础上添加自定义的 print() 函数，完成链表的遍历，具体代码如下：

//链表的输出
void print(struct stu *head)
{
    struct stu *p; //声明指针变量p
    printf("id \t score\n"); //\t 表示跳格，即留8个空格
    p = head;
    while(p != NULL)
    {
        printf("%ld\t%f\n",p->id,p->score);
        p = p->next;
    }
}

分析print()函数的功能：

• 先将链表头指针作为参数，在函数中声明了指针变量 p，将链表的头指针参数赋值给指针变量 p；
• 然后执行 while 循环，若指针变量 p 非为空，则输出指针变量 p 所指向节点的数据。再执行 p = p−>next，让指针变量 p 指向链表的下一个节点。
• 若指针变量 p 为空，则表明指针变量 p 已经指向链表的尾部，链表的遍历已完成。

链表的遍历如下图所示。

3) 查找节点

下面的 find() 函数是从链表中查找与 id 值相同的节点，代码如下：

struct stu *find(struct stu *head,long a)
{
    struct stu *temp;
　
    temp = head;
　
    if(temp == NULL) //如果原来链表是空表
        return NULL;
    else
    {
        //查找id值不等于链表中节点值且没有到达链表末端，则后移
        while (( temp->id != a) && (temp->next != NULL))
            temp = temp->next; //p1后移一个节点
    }
　
    return temp;
}

查找节点比较简单，就是匹配对应的 id 值，如果不相等且没有到达链表末端，则将链表指针不断后移，直到找到相等的值或到达链表末端为止。

4) 删除节点

下面的 del() 函数是从链表中删除与 id 值相同的节点，代码如下：

struct stu *del(struct stu *head,long id)
{
    struct stu *p1,*p2;
　
    if(head == NULL) //判断是否为空链表
    {
        printf("是空链表");
        return head;
     }
    p1 = head; //p1指向第一个节点
    //p1指向的不是要找的节点，且后面还有节点
    while(id != p1->id && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next; //p1后移节点
    }
    if(id == p1->id) //找到了对应的节点
    {
        if(p1 == head) //如果p1是首节点，把第二个节点给head
             head = p1->next;
        else
             p2->next = p1->next; //下一个节点地址赋给前一个节点
        printf("已删除:%ld\n",id);
        free(p1); //释放p1节点空间
        //n为全局变量，含义为节点数，不在本函数内定义
        n = n-1; //节点数n-1
     }
    else
        printf("链表中找不到对应节点");
　
    return head;
}

在 del() 函数中，包含 head 和 id 两个参数，参数值通过主程序中头节点和待删除学生的学号传递过来。

代码先判断该链表是否为空，如果为空，则无法删除并返回主函数。然后执行 while 循环找匹配的节点，先判断查找学号是否与链表当前节点的学生学号相等，或者链表是否到达链表末端，如果查找到匹配学号或者到达链表末端，则停止循环，否则链表指针不断移向下一个节点。

此时，p2 指针跟着 p1 指针移动，且在 p1 指针后面。如果找到匹配节点，则判断匹配节点是否恰好是头节点，即判断 p1 是否是首节点，如果是则将第二个节点地址赋值给 head，否则将前一个节点 p1 的下一个节点地址赋值给前一个节点 p2 指向的下一个节点地址，即将 p1 节点从链表中移除，并将 p1 节点空间释放，然后执行 n=n−1，将总节点数减 1。

动态删除链表节点过程如下图所示。

5) 插入节点

向链表中插入节点，对应的 insert() 函数代码如下，其中参数 stud 为待插入节点的地址或指针：

struct stu *insert(struct stu *head, struct stu *stud)
{
    struct stu *p0, *p1, *p2;
    p1 = head; //p1指向头节点
    p0 = stud; //p0指向要插入的新节点
    if(head == NULL) //如果原来链表是空表
    {
        head = p0; //头节点指向新节点p0,只有1个节点
        p0->next = NULL; //p0指向空
    }
    else
    {
        //新添加节点p0的id值如果大于链表中节点的id值，则后移
        while ((p0->id > p1->id) && (p1->next != NULL))
        {
            p2 = p1; //p2指向p1所指向的节点，跟着p1移动
            p1 = p1->next; //p1后移一个节点
        }
        if(p0->id < p1->id) //p0->id的值比当前的p1->id的值小，插入节点
        {
            if(head == p1)
                head = p0; //在头节点前插入新节点
            else
               p2->next = p0; //p2接入新节点
            p0->next = p1; //新节点接向p1,原来p2的下一个节点
        }
        else //新节点p0的id值大于链表中任一个节点的id值,在链表最后插入节点
        {
            p1->next = p0;
            p0->next = NULL;
        }
    }
    //n为节点数，全局变量
    n = n+1; //节点数加1
    return head;
}

下面通过重新插入 id=2，score=88 的节点来描述节点的插入过程。插入节点与删除节点的代码前面略相同。先判断链表是否是空表，如果非空，则通过 while 循环找到插入节点的位置 p1。在找到插入位置 p1 后，判断 head 是否等于 p1，如果是则把 p0 赋值给 p1，即将 p0 作为新的头节点，否则将 p0 赋值给 p2 的下一个节点，即将 p2 的下一个节点指向 p0，如下图中的第一步所示。


然后将 p0 的下一个节点指向 p1，即将新节点 p0 指向原来的 p1，完成节点的插入，如图 7 中的第二步所示。

如果新节点 p0 的 id 值大于链表中任一个节点的 id 值，则在链表最后插入节点，先将 p1 的下一个节点指向 p0，再将 p0 的下一个节点指向空。

调用 del() 函数和 insert() 函数的主函数代码如下：

int main()
{
    struct stu *head,*temp;
    head = create(); //创建
    print(head); //遍历
　
    printf("删除链表id为2的节点\n");
    head = del(head,2);
    print(head); //遍历
　
    printf("重新输入新节点学号2和成绩88\n");
    //重新开辟一个新节点
    temp = (struct stu*)malloc(LEN);
    scanf("%ld %f",&temp->id,&temp->score);
    head = insert(head,temp);
    print(head); //遍历
　
    return 0;
}