【数据结构】单链表 — 纯C实现单链表

时间：2023-02-14 19:03:21

????前言

本文介绍了单链表的定义以及常用结点的实现。

一、定义

1.概念

顺序表最大缺点就是：插入和删除的时候需要移动大量的元素。 而单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

2.特点

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。 链表中每个元素本身由两部分组成： ● 数据域：存放数据。

● 指针域：存放指向后继结点的地址； 链表的第一个结点被称为：头节点

【数据结构】单链表 — 纯C实现单链表【数据结构】单链表 — 纯C实现单链表

3.优点

①.链表是一个动态数据结构，无需给出链表的初始大小。 ②.任意位置插入删除时间复杂度为O(1)。 与数组不同，在插入或删除元素后，我们不必移动元素。 在链表中，我们只需要更新节点的下一个指针中存在的地址即可。 ③.由于链表的大小可以在运行时增加或减小，因此不会浪费内存。

4.缺点

①.存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。 ②.要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 O ( n) 在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为 O ( 1) 。 双链表还允许在特定的数据元素之前插入或删除元素。 ③.存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。

5.结点定义

typedef int LinkType; //数据类型
typedef struct SLlist {
	LinkType data;//数据域
	struct SLlist* next;//指针域
}SLlist;

利用typedef修改int类型的名字，下面int的地方全部可以用typedef后的名字代替，便于修改数据类型。 由于每个结点都是两部分，所以结构体内部有两部分： 一部分存储数据，另一部分存储下一个结点的地址。

二、接口实现

1.创建链表结点

创建单个结点

创建单个结点是我们实现后面接口的基础。

SLlist* BuySLlist(LinkType x) {
	SLlist* newnode = (SLlist*)malloc(sizeof(SLlist));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

创建链表

这里我为了测试方便，每个结点的数据内容我并没有使用scanf函数输入，实际使用过程中大家可以在循环里面加入scanf函数。

SLlist* CreateSLlist(LinkType n)
{
	SLlist* phead = NULL, * ptail = NULL;
	int x = 0;
	for (int i = 0; i < n; ++i)
	{
		SLlist* newnode = BuySLlist(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}

打印链表

为了测试的结构直观显示，我就先把打印函数写出来。

void PrintSLlist(SLlist* phead) {
	SLlist* cur = phead;
	while (cur != NULL) {         //（1）
		printf("%d->", cur->data);//（2）
		cur = cur->next;          //（3）
	}
	printf("NULL!");              //（4）
}

（1）当指针为空时，结束循环 （2）打印当前指针指向的数据 （3）将当前指针修改为当前指针指针域指向的结点的地址 （4）为了方便测试，打印NULL代表结束

测试创建功能

为了防止错误堆积到最后，我们平时写代码的时候就应该这样。每写出一个函数就可以测试以下。防止最后错误太多，看都不想看了????????????

void Test02()
{
	SLlist* n1 = CreateSLlist(10);
	PrintSLlist(n1);
}
int main()
{
	Test02();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表 如图，测试正常。

2.尾插尾删

尾部插入

void SLlistPushBack(SLlist** pphead, LinkType x)
{
	SLlist* newnode = BuySLlist(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLlist* tail = *pphead;
		// 找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

尾部删除

void SLlistPopBack(SLlist** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLlist* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

尾插尾删测试

//测试尾插函数是否正常
void Test03()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPushBack(&n1, 10);
	PrintSLlist(n1);
}
//测试尾删函数是否正常
void Test04()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPopBack(&n1);
	PrintSLlist(n1);
}

测试尾部插入函数

//主函数实现
int main()
{
	Test03();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表 测试尾部删除函数

//主函数实现
int main()
{
	Test04();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表

3.头插头删

头部插入

//头插
void SLlistPushFront(SLlist** pphead, LinkType x)
{
	SLlist* newnode = BuySLlist(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头部删除

//头删
void SLlistPopFront(SLlist** pphead)
{
	assert(*pphead);
	SLlist* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

头插头删测试

//测试头插函数是否正常
void Test05()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPushFront(&n1, 30);
	SLlistPushFront(&n1, 40);
	PrintSLlist(n1);
}
//测试头删函数是否正常
void Test06()
{
	SLlist* n1 = CreateSLlist(10);
	SLlistPopFront(&n1);
	SLlistPopFront(&n1);
	PrintSLlist(n1);
}

测试头部插入函数

//主函数实现
int main()
{
	Test05();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表 测试头部删除函数

//主函数实现
int main()
{
	Test06();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表

4.pos位的插入删除

想要在pos位置进行插入删除，我们首先就要明确pos位置在哪里。 同顺序表一样，我们需要先写一个find函数来找到pos位置。

查找pos位置

//单链表查找位置
SLlist* SLTFind(SLlist* phead, LinkType x)
{
	SLlist* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

在pos位置前插入

//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLlistPushFront(pphead, x);
	}
	else
	{
		SLlist* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLlist* newnode = BuySLlist(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

在pos位置后插入

//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x)
{
	assert(pos);
	SLlist* newnode = BuySLlist(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除pos位置的数

//删除pos位置的函数
void SLTErase(SLlist** pphead, SLlist* pos)
{
	assert(pos);
	assert(*pphead);
	if (pos == *pphead)
	{
		SLlistPopFront(pphead);
	}
	else
	{
		SLlist* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

删除pos位置后的数

//删除pos位置后的函数
void SLTEraseAfter(SLlist* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLlist* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}

pos位置上的插入删除测试

//测试在pos位置后插入函数是否正常
void Test07()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	PrintSLlist(n1);
}
//测试在pos位置前插入函数是否正常
void Test08()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
}
//测试删除pos位置后函数是否正常
void Test09()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
	printf("\n");
	SLTEraseAfter(p);
	PrintSLlist(n1);
}
//测试删除pos位置函数是否正常
void Test10()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
	printf("\n");
	SLlist* p2 = SLTFind(n1, 90);
	SLTErase(&n1, p2);
	PrintSLlist(n1);
}

和上面的测试一样，想测试那个，就把test函数修改为对于的函数。

//主函数实现
int main()
{
	Test10();
	return 0;
}

【数据结构】单链表 — 纯C实现单链表

5.销毁链表

通过循环，使用free函数释放每一个空间即可。

void SLTDestroy(SLlist** pphead)
{
	SLlist* cur = *pphead;
	while (cur)
	{
		SLlist* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

三、代码汇总

SLlist.h用来声明函数 SLlist.c用来定义函数 test.c 用来测试函数

SLlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LinkType; //数据类型
typedef struct SLlist {
	LinkType data;//数据域
	struct SLlist* next;//指针域
}SLlist;
//创建单个结点
SLlist* BuySLlist(LinkType x);
//创建链表
SLlist* CreateSLlist(LinkType n);
//打印链表
void PrintSLlist(SLlist* phead);
//尾插
void SLlistPushBack(SLlist** pphead, LinkType x);
//尾删
void SLlistPopBack(SLlist** pphead);
//头插
void SLlistPushFront(SLlist** pphead, LinkType x);
//头删
void SLlistPopFront(SLlist** pphead);
//查找
SLlist* SLTFind(SLlist* phead, LinkType x);
//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x);
//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x);
//删除pos位置后的数据
void SLTEraseAfter(SLlist* pos);
//删除pos位置的数据
void SLTErase(SLlist** pphead, SLlist* pos);
//销毁单链表
void SLTDestroy(SLlist** pphead);

SLlist.c

#include"SLlist.h"
//创建单个结点
SLlist* BuySLlist(LinkType x) {
	SLlist* newnode = (SLlist*)malloc(sizeof(SLlist));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//创建链表
SLlist* CreateSLlist(LinkType n)
{
	SLlist* phead = NULL, * ptail = NULL;
	int x = 0;
	for (int i = 0; i < n; ++i)
	{
		SLlist* newnode = BuySLlist(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
//打印链表
void PrintSLlist(SLlist* phead) {
	SLlist* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL!");
}
// 尾插
void SLlistPushBack(SLlist** pphead, LinkType x)
{
	SLlist* newnode = BuySLlist(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLlist* tail = *pphead;
		// 找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//尾删
void SLlistPopBack(SLlist** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLlist* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
//头插
void SLlistPushFront(SLlist** pphead, LinkType x)
{
	SLlist* newnode = BuySLlist(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SLlistPopFront(SLlist** pphead)
{
	assert(*pphead);
	SLlist* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//单链表查找位置
SLlist* SLTFind(SLlist* phead, LinkType x)
{
	SLlist* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}
//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x)
{
	assert(pos);
	SLlist* newnode = BuySLlist(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLlistPushFront(pphead, x);
	}
	else
	{
		SLlist* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLlist* newnode = BuySLlist(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//删除pos位置后的函数
void SLTEraseAfter(SLlist* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLlist* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}
//删除pos位置的函数
void SLTErase(SLlist** pphead, SLlist* pos)
{
	assert(pos);
	assert(*pphead);
	if (pos == *pphead)
	{
		SLlistPopFront(pphead);
	}
	else
	{
		SLlist* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
	}
}
//销毁单链表
void SLTDestroy(SLlist** pphead)
{
	SLlist* cur = *pphead;
	while (cur)
	{
		SLlist* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

test.c

#include"SLlist.h"
//测试创建结点函数是否正常
void Test01()
{
	SLlist* n1 = BuySLlist(1);
	PrintSLlist(n1);
}
//测试创建链表函数是否正常
void Test02()
{
	SLlist* n1 = CreateSLlist(10);
	PrintSLlist(n1);
}
//测试尾插函数是否正常
void Test03()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPushBack(&n1, 10);
	PrintSLlist(n1);
}
//测试尾删函数是否正常
void Test04()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPopBack(&n1);
	PrintSLlist(n1);
}
//测试头插函数是否正常
void Test05()
{
	SLlist* n1 = CreateSLlist(5);
	SLlistPushFront(&n1, 30);
	SLlistPushFront(&n1, 40);
	PrintSLlist(n1);
}
//测试头删函数是否正常
void Test06()
{
	SLlist* n1 = CreateSLlist(10);
	SLlistPopFront(&n1);
	SLlistPopFront(&n1);
	PrintSLlist(n1);
}
//测试在pos位置后插入函数是否正常
void Test07()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	PrintSLlist(n1);
}
//测试在pos位置前插入函数是否正常
void Test08()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
}
//测试删除pos位置后函数是否正常
void Test09()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
	printf("\n");
	SLTEraseAfter(p);
	PrintSLlist(n1);
}
//测试删除pos位置函数是否正常
void Test10()
{
	SLlist* n1 = CreateSLlist(10);
	SLlist* p = SLTFind(n1, 3);
	SLTInsertAfter(p, 30);
	SLTInsert(&n1, p, 90);
	PrintSLlist(n1);
	printf("\n");
	SLlist* p2 = SLTFind(n1, 90);
	SLTErase(&n1, p2);
	PrintSLlist(n1);
}
//测试销毁函数是否正常
void Test11()
{
	SLlist* n1 = CreateSLlist(10);
	SLTDestroy(&n1);
	PrintSLlist(n1);
}
//主函数实现
int main()
{
	Test10();
	return 0;
}
标签：

相关文章