什么是链表

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。由前面的介绍中已知：用数组存放数据时，必须事先定义固定的数组长度（即元素个数）。

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。

如图所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

链表中数据元素的构成

每个元素本身由两部分组成：

1. 本身的信息，称为“数据域”；
2. 指向直接后继的指针，称为“指针域”。

这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

由于每个结点中只包含一个指针域，生成的链表又被称为 线性链表 或 单链表。

链表中存放的不是基本数据类型，需要用结构体实现自定义：

struct Student {
    int num;
    float score;
    struct Student *next;
};

参考代码

#include <stdio.h>
#include <malloc.h>

struct Student {
    int num;
    float score;
    struct Student *next;
};

int n;
struct Student* create() {
    n = 0;
    struct Student *head;
    struct Student *p1, *p2;
    p1 = p2 = (struct Student *)malloc(sizeof(Student));
    scanf("%d,%f", &p1->num, &p1->score);
    head = NULL;
    while (p1->num != 0) {
        n = n + 1;
        if (n == 1) head = p1;
        else p2->next = p1;
        p2 = p1;
        p1 = (struct Student *)malloc(sizeof(Student));
        p1->next = NULL;
        scanf("%d,%f", &p1->num, &p1->score);
    }
    return head;
};

void print(struct Student *head) {
    struct Student *p;
    printf("Total %d Students.\n", n);
    p = he...

掌握本节内容