数据结构之单链表

1.链表的概念和结构

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

与顺序表不同，链表的每个节点都是独立申请下来的空间。
节点分成两个部分：当前节点保存的数据和保存的下一节点的地址（指针变量）

为什么我们需要指针变量来保存下一节点的位置？
链表中每一个节点都是单独申请的（需要插入数据就去申请一个节点），我们需要一个指针来保存下一个节点的地址，这样我们才能找到下一个节点。

//用结构体定义节点的结构
typedef int SLTDataType;//对int重命名，可以提高代码的可维护性

struct Slist
{
	SLTDataType data;//节点中的数据
	struct Slist* next;//用指针变量保存下一个节点的地址
};

typedef struct Slist SLTNode;

提醒：

• 链表在逻辑结构上是连续的，在物理结构上不一定连续
• 节点的空间一般是从堆上申请的

2.链表的分类

链表的结构有很多，但是平时我们用得最多的就是单链表（单向，不带头，不循环）和双向循环链表（双向，带头，循环）

• 单向不带头不循环链表：
  • 结构简单，一般不会单独用来存储数据。实际中更多的是作为其他数据结构的子结构
• 双向带头循环链表：
  • 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是双向带头循环链表。

3.单链表（单向，不循环，不带头）的实现

3.1 开辟空间

//向内存中申请空间
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

每个节点开辟一般都是采用动态内存开辟，这里我选用的是malloc函数，因为开辟的是节点所以sizeof里面的LTNode，数据就直接插入，我们要让新开辟的节点的next指针指向NULL。最后我们要返回该节点的地址。

3.2 打印

给定了链表，我们应该怎样实现从头到尾的打印呢？
这里我创建了一个节点指针（头指针）plist让它指向第一个节点，经过遍历，知道节点的next==NULL就停止

//打印
void SLTPrint(SLTNode* phead)
{
	//phead!=NULL
	//因为不能对NULL进行解引用
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead不能为空，不能对NULL进行解引用
	//先申请空间
	SLTNode* newnode = SLTBuyNode(x);

	//插入数据
	//if没有节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else//至少有1个节点
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

3.4 头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead不能为空，不能对NULL进行解引用
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);

	//插入数据
	newnode->next = *pphead;
	*pphead = newnode;
}

3.5 尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表也不能为空
	//如果只有1个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//至少有2个节点
	{
		SLTNode* cur = *pphead;
		SLTNode* prev = NULL;
		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}

3.6 头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表是空就不用删了

	//如果只有1个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//至少有2个节点
	{
		SLTNode* cur = *pphead;
		*pphead = cur->next;
		free(cur);
		cur = NULL;
	}
}

3.7 查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);//链表为空就不用找了
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.8 在指定位置之前插入数据

//在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead && *pphead);

	//在pos之前插入
	//如果pos在头节点，就采用头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else//pos不在头节点处
	{
		SLTNode* newnode = SLTBuyNode(x);
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		//cur newnode pos
		cur->next = newnode;
		newnode->next = pos;
	}
}

3.9 删除指定位置的数据

//删除指定节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pphead && *pphead);

	//如果pos的位置在头节点
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else//至少有2个节点
	{
		SLTNode* cur = *pphead;
		SLTNode* next = pos->next;

		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = next;
		free(pos);
		pos = NULL;
	}
}

3.10 销毁链表

//销毁
void SLTDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

链表的接口还有很多，这里我就写了一些比较常见的接口实现，后面的其他接口就不一 一写了