链表的基础概念这里就不讲了,随便一个搜索引擎就能找到无数答案,我这里想讲点别人不会讲的东西,以及尝试如何让一窍不通于链表的同学快速理解和入门。
此处我们使用C进行演示
结点的创建
我们知道链表是由一个个结点串联而成的,而每个结点分为两块区域,一块是数据域,相当于数组中存储的那个数据;另一块是指针域,这里存放的是指向下一个结点的地址。在链表遍历的过程中,我们根据前一个结点的指针域中的那个地址找到下一个结点,就这样一个接一个往下遍历,进行增删改查等一系列基础操作。

知道了结点的基础结构就可以来进行创建了。
1 2 3 4 5 6
| typedef struct lint{ int score; struct lint* next; }Lint;
|
这里使用typedef是为了重命名,省的以后创建指针时还要连带着 struct lint*
。之后创建指针就可以直接Lint* p而不是struct lint* p
链表初始化
链表中有一个特殊的结点–头结点。头结点的数据域一般不用来存放和其他节点同类的数据,它的诞生是为了在实际应用过程中存放一些数据(下面会演示到)。
我们先来进行无头结点的初始化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| Lint * initLint(){ Lint* p = NULL; Lint* temp = (Lint*)malloc(sizeof(Lint)); temp->score = 90; temp->next = NULL; p = temp; for(int i = 0;i < 10;i++){ Lint * a = (Lint*) malloc(sizeof(Lint)); a->score = i + 91; a->next = NULL; temp->next = a; temp = temp->next; } return p; }
|
再来看有头结点的初始化方式(由于存在头结点稍微有些复杂,因此后续的演示会采用有头结点的链表):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| 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; }
|
链表的输出
现在我们已经完成了整条链表的手动赋值初始化,最基础的当然就是输出链表了。
基本的思想非常简单,头指针已经指明了链表的头,利用指针输出结点的数据,然后根据指针域中的地址移到下一个结点,循环往复,一直到指针域为空就停止输出。
1 2 3 4 5 6 7 8 9
| void showLint(Lint* p){ while (p->next){ p = p->next; printf("%d\t", p->score); } printf("\n"); }
|
运行结果:

基础操作
1. 增

增加结点的逻辑是:将新增结点的指针域指向后一个结点,然后将原链表中的前一个结点的指针域指向新增的结点。(注意顺序不能颠倒,否则会导致插入位置后面的结点全部丢失)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| 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; }
|
主函数中调用
1 2 3 4
| printf("请输入插入的位置和数字,用空格隔开:"); scanf("%d%d", &n, &num); insertLint(p, n, num); showLint(p);
|
运行结果:

2. 删
逻辑和增差不多,将temp指针指向要删除结点的直接前驱,将指针域指向下下个结点,然后释放删除结点的内存即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| 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; }
|
在主函数中调用:
1 2 3 4
| printf("请输入删除第几个元素:"); scanf("%d", &n); delLint(p, n); showLint(p);
|
运行结果:

3. 改
这个逻辑更简单,指针指向要修改的结点,直接修改其score值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 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; }
|
运行结果:

4. 查
查的基本思想是指针进行遍历链表,对每个节点的数据域进行对比,如果相同就可以直接退出返回结果了。如果一直到链表结束还没有匹配成功就说明没有找到。
1 2 3 4 5 6 7 8 9 10
| 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; } return 0; }
|
当然也可以将头结点的数据域用于存储位置,而无需单独创建一个i
用于记录位置。
1 2 3 4 5 6 7 8
| 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; }
|
主函数进行调用
1 2 3 4 5 6
| printf("请输入需要查询的分数:"); scanf("%d", &num); if (!searchLint(p, num)) printf("未查询到该分数"); else printf("在第%d个元素", searchLint(p, num));
|
运行结果如下:

完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| #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)); }
|
约瑟夫问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
#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; }
|