【C语言】-- 数据结构 -- 单向单链表_c语言单向链表

目录

1. 单链表

2.单向单链表的分类

    2.1 带头或者不带头(带头：哨兵位)

    2.2 循环或者非循环  

3. 不带头单向单链表的实现

    3.1 链表的打印

    3.2 动态创建一个节点

    3.3 单链表的尾插

             3.4 单链表的头插

    3.5 单链表的尾删

         3.5.1 只有一个节点时：

         3.5.2 有两个或更多节点时：

    3.6 单链表的头删

         3.6.1 只有一个节点时：

​         3.6.2 有两个或更多节点时：

    3.7 单链表的查找(返回NULL就是没有找到)

    3.8 单链表的插入（之前）

         3.8.1 只有一个节点时： 

         3.8.2 有两个或更多节点时：

---

1. 单链表

其的存在就例如一列火车，我们可以对车厢的链接顺序更改，又必须是一个型号的火车车厢，并且不能说每一节车厢完全属于一起的，连续的。但又进行了链接，属于同一个类型。也就是逻辑上是连续的，但是物理上却不是。从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

---

2.单向单链表的分类

    2.1 带头或者不带头(带头：哨兵位)

    2.2 循环或者非循环  

---

3. 不带头单向单链表的实现

typedef int SLTDateType;    //便于对于单链表的数据存储类型的改变
 
typedef struct SListNode
{
	SLTDateType a;    //指向动态开辟的数组
	struct SListNode* next;    //该节点所指向的下一个节点或NULL(结尾)
}SLTNode;
 
//动态创建一个节点
SLTNode* SListNewNode(SLTDateType n);
//链表的打印
void SListPrint(SLTNode* pphead);
//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType n);
//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDateType n);
//单链表的尾删
void SListPopBack(SLTNode** pphead);
//单链表的头删
void SListPopFrond(SLTNode** pphead);
//单链表的查找(返回NULL就是没有找到)
SLTNode* SListFind(SLTNode* phead, SLTDateType n);
//单链表的插入（之前）
void SListInsertForward(SLTNode** pphead, SLTNode* pos, SLTDateType n);

    3.1 链表的打印

//链表的打印
void SListPrint(SLTNode* pphead)
{
	SLTNode* cur = pphead;
	while (cur != NULL)
	{
		printf("%d->", cur->a);
		cur = cur->next;
	}
	printf("NULL\n");
}

---

    3.2 动态创建一个节点

        是极为重要的一个操作，只要是关于插入的功能都需要运用，所以此处将其进行封装，便于使用。

//动态创建一个节点
SLTNode* SListNewNode(SLTDateType n)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
 
	newnode->a = n;
	newnode->next = NULL;
	return newnode;
}

---

    3.3 单链表的尾插

        **pphead == &head

        主要针对于无节点的单链表链表，对于此类单链表如若按常理执行，会访问结构指针成员（struct SListNode* next），会导致野指针的问题。正确的操作就是直接对等于NULL的指针head直接进行更改，使得我们所插入的数据变为head所指向的。

        这个操作，改变的不是head所可指向的数据，而是其本身。而更改其本身，是无法通过传参的形式更改，只会是一个临时拷贝，无法进行直接的更改，于是就需要运用二级指针。传入&head，以**pphead接收。 

//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType n)
{
	assert(pphead);
	SLTNode* newnode = SListNewNode(n);
 
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (NULL != cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

 

（注意（动态图制作有问题）：newnode节点的next应该是NULL)

---

    3.4 单链表的头插

//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDateType n)
{
	assert(pphead);
	SLTNode* newnode = SListNewNode(n);
 
	newnode->next = *pphead;
	*pphead = newnode;
}

---

    3.5 单链表的尾删

        此功能，是很容易就能实现的，直接free最后一个节点，然后再将前一个节点中的next改为NULL即可。但，需要注意phead是不能为空的，不然怎么删除？

        我们对于含有元素的链表，是需要最后一个节点与倒数第二个节点。

        3.5.1 只有一个节点时：

         3.5.2 有两个或更多节点时：

//单链表的尾删
void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	SLTNode* cur = *pphead;
	if (NULL == cur->next) //只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else //有两个或更多节点时
	{
		while (NULL != cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}

---

    3.6 单链表的头删

        需要注意phead是不能为空的，不然根本没有节点供给删除。

//单链表的头删
void SListPopFrond(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	if (NULL == (*pphead)->next) //只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else //有两个或更多节点时
	{
		SLTNode* cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
	}
}

         3.6.1 只有一个节点时：

          3.6.2 有两个或更多节点时：

 

---

    3.7 单链表的查找(返回NULL就是没有找到)

//单链表的查找(返回NULL就是没有找到)
SLTNode* SListFind(SLTNode* phead, SLTDateType n)
{
	assert(phead);
 
	SLTNode* cur = phead;
	while (n != cur->a)
	{
		cur = cur->next;
		if (NULL == cur)
		{
			return NULL;
		}
	}
	return cur;
}

---

    3.8 单链表的插入（之前）

        与头插差不多，只不过同样的是得到插入的前面一个节点的地址，，正因为所传入的pos就是所插入的后一个节点的地址，于是通过cur->next确定是不是下一个就是其。 

//单链表的插入（之前）
void SListInsertForward(SLTNode** pphead, SLTNode* pos, SLTDateType n)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	SLTNode* newnode = SListNewNode(n);
	SLTNode* cur = *pphead;
 
	if (cur == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		while (pos != cur->next)
		{
			cur = cur->next;
		}
		newnode->next = cur->next;
		cur->next = newnode;
	}
}

          3.8.1 只有一个节点时： 

          3.8.2 有两个或更多节点时：