数据结构初阶之单链表(C语言实现)

虽然顺序具有方便下标随机访问(因为是连续物理空间)的优点,但是也具有一定的缺陷,

如:

1. 插入数据,空间不足时要扩容,但是扩容有性能消耗

2. 头部或者中间位置插入删除数据,需要挪动数据,效率比较低

3. 空间扩容太大,可能存在一定空间占用,浪费空间,不能按需申请和释放空间

由于这些缺陷,链表诞生了

那么链表是什么?

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。

数据结构初阶之单链表(C语言实现)_第1张图片

从上图可看出:

1. 链式结构在逻辑上是连续的,但是在物理上不一定连续

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间,是按照一定的此略来分配的,两次申请的空间可能连续,也可能不连续

链表分类:

单向或者双向

数据结构初阶之单链表(C语言实现)_第2张图片

 带头或者不带头

数据结构初阶之单链表(C语言实现)_第3张图片

循环或者非循环

数据结构初阶之单链表(C语言实现)_第4张图片

 常用的结构:

无头单向非循环链表

结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在面试笔试中出现很多。

数据结构初阶之单链表(C语言实现)_第5张图片

带头双向循环链表

结构最复杂,一般用在单独处处数据,实际中使用的链表数据结构,都是带头双向循环链表。另外整个结构虽然结构复杂,但是使用代码实现以后会发现会带来很多优势,实现反而简单了

数据结构初阶之单链表(C语言实现)_第6张图片


 这里实现的是无头单向非循环链表

将要完成接口有:

//创建结点
SListNode* BuySListNode(SListDateType x);

//打印链表
void PrintSList(SListNode* phead);

//尾插
void SListPushBack(SListNode** pphead, SListDateType x);

//头插
void SListPushFornt(SListNode** pphead, SListDateType x);

//尾删
void SListPopBack(SListNode** pphead);

//头删
void SListPopFront(SListNode** pphead);

//查找指定值
SListNode* SListFind(SListNode* phead, SListDateType x);

//在指定位置前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x);

//在指定位置后插入
void SListInsertAfter(SListNode* pos, SListDateType x);

//删除指定位置
void SListErase(SListNode** pphead, SListNode* pos);

//删除指定位置后结点
void SListEraseAfter(SListNode* pos);

//销毁链表
void SListDestroy(SListNode** pphead);

注:无头单向非循环链表需要理解二级指针传参,以及链表为空和不存在与顺序表的为空和不存在

定义的结构体结点:

typedef int SListDateType;//方便类型灵活变换

typedef struct SListNode
{
	int date;//数据
	struct SListNode* next;//存放下一个结点的地址
}SListNode;

创建新结点:

这里需要注意,由于链表的特点,我们操作结构体指针,而不是操作结构体,这一点与顺序表不同,所以我们要做的不是初始化,而是要写一个创建新结点的接口函数,当结点创建好就把数据放入

//创建新结点
SListNode* BuySListNode(SListDateType x)
{
	//开辟一块动态内存
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	//开辟失败终止程序
	if (newnode == NULL)
	{
		printf("Fail\n");
		exit(-1);
	}
	else
	{
		newnode->date = x;//将x放入新开辟date
		newnode->next = NULL;//开辟空间后不知道指向哪,先置空
	}
	//将开辟空间返回
	return newnode;
}

尾部插入结点:

这里需要注意

由于尾插可能会改变第一个结点(链表为空),既然第一个结点会被改变,就应该传地址,而传过来的应该是一个一级指针指向链表的第一个结点,所以这里应该用二级指针接收

尽管传过来的一级指针指向的链表可能为空(即这个一级指针被赋为空),这也只是说明链表为空,但是存在这个链表,但是pphead作为应该二级指针指向传过来的一级指针,所以pphead里存放了这个一级指针的地址,既然有这个一级指针,那么这个一级指针便有地址存放一级指针,所以pphead不可能为空,否则就不是链表为空,那是链表不存在了,这是非法的情况

当链表为空需要分开讨论,直接将新创建的结点赋值

其他情况如下:

数据结构初阶之单链表(C语言实现)_第7张图片

void SListPushBack(SListNode** pphead, SListDateType x)
{
	assert(pphead);//pphead不能为空
	//传x并接收创建的结点
	SListNode* newnode = BuySListNode(x);
	//如果传的是NULL,说明是空链表,将开辟的空间直接赋给空的链表
	if (*pphead == NULL)
	{
		//当链表尾空,将第一次新开的结点赋值,则*pphead存放的则始终是第一个结点
		*pphead = newnode;
	}
	//如果传的不是NULL,说明不是空链表,原来的链表有结点
	else
	{
		//找尾巴,将头结点给找尾结点
		SListNode* tail = *pphead;
		//当tail中的next等于NULL,说明其就是结尾的结点
		while (tail->next != NULL)
		{
			//找尾结点,不断的将下一个结点的地址给tail,直到下一个结点的地址是NULL
			tail = tail->next;
		}
		//当tail->next==NULL,将新开的结点赋值,替换NULL
		tail->next = newnode;
	}
}

打印链表:

由于是打印,第一个结点也不会被改变,所以采用传值,即传一级指针的值,就用一级指针接收

void PrintSList(SListNode* phead)
{
	SListNode* cur = phead;//将头结点赋值给现结点
	//使用现结点遍历,cur->next==NULL是链表结束的标志
	while (cur != NULL)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

头部插入结点:

这里头部插入和尾部插入同理,

插入情况如下:

数据结构初阶之单链表(C语言实现)_第8张图片

void SListPushFornt(SListNode** pphead, SListDateType x)
{
	assert(pphead);//pphead不能为空
	//接收创建的新结点
	SListNode* newnode = BuySListNode(x);
	//将首结点地址给新建结点的next
	newnode->next = *pphead;
	//将新建结点的地址放首结点
	*pphead = newnode;
}

尾部删除结点:

尾删和前面的尾插同理,还要注意链表为空以及链表只有一个结点的两种特殊情况,得分开情况讨论,因为prev不能为空,所以分情况讨论

没有结点无法删除

只有一个结点则直接删除

数据结构初阶之单链表(C语言实现)_第9张图片

 其他情况如下:

数据结构初阶之单链表(C语言实现)_第10张图片

void SListPopBack(SListNode** pphead)
{
	assert(pphead);//链表必须存在

	//空链表直接返回
	if (*pphead == NULL)
	{
		return;
	}
	//链表只有一个结点,直接释放
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//链表大于一个结点
	else
	{	
		//采用双指针做法
		SListNode* tail = *pphead;
		SListNode* prev = NULL;
		//找尾
		while (tail->next != NULL)
		{
			//保留前一个结点的地址
			prev = tail;
			tail = tail->next;
		}
		//释放尾结点并置空
		free(tail);
		tail = NULL;
		//前一个结点的next置空
		prev->next = NULL;
		/*
		两次解引用的做法
			while (tail->next->next != NULL)
			{
				tail = tail->next;
			}
			free(tail->next);
			tail->next = NULL;
		*/
	}

}

头部删除结点:

与尾插同理,还要链表不能为空,为空无法删除

数据结构初阶之单链表(C语言实现)_第11张图片

void SListPopFront(SListNode** pphead)
{
	assert(pphead);//链表必须存在

	//链表为空
	if (*pphead == NULL)
	{
		return;
	}
	//链表不为空
	else
	{
		//存放第二个结点的地址
		SListNode* next = (*pphead)->next;
		//释放第一个结点
		free(*pphead);
		//指向第二个结点
		*pphead = next;
	}
}

查找指定的值:

由于是查找,不改第一个结点,所以传值,用一级指针接收

SListNode* SListFind(SListNode* phead, SListDateType x)
{
	//遍历链表的现指针
	SListNode* cur = phead;

	//查找x
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	//找不到 
	return NULL;
}

在指定位置前插入:

 与尾插同理,第一个结点可能改变,而且待插位置不能为空,这里需要分情况讨论,

当插入的结点是第一个结点时,正好是头插,因为prev不能为空,所以单独讨论

当插入的结点不是第一个时:

数据结构初阶之单链表(C语言实现)_第12张图片

void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x)
{
	assert(pphead);//链表必须存在
	assert(pos);//插入的位置不能为空

	//当插入的结点是第一个时
	if (pos == *pphead)
	{
		SListPushFornt(pphead, x);
	}
	//当插入的结点不是第一个时
	else
	{
		//从第一个结点开始遍历
		SListNode* prev = *pphead;

		//查找pos位置
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		//创建新的结点
		SListNode* newnode = BuySListNode(x);

		//插入
		prev->next = newnode;
		newnode->next = pos;
	}
}

在指定位置后插入:

这种情况第一个不可能被改变,所以传值就行,使用一级指针接收,以及待插位置不能为空

数据结构初阶之单链表(C语言实现)_第13张图片

void SListInsertAfter(SListNode* pos, SListDateType x)
{
	assert(pos);//插入的位置不能为空

	//创建结点
	SListNode* newnode = BuySListNode(x);

	//插入
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置的结点:

有可能删除第一个结点,二级指针接收,位置不能为空

需要分情况讨论:

当删除的结点是第一个结点时,也就是头删,需要单独讨论,因为prev不能为空

其他情况如下:

数据结构初阶之单链表(C语言实现)_第14张图片

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);//链表必须存在
	assert(pos);//查找的位置不能为空

	//当删除的位置是第一个结点时
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	//当删除的位置是不是第一个结点时
	else
	{
		//从第一个结点开始遍历
		SListNode* prev = *pphead;
		
		//查找pos
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		//删除结点
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

}

删除指定位置后的结点:

不可能删除第一个结点,所以传值,一级指针接收,位置不能为空

数据结构初阶之单链表(C语言实现)_第15张图片

void SListEraseAfter(SListNode* pos)
{
	assert(pos);//pos不能为空

	//存放待删除的结点
	SListNode* next = pos->next;

	//pos不是最后一个结点,也就是next不能为空
	if (next)
	{
		//删除结点
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

销毁链表:

第一个结点会被改变,传地址,二级指针接收

void SListDestroy(SListNode** pphead)
{
	assert(pphead);//链表得存在

	SListNode* cur = *pphead;

	while (cur)
	{
		//指向待删除的下一个结点
		SListNode* next = cur->next;
		//删除
		free(cur);
		//指向下一个结点,正好到了最后一个结点cur被置空
		cur = next;
	}
}

由此可见,单链表结构:

适合头插头删

不适合尾部或者中间某个位置插入删除

你可能感兴趣的