C 语言 【单链表】

        单链表是一种基本的数据结构，由一系列节点组成，每个节点包含数据域和指针域。‌数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。单链表的特点包括动态存储、非连续存储、易于插入和删除。

        节点可以定义成一个结构体，每个节点中包含一个数据和下一个节点的地址。

//构造节点
typedef int SLDataType;

struct SLNode
{
	SLDataType data;
	struct SLNode* next;
};

typedef struct SLNode SLNode;

        上面的结构体定义了一个节点，节点中存放的数据类型被定义成了SLDataType类型，节点的名称叫做SLNode。

1、单链表的顺序访问

        这里给出单链表的逻辑结构：首先有一个节点指针pList指向开始的节点，节点中的next存放的是下一个节点的地址。可以通过next访问下一个节点。最后一个节点的next中存放的是空指针NULL；

        这里写一个打印单链表的函数，以示范单链表的访问功能；

void SLPrint(SLNode* phead);

        这里需要说明的是，打印函数在访问链表的过程中不涉及更改链表，所以在设计函数时参数部分用节点的指针就可以。进一步来说，打印函数需要将每一个节点的data打印出来，这个时候可以按照如下的方式进行访问节点；

        当cur为NULL时打印NULL即可，那么函数的实现可以写成如下的形式；（由于链表为空时能进行打印功能，所以不能在函数体最开始进行断言操作） 

void SLPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2、单链表的末尾插入

        链表的末尾插入首先需要创建新的节点，这里可以创建一个新的节点指针，并对里面的内容分进行初始化，由于后面还会涉及到节点的创建，所以在这里选择将其封装成一个函数；  在创建完成时，返回新节点的指针用于后续的拼接。

SLNode* SLBuyNode(SLDataType val)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		perror("PushBack malloc faile");
		return;
	}

	newNode->data = val;
	newNode->next = NULL;

	return newNode;
}

        在末尾插入节点时会有两种情况：1、链表本身为空  2、链表不为空

        当链表本身为空时，我们需要将新创建的节点与pList进行拼接，此时的操作就会改变pList的值，在写函数时我们要改变的是一级节点指针的内容，所以在函数传参时应该传入二级节点指针才能达到目的效果。

        当链表pList为空时,将新创建的节点的地址newNode赋值给pList.然而在函数调用过程中形参的改变不影响实参的变化。所以在这里选择使用*pphead = newNode ，这样就可以达到修改实参的目的。

        当链表不为空时，需要找到链表的最后一个节点的地址tail，修改最后一个节点的next 使其指向创建的新节点newNode。

        这里需要注意的是，我们需要改变的是最后一个节点中nest的值，那么就需要最后一个节点的地址tail ，当tail->next非空时 将tail->next赋值给tail即可找到最后一个节点的地址。最后将newNode赋值给tail->next即可。这样尾插节点就实现了，下面是代码实现：

void SLPushBack(SLNode** pphead,SLDataType val)
{
	//1、创建新的节点指针
	SLNode* newNode = SLBuyNode(val);

	//进行拼接
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		//找最后一个节点的结构体指针
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

3、单链表的末尾删除

        需要考虑的是当链表为空时就不能进行删除操作，所以需要在函数体开始进行断言操作。第二点：目标链表的节点数为1时，删除完节点之后要修改pList的值，使它的值为NULL;这里就需要更改pList的值，所以在函数传参时就需要传入节点的二级指针。函数声明如下：

void SLPopBack(SLNode** pphead);

        当链表只有一个节点时：直接释放pList 再将其置空

        当链表中的节点个数大于1时，先找到倒数第二个节点的地址，用于将倒数第二个节点中的next置为空，也需要找到倒数第一个结点的地址，直接释放再将其置为空。

        那么单链表的末尾删除就可以写成如下的形式：

void SLPopBack(SLNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next != NULL)
	{
		//链表节点大于1个
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;
	}
	else
	{
		free(*pphead);
		*pphead = NULL;
	}
}

4、单链表的头部插入

        链表为空时可以进行插入操作，所以不能进行断言操作。当链表为空时，创建新节点之后需要将新节点的地址赋值给pList，在这个操作中需要修改pList的值，所以在函数传参时需要传入节点的二级指针。单链表的头部插入函数声明如下：

void SLPushFront(SLNode** pphead, SLDataType val);

        在头部插入时，均需要修改pList的值。然后将新节点中next的值修改为原来pList的值

         可以看到，上述的两种情况可以合并为一种情况来写，所以单链表的头部插入函数可以写成如下的形式：

void SLPushFront(SLNode** pphead, SLDataType val)
{
	SLNode* newNode = SLBuyNode(val);
	newNode->next = *pphead;
	*pphead = newNode;
}

5、单链表的头部删除

        链表为空时不能进行删除操作，所以在函数体内要进行断言操作。每次删除一个节点之后，要将第二个节点的地址赋值给pList，在这里也需要修改pList的值，所以在函数传参时，也需要传入节点的二级指针。函数的声明如下：

void SLPopFront(SLNode** pphead);

         按照上面的逻辑就可以定义函数为：

void SLPopFront(SLNode** pphead)
{
	assert(*pphead != NULL);

	SLNode* first = *pphead;
	*pphead = first->next;

	free(first);
	first = NULL;
}

单链表的测试：

void Test1()
{
	SLNode* pList;
	pList = NULL;
	

	SLPushBack(&pList,1);
	SLPushBack(&pList,2);
	SLPushBack(&pList,3);
	SLPushBack(&pList,4);
	SLPrint(pList);

	SLPopBack(&pList);
	SLPopBack(&pList);
	SLPopBack(&pList);
	SLPopBack(&pList);

	SLPrint(pList);


}

void Test2()
{
	SLNode* pList;
	pList = NULL;


	SLPushBack(&pList, 1);
	SLPushBack(&pList, 2);
	SLPushBack(&pList, 3);
	SLPushBack(&pList, 4);
	SLPrint(pList);

	SLPushFront(&pList,1);
	SLPushFront(&pList,2);
	SLPushFront(&pList,3);
	SLPushFront(&pList,4);

	SLPrint(pList);


}

void Test3()
{
	SLNode* pList;
	pList = NULL;

	SLPushFront(&pList, 1);
	SLPushFront(&pList, 2);
	SLPushFront(&pList, 3);
	SLPushFront(&pList, 4);

	SLPrint(pList);

	SLPopFront(&pList);
	SLPrint(pList);
	SLPopFront(&pList);
	SLPrint(pList);
	SLPopFront(&pList);
	SLPrint(pList);
	SLPopFront(&pList);
	SLPrint(pList);
	


}

int main()
{
	Test1();
	Test2();
	Test3();

	return 0;
}

        下附运行结果，可以观察到，上述功能均已实现。