-
12_C++_链表_回调函数
链表
数组的优点
访问元素的速度快
每个元素占用的空间相对于链表节点少数组的缺点
数组是静态空间，一旦分配内存就不可以动态扩展
要不分配不够 → \rightarrow → 重新分配内存；要不分配过多 → \rightarrow → 浪费空间；
对于数组头部进行插入和删除效率低链表的组成
- 链表由节点组成；
- 节点由数据域和指针域组成；
- 一个简单的链表节点如下：
struct LinkNode { int num ; struct LinkNode * next; }- 1
- 2
- 3
链表的分类
按照内存分配的位置
静态链表 → \rightarrow → 链表分配在栈区
动态链表 → \rightarrow → 链表分配在堆区按照链表的形状区域
单向链表：指针域只有下一个节点的位置，最后一个节点的指针域是
NULL；
单向循环链表：最后节点的指针域从NULL指向第一个节点的位置；
双向链表：指针域有下一个节点和上一个节点的位置；
双向循环链表：单向循环链表 + 双向链表 → \rightarrow → 指针域有两个地址，头部和尾部都有地址链表的实现
单向链表 + 静态链表
#include#include #include // 先定义链表的节点 typedef struct LinkNode { int num; struct LinkNode* next; } linknode; void test01() { // 先定义节点 linknode node1 = { 10,NULL }; linknode node2 = { 20,NULL }; linknode node3 = { 30,NULL }; linknode node4 = { 40,NULL }; linknode node5 = { 50,NULL }; // 对节点进行链接 node1.next = &node2; node2.next = &node3; node3.next = &node4; node4.next = &node5; // 对链表进行遍历 // 先定义一个当前的指针指向链表头部 linknode* pCurrent = &node1; while (pCurrent != NULL) { // 当链表指针不是NULL的时候 // 打印链表的数据 printf("%d\n", pCurrent->num); // 紧接着将链表指针指向这个结构体的next成员 // next本身是struct *类型，可以被指向 pCurrent = pCurrent->next; } } int main() { test01(); system("pause"); return 0; } - 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
单向链表 + 动态链表
#include#include #include // 先定义链表的节点 typedef struct LinkNode { int num; struct LinkNode* next; } linknode; void test01() { // 先定义节点 linknode node1 = { 10,NULL }; linknode node2 = { 20,NULL }; linknode node3 = { 30,NULL }; linknode node4 = { 40,NULL }; linknode node5 = { 50,NULL }; // 对节点进行链接 node1.next = &node2; node2.next = &node3; node3.next = &node4; node4.next = &node5; // 对链表进行遍历 // 先定义一个当前的指针指向链表头部 linknode* pCurrent = &node1; while (pCurrent != NULL) { // 当链表指针不是NULL的时候 // 打印链表的数据 printf("%d\n", pCurrent->num); // 紧接着将链表指针指向这个结构体的next成员 // next本身是struct *类型，可以被指向 pCurrent = pCurrent->next; } } void test02() { // 在堆区开辟空间，创建节点 linknode* n1 = malloc(sizeof(linknode)); linknode* n2 = malloc(sizeof(linknode)); linknode* n3 = malloc(sizeof(linknode)); linknode* n4 = malloc(sizeof(linknode)); // 对节点进行链接 n1->num = 100; n1->next = n2; n2->num = 200; n2->next = n3; n3->num = 300; n3->next = n4; n4->num = 400; n4->next = NULL; // 遍历链表 linknode* pCurrent = n1; while (pCurrent != NULL) { printf("%d\n", pCurrent->num); pCurrent = pCurrent->next; } // malloc结束后都要进行释放 free(n1); free(n2); free(n3); free(n4); } int main() { // test01(); test02(); system("pause"); return 0; } - 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
带头结点的链表
优点：头节点永远都是固定的
main.c文件：#include#include #include #include"linklist.h" int main() { struct LinkNode* pH = initLinkNode(); if (foreachLinkNode(pH) > 0) { printf("打印成功！\n"); } system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
linklist.h文件：
#pragma once #include#include #include // 在.h的文件中创建一个节点 struct LinkNode { // 节点的数据域 int num; // 节点的指针域 struct LinkNode* next; }; // 创建链表，让用户输入数据，返回链表的头地址 struct LinkNode* initLinkNode(); // 遍历列表并打印，返回值是int变量用于检测是否打印完了 int foreachLinkNode(struct LinkNode * ln); - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
linklist.c文件：
#define _CRT_SECURE_NO_DEPRECATE #include"linklist.h" struct LinkNode* initLinkNode() { // 创建带头链表的“头” struct LinkNode* pHeader = malloc(sizeof(struct LinkNode)); // 对“头”进行赋值 // num值为-1表示“结束/空(NULL)” pHeader->num = -1; pHeader->next = NULL; // 创建一个“尾”节点 struct LinkNode* pTail = malloc(sizeof(struct LinkNode)); // 对“尾”进行赋值 // num值为-1表示“结束/空(NULL)” pTail->num = -1; pTail->next = NULL; // 初始化的时候，“头”等于“尾” pHeader = pTail; // 定义一个变量承载用户的输入 int val = -1; while (1) { // 与用户交互，让用户输入节点数据 printf("现在请您输入链表节点数据,-1表示结束：\n"); scanf("%d", &val); // 检测用户输入的数据是否是-1了 if (val == -1) { break; } // 创建新节点 struct LinkNode * newNode = malloc(sizeof(struct LinkNode)); newNode->num = val; newNode->next = NULL; // 更新链表指向 pTail->next = newNode; pTail = newNode; } return pHeader; } int foreachLinkNode(struct LinkNode* ln) { // 先定义一个flag int flag = 0; // 判断传入的指针是否是空指针 if (ln == NULL) { flag = -1; } // 遍历链表 struct LinkNode* pCurrent = ln->next; while (pCurrent != NULL) { printf("%d\n", pCurrent->num); pCurrent = pCurrent->next; flag = 1; } return flag; }- 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
链表的插入操作
思路：设置两个辅助变量，用来指向当前数据的节点和上一数据的节点；
在linklist.c文件写以下函数：int insertLinkNode(struct LinkNode* ln, int oldValue, int newValue) { int result = 1; if (ln == NULL) { result = 0; } // 定义两个辅助指针 struct LinkNode* pNow = malloc(sizeof(struct LinkNode*)); struct LinkNode* pPre = malloc(sizeof(struct LinkNode*)); pNow = ln->next; pPre = ln; // 对链表进行查找 while (pNow != NULL) { if (pNow->num == oldValue) {break;} pPre = pNow; pNow = pNow->next; } // 创建节点 struct LinkNode* temp = malloc(sizeof(struct LinkNode)); temp->num = newValue; temp->next = NULL; // 插入操作 pPre->next = temp; temp->next = pNow; return result; }- 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
在main.c文件中调用这个函数：
int main() { struct LinkNode* pH = initLinkNode(); if (foreachLinkNode(pH) > 0) { printf("打印成功！\n"); } if (insertLinkNode(pH, 20, 200)) { foreachLinkNode(pH); } system("pause"); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
删除链表的节点
思路：设置两个辅助变量，用来指向当前数据的节点和上一数据的节点；
当删除节点的时候：pPre->next = pNow->next;
在linklist.c文件写以下函数：int deleteLinkNode(struct LinkNode* ln, int d) { int result = 1; if (ln == NULL) { result = 0; } // 定义两个辅助指针 struct LinkNode* pNow = malloc(sizeof(struct LinkNode*)); struct LinkNode* pPre = malloc(sizeof(struct LinkNode*)); pNow = ln->next; pPre = ln; // 对链表进行查找 while (pNow != NULL) { if (pNow->num == d) { break; } pPre = pNow; pNow = pNow->next; } // 删除节点 pPre->next = pNow->next; free(pNow); return result; }- 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
清空/销毁链表
思路：用一个临时变量存放需要
free的节点struct LinkNode* clearLinkNode(struct LinkNode* ln) { int result = 1; if (ln == NULL) { result = 0; } // 定义一个辅助指针 struct LinkNode* pCurrent = ln->next; struct LinkNode* pTemp = NULL; // 对链表进行查找 while (pCurrent != NULL) { pTemp = pCurrent->next; free(pCurrent); pCurrent = pTemp; } return result; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
因为清空后节点，因此再使用
foreachLinkNode函数就会报错。回调函数
函数指针
函数名的本质是函数的入口地址；
函数指针是指向函数入口的指针；函数指针的写法
// 返回值类型 + （指针函数名）（形参表列） void (*p)(int,char)- 1
- 2
函数指针的定义
- 先定义出函数类型，再通过类型定义出函数指针
typedef void(FUNC_TYPE)(); FUNC_TYPE * pFunc = func;- 1
- 2
- 先定义出函数指针类型，再定义函数指针
typedef void(*FUNC_TYPE)(); FUNC_TYPE pFunc = func;- 1
- 2
- 直接定义函数指针变量
void(* pFunc )() = func;- 1
函数指针数组的定义
void(*FuncArray[3])(int,char)- 1
函数指针案例1——打印任意类型数据
#include#include #include struct Person { int age; char sex[64]; }; void intPrint(void* data) { int* num = data; printf("%d\n", *num); }; void charPrint(void* data) { char* num = data; printf("%c\n", *num); }; void doublePrint(void* data) { double* num = data; printf("%f\n", *num); }; void structPrint(void* data) { struct Person* num = data; printf("%d %s\n", num->age, num->sex); }; void myPrint(void* dataAddress,void(*fName)(void*)) { fName(dataAddress); }; int main() { // 用户自己定义一个变量和他的数据类型 int a = 10; char b = 'a'; double c = 3.1415; struct Person d = { 18,'F' }; // 采用回调函数的方式显示各种变量的数据类型 myPrint(&a, intPrint); myPrint(&b, charPrint); myPrint(&c, doublePrint); myPrint(&d, structPrint); system("pause"); return 0; } - 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
回调函数案例2——打印任意类型的数组
#include#include #include /// -- 程序员代码部分 -- /// // 回调函数 void typePrint(void* p, void(*fName)(void*), int size, int lenth) { // 用单字节的字符型指针承接void char* c = p; for (int i = 0; i < lenth; i++) { // 将地址和用户写的函数放进来 fName(c); // 遍历的时候，依次跳过这个变量类型的大小 c += size; } } /// -- 用户代码部分 -- /// struct Person { int age; char name[128]; }; void intPrint(void* data) { int* num = data; printf("%d\n", *num); } void structPrint(void* data) { struct Person* person = data; printf("%d %s\n", person->age, person->name); } void test01() { int arr[5] = { 1,2,3,4,5 }; struct Person student[4] = { {18,'aaa'},{19,'bbb'},{20,'ccc'},{18,'ddd'}}; // 输出数组的首地址、用户写的函数、变量类型占空间大小、数组长度 int len1 = sizeof(arr) / sizeof(int); typePrint(arr, intPrint, sizeof(int),len1); int len2 = sizeof(student) / sizeof(struct Person); typePrint(student, structPrint, sizeof(struct Person), len2); return 0; } int main() { test01(); system("pause"); return 0; } - 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
回调函数案例3——查找元素是否存在
#include#include #include /// -- 用户代码部分 -- /// struct Person { int age; char name[1024]; }; int myCompare(void* data1, void* data2) { struct Person* p1 = data1; struct Person* p2 = data2; if (p1->age == p2->age && strcmp(p1->name, p2->name) == 0) { return 1; } else { return 0; } } void test01() { struct Person student[4] = { {18,'aaa'},{19,'bbb'},{20,'ccc'},{18,'ddd'} }; // 输出数组的首地址、用户写的函数、变量类型占空间大小、数组长度 int len2 = sizeof(student) / sizeof(struct Person); struct Person compareData = { 30,'ccc' }; FindElement(student, myCompare, sizeof(struct Person), len2, &compareData); return 0; } /// -- 程序员代码部分 -- /// int FindElement(void* p, int(*fName)(void*, void*), int size, int lenth, void* comparedata) { struct Person* cpdata = comparedata; printf("对比的数据是：%d %s 。\n", cpdata->age, cpdata->name); char* pP = p; int res = NULL; for (int i = 0; i < lenth; i++) { pP += size; res = fName(pP, comparedata); if (res == 1) { printf("成功了！\n"); break; } } printf("找不到！\n"); } /// -- 主程序部分 -- /// int main() { test01(); system("pause"); return 0; } - 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
-
相关阅读:
git解决冲突的方法。
中国男装产业政府战略管理与区域发展战略研究咨询报告
基于matlab创建基于物理统计的雷达模型（附源码）
uniapp或者vue项目环境变量的模式来自动替换网络请求的baseUrl
一起Talk Android吧（第四百二十一回：绘图中添加阴影）
YOLOv5项目实战（3）— 如何批量命名数据集中的图片
随笔 | 写在九月末的这一天
win10 安装openssl并使用openssl创建自签名证书
【Logback】开发环境怎么组织xml文件构建日志策略
机器人路径规划：基于Q-learning算法的移动机器人路径规划，可以自定义地图，修改起始点，提供MATLAB代码
- 原文地址：https://blog.csdn.net/m0_48948682/article/details/126085612
