数据结构--链表入门超详细解析(简单易懂纯原篇)

链表的基础概念这里就不讲了，随便一个搜索引擎就能找到无数答案，我这里想讲点别人不会讲的东西，以及尝试如何让一窍不通于链表的同学快速理解和入门。

此处我们使用C进行演示

---

结点的创建

我们知道链表是由一个个结点串联而成的，而每个结点分为两块区域，一块是数据域，相当于数组中存储的那个数据；另一块是指针域，这里存放的是指向下一个结点的地址。在链表遍历的过程中，我们根据前一个结点的指针域中的那个地址找到下一个结点，就这样一个接一个往下遍历，进行增删改查等一系列基础操作。

知道了结点的基础结构就可以来进行创建了。

typedef struct lint{
  	// 数据域
    int score;
  	// 指针域
    struct lint* next; // 因为next是指向结点的，因此也要是结点的类型
}Lint;

这里使用typedef是为了重命名，省的以后创建指针时还要连带着 struct lint*。之后创建指针就可以直接Lint* p而不是struct lint* p

---

链表初始化

链表中有一个特殊的结点–头结点。头结点的数据域一般不用来存放和其他节点同类的数据，它的诞生是为了在实际应用过程中存放一些数据(下面会演示到)。

我们先来进行无头结点的初始化。

Lint * initLint(){
    // 创建头指针
    Lint* p = NULL;
  	// 创建一个临时指针初始化首元结点，并且用于移动和调整后续结点
    Lint* temp = (Lint*)malloc(sizeof(Lint));
  	temp->score = 90;
  	temp->next = NULL;
  	// 头指针需要指向首元结点，这样才能定位这串链表的位置
  	p = temp;
  	// 手动创建10个元素
    for(int i = 0;i < 10;i++){
        // 从第二个结点开始创建
        Lint * a = (Lint*) malloc(sizeof(Lint));
        a->score = i + 91;
        a->next = NULL;
        // 将当前temp指向的结点的next指向下一个结点
        temp->next = a;
        // temp移到下一个结点。这样在下次循环运行到上一行(line17)时能持续
        temp = temp->next;  // 或 temp = a;
    }
    return p;
}

再来看有头结点的初始化方式(由于存在头结点稍微有些复杂，因此后续的演示会采用有头结点的链表):

Lint * initLint(){
    // 创建头指针，并用其创建头结点
    Lint * p = (Lint*)malloc(sizeof (Lint));
    // 及时指定指针的指向以确保指针安全
    p->next = NULL;
    // 创建一个临时的指针指向头结点以进行后续的操作
    Lint * temp = p;
    for(int i = 0;i < 10;i++){
        // 从首元结点开始创建
        Lint * a = (Lint*) malloc(sizeof(Lint));
        a->score = i + 90;
        a->next = NULL;
        // 将当前temp指向的next指向下一个结点
        temp->next = a;
        // temp移到下一个结点
        temp = temp->next;  // 或 temp = a;
    }
    return p;
}

---

链表的输出

现在我们已经完成了整条链表的手动赋值初始化，最基础的当然就是输出链表了。

基本的思想非常简单，头指针已经指明了链表的头，利用指针输出结点的数据，然后根据指针域中的地址移到下一个结点，循环往复，一直到指针域为空就停止输出。

void showLint(Lint* p){	
  	// 一开始p指针在头结点，这个数据域是空的，因此需要检测其指针域中是否有下一个节点的地址。如果为空，则退出循环
    while (p->next){
      	// p从头结点移出，到首元结点开始输出
        p = p->next;
        printf("%d\t", p->score);
    }
    printf("\n");
}

运行结果:

---

基础操作

1. 增

增加结点的逻辑是：将新增结点的指针域指向后一个结点，然后将原链表中的前一个结点的指针域指向新增的结点。(注意顺序不能颠倒，否则会导致插入位置后面的结点全部丢失)

Lint* insertLint(Lint* p,int n, int num){		// 将num插入到第n个位置
    Lint * temp = p;
    // 通过遍历将temp指针移到指向插入位置的直接前驱结点的位置
    for (int i = 1;i < n;i++){
        // 防止超过链表现有长度
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    // 创建插入的新结点
    Lint * a = (Lint*) malloc(sizeof (Lint));
    a->score = num;
  	// 新节点数据域指向原位置后一个结点
    a->next = temp->next;
  	// temp后移一个结点
    temp->next = a;
    return p;
}

主函数中调用

printf("请输入插入的位置和数字，用空格隔开:");
    scanf("%d%d", &n, &num);
    insertLint(p, n, num);
    showLint(p);

运行结果：

2. 删

逻辑和增差不多，将temp指针指向要删除结点的直接前驱，将指针域指向下下个结点，然后释放删除结点的内存即可。

Lint* delLint(Lint* p,int n){
    Lint * temp = p;
    // 用于存储临时删除的结点
    Lint * back = NULL;
    // temp移到删除结点的直接前驱结点
    for (int i = 1;i < n;i++){
        // 防止越过链表
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    // 临时存储被删除结点,防止丢失
    back = temp->next;
  	// 指向下下个结点
    temp->next = temp->next->next;
    // 手动释放内存防止泄露
    free(back);
    return p;
}

在主函数中调用:

printf("请输入删除第几个元素:");
scanf("%d", &n);
delLint(p, n);
showLint(p);

运行结果:

3. 改

这个逻辑更简单，指针指向要修改的结点，直接修改其score值

Lint* changeLint(Lint* p,int n, int num){
  	// temp可以一开始就指向首元结点
    Lint * temp = p->next;
    for (int i = 1;i < n;i++){
        // 防止越过链表
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    // 修改
    temp->score = num;
    return p;
}

运行结果:

4. 查

查的基本思想是指针进行遍历链表，对每个节点的数据域进行对比，如果相同就可以直接退出返回结果了。如果一直到链表结束还没有匹配成功就说明没有找到。

int searchLint(Lint* p, int num){
    Lint * temp = p;
    int i;  // 用于记数
    for(i = 1;temp->next != NULL;i++){
      	// 因为是从头结点开始的，因此要先移到首元结点
        temp = temp->next;
        if (temp->score == num)return i;	// 返回i表示找到的位置
    }
    return 0;	// 返回0表示未找到
}

当然也可以将头结点的数据域用于存储位置，而无需单独创建一个i用于记录位置。

int searchLint(Lint* p, int num){
    Lint * temp = p;
    for(p->score = 1;temp->next != NULL;p->score++){
        temp = temp->next;
        if (temp->score == num)return p->score;
    }
    return 0;
}

主函数进行调用

printf("请输入需要查询的分数:");
scanf("%d", &num);
if (!searchLint(p, num))
  printf("未查询到该分数");
else
  printf("在第%d个元素", searchLint(p, num));

运行结果如下:

---

完整代码

#include "stdio.h"
#include "stdlib.h"
typedef struct lint{
    int score;
    struct lint* next;
}Lint;
Lint * initLint(){
    Lint * p = (Lint*)malloc(sizeof (Lint));
    p->next = NULL;
    Lint * temp = p;
    for(int i = 0;i < 10;i++){
        Lint * a = (Lint*) malloc(sizeof(Lint));
        a->score = i + 90;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}
void showLint(Lint* p){
    while (p->next){
        p = p->next;
        printf("%d\t", p->score);
    }
    printf("\n");
}

// 增
Lint* insertLint(Lint* p,int n, int num){
    Lint * temp = p;
    for (int i = 1;i < n;i++){
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    Lint * a = (Lint*) malloc(sizeof (Lint));
    a->score = num;
    a->next = temp->next;
    temp->next = a;
    return p;
}

// 删
Lint* delLint(Lint* p,int n){
    Lint * temp = p;
    Lint * back = NULL;
    for (int i = 1;i < n;i++){
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    back = temp->next;
    temp->next = temp->next->next;
    free(back);
    return p;
}

// 改
Lint* changeLint(Lint* p,int n, int num){
    Lint * temp = p->next;
    for (int i = 1;i < n;i++){
        if (temp->next == NULL){
            printf("位置错误!\n");
            return p;
        }
        temp = temp->next;
    }
    temp->score = num;
    return p;
}

// 查(头结点存储位置)
int searchLint(Lint* p, int num){
    Lint * temp = p;
    for(p->score = 1;temp->next != NULL;p->score++){
        temp = temp->next;
        if (temp->score == num)return p->score;
    }
    return 0;
}

int main(){
    int n, num;
    Lint* p = initLint();
    showLint(p);
    // 增
    printf("请输入插入的位置和数字，用空格隔开:");
    scanf("%d%d", &n, &num);
    insertLint(p, n, num);
    showLint(p);
    // 删
    printf("请输入删除第几个元素:");
    scanf("%d", &n);
    delLint(p, n);
    showLint(p);
    // 改
    printf("请输入修改第几个元素为什么数,空格隔开:");
    scanf("%d%d", &n, &num);
    changeLint(p, n, num);
    showLint(p);
    // 查
    printf("请输入需要查询的分数:");
    scanf("%d", &num);
    if (!searchLint(p, num))
        printf("未查询到该分数");
    else
        printf("在第%d个元素", searchLint(p, num));
}

---

约瑟夫问题

//约瑟夫问题：n 个人围成一个圆圈，首先第1个人开始，一个人一个人顺时针报数, 报到第m个人，令其出列；然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人时，此人即为优胜者。
//例如：n=8，m=3
#include "stdio.h"
#include "stdlib.h"
typedef struct lint{
    int num;
    struct lint* next;
}Lint;
// 带有头结点的链表初始化
Lint* initLint(int n){
    Lint* p = (Lint*) malloc(sizeof(Lint));
    Lint* temp = p;
    p->next = NULL;
    for (int i = 0; i < n; i++) {
        Lint* a = (Lint*) malloc(sizeof(Lint));
        a->num = i+1;
        a->next = NULL;
        temp->next = a;
        temp = a;
    }
    // 循环链表
    temp->next = p->next;
    return p;
}
// 实现功能函数
void Func(Lint* p, int m){
    Lint* temp = p;
    // 就剩下自己一个结点
    while(temp->next != temp->next->next){
        for (int i = 0;i < m-1;i++)temp = temp->next;
        printf("%d\t", temp->next->num);
        // 删除结点
        temp->next = temp->next->next;
    }
    printf("%d", temp->num);
}
int main(){
    int n, m;
    printf("请输入n和m的值(用空格隔开):");
    scanf("%d%d", &n, &m);
    if (n >= m){
        Lint* p = initLint(n);
        Func(p, m);
    }else
        printf("输入错误!");
    return 0;
}