• c—线性表

    文章目录

    线性表基本概念

    基本概念

    • 线性表是零个或者多个数据元素的有限序列。
    • 特性：
      在这里插入图片描述

    数学定义

    • 定义
      在这里插入图片描述
    • 性质
      在这里插入图片描述

    线性表的顺序存储

    顺序存储的概念

    在这里插入图片描述

    线性表顺序存储设计与实现

    • 案例：动态数组
      在这里插入图片描述

    示例：

    1. 建立头文件——DynamicArray.h
    #pragma once//防止头文件重复包含
//#ifndef DYNAMIC_ARRAY_H
//#define DYNAMIC_ARRAY_H


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//声明
//头文件放一些接口

//动态增长内存，将数据放到堆上

//动态数组结构体定义
typedef struct DYNAMICARRAY
{
	int* pAdder;//存放数据的地址
	int size;//当前元素个数
	int capacity;//容量，容器当前能容纳多少元素
}Dynamic_Array;

//写一些关于DYNAMICARRAY结构体操作的函数
//初始化
Dynamic_Array* Init_Array();
//插入
void Push_Array(Dynamic_Array* arr, int value);
//根据位置删除
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos);
//根据值删除
void RemoveByValue_Array(Dynamic_Array* arr, int value);
//查找
 int Find_Array(Dynamic_Array* arr, int value);
 //打印
 void Printf_Array(Dynamic_Array* arr);
//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr);
//清空数组
void Clear_Array(Dynamic_Array* arr);
//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr);
//获得动态数组当前元素个数
int Size_Array(Dynamic_Array* arr);
//根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos);

//#endif

    • 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
    1. 建立 DynamicArray.c 源文件，进行各个函数的编写
    #include"DynamicArray.h"

//初始化
Dynamic_Array* Init_Array()
{
	Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array));
	myArray->size = 0;
	myArray->capacity = 20;
	myArray->pAdder = (int*)malloc(sizeof(int)*myArray->capacity);
	return myArray;
}


//插入
void Push_Array(Dynamic_Array* arr, int value)
{
	if (arr == NULL)
	{
		return ;
	}
	//判断空间是否足够
	if (arr->size == arr->capacity)
	{
		//第一步，开辟更大的一块空间 ，新空间是就空间的2倍
		int* newpAdder= (int*)malloc(sizeof(int)*arr->capacity * 2);
		//第二部拷贝数据
		memcpy(newpAdder, arr->pAdder, arr->capacity * sizeof(int));
		//释放就空间
		free(arr->pAdder);
		//更新容量
		arr->capacity = arr->capacity * 2;
		arr->pAdder = newpAdder;
		
	}
	// 插入新元素
		arr->pAdder[arr->size] = value;
		arr->size++;
}


//根据位置删除
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos)
{

	if (arr == NULL)
	{
		return ;
	}
	//判断位置是否有效
	if (pos < 0 || pos >= arr->size)
	{
		return;
	}
	//删除元素
	for (int i = pos; i < arr->size - 1; i++)
	{
		arr->pAdder[i] = arr->pAdder[i + 1];
	}
	arr->size--;
}


//根据值删除value（第一次出现时）
void RemoveByValue_Array(Dynamic_Array* arr, int value)
{
	if (arr == NULL)
	{
		return ;
	}
	//找到值的位置
	int pos= Find_Array(arr,value);
	
	//根据位置删除，调用位置删除函数
	RemoveByPos_Arrray(arr, pos);
}


//查找
int Find_Array(Dynamic_Array* arr, int value)
{
	if (arr == NULL)
	{
		return -1;
	}
	int pos = -1;
	for (int i = 0; i < arr->size; i++)
	{
		if (arr->pAdder[i] == value)
		{
			pos = i;
			break;
		}
	}
	return pos;
}


//打印
void Printf_Array(Dynamic_Array* arr)
{
	if (arr == NULL)
	{
		return;
	}
	for (int i = 0; i < arr->size; i++)
	{
		printf("%d ", arr->pAdder[i]);
	}
	printf("\n");
}


//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr)
{
	if (arr == NULL)
	{
		return;
	}
	if (arr->pAdder != NULL)
	{
		free(arr->pAdder);
		
	}
	free(arr);
}


//清空数组
void Clear_Array(Dynamic_Array* arr)
{
	if (arr == NULL)
	{
		return ;
	}
	arr->size = 0;
}


//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr)
{
	if (arr == NULL)
	{
		return -1;
	}
	return arr->capacity;
}


//获得动态数组当前元素个数
int Size_Array(Dynamic_Array* arr)
{
	if (arr == NULL)
	{
		return -1;
	}
	return arr->size;
}


//根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos)
{
	return arr->pAdder[pos];
}

    • 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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    1. 建立 01动态数组.c 源文件，进行测试
    #include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include"DynamicArray.h"

void test01()
{
	//初始化动态数组
	Dynamic_Array* myArray=Init_Array();

	printf("数组容量：%d\n", Capacity_Array(myArray));
	printf("数组大小：%d\n", Size_Array(myArray));
	
	//插入元素
	for (int i = 0; i <30; i++)
	{
		Push_Array(myArray, i);
	}
	Printf_Array(myArray);
	printf("数组容量：%d\n", Capacity_Array(myArray));
	printf("数组大小：%d\n", Size_Array(myArray));

	RemoveByPos_Arrray(myArray, 2);
	RemoveByValue_Array(myArray, 8);
	//打印
	Printf_Array(myArray);
	//查找元素5的位置
	int pos = Find_Array(myArray, 5);
	printf("元素5的位置为：%d\n", pos);

	//释放
	FreeSpace_Array(myArray);
}
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

    结果：

    数组容量：20
数组大小：0
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
数组容量：40
数组大小：30
0 1 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
元素5的位置为：4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    线性表的链式存储

    基本概念

    在这里插入图片描述

    单项链表的设计与实现

    • 单向链表的数据域与指针域是放在一起的，插入新结点的时候，需要开辟新的空间来创建新结点。
      指定位置插入元素的过程
      在这里插入图片描述
    • 示例：单项列表
    1. 先建立一个头文件，LinkList.h 头文件
    #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//链表节点
typedef struct LINKNODE
{
	void* data;//无类型指针可以指向任何类型的数据的地址
	struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef struct LINKLIST
{
	LinkNode* head;//头结点，属于结构体嵌套  
	int size;//当前元素个数
	//链表不需要提前设置容量
}LinkList;

//打印函数指针
typedef void(*PRINTLINKNODE)(void*);//typedef定义函数指针
//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list,int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list, void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);//???
//释放链表内存
void FreeSpace_LinkList(LinkList* list);

    • 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
    1. 建立一个 LinkList.c 的源文件，进行各个函数的编写
    #include"LinkList.h"


//初始化链表
LinkList* Init_LinkList()//维护结构体，对结构体进行操作
{
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head = 0;
	//给头节点开辟空间，头结点不保存数据信息
	list->head = (LinkNode*)malloc(sizeof(LinkNode));
	//头结点初始化,头结点的下一个结点才是链表的第一个结点
	list->head->data = NULL;
	list->head->next = NULL;
	return list;
}


//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data)
{
	if (list ==NULL ||data==NULL)
	{
		return;
	}
	//对于pos越界的友好处理
	if (pos<0 || pos>list->size)
	{
		pos = list->size;
	}
	//创建新结点
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	newnode->data = data;
	newnode->next = NULL;
	//找寻结点,辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//将新结点插入链表
	newnode->next = pCurrent->next;
	pCurrent->next = newnode;

	list->size++;
}


//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos)
{
	if (list == NULL)
	{
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	//查找待删除结点的上一个结点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//缓存删除的结点
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	//释放删除结点的内存
	free(pDel);
	list->size--;
}


//获得链表的长度
int Size_LinkList(LinkList* list)
{
	return list->size;
}


//查找
int Find_LinkList(LinkList* list, void* data)
{
	if (list == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}
	LinkNode* pCurrent = list->head->next;
	int i=0;
	while (list != NULL)
	{
		if (pCurrent->data == data)
		{
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}	
	return i;
}


//返回第一个节点的元素
void* Front_LinkList(LinkList* list)
{
	return list->head->next->data;
}


//打印链表节点的元素
void Print_LinkList(LinkList* list, PRINTLINKNODE print)//???
{
	if (list == NULL)
	{
		return;
	}
	//辅助指针变量
	LinkNode* pCurrent = list->head->next;
	while (pCurrent != NULL)
	{
		print(pCurrent->data);//调用函数
		pCurrent = pCurrent->next;
	}
}


//释放链表内存
void FreeSpace_LinkList(LinkList* list)
{
	if (list == NULL)
		return;
	//辅助指针变量，先释放结点内存
	LinkNode* pCurrent = list->head;
	while (pCurrent!=NULL)
	{
		//缓存下一个结点，要不然每遍历一个就释放一个，会不好查找下一个结点
		LinkNode* pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;
	}
	//释放链表
	list->size = 0;
	free(list);
}

    • 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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    1. 建立 02单项列表.c 源文件，进行测试
    #include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include"LinkList.h"

//自定义的数据类型
typedef struct PERSON
{
	char name[21];
	int age;
	int score;
}person;

//打印函数
void myPrint(void* data)
{
	person* p = (person*)data;
	printf("名字：%s 年龄：%d 成绩：%d\n", p->name, p->age, p->score);
}
int main()
{
	//创建列表
	LinkList* list = Init_LinkList();
	//创建数据类型
	person p1 = { "张三",18,98 };
	person p2 = { "李四",16,89 };
	person p3 = { "王五",15,99 };
	person p4 = { "刘六",19,86 };
	person p5 = { "陈七",23,87 };
	//数据插入链表
	printf("-------------插入--------------\n");
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);
	//打印
	Print_LinkList(list, myPrint);

	//查找
	printf("-------------查找---------------\n");
	int pos=Find_LinkList(list, &p2);//当调用的为有返回值的函数的时候，要设置返回值
	printf("所查找的元素位置为：%d\n",pos );
	
	//删除
	printf("--------------删除位置3的元素---------------\n");
	RemoveByPos_LinkList(list, 3);
	Print_LinkList(list,myPrint);
	
	//返回第一个结点
	printf("-----------------返回第一个结点元素--------------\n");
	person* ret = Front_LinkList(list);
	printf("姓名：%s 年龄：%d 成绩： %d\n", ret->name, ret->age, ret->score);
	//释放列表
	FreeSpace_LinkList(list);


	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

    结果：

    -------------插入--------------
名字：陈七 年龄：23 成绩：87
名字：刘六 年龄：19 成绩：86
名字：王五 年龄：15 成绩：99
名字：李四 年龄：16 成绩：89
名字：张三 年龄：18 成绩：98
-------------查找---------------
所查找的元素位置为：3
--------------删除位置3的元素---------------
名字：陈七 年龄：23 成绩：87
名字：刘六 年龄：19 成绩：86
名字：王五 年龄：15 成绩：99
名字：张三 年龄：18 成绩：98
-----------------返回第一个结点元素--------------
姓名：陈七 年龄：23 成绩： 87

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    企业链表的设计与实现

    • 企业链表的数据域与指针域是分离的，且代码量较少。
      示例：企业链表
    1. 建立一个 LinkList.h 头文件
    #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//链表小结点
typedef struct LINKNODE
{
	struct LINKNODE* next;
}LinkNode;

//链表结点
typedef struct LINKLIST
{
	LinkNode head;
	int size;
}LinkList;


//定义打印函数指针
typedef void(*PRIENTFNODE)(LinkNode*);
//比较函数指针
typedef int(*COMPARENODE)(LinkNode*, LinkNode*);

//初始化
LinkList* Init_LinkList();
//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);//插入的数据为LinkNode*类型的
//删除
void Remove_LinkList(LinkList* list, int pos);
//查找
int Find_LinkList(LinkList* list, LinkNode* data,COMPARENODE compare);
//返回链表大小
int Size_LinkList(LinkList* list);
//打印
void Printf_LinkList(LinkList* list, PRIENTFNODE printf);
//释放链表内存
void Free_LinkList(LinkList* list);

    • 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
    1. 建立一个 LinkList.c 的源文件
    #include"LinkList.h"



//初始化
LinkList* Init_LinkList()
{
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head.next = NULL;
	list->size = 0;
	return list;
}


//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data)//插入的数据为LinkNode*类型的
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	if (pos<0 || pos>list->size)
	{
		pos = list->size;
	}
	//插入新节点
	LinkNode* pcurrent = &(list->head);//因为在LinkList.h中定义LinkList时，head不是指针类型，所以要转换成地址类型
	for (int i = 0; i < pos; i++)
	{
		pcurrent = pcurrent->next;
	}
	//插入新结点
	data->next = pcurrent->next;
	pcurrent->next = data;
	list->size++;
}


//删除
void Remove_LinkList(LinkList* list, int pos)
{
	if (list == NULL)
	{
		return;
	}
	if (pos<0 || pos>list->size)
	{
		return;
	}
	//辅助结点
	LinkNode* pcurrent = &(list->head);
	for (int i = 0; i < pos; i++)
	{
		pcurrent = pcurrent->next;
	}
	//删除结点
	pcurrent->next = pcurrent->next->next;
	list->size--;

}


//查找
int Find_LinkList(LinkList* list, LinkNode* data, COMPARENODE compare)
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	LinkNode* pcurrent = list->head.next;
	int index = 0;
	while (pcurrent != NULL)
	{
		if (compare(pcurrent, data) == 0)
		{
			break;
		}
		pcurrent = pcurrent->next;
		index++;
	}
	return index;
}


//返回链表大小
int Size_LinkList(LinkList* list)
{
	return 0;
}


//打印
void Printf_LinkList(LinkList* list, PRIENTFNODE printf)
{
	if (list == NULL)
	{
		return;
	}
	//辅助指针
	LinkNode* pcurrent = list->head.next;
	while (pcurrent != NULL)
	{
		printf(pcurrent);
		pcurrent = pcurrent->next;
	}
}


//释放链表内存
void Free_LinkList(LinkList* list)
{
	if (list == NULL)
	{
		return;
		free(list);
	}
}

    • 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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    1. 建立一个 03企业链表.c 的源文件，进行测试
    #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkList.h"

typedef struct PERSON
{
	LinkNode node;
	char name[21];
	int age;
}person;
void myprintf(LinkNode* data)
{
	person* p = (person*)data;
	printf("姓名：%s 年龄：%d\n", p->name, p->age);
}
int main()
{
	//创建链表
	LinkList* list = Init_LinkList();
	//创建数据
	/*person p1 = { "张三",18 }; 
	person p2 = { "李四",19 };
	person p3 = { "王五",17 };*/   //不能这样写，因为person还有定义个node

	person p1, p2, p3;
	strcpy(p1.name, "张三");
	strcpy(p2.name, "李四");
	strcpy(p3.name, "王五");
	p1.age = 18;
	p2.age = 17;
	p3.age = 19;
	//将节点插入链表
	Insert_LinkList(list, 0, (LinkNode*)&p1);
	Insert_LinkList(list, 0, (LinkNode*)&p2);
	Insert_LinkList(list, 0, (LinkNode*)&p3);
	
	
	//打印
	Printf_LinkList(list, myprintf);

	//删除结点
	Remove_LinkList(list, 1);
	printf("删除1位置的结点后链表元素为：\n");
	Printf_LinkList(list, myprintf);
	//释放链表内存
	Free_LinkList(list);
}

    • 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

    结果：

    姓名：王五 年龄：19
姓名：李四 年龄：17
姓名：张三 年龄：18
删除1位置的结点后链表元素为：
姓名：王五 年龄：19
姓名：张三 年龄：18

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    循环链表的设计与实现

    在这里插入图片描述
    示例：

    1. 建立一个 CircleLinkList.h 头文件
    #pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define CIRCLELINKLIST_TRUE 1  //宏定义
#define CIRCLELINKLIST_FALSE 0

typedef struct CIRCLELINKNODE
{
	struct CIRCLELINKNODE* next;
	
}CircleLinkNode;
typedef struct CIRCLELINKLIST
{
	CircleLinkNode head;
	int size;
}CirecleLinkList;

typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);//比较回调

typedef void(*PRINTFNODE)(CircleLinkNode*);//打印回调

//编写针对链表结构体操作的API函数

//初始化函数
CirecleLinkList* Init_CircluLinkList();
//插入函数
void Insert_CircluLinkList(CirecleLinkList* clist, int pos, CircleLinkNode*data);
//获得第一个元素
CircleLinkNode* Front_CircleLinkList(CirecleLinkList* clist);
//根据位置删除元素
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos);
//根据值删除元素
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode*data,COMPARENODE compare);
//获得链表的长度
int Size_CircleLinkList(CirecleLinkList* clist);
//判断是否为空
int IsEmpty_CircleLinkList(CirecleLinkList* clist);
//查找
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
//打印结点
void Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print);
//释放内存
void FreeSpace_CircleLinkList(CirecleLinkList* clist);

    • 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
    1. 建立一个 CircleLinkList.c 源文件
    #include "CircleLinkList.h"

//初始化函数
CirecleLinkList* Init_CircluLinkList()
{
	CirecleLinkList* clist = (CirecleLinkList*)malloc(sizeof(CirecleLinkList));
	clist->size = 0;
	clist->head.next = &(clist->head);
	return clist;
}


//插入函数
void Insert_CircluLinkList(CirecleLinkList* clist, int pos, CircleLinkNode*data)
{
	if (clist == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	if (pos<0 || pos>clist->size)
	{
		pos = clist->size;
	}
	//根据位置查找结点
	//辅助指针变量
	CircleLinkNode* pcurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
		pcurrent = pcurrent->next;
	}
	//新数据入链表
	data->next = pcurrent->next;
	pcurrent->next = data;
	clist->size++;
}


//获得第一个元素
CircleLinkNode* Front_CircleLinkList(CirecleLinkList* clist)
{
	
	return clist->head.next;
}


//根据位置删除元素
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos)
{
	if (clist == NULL)
	{
		return;
	}
	if (pos<0 || pos>clist->size)
	{
		return;
	}
	CircleLinkNode* pcurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
		pcurrent = pcurrent->next;
	}
	//缓存当前节点的下一个结点，即需要删除的结点
	CircleLinkNode* pnext = pcurrent->next;
	pcurrent->next = pnext->next;
	clist->size--;
}


//根据值删除元素
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
	if (clist == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	//这个是循环链表
	CircleLinkNode* pprev = &(clist->head);
	CircleLinkNode* pcurrent = pprev->next;
	for (int i = 0; i < clist->size; i++)
	{
		if (compare(pcurrent,data) == CIRCLELINKLIST_TRUE)
		{
			pprev->next = pcurrent->next;
			break;
		}
		pprev=pcurrent;
		pcurrent = pprev->next;
	}
	clist->size--;

}


//获得链表的长度
int Size_CircleLinkList(CirecleLinkList* clist)
{
	return clist->size;
}


//判断是否为空
int IsEmpty_CircleLinkList(CirecleLinkList* clist)
{
	if (clist->size == 0)
	{
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}


//查找
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
	if (clist == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}
	CircleLinkNode* pcurrent = clist->head.next;
	int flag = -1;
	for (int i = 0; i < clist->size;i++)
	{
		if (compare(pcurrent, data) == CIRCLELINKLIST_TRUE)
		{
			flag = i;
			break;
		}
		pcurrent = pcurrent->next;
	}
	return flag;
}


//打印结点
void Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print)
{
	if (clist == NULL)
	{
		return;
	}
	//辅助指针变量
	CircleLinkNode* pcurrent = clist->head.next;
	for (int i = 0; i < clist->size; i++)//打印两遍的话得乘2，还需要判断一下，是否为头结点（因为是循环链表）
	{
		if (pcurrent == &(clist->head))
		{
			pcurrent = pcurrent->next;//判断如果为头结点  则指向下一个结点，因为头结点没有存放数据
			printf("-----------------------\n");
		}
		print(pcurrent);
		pcurrent = pcurrent->next;
	}
}


//释放内存
void FreeSpace_CircleLinkList(CirecleLinkList* clist)
{
	if (clist == NULL)
	{
		return;
	}
	free(clist);
}

    • 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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    1. 建立一个 01循环链表.c 的源文件，进行功能测试
    #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"CircleLinkList.h"



typedef struct PERSON
{
	CircleLinkNode node;
	char name[21];
	int age;
	int score;
}person;

void myprintf(CircleLinkNode* data)//回调函数的编写
{
	person* p = data;
	printf("姓名：%s 年龄：%d 成绩：%d\n", p->name, p->age, p->score);
}

int mycompare(CircleLinkNode* data1, CircleLinkNode* data2)
{
	person* p1 = data1;
	person* p2 = data2;
	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age&&p1->score == p2->score)
	{
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}
int main()
{
	//创建循环列表
	CirecleLinkList* clist = Init_CircluLinkList();

	person p1, p2, p3,p4,p5;
	strcpy(p1.name, "张三");
	strcpy(p2.name, "李四");
	strcpy(p3.name, "王五");
	strcpy(p4.name, "刘六");
	strcpy(p5.name, "陈七");
	p1.age = 20;
	p2.age = 18;
	p3.age = 21;
	p4.age = 19;
	p5.age = 22;
	p1.score = 98;
	p2.score = 97;
	p3.score =99;
	p4.score = 87;
	p5.score = 90;

	//插入,数据入链表
	Insert_CircluLinkList(clist,100, (CircleLinkNode*)&p1);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p2);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p3);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p4);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p5);

	//打印
	Printf_CircleLinkList(clist, myprintf);


	//根据值删除
	/*person pdel;
	strcpy(pdel.name, "王五");
	pdel.age = 21;
	pdel.score = 99;
	RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&pdel, mycompare);*/ //==

	RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&p3, mycompare); //==
	printf("删除后的链表为：\n");
	Printf_CircleLinkList(clist, myprintf);
	//释放内存
	FreeSpace_CircleLinkList(clist);

	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

    结果：

    姓名：张三 年龄：20 成绩：98
姓名：李四 年龄：18 成绩：97
姓名：王五 年龄：21 成绩：99
姓名：刘六 年龄：19 成绩：87
姓名：陈七 年龄：22 成绩：90
删除后的链表为：
姓名：张三 年龄：20 成绩：98
姓名：李四 年龄：18 成绩：97
姓名：刘六 年龄：19 成绩：87
姓名：陈七 年龄：22 成绩：90

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    约瑟夫问题——循环链表的典型应用

    在这里插入图片描述
    在这里插入图片描述
    示例：

    1. 建立一个 CircleLinkList.h 的头文件
      如上： 循环链表所示
    2. 建立一个 CircleLinkList.c 的源文件
      如上：循环链表所示
    3. 建立一个 02约瑟夫问题.c 的源文件，进行主函数的编写
    #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "CircleLinkList.h"
#define M 8
#define N 3


typedef struct MYNUM
{
	CircleLinkNode node;
	int value;
}mynum;

void myprintf(CircleLinkNode* data)
{
	mynum* num = (mynum*)data;
	printf("%d ", num->value);
}
void mycompare(CircleLinkNode*data1, CircleLinkNode* data2)
{
	mynum* num1 = data1;
	mynum* num2 = data2;
	if (num1->value == num2->value)
	{
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}

int main()
{
	CirecleLinkList* clist = Init_CircluLinkList();
	//链表插入数据
	mynum num[M];
	for (int i = 0; i < M; i++)
	{
		num[i].value= i + 1;
		Insert_CircluLinkList(clist, i,(CircleLinkNode*)&num[i]);
	}

	//打印
	Printf_CircleLinkList(clist, myprintf);
	printf("\n");

	int index = 1;
	//辅助指针
	CircleLinkNode* pcurrent = clist->head.next;
	while (Size_CircleLinkList(clist) > 1)
	{
		if (index == N)
		{
			mynum* tempnum = (mynum*)pcurrent;
			printf("%d ", tempnum->value);
			//缓存待删除结点的下一个结点
			CircleLinkNode* pnext = pcurrent->next;
			//根据值删除
			RemoveByValue_CircleLinkList(clist, pcurrent, mycompare);
			pcurrent = pnext;
			if (pcurrent == &(clist->head))
			{
				pcurrent = pcurrent->next;
			}
			index = 1;
		}
		pcurrent = pcurrent->next;
		if (pcurrent == &(clist->head))
		{
			pcurrent = pcurrent->next;
		}

		index++;
	}
	if (Size_CircleLinkList(clist) == 1)
	{
		mynum* tempnum=(mynum*)Front_CircleLinkList(clist);
		printf("%d ", tempnum->value);
	}
	else
	{
		printf("出错！！！");
	}
	//释放
	FreeSpace_CircleLinkList(clist);

}

    • 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

    结果：

    1 2 3 4 5 6 7 8
3 6 1 5 2 8 4 7

    • 1
    • 2
  • 相关阅读:
    Mac-问题
    让前端和后端要“动手”的7大行为，你中了几个。
    JavaScript小技能:原型链的运作机制、Promise链
    文心一言api开发者文档，python版ERNIE-3.5-8K-Preview模型调用方法
    把苦难的时光删去：从小县城售货员到深圳IT白领的蜕变之路
    day47 JavaScript基础
    Dev-C++ 实用安装教程
    Linux基础学习笔记（十三）——文件的格式化处理
    过来人ETC Coop喊话宝二爷：分叉以太坊没那么简单
    罗胖关于学习的观点
  • 原文地址：https://blog.csdn.net/qq_44921148/article/details/125493110