动态链表详解：

什么是链表：

链表是一种常见的重要的

数据结构

，是动态的进行

内存分配

的一种结构，通过

结构体

去进行建立。

链表中有一个“

头指针

”变量，本文中用

head

表示，它存放一个

地址

，这个地址指向链表的

第一个元素

。就这样一直连接下去，知道最后一个元素，它不再指向其他元素，称作是“

表尾

”，存放一个空地址 NULL 表示链表结束。

链表中的每个元素又叫“

结点

”。

每个节点都必须包含两部分：

• 用户所需的实际数据
• 下一个结点的地址。

我们建立链表的目的还是为了

存放数据

，因此节点中必须要有实际的数据存放，通过下一个结点的地址再去访问下一个结点，读取下一个结点的内容。

可以看成链表中的各元素在内存中的地址可以是

不连续的

，要找到某一元素，必须要找到它的上一个元素，根据它提供的地址，才能定位到下一个元素。因此链表的首地址很重要，相当于是整个链表的入口地址，通过它才能去访问整个地址。

链表是如何建立起来的：

显而易见，链表这种数据结构，必须通过

指针变量

才能实现，每个节点中必须包含指针变量，用它来存放下一个结点的地址。

而结构体变量，用它去建立链表是最合适的，因为一个结构体变量可以包含若干和不同的数据成员，用结构体变量去充当结点，可以存放很多的数据：

struct link {
    int num;
    char ch;
    char *str;
    float x;
    double y;
    struct link *next;
};

建立链表的结构体中可以包含很多数据类型和数据，与普通的结构体不同的是，该结构体必须包含一项为指向该结构体类型的指针 struct link *next 用来存放下一个节点的地址。

**注意：**上面的代码只是定义了一个叫 link 的结构体，实际上并没有分配内存空间，只有定义了结构体变量之后才会分配

静态链表：

静态链表使用的不多，因为静态链表中所有的数据都是在程序内部填充好的，不是临时开辟的，使用完后也不会释放。

#include <stdio.h>

// 创建结构体：
struct link {
    int num;
    char *name;
    struct link * next;
};

int main(void)
{
    // 定义结构体变量：
    struct link x, y, z, *head, *p;
    // 为结构体变量填充数据：
    x.num = 100; x.name = "wang";
    y.num = 110; y.name = "zhang";
    z.num = 120; z.name = "li";
    // 将结构体变量连接起来：
    head = &x;
    x.next = &y;
    y.next = &z;
    z.next = NULL;

    // 开始遍历链表：
    p = head;
    while(p != NULL)
    {
        printf("num:%d name:%s\n", p->num, p->name);
        p = p->next;
    }
    return 0;
}

动态链表：

建立动态链表是指在程序执行过程中从无到有的建立起一个链表，即一个个的开辟结点和输入各节点的数据，并建立起前后相连的关系。

这里用一个简单的结构体举例：

// 建立动态链表所用的结构体：
struct link {
    int num;
    struct link *next;
};

写了六个函数：

• 开辟链表的函数
• 输出链表的函数
• 删除结点的函数
• 插入结点的函数
• 延长链表的函数
• 链表排序的函数

其中，链表的开辟是最重要的一步，只要理解了动态链表开辟的过程，就能理解动态链表的基本组成原理。

下面是动态链表的函数与详解：

# include "stdio.h"
# include "stdlib.h"

# define LEN sizeof(struct link)

// 建立动态链表所用的结构体：
struct link {
    int num;
    struct link *next;
};

// 静态内存区的全局变量：负责记录节点个数：
static int n;

// 开辟链表的函数：
struct link *creat(void);

// 输出链表的函数：
void print(struct link *const);

// 删除动态链表节点的函数：x 为待删除的数据值：
struct link *del(struct link *, int);

// 插入节点的函数：
struct link *insert(struct link *, struct link *, int);

// 延长链表的函数：
struct link *extend(struct link *);

// 给链表排序的函数：
void sort(struct link *);

int main(void) {
    struct link *head;
    head = creat();
    print(head);
    int ch = '#';
    char *sentence = "请选择您的操作：\n0.退出程序  1.打印链表的值  2.删除链表节点  3.插入链表节点  4.延长链表  5.给链表排序:";
    while (1) {
        printf("%s", sentence);
        scanf("%d", &ch);
        if (ch == 0) {
            printf("程序退出！");
            break;
        }
        if (ch == 1) {
            print(head);
        }
        if (ch == 2) {
            if (head == NULL) {
                printf("链表为空！请先输入数值！\n");
            } else {
                int x;
                printf("请输入要删除的数值：");
                scanf("%d", &x);
                head = del(head, x);
                print(head);
            }
        }
        if (ch == 3) {
            int pos;
            struct link *plus = (struct link *) malloc(LEN);
            plus->next = NULL;
            if (head == NULL || n == 0) {
                printf("链表为空！请先添加数据！");
            } else {
                printf("请输入要插入的数值：");
                scanf("%d", &plus->num);
                printf("请输入要插入的位置：");
                scanf("%d", &pos);
                head = insert(head, plus, pos);
                print(head);
            }
        }
        if (ch == 4) {
            head = extend(head);
            printf("添加数据成功！\n");
            print(head);
        }
        if (ch == 5) {
            sort(head);
            printf("链表排序成功！\n");
            print(head);
        }
    }
}

// 开辟链表的函数：
struct link *creat() {
    // 定义三个结构体指针变量，其中head指向链表首地址：
    struct link *head = NULL, *p, *q;
    n = 0;
    // 使用 malloc 开辟第一个节点，然后使 p,q 指向那片空间：
    // malloc带回的是不指向任何类型的指针数据 void 类型
    // 需要通过(struct link *)强制类型转换
    p = q = (struct link *) malloc(LEN);
    // 输入数据，当输入0的时候停止建立：
    // 因为 p 指向这片空间，通过 p 把数据写入那片内存空间
    printf("请输入数据开始建立链表：输入0时停止：");
    scanf("%d", &p->num);
    while (p->num != 0) {
        // 让节点数目 +1；
        n++;
        if (n == 1) {
            // 当第一次建立节点时让 head 指向第一个节点：
            head = p;
        } else {
            // 将新开辟的节点的地址赋值给上一个节点的 next 成员
            // 因为 q 指向这一个节点，对 q 进行的操作就是对节点的操作
            // 通过这一步把新开辟的节点和上一个节点连接起来
            q->next = p;
        }
        // 第一次循环的时候没有作用，此时 p 和 q 都是指向第一个节点
        // 之后的循环使 q 也指向刚建立的那个节点：
        q = p;
        // 第一次循环的时候开辟第二个节点
        // 之后的循环也是开辟新的节点并让 p 指向那片空间
        p = (struct link *) malloc(LEN);
        // 通过 p1 再次把数据写入新的内存空间中：
        scanf("%d", &p->num);
    }
    // 最后让 q 指向空，使链表最后一个结点的 next 指向 NULL
    // 将 NULL 设置为填表结尾的标志：
    q->next = NULL;
    // 此时 p 正指向输入数据为0的地址空间，将其释放掉：
    free(p);
    printf("建立链表成功！\n");
    // 把指向表头的指针返回出去：
    return head;
}

// 输出链表的函数：
void print(struct link *const head) {
    // 这里将 head 指针类型传入为 const 保护 head 的地址不被改变
    struct link *p = head;
    // 确保链表不为空：
    if (head != NULL) {
        printf("链表中的数据为：\n");
        // 开始循环打印链表的数据，当到 NULL 时停止：
        do {
            printf("%d ", p->num);
            p = p->next;
        } while (p != NULL);
        printf("\n");
    } else {
        printf("链表为空！\n");
    }
}

// 删除动态链表节点的函数：有重复数据时默认删除第一个：
struct link *del(struct link *head, int x) {
    // 删除一个节点是把它从链表中分离出来，只要撤销原来的链接关系即可
    // 这里指定 x 的数据的值作为删除节点的标志
    struct link *p, *q;
    // 检测链表为空：
    if (head == NULL) {
        printf("链表为空！\n");
        return head;
    }
    p = head;
    // 通过循环条件寻找待删除的数据：
    while (x != p->num && p->next != NULL) {
        // 让 q 是始终是 p 前面的那个节点：
        // 通过循环让 p 定位到待删除的节点位置：
        // 这样可以将待删除节点前的节点(q位置)与待删除节点后的节点(p->next)位置连接起来
        q = p;
        p = p->next;
    }
    // 再次确认条件：开始删除节点，这里分为两种情况：
    if (x == p->num) {
        // 如果待删除的节点是第一个节点，就要将 head 后移一个位置：
        // 如果不是第一个节点，就断开原有的连接，重新建立连接：
        // 将待删除节点前的节点(q位置)与待删除节点后的节点(p->next)位置连接起来
        if (p == head) {
            head = p->next;
        } else {
            q->next = p->next;
        }
        printf("数值为%d的节点已删除！\n", x);
        // 将删除的那个节点的空间释放掉：
        free(p);
        // 节点数目减一；
        n--;
    } else {
        printf("未找到数值为%d的节点！\n", x);
    }
    // 返回新的头指针：
    return head;
}

// 插入节点的函数：
struct link *insert(struct link *head, struct link *data, int pos) {
    // 函数接受的参数是头指针、要插入的结构体指针和要插入的位置：
    struct link *t = data, *p = head, *q = p->next;
    int i;
    // 判断当链表为空时，将插入的数据作为第一个节点：
    // 当链表不为空时，将有三种情况：
    if (head == NULL || n == 0) {
        head = t;
        t->next = NULL;
    } else {
        // 当要插入的位置为链表的头部时，将插入节点的地址位置给 head
        // 然后再与后面的链表连接起来：
        if (pos == 1 || pos == 0) {
            head = t;
            t->next = p;
        } else if (pos > n) {
            // 当要插入位置位于链表的末尾时；先通过循环定位到链表的尾端
            // 将插入的节点与尾端相连，最后将新的尾端地址改为 NULL
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = t;
            // 修改新的尾端：
            t->next = NULL;
        } else {
            // 当插入节点位于中间时，通过 p,q两个指针同时定位到插入位置前一个节点和后一个节点
            for (i = 2; i < pos && p->next != NULL; i++) {
                // 通过循环进行定位：
                p = p->next;
                q = q->next;
            }
            // 找到对应位置后插入节点：
            p->next = t;
            t->next = q;
        }
    }
    // 插入节点后让节点数目+1：
    n++;
    return head;
}

// 延长链表的函数：
struct link *extend(struct link *head) {
    // 延长链表指的是在链表的尾部继续添加数据：
    struct link *till = head, *p, *q;
    // 此时分为两种情况：
    // 第一种情况时当链表为空的时候，就要重新去开辟链表：
    // 第二种情况时当链表不为空的时候，就在链表的尾部添加数据：
    if (till == NULL) {
        printf("链表为空，请输入数据建立链表：输入0时停止:");
        p = q = (struct link *) malloc(LEN);
        // 链表为空时，要将新建立的空间的指针赋值给头指针 till
        till = p;
    } else {
        // 链表不为空时，先定位到链表的尾端：
        q = till;
        while (q->next != 0) {
            q = q->next;
        }
        printf("请输入您要添加的数据：输入0时停止:");
        // p 指针负责去开辟新的空间：
        p = (struct link *) malloc(LEN);
    }
    // 输入数据：
    scanf("%d", &p->num);
    // 通过循环去添加数据：
    // 此时不管之前链表是否为空，同样都是将数据添加到链表的尾部：
    while (p->num != 0) {
        // 只要有数据添加：节点数+1
        n++;
        // 将节点与后一个节点连接起来：
        q->next = p;
        // 跳转到末尾的那个节点上：
        q = p;
        p = (struct link *) malloc(LEN);
        scanf("%d", &p->num);
    }
    // 让最后一个节点指向空地址：
    q->next = NULL;
    // 释放 p 所占用的空间：
    free(p);
    return till;
}

// 给链表数据排序的函数：
void sort(struct link *head) {
    // 对链表进行排序其实并不是一件简单的事情，因为链表的各个数据并不是紧密连接的
    // 这里先用结构体数组来读取链表的数据，转化为对数组的排序：
    // 排序过后再将数据重新写入链表中，可以保持原链表的结构不发生改变：
    struct link a[n], *p = head, t;
    int i, j, swap;
    // 将链表中的数据写入结构体数组中数组中：
    for (i = 0; i < n; i++) {
        a[i] = *p;
        p = p->next;
    }
    // 通过冒泡排序对数组进行排序：
    for (i = 0; i < n; i++) {
        swap = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (a[j].num > a[j + 1].num) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swap = 1;
            }
        }
        if (swap == 0) {
            break;
        }
    }
    // 将数据重新写入链表中：
    p = head;
    for (i = 0; i < n; i++) {
        p->num = a[i].num;
        p = p->next;
    }
    // 这种方法的特点是能保持原链表的结构不发生改变
    // 改变的只是链表中各个节点的数据：
}