投稿
  1. 首页
  2. C

【ONE·Data || 单链表简单实现】

code • 2022-5-16 • C • 阅读 24

【ONE·Data || 单链表简单实现】,第1张

总言

  C语言简单实现单链表的各个流程，代码解释在注释中。

文章目录
  • 总言
  • slist.h
  • test.c
  • slist.c
  • 图解补充

  

slist.h 
#pragma once
#define _CRT_SECURE_NO_WARNINGS

//SList-single
/*
* 链表的特点：
* 1、按需申请和释放空间
* 2、头部或者中间插入删除，不需要挪动数据（只需要将原先结点处的链表关系断开与重链接）
* ps：各种数据结构有其优缺点。
*/



//头文件
#include
#include
#include



//定义一个单链表结构:无头、单向
//解释：类同顺序表，以结构体形式定义单链表，此处结构体为最基本的使用单元：链表的每一个结点
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//单链表中一个结点
	struct SListNode* next;//指向下一个结点地址的指针
}SLTNode;



//单链表的主要使用功能：动态申请一个结点、单链表打印、查找、头删、头插、尾删、尾插、pos位置插入删除
void SListPrint(SLTNode* phead);
void SListPushBack(SLTNode** phead, SLTDataType x);
void SListPushFront(SLTNode** phead, SLTDataType x);
void SListPopFront(SLTNode** phead);
void SListPopBack(SLTNode** phead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

//在pos位置之前插入新结点：时间复杂度O(n)，因为需要查找pos之前的结点
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置处的结点：时间复杂度O(n)，因为需要查找pos之前的结点
void SListErase(SLTNode** phead, SLTNode* pos);

//在pos位置之后插入新结点
void SListInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置之后的结点
void SListEraseAfter(SLTNode** phead, SLTNode* pos);

  
  

test.c 
#include"SList.h"

//创建一个链表：手搓链表，有时做oj题不方便调试时的一个小技巧
//另一个调试技巧是走读代码，即画图结合代码分析，需要注意代码复杂时大脑别混乱
void TestList1()
{
	//此处创建结点也可以使用循环
	SLTNode* n1 = malloc(sizeof(SLTNode));
	assert(n1);
	SLTNode* n2 = malloc(sizeof(SLTNode));
	assert(n2);
	SLTNode* n3 = malloc(sizeof(SLTNode));
	assert(n3);
	SLTNode* n4 = malloc(sizeof(SLTNode));//使用动态内存是为了按需申请和释放
	assert(n4);
	//为结点中存储的数据
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	//将每个结点关联起来
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	//本质上是将后一个结点的地址存入前一个结点中(结构体成员)，此处举例的是单向链表，故最后一个结点处存储的是空指针。
	//这也是为什么创建SLTNode结构体时需要自引用的原因(创建一个相同类型的结构体指针，此指针是结构体成员，用于存放具有该结构体类型变量的地址)

	//测试单链表打印
	SListPrint(n1);
}

testlist2()
{
	//头插、结点为空时
	SLTNode* n1 = NULL;
	SListPushFront(&n1, 1);
	SListPrint(n1);
	//头插、结点不为空时
	SListPushFront(&n1, 2);
	SListPushFront(&n1, 3);
	SListPushFront(&n1, 4);
	SListPushFront(&n1, 5);
	SListPrint(n1);
	//尾插、结点为空时
	SLTNode* n2 = NULL;
	SListPushBack(&n2, 1);
	SListPrint(n2);
	//尾插、结点不为空时
	SListPushBack(&n2, 2);
	SListPushBack(&n2, 3);
	SListPushBack(&n2, 4);
	SListPushBack(&n2, 5);
	SListPrint(n2);

}


void testlist3()
{
	SLTNode* n1 = NULL;
	SListPushFront(&n1, 1);
	SListPushFront(&n1, 2);
	SListPushFront(&n1, 3);
	SListPushFront(&n1, 4);
	SListPushFront(&n1, 5);
	SListPushFront(&n1, 6);
	SListPushFront(&n1, 7);
	SListPushFront(&n1, 8);
	SListPushFront(&n1, 9);
	SListPushFront(&n1, 10);
	SListPrint(n1);
	//尾删
	SListPopBack(&n1);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPrint(n1);
	//头删
	SListPopFront(&n1);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPrint(n1);
}

testlist4()
{
	SLTNode* n1 = NULL;
	SListPushFront(&n1, 1);
	SListPushFront(&n1, 2);
	SListPushFront(&n1, 3);
	SListPushFront(&n1, 4);
	SListPushFront(&n1, 5);
	SListPushFront(&n1, 6);
	SListPrint(n1);
	//测试查找和修改
	SLTDataType aim;
	while (scanf("%d", &aim) != EOF)
	{
		SLTNode* result = SListFind(n1, aim);
		if (result != NULL)
		{
			printf("找到了\n");
			//修改找到的目标数据
			result->data = 0;//此处可自行修改,类比通讯录等
			SListPrint(n1);

		}
		else
		{
			printf("找不到\n");
		}
	}
}

testlist5()
{
	SLTNode* n1 = NULL;
	SListPushFront(&n1, 1);
	SListPrint(n1);
	//pos位置插入：当pos指向头部时
	SLTNode* aim1 = SListFind(n1, 1);
	if (aim1)
	{
		SListInsert(&n1, aim1, 20);
	}
	SListPrint(n1);
	SListPushFront(&n1, 2);
	SListPushFront(&n1, 3);
	SListPushFront(&n1, 4);
	SListPushFront(&n1, 5);
	SListPushFront(&n1, 6);
	SListPrint(n1);
	//在aim位置前插入（也可根据需要自行调整）
	SLTNode* aim2 = SListFind(n1, 4);
	if (aim2)
	{
		SListInsert(&n1, aim2, 40);
	}
	SListPrint(n1);
}

testlist6()
{
	SLTNode* n1 = NULL;
	SListPushFront(&n1, 1);
	SListPushFront(&n1, 2);
	SListPushFront(&n1, 3);
	SListPushFront(&n1, 4);
	SListPushFront(&n1, 5);
	SListPushFront(&n1, 6);
	SListPrint(n1);
	//pos位置删除：当pos指向头部时
	SLTNode* aim1 = SListFind(n1, 1);
	if (aim1)
	{
		SListErase(&n1,aim1);
	}
	SListPrint(n1);
	//pos位置删除：当pos指向头部时
	SLTNode* aim2 = SListFind(n1, 4);
	if (aim2)
	{
		SListErase(&n1,aim2);
	}
	SListPrint(n1);
}

int main(void)
{
	//头插、尾插检查
	//testlist2();
	//头删、尾删检查
	//testlist3();
	//查找与修改检查
	//testlist4();
	//pos位置前插入检查
	//testlist5();
	//pos位置处删除数据
	testlist6();
	return 0;
}

  
  

slist.c 
#include"SList.h"


//单链表的主要使用功能：动态申请一个结点、单链表打印、查找、头删、头插、尾删、尾插、pos位置插入删除
//思考细节：
//1、链表打印，将已有链表数据逐一打印
//2、头插、尾插等，都需要进行新增数据的 *** 作
// 其遵循“按需申请、释放”的规则，故需要灵活申请结点，此程序块可单独拎出构成一个辅助函数





//链表打印：
//思考：打印链表数据，可传递链表结点指针，指向data为该结点数据，指向nest能找到后续结点并打印
//打印具有连贯性，需要将顺序表所有结点数据（包含结点关系）都打印出来
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;//提问：为什么此处不直接使用phead指针，而需要额外创建一个同类型指针？
	while (cur != NULL)
	{
		//打印链表两步骤·其一：打印当前结点的数据
		printf("%d->", cur->data);
		//打印链表两步骤·其二：在当前结点中找到下一个结点的地址
		cur = cur->next;
		//cur被赋值后存储下一个结点(结构体)的地址(next指针)，故后续可用cur访问，直至最终cur指向为空
	}
	printf("NULL\n");
}





//辅助函数：动态申请一个新的结点
//思考：新增结点，需要注意结点的类型
//不同于头文件中只是定义结点的大致结构，此处是确切需要一个新结点，故要对新增的结点进行初始化处理
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;//对结点指向关系一律置空，后续根据使用函数再自行修改关系
	return newnode;
}




//单链表尾插
//思考：单链表尾插，即在链表末尾插入一个新的结点，根据链表数据有无分情况 *** 作
//若链表已有数据，动态申请新结点后，需将该结点与原先尾结点链接，形成新的链表关系（原先尾结点指向新增结点，新增结点成为尾结点，其next置空）
//若链表无数据，则尾插为其首数据，需要配合上述辅助函数使用
//设置参数：对链表做出修改，需要指向结点（结构体）的指针；插入数据，需要清楚数据
void SListPushBack(SLTNode** phead, SLTDataType x)
{	//思考：一级指针SLTNode * phead指针，其作为实参传递实际为值传递，作为形参只能改变结构体内部数据
	//此处链表需要在函数中变动该指针本身，则需要址传递，即SLTNode** phead
	assert(phead);
	SLTNode* newnode = BuySListNode(x);

	//链表无数据情况
	if (*phead == NULL)
	{
		*phead = newnode;//此处尾插是改变结构体指针本身，故需要SLTNode**
	}
	else//链表有数据时
	{
		//找到原先尾结点
		SLTNode* tail = *phead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		//建立新关系
		tail->next = newnode;//此处尾插是改变结构体成员，故使用SLTNode*
	}
	//注意：此处虽然newnode在出了函数后会被销毁，但malloc动态申请的空间仍在，此处已经让尾结点中的指针指向了该块内存空间。
	//函数传参后，改变指针变量需要用二级指针，改变指针所指向的对象，使用对应的指针即可，此处要注意区别。
}



//单链表头插
//思考：头插，即新增一个结点，使得该结点为链表的头部。
//所需 *** 作：在新增结点的next变量中存储原先的头结点，改变链表头结点的指向位置（phead指针）
void SListPushFront(SLTNode** phead, SLTDataType x)
{
	assert(phead);

	//新增结点
	SLTNode* newnode = BuySListNode(x);
	//头插，改变头部关系
	newnode->next = *phead;
	*phead = newnode;
	//头插不用分结点是否为空的情况，理解上述代码，当phead为NULL时，其将直接赋值给newnode->next逻辑关系成立

}



//单链表头删
//思考：头删，即删除头部结点，需要注意释放该结点对应的动态内存空间，以及更改phead指针的新指向
//此外头删还需要注意当链表内无结点时的情况，即结点为空时
void SListPopFront(SLTNode** phead)
{
	assert(phead);
	//检查链表结点是否为空:
	//if (*phead == NULL)
	//	return;
	assert(*phead);//另一种写法

	一种写法：将头结点保存起来，让链表头部phead指向头结点中的next指针（即第二个结点），再释放头结点
	//SLTNode* tmpphead = *phead;
	//*phead = (*phead)->next;
	//free(tmpphead);

	//另一种写法：将头结点中的next指针保存起来，释放头结点，再将链表头部phead指向被保存的next指针
	//（由于next指针指向第二结点，因此phead此时指向的第二结点成为了新的头结点）
	SLTNode* tmpnext = (*phead)->next;
	free(*phead);//要注意free的是结点，即SLTNode对应的指针，而不是该指针的地址SLTNode**
	*phead = tmpnext;
}



//单链表尾删
//思考：链表尾删，相当于要找到尾结点，next=NULL时，将此结点释放，同时还需要倒数第二个结点，将其中的next置空
void SListPopBack(SLTNode** phead)
{
	assert(phead);
	assert(*phead);
	if((*phead)->next==NULL)
	{
		//若只有一个结点的情况，此时tail进不去循环中，后续会出错（tail->next = NULL），故需要单独拎出来
		free(*phead);
		*phead = NULL;
	}
	else
	{
		//法一：站在尾结点的角度，遍历找到NULL，另存一指针指向倒数第二结点
		SLTNode* tail = *phead;//SLTNode* tail = NULL;
		SLTNode* cur = *phead;
		while (cur->next != NULL)
		{
			tail = cur;
			cur = cur->next;
			//当cur指针找到NULL时，即为需要被删除的尾结点，则tail指针对应倒数第二个结点
		}
		free(cur);
		cur = tail;
		cur->next = NULL;//tail->next = NULL;


		法二：站在倒数第二结点，遍历找到尾结点处的NULL
		//SLTNode* tail = *phead;
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	}
}




//单链表查找：可搭配修改单链表使用
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{

	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//此处单链表查找附加作用是修改对应链表对应结点
}



//pos位置之前插入：一般配合查找函数使用，见test.c中testlist5
//思考：单链表中，pos插入一般不以第几个元素（第几个结点）为标准，而是以是否存在某个结点为插入标准
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(phead);
	assert(pos);//此处检查是为了下述代码while (prev->next != pos)中，当pos==NULL时，会出现在NULL前插入结点的情况，类似于尾插，但不符合要求

	
	//头插，该情况下要变动phead的指向位置，需要单独考虑
	if (pos == *phead)
	{
		SListPushFront(phead,x);
	}
	else
	{
		//找到pos前结点，增加新结点，修改这些结点的关系
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}




//pos位置处删除
void SListErase(SLTNode** phead, SLTNode* pos)
{
	assert(phead);
	assert(pos);
	//头删
	if (pos == *phead)
	{
		SListPopFront(phead);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
		//从代码书写习惯，free释放后需要置空，但此处是形参，为临时变量，置空无用，且出了函数就会恢复为随机地址
	}
}



//pos位置后插入
void SListInsertAfetr(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(pos);

	写法一：需要注意顺序
	//SLTNode* newnode = BuySListNode(x);
	//newnode->next = pos->next;
	//pos->next = newnode;

	//写法二：借助一个指针,则可忽视顺序问题
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;

}



//pos位置后删除
void SListEraseAfter(SLTNode** phead, SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
		return;
	SLTNode* del = pos->next;
	pos->next = del->next;//pos->next=pos->next->next;
	free(del);
	del = NULL;
	//从代码书写习惯，free释放后需要置空，但此处是形参，为临时变量，置空无用，且出了函数就会恢复为随机地址
}

  
  

图解补充





  
  
  

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/914705.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表（0条）

保存