• 2.C语言--链表-头插、头删、尾插、尾删、查找、插入和删除

    文章目录

    简介

    	本文主要介绍链表的头插、头删、尾插、尾删、查找、插入和删除，提供全部的.c和.h文件，确保使用者直接复制粘贴到编译器上即可直接运行程序。

    • 1

    动态顺序表结构体

    typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

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

    1.头插功能

    	思路是将节点的首地址赋值到新申请节点的next中。

    • 1
    /*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{
	assert(ppHead != NULL);

	SLTNode* newNode = CreatListNode(x);

	newNode->next = *ppHead;

	*ppHead = newNode;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    	开辟一个新的节点，并将要插入的值放心节点对应的data中。

    • 1
    /*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NULL == newNode)
	{
		printf("CreatListNode malloc fail\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;

	return newNode;
}

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

    2.头删功能

    	思路是将下一个节点的地址赋值到头节点地址上，将当前节点free掉。

    • 1
    /*头删*/
void SListPopFront(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	SLTNode* next = (*ppHead)->next;

	free(*ppHead);

	*ppHead = next;

	return;
}

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

    3.尾插功能

    	思路是先检查输入*ppHead是否为空，不为空就找到链表的尾节点进行新节点的插入。

    • 1
    /*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{
	assert(ppHead != NULL);
	/*新结点申请空间*/
	SLTNode* newNode = CreatListNode(x);

	if (*ppHead == NULL)
	{
		*ppHead = newNode;
	}
	else
	{
		/*找到尾结点*/
		SLTNode* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newNode;
	}

	return;
}

    • 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

    4.尾删功能

    	思路是释放节点时，要将下一个节点的地址保存好再释放当前节点。

    • 1
    /*尾删*/
void SListPopBack(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	/*如果只有一个节点时，直接释放此节点*/
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else/*存在2个及2个以上节点的处理方式*/
	{
		SLTNode* tail = *ppHead;
		SLTNode* pre = NULL;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}

		pre->next = NULL;

		free(tail);
		tail = NULL;
	}

	return;
}

    • 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

    5.查找功能

    	思路是遍历，找到节点后返回当前节点的地址，找不到就返回NULL。

    • 1
    /*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{
	assert(pHead != NULL);

	SLTNode* cur = pHead;

	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}

	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    6.插入功能

    6.1 指定位置之（前）去插入一个节点

    	此方法是比较笨的方法，为了节约资源应该将数据往指定位置的后边插入。

    • 1
    /*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{
	assert(ppHead != NULL);
	assert(pos != NULL);
	SLTNode* newNode = CreatListNode(x);

	if (*ppHead == pos)/*pos的位置在第一个位置时*/
	{
		newNode->next = *ppHead;
		*ppHead = newNode;
	}
	else
	{
		/*找到pos位置的前一个位置*/
		SLTNode* posPrev = *ppHead;

		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}

		posPrev->next = newNode;
		newNode->next = pos;
	}

	return NULL;
}

    • 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

    6.2 指定位置之（后）去插入一个节点

    	此方法是常用的插入方式，时间复杂度是O(1)。

    • 1
    /*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos != NULL);

	SLTNode* newNode = CreatListNode(x);

	newNode->next = pos->next;

	pos->next = newNode;

	return NULL;
}

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

    7.删除功能

    7.1 删除指定位置的数据-时间复杂度O(N)

    	此方法需要记住当前节点前一个的节点地址，会多耗费时间资源，时间复杂度O(N)。

    • 1
    SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{
	assert(ppHead != NULL);
	assert(pos != NULL);
	/*如果删除的数据是头*/
	if (*ppHead == pos)
	{
		SListPopFront(ppHead);
	}
	else
	{
		SLTNode* prev = *ppHead;
		while (prev->next != pos)/*找到pos前一个节点*/
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    7.2 删除指定位置后一个位置的数据-时间复杂度O(1)

    	此方法需要记住当前节点前一个的节点地址，会多耗费时间资源，时间复杂度O(1)。

    • 1
    /*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{
	assert(pos->next != NULL);

	SLTNode* next = pos->next;

	pos->next = next->next;

	free(next);
	next = NULL;

	return NULL;
}

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

    8. 释放链表缓存

    	思路将下一个节点的地址先记住，然后释放当前节点。再将保存的地址赋值到当前节点循环释放缓存。

    • 1
    /*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	SLTNode* cur = *ppHead;

	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*ppHead = NULL;

	return NULL;
}

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

    9. 打印链表的值

    /*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{
	SLTNode* cur = pHead;

	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	return;
}

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

    10.此程序共包含3个文件，2个.c文件和1个.h文件

    10.1 SList.h文件

    	文件中包含了函数功能的头文件以及对应的结构体。

    • 1
    #pragma once
#include 
#include 
#include 

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;




void SListTPrint(SLTNode *pHead);							/*打印链表的值*/
void SListPushBack(SLTNode** ppHead, SLTDateType x);		/*插入数据-尾插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x);		/*插入数据-头插*/

void SListPopBack(SLTNode** ppHead);						/*尾删*/
void SListPopFront(SLTNode** ppHead);						/*头删*/

SLTNode* SListFind(SLTNode* pHead, SLTDateType x);				    /*查找*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x);/*指定位置插入数据-在pos位置之前去插入一个节点*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x);				/*指定位置插入数据-在pos位置之后去插入一个节点*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos);				/*删除指定位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos);								/*删除指定位置后一个位置的数据*/
SLTNode* SListDestory(SLTNode** ppHead);							/*释放链表缓存*/

SLTNode* CreatListNode(SLTDateType x);								/*创建一个新的节点*/

    • 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

    10.2 SList.c文件

    	文件中包含了功能函数的具体实现方式。

    • 1
    #define _CRT_SECURE_NO_WARNINGS
#include "SList.h"



/*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{
	assert(ppHead != NULL);
	/*新结点申请空间*/
	SLTNode* newNode = CreatListNode(x);

	if (*ppHead == NULL)
	{
		*ppHead = newNode;
	}
	else
	{
		/*找到尾结点*/
		SLTNode* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newNode;
	}

	return;
}

/*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{
	assert(ppHead != NULL);

	SLTNode* newNode = CreatListNode(x);

	newNode->next = *ppHead;

	*ppHead = newNode;

	return;
}

/*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NULL == newNode)
	{
		printf("CreatListNode malloc fail\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;

	return newNode;
}

/*尾删*/
void SListPopBack(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	/*如果只有一个节点时，直接释放此节点*/
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else/*存在2个及2个以上节点的处理方式*/
	{
		SLTNode* tail = *ppHead;
		SLTNode* pre = NULL;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}

		pre->next = NULL;

		free(tail);
		tail = NULL;
	}

	return;
}

/*头删*/
void SListPopFront(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	SLTNode* next = (*ppHead)->next;

	free(*ppHead);

	*ppHead = next;

	return;
}

/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{
	assert(pHead != NULL);

	SLTNode* cur = pHead;

	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}

	return NULL;
}

/*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{
	assert(ppHead != NULL);
	assert(pos != NULL);
	SLTNode* newNode = CreatListNode(x);

	if (*ppHead == pos)/*pos的位置在第一个位置时*/
	{
		newNode->next = *ppHead;
		*ppHead = newNode;
	}
	else
	{
		/*找到pos位置的前一个位置*/
		SLTNode* posPrev = *ppHead;

		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}

		posPrev->next = newNode;
		newNode->next = pos;
	}

	return NULL;
}


/*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos != NULL);

	SLTNode* newNode = CreatListNode(x);

	newNode->next = pos->next;

	pos->next = newNode;

	return NULL;
}

/*删除指定位置的数据--时间复杂度O(N)*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{
	assert(ppHead != NULL);
	assert(pos != NULL);
	/*如果删除的数据是头*/
	if (*ppHead == pos)
	{
		SListPopFront(ppHead);
	}
	else
	{
		SLTNode* prev = *ppHead;
		while (prev->next != pos)/*找到pos前一个节点*/
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

	return NULL;
}

/*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{
	assert(pos->next != NULL);

	SLTNode* next = pos->next;

	pos->next = next->next;

	free(next);
	next = NULL;

	return NULL;
}

/*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{
	assert(ppHead != NULL);

	SLTNode* cur = *ppHead;

	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*ppHead = NULL;

	return NULL;
}

/*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{
	SLTNode* cur = pHead;

	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	return;
}

    • 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
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243

    10.3 test.c文件

    	用来进行相应功能的测试，分别测试尾插、尾删和头插、头删等功能。

    • 1
    #define _CRT_SECURE_NO_WARNINGS
#include 
#include "SList.h"


void Test1()
{
	SLTNode* SList = NULL;

	/*尾插*/
	SListPushBack(&SList, 1);

	SListPushBack(&SList, 2);

	SListPushBack(&SList, 3);

	SListPushBack(&SList, 4);

	/*尾删*/
	SListPopBack(&SList);

	/*打印链表*/
	SListTPrint(SList);

	printf("NULL\n");

	return;
}

void Test2()
{
	SLTNode* SList = NULL;

	/*头插*/
	SListPushFront(&SList, 1);

	SListPushFront(&SList, 2);

	SListPushFront(&SList, 3);

	/*头删*/
	SListPopFront(&SList);

	/*打印*/
	SListTPrint(SList);

	printf("NULL");

	return;
}

void Test3()
{
	SLTNode* SList = NULL;
	SLTNode* pos = NULL;
	int i = 1;

	/*尾插*/
	SListPushBack(&SList, 1);

	SListPushBack(&SList, 5);

	SListPushBack(&SList, 2);

	SListPushBack(&SList, 3);

	SListPushBack(&SList, 2);

	/*查找数字的位置*/
	pos = SListFind(SList, 2);

	while (pos)/*查找到数据为2的节点的地址*/
	{
		printf("第%d个pos节点的:%p->%d\n", i++, pos->next, pos->data);
		if (pos->next)
		{
			pos = SListFind(pos->next, 2);
		}
		else/*为空指针时，直接跳出循环*/
		{
			break;
		}
	}
	/*改变对应节点位置的数据,将5位置前边的位置添加个20*/
	pos = SListFind(SList, 5);

	if (pos)/*在5的位置之前插入20*/
	{
		SListInsert(&SList, pos, 20);
	}

	pos = SListFind(SList, 5);

	if (pos)/*在5的位置之后插入100*/
	{
		SListInsertAfter(pos, 100);
	}
	/*打印*/
	SListTPrint(SList);

	printf("NULL");

	return;
}

int main()
{
	Test1();/*尾插+尾删*/

	//Test2();/*头插+头删*/

	//Test3(); /*指定位置前插入、后插入、寻找指定数据节点的位置*/

	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
    • 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
    	这里代码大家可以自己拷贝到VS编译器中，Test1()，Test2()，Test3()，分别打开注释看一下效果，本人亲测过，可以直接运行出结果的。

    • 1
  • 相关阅读:
    HTML中， 在同一行上出现高低不一样的文字，处理对齐效果
    【云原生之Docker实战】使用docker部署 Searxng个人搜索引擎平台
    关键词搜索商品API
    第二批入围企业公示！年度TOP100智能网联供应商评选
    CSS Form表单布局
    Python数据可视化：类别比较图表可视化
    新一代爬虫神器puppeteer介绍
    【手把手带你学JavaSE】第四篇：Java中的方法
    基于ntchat的微信群聊同步机器人
    How to customize the text of a generic Qlik Sense error message
  • 原文地址：https://blog.csdn.net/ls3614140/article/details/134496680