大魔王（已黑化）

大魔王（已黑化）

关注
发信
关注(28)粉丝(399)

C语言实现链表--数据结构

C语言实现链表--数据结构-LMLPHP

一、前言

  • 下面的链表都是针对无头单向不循环这钟来说的。

C语言实现链表--数据结构-LMLPHP

二、链表实现

1、创建结构体类型

代码：

typedef int SListDateType;

typedef struct SeqListNode
{
	SListDateType date;
	struct SeqListNode* next;
}SListNode;

2、创建结点

代码：

//创建新结点。
SListNode* BuyNewnode(SListDateType x)
{
	SListNode* newnode = malloc(sizeof(SListNode));
	assert(newnode);
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

3、打印单链表

代码：

//打印单链表。
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

4、单链表尾插

//单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x)
{
	assert(pphead);

	SListNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

5、单链表头插

代码：

//单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x)
{
	assert(pphead);
	SListNode* newnode=BuyNewnode(x);
	newnode->next = *pphead;//先指向这个，如果先弄下面一步，就找不到原头节点的位置了。
	*pphead = newnode;//pphead是二级指针，解引用后就是一级指针，newnode也是一级指针，然后让newnode赋给pphead，这样就改变了实参。
}

6、单链表尾删

代码：

//单链表尾删。
void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	assert(*pphead);//指针指向的内容不能是空的
	SListNode* cur = *pphead;
	SListNode* cur_ = NULL;//存倒数第二个结点的位置
	if (cur->next == NULL)
	{
		free(cur);
		*pphead = NULL;
		return;
	}
	while (cur->next)
	{
			cur_ = cur;//保留要释放结点的前一个位置，然后当下面用完cur（释放）后，让cur_（释放后的最后结点位置指向空）
			cur = cur->next;
	}
	free(cur);
	cur_->next = NULL;
}

7、单链表头删

代码：

//单链表头删。
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = (*pphead)->next;
	free(first);
}

8、单链表查找

代码：

//单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);//既然查找了，那么就不能为空链表，否则没有意义，这是使用者的问题。
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//上面已经判断不能为空链表，所以这里返回的空指针指的就是找不到，而不是链表为空。
}

9、单链表插入

☃️该位置之后插入

代码：

//单链表插入(pos之后)。
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x)
{
	assert(pos);//插入默认是该链表不为空的，如果想要空的时候插入，用头插函数。
	SListNode* cur = phead;
	SListNode* newnode = BuyNewnode(x);
	while (cur!=pos)
	{
		cur = cur->next;
	}
	newnode->next = cur->next;
	cur->next = newnode;
}

☃️该位置之前插入（插入正常理解）

//单链表插入(pos之前)。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x)
{
	assert(pphead);

	assert(*pphead);//和刚才同理，链表没有元素的时候插入调用头插函数。
	SListNode* cur = *pphead;
	SListNode* newnode = BuyNewnode(x);
	if (cur->next == NULL)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

10、单链表删除

代码：

//单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	if (cur == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		while (cur->next!=pos)
		{
			cur = cur->next;
		}
		cur->next = cur->next->next;//或者写成cur->next = pos->next;
		free(pos);
	}
}
  • 因为传的pos是一级指针，所以我们无法在函数里修改pos的值，我们只能修改pos指向位置的内容，当我们释放pos后，实参pos便指向释放后的位置，也就变成了野指针，所以我们需要在出函数后让pos置空。

11、单链表销毁

//单链表的销毁。
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* pc = cur;
		cur = cur->next;
		free(pc);
	}
}

三、总代码

SeqListNode.h

SeqListNode.h

#pragma once

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


typedef int SListDateType;

typedef struct SeqListNode
{
	SListDateType date;
	struct SeqListNode* next;
}SListNode;

//创建新结点。
SListNode* BuyNewnode(SListDateType x);

//打印单链表。
void SListPrint(SListNode* phead);

//单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x);

//单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x);

//单链表尾删。
void SListPopBack(SListNode** pphead);

//单链表头删。
void SListPopFront(SListNode** pphead);

//单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x);

//单链表插入。
//pos之后插入。
//不用从头开始查找，比较高效
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x);
//pos之前插入。
//还要从头开始查找，不合适
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x);

//单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos);

//单链表的销毁。
void SListDestroy(SListNode** phead);

SeqListNode.c

SeqListNode.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqListNode.h"

//创建新结点。
SListNode* BuyNewnode(SListDateType x)
{
	SListNode* newnode = malloc(sizeof(SListNode));
	assert(newnode);
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

//打印单链表。
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

//单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x)
{
	assert(pphead);

	SListNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

//单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x)
{
	assert(pphead);

	SListNode* newnode=BuyNewnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表尾删。
void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	assert(*pphead);//指针指向的内容不能是空的
	SListNode* cur = *pphead;
	SListNode* cur_ = NULL;//存倒数第二个结点的位置
	if (cur->next == NULL)
	{
		free(cur);
		*pphead = NULL;
		return;
	}
	while (cur->next)
	{
			cur_ = cur;//保留要释放结点的前一个位置，然后当下面用完cur（释放）后，让cur_（释放后的最后结点位置指向空）
			cur = cur->next;
	}
	free(cur);
	cur_->next = NULL;
}

//单链表头删。
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = (*pphead)->next;
	free(first);
}

//单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//单链表插入(pos之后)。
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x)
{
	assert(pos);
	SListNode* cur = phead;
	SListNode* newnode = BuyNewnode(x);
	while (cur!=pos)
	{
		cur = cur->next;
	}
	newnode->next = cur->next;
	cur->next = newnode;
}

//单链表插入(pos之前)。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	SListNode* newnode = BuyNewnode(x);
	if (cur->next == NULL)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

//单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	if (cur == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		while (cur->next!=pos)
		{
			cur = cur->next;
		}
		cur->next = cur->next->next;
		free(pos);
	}
}

//单链表的销毁。
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* pc = cur;
		cur = cur->next;
		free(pc);
	}
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqListNode.h"

void test1()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc,0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPushBack(&pc, 4);
	SListPrint(pc);

	SListPushBack(&pc, 5);
	SListPrint(pc);

	SListPushBack(&pc, 6);
	SListPrint(pc);

	SListPushBack(&pc, 7);
	SListPrint(pc);
}

void test2()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushFront(&pc, 0);
	SListPrint(pc);

	SListPushFront(&pc, 1);
	SListPrint(pc);

	SListPushFront(&pc, 2);
	SListPrint(pc);

	SListPushFront(&pc, 3);
	SListPrint(pc);

	SListPushFront(&pc, 4);
	SListPrint(pc);

	SListPushFront(&pc, 5);
	SListPrint(pc);

	SListPushFront(&pc, 6);
	SListPrint(pc);

	SListPushFront(&pc, 7);
	SListPrint(pc);
}
void test3()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc, 0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);
}
void test4()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc,0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPushBack(&pc, 4);
	SListPrint(pc);

	SListPushBack(&pc, 5);
	SListPrint(pc);

	SListPushBack(&pc, 6);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);
}
void test5()
{
	SListNode* pc = NULL;
	SListPushBack(&pc,0);
	//SListPushBack(&pc,1);
	//SListPushBack(&pc,2);
	SListPrint(pc);
	SListNode* pos = SListFind(pc,0);
	assert(pos);
	//SListInsertAfter(*pc, pos, 9);//pos之后插入。
	SListInsertBefore(&pc, pos, 5);//pos之前插入。
	SListPrint(pc);
	pos = SListFind(pc, 5);
	SListEraseAfter(&pc, pos);//删除后要置空
	pos = NULL;//这块被释放了，所以置空
	SListPrint(pc);
	SListDestroy(&pc);
}

int main()
{
	//test1();//测试尾插。
	//test2();//测试头插。
	test3();//测试尾删。
	//test4();//测试头删。
	//test5();//测试查找,插入,销毁。
	return 0;
}

四、总结

C语言实现链表--数据结构-LMLPHP

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话，就点我进入主页关注我吧！

04-21 19:25
Powered by LMLPHP ©2024 大魔王（已黑化） 0.008488