189 8069 5689

C语言实现——单链表-创新互联

一、总体思路

单链表就是利用指针和结构体对数据的一种存储和管理模式，定义一个结构体变量，成员一个用于存放数据，一个是用于链接下一个数据的指针，每一个独立的结构体变量在单链表中通常被叫作节点，一个个节点通过指针相连，像一个链子一样，清楚定义的前提下，结合图形去一一实现这个链表的定义和增删查改。

创新互联公司自2013年起，先为恒山等服务建站，恒山等地企业，进行企业商务咨询服务。为恒山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

二、单链表的定义 1.节点的声明（结构体的声明）

节点要包含一个放数据的成员和指向下一个节点的指针：

#define SLT_Data_Type int//方便更改链表的数据类型

typedef struct SLT
{
	SLT_Data_Type data;//数据
	struct SLT* next;//指针
}SLT;

2.节点的定义

由于节点的开辟是个重复多次的动作，在后面的增加数据也要用，因此将开辟节点分装成一个函数

SLT* Buy_SLT_Data(SLT_Data_Type k)//开辟节点
{
	SLT* p=(SLT*)malloc(sizeof(SLT));
	if(p==0)
	{
		perror("malloc error");
		exit(-1);
	}
	p->data=k;
	p->next=NULL;
	return p;
}

参数是在节点放的数据，将指针默认指向NULL，最后返回开辟好节点的地址。

3.链表的定义

我们定义一个函数，参数为我们想要一次性开辟的节点数，由这个函数实现将节点串联起来，由于为了方便调试，因此数据上一开始先不采用自主输入的方式，最后返回链表的头地址。

SLT* InitSLT(int n)//创建链表
{
	int i;
	SLT* phead=NULL;
	SLT* fail=NULL;
	for(i=0;inext=Buy_SLT_Data(i);
			fail=fail->next;
		}
	}
	return phead;
}

三、打印链表

为了方便调试和展示效果，我们先将链表的打印实现，由一个指针，从头开始，打印一个后，找到下一个继续打印，直到该指针指向空即为结束。

void SLTPrint(SLT* phead)
{
	SLT* fail=phead;
	while(fail)
	{
		printf("%d ->",fail->data);
		fail=fail->next;
	}
	printf("NULL\n");
}

四、尾插与尾删 1.尾插

先考虑边界条件，若链表为空可以尾插吗？

可以，但如果链表为空，意味着要改变最开始的地址，而最开始的地址作为形参传到函数中是不够的，要使用二级指针去对最初的地址进行操作。

考虑好边界条件以后，若列表不为空，所有的其他情况是否采用同一套逻辑执行？

是的，因此我们将情况分成两种，一个是当头地址为空，我们将用二级指针对头地址进行更改为新开辟的节点，若头地址不为空，我们将找到最后一个节点，将新开辟的节点进行链接。

void SLTPushBack(SLT** pphead,SLT_Data_Type k)
{
	SLT* tail=*pphead;
	SLT* newdata=Buy_SLT_Data(k);
	if(*pphead == NULL)//空链表
	{
		*pphead=newdata;
	}
	else
	{
		while(tail->next)//找到最后一个节点
		{
			tail=tail->next;
		}
		tail->next=newdata;
	}
}

2.尾删

还是优先考虑下边界条件，当链表为空，能不能删？

不能删，因此我们要对空的头地址进行断言

当链表只有一个节点的时候，我们要删除的是最初传入的地址，因此对头地址需要修改，要穿二级指针，因此同样分两种逻辑。

当只有一个的时候，对二级指针进行操作，删除外面的头地址指向的空间，并且要把地址置空

当多个的时候，用指针遍历到倒数第二个，先将下一个数据空间释放，再将next指针指向空。

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

五、头插和头删 1.头插

先考虑边界条件，若为空链表可以头插吗？

可以，而且每次头插本质上都是更改头地址，因此也是要用二级指针，我们将新开辟的节点直接链接到原先的头地址上，并且将头地址更新即可

void SLTPushFront(SLT** pphead,SLT_Data_Type k)//头插
{
	SLT* newhead=Buy_SLT_Data(k);
	newhead->next=*pphead;
	*pphead=newhead;
}
2.头删

考虑边界情况，空链表可以删除吗

显然不能，因此应该加上断言，只有一个的情况能删除吗？

可以，而且头删都会改变头地址，因此得传二级指针

void SLTPopFront(SLT** pphead)//头删
{
	SLT* newhead=(*pphead)->next;
	assert(*pphead);
	free(*pphead);
	*pphead=newhead;
}

六、指定数后插和后删 1.查找

由于链表的地址不连续，要实现指定数位置的后插和后删，我们都需要先找到这个数的地址，因此我们先分装出个函数，专门实现对指定数字进行查找的。

查找的思路就是那一个指针去遍历整个链表当找到的时候返回地址，当没找到的时候，我们返回空指针，同样考虑边界问题，空链表不能被查找，又或者查找以后返回NULL（这个是否选择要断言可根据自己选择设计）

SLT* SLTFine(SLT* phead,SLT_Data_Type n)
{
	SLT* cur=phead;
	assert(phead);
	while(cur)
	{
		if(cur->data==n)
			return cur;
		cur=cur->next;
	}
	return NULL;
}
2.指定数后插

我们要在指定的数字后插入，首先我们应该要传参的时候给到指定的数或者指定数的地址，从用户的角度上考虑，我这里参数选择是给指定的数。

同样我们要考虑边界问题，当链表为空时，可以指定数字插入吗？实际上我们压根就找不到这个数，更别说后插了，再者，如果我们找不到指定数的地址，也就是返回的是空指针，说明这个数不存在链表或者链表为空，因此我们需要对指定数的地址进行断言

接下来就是设计如何进行一般情况下的链接

通过画图，我们可以看到，指定位置的next一开始指向的地方，如果我们不注意赋值的顺序，就可能会丢失地址信息，图中1和2的顺序不可逆，实在要反过来，就得创建临时变量去存指定位置next的地址。

void SLTInsertAfter(SLT* phead,SLT_Data_Type n,SLT_Data_Type k)
{
	SLT* newdata=Buy_SLT_Data(k);//新的节点
	SLT* pn=SLTFine(phead,n);//插入的位置在该地址后一位
	assert(pn);//找不到位置
	//链接
	newdata->next=pn->next;
	pn->next=newdata;
}

2.指定后删

指定位置往后删除，我们同样传指定位置的数字，在函数内部找地址，同样，如果找不到，什么可能是空链表或者没有这个指定的数，因此也需要断言

而接下来是这个功能的设计考虑，我们要删除一个指定位置的后一位，我们还得将该位置的后两位的节点往前链接上来，因此我们的边界考虑，出来空链表的情况，还有假如只有一个节点，删除该节点的后一节点，相当于什么都不做，或者也可以断言警告它后面没东西可以删。

此外，一般情况的逻辑

1.将指定位置的后两位节点指针（指定位置的next的next）交给一个临时变量指针存着

2.通过指定位置的next找到要删除的节点，free掉该空间

3.将临时指针里存放的地址给到指定位置的next进行链接

void SLTEraseAfter(SLT* phead,SLT_Data_Type n)
{
	SLT* pn=SLTFine(phead,n);//删除该位置的下一个节点
	SLT* cmp=NULL;
	assert(pn && pn->next);//找不到或者要删的下一个是个空的
	cmp=pn->next->next;
	free(pn->next);
	pn->next=cmp;
}

七、指定删除

大家可能再刚学到指定位置往后增删的操作的时候，会有些不理解，插入也就算了，为什么删除不是指定哪个就删哪个，而要删后一个呢？

我们假设现在要实现指定位置删除，那么我们同样的需要指定数字的地址，函数参数的设计上和是一个指定后删没差别

考虑边界情况，空链表和找不到指定删除的数字时，都是没办法删除的，空链表必然找不到指定数字，因此断言指定数字的地址即可

此外指定位置为头位置时，我们也需要对头地址进行更改，因此需要二级指针

除开头地址的删除，就是一般情况下的指定删除，我们通过画图设计实现思路

我们看着图思考，假设要删除指定的节点，我们删完后还需要将它的前后两个链接起来，但是目前我们只能知道的是传参的头地址和指定位置的地址，因此相比于指定位置后一位删除，这个指定删除要一个指针去遍历一遍链表，找到指定位置的前一个地址，才能完成链接，在数据较多的情况下，效率上肯定是低于删后一项的，但对于用户使用上却是更加方便的。

实现思路：

1.分逻辑，如果指定位置是头位置，单独一个逻辑删除头位置后，将新的头地址用二级指针传给链表开头。

2.如果不是头地址，先用一个指针遍历链表找到指定位置的前一项

3.指定位置前一项记录下指定位置的后一项（链接）

4.释放指定位置的空间（删除）

void SLTErase(SLT** pphead,SLT_Data_Type n)
{
	SLT* pn=SLTFine(*pphead,n);//要删除的位置
	SLT* cur=*pphead;
	assert(*pphead);
	if(pn == cur)//头删
	{
		SLTPopFront(pphead);
	}
	else//若要删除位置不在头
	{
		while(cur->next != pn)//找到删除位置的前一个
			cur=cur->next;
		cur->next=pn->next;
		free(pn);
	}
}

八、销毁链表

在使用完链表后，由于动态开辟的内存是堆上的空间，因此我们还需要对链表的空间进行释放，

释放链表就是两个指针并肩走的思路（该思路在很多题目和操作中十分重要）

void SLTDeastroy(SLT** pphead)
{
	SLT* tail=NULL;
	if(*pphead == NULL)
		return;
	tail=(*pphead)->next;
	free(*pphead);
	*pphead=NULL;
	while(tail)
	{
		SLT* pnext=tail->next;
		free(tail);
		tail=pnext;
	}
}

总结

本篇用C语言实现了一个最基本的单链表，逐步对每一步进行了分析和设计，捋清楚了链表的实现思路，并且附上了代码，如果有哪里不足，欢迎大家指出。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


标题名称：C语言实现——单链表-创新互联
转载来于：http://cdxtjz.cn/article/cdgpgs.html

其他资讯