数据结构——C语言单链表的实现

一.链表的节点

//链表中的数据类型,方便后续的更改
typedef int SLTDatatype;

//链表的节点
typedef struct SLTNode
{
	SLTDataType data;
	struct SLTNode* next;
}SLTNode;

二.如何在在链表中插入数据

1.尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
	//给要插入的数据创造一个新的节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	
	//如果*pphead为空，就让它指向第一个节点
	//否则就找到最后一个节点，让最后一个节点的next指向新节点
	if(*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while(tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

但是这里我们为什么要使用二级指针呢？

1. 因为我的这个单链表是没有哨兵位的（也就是说我们是用指针指向了第一个节点），如果是有哨兵位的话，哨兵位就是第一个节点。
2. 因为我们是用指针指向的第一个节点，要改变第一个指针的内容，我们只能用二级指针来接收一级指针。一级指针传给一级指针相当于值传递
   

2.改进

之后我们不管是，尾插，还是中间插入都要进行一步相同的操作（创建新节点），所以我们把它提出来，单独作为一个函数。

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

3.头插

新节点的下一个节点指向原来的头节点，再把头节点指向新节点

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

4.指定位置pos，在pos前插入数据

要指定位置pos，我们还要写一个查找函数
找到了我们要的数据就返回它的地址，没有就返回NULL

SLTNode* SLTFind(SLTNode* phead,SLTDateType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while(cur)
	{
		if(cur->data = x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

如果是在头节点前插入数据，我们可以直接调用之前写好的头插。
其它节点前插入数据，我们需要知道原本在这个节点前的数据地址，让它的next指向要插入的节点，将插入节点的next指向被插入的节点。

//在pos位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);


	SLTNode* cur = *pphead;
	if (cur == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		cur->next = newnode;
		newnode->next = pos;
	}
}

三 .删除数据

1.头删

要先保留头节点的地址，让头节点指向头节点下一个节点的地址，最后释放掉保留下来的原来的头节点

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* erase = *pphead;
	*pphead = (*pphead)->next;
	free(erase);
	erase = NULL;
}

2.尾删

找到最后一个节点的前一个节点，释放掉最后一个节点，最后一个节点的next指向NULL
如果只有一个节点，那就释放掉它，然后phead指针指向NULL（函数中的*pphead 等价于 phead）

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* cur = *pphead;
	while (cur->next && cur->next->next)
	{
		cur = cur->next;
	}
	if (cur->next == NULL)
	{
		free(cur);
		*pphead = NULL;
	}
	else
	{
		free(cur->next);
		cur->next = NULL;
	}
}

3.指定位置删除数据

如果是删除的第一个位置的节点，调用头删。
其他节点的删除，在循环是我们需要注意保留被删除元素的前一个元素的地址，最后用被删除元素的前一个元素的next指向，被删除元素的next，最后释放掉被删除元素。

//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	SLTNode* cur = *pphead;
	if (cur == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}