13_C++_链表_回调函数

C++，链表和回调函数，一些知识点和源代码

Ctrl+Alt+L

336人浏览 · 2022-07-31 23:42:19

Ctrl+Alt+L · 2022-07-31 23:42:19 发布

链表

数组的优点

访问元素的速度快
每个元素占用的空间相对于链表节点少

数组的缺点

数组是静态空间，一旦分配内存就不可以动态扩展
要不分配不够 $\rightarrow$ 重新分配内存；要不分配过多 $\rightarrow$ 浪费空间；
对于数组头部进行插入和删除效率低

链表的组成

链表由节点组成；
节点由数据域和指针域组成；
一个简单的链表节点如下：

struct  LinkNode 
{ int num ;  
  struct LinkNode * next; }

链表的分类

按照内存分配的位置

静态链表 $\rightarrow$ 链表分配在栈区
动态链表 $\rightarrow$ 链表分配在堆区

按照链表的形状区域

单向链表：指针域只有下一个节点的位置，最后一个节点的指针域是NULL；
单向循环链表：最后节点的指针域从NULL指向第一个节点的位置；
双向链表：指针域有下一个节点和上一个节点的位置；
双向循环链表：单向循环链表 + 双向链表 $\rightarrow$ 指针域有两个地址，头部和尾部都有地址

链表的实现

单向链表 + 静态链表

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

// 先定义链表的节点
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;
}

单向链表 + 动态链表

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

// 先定义链表的节点
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;
}

带头结点的链表

优点：头节点永远都是固定的
main.c文件：

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include"linklist.h"

int main() 
{
	struct LinkNode* pH = initLinkNode();
	if (foreachLinkNode(pH) > 0) 
	{
		printf("打印成功！\n");
	}
	system("pause");
	return 0;
}

linklist.h文件：

#pragma once
#include <stdio.h>
#include<stdlib.h>
#include<string.h>

// 在.h的文件中创建一个节点
struct LinkNode
{
	// 节点的数据域
	int num;
	// 节点的指针域
	struct LinkNode* next;
};

// 创建链表，让用户输入数据，返回链表的头地址
struct LinkNode* initLinkNode();

// 遍历列表并打印，返回值是int变量用于检测是否打印完了
int foreachLinkNode(struct LinkNode * ln);

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;
}

链表的插入操作

思路：设置两个辅助变量，用来指向当前数据的节点和上一数据的节点；
在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;

}

在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;
}

删除链表的节点

思路：设置两个辅助变量，用来指向当前数据的节点和上一数据的节点；
当删除节点的时候：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;
}

清空/销毁链表

思路：用一个临时变量存放需要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;
}

因为清空后节点，因此再使用foreachLinkNode函数就会报错。

回调函数

函数指针

函数名的本质是函数的入口地址；
函数指针是指向函数入口的指针；

函数指针的写法

// 返回值类型 + （指针函数名）（形参表列）
void (*p)(int,char)

函数指针的定义

先定义出函数类型，再通过类型定义出函数指针

	typedef void(FUNC_TYPE)();
	FUNC_TYPE * pFunc = func;

先定义出函数指针类型，再定义函数指针

	typedef void(*FUNC_TYPE)();
	FUNC_TYPE pFunc = func;

直接定义函数指针变量

	void(* pFunc )() = func;

函数指针数组的定义

void(*FuncArray[3])(int,char)

函数指针案例1——打印任意类型数据

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

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;
}

回调函数案例2——打印任意类型的数组

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/// -- 程序员代码部分 -- ///
// 回调函数
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;
}

回调函数案例3——查找元素是否存在

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


/// -- 用户代码部分 -- ///
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;
}