[数据结构与算法]单向链表的一些接口函数

链表相对于书虚表而言，更加利用内存，并且在内存上不是连续的。

下面来写一些简单的接口函数

先定义一个链表

//重定义
typedef int DataType;
struct SListNode
{
	DataType data;
	struct SListNode* next;
};
//重定义
typedef struct SListNode SLTNode;

链表的输出函数

//输出
void SListPrint(SLTNode* ps)
{
	SLTNode* cur = ps;
    //当cur的地址不为NULL的时候，输出cur->data值
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

链表的尾插函数

//尾插
void SListPushBack(SLTNode** pps, DataType x)
{
	//扩容一个节点
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	NewNode->data = x;
	NewNode->next = NULL;
    //当链表为空时
	if (*pps == NULL)
	{
		*pps = NewNode;
	}
	else
	{
		//找尾节点的指针
		SLTNode* find = *pps;
		while (find->next != NULL)
		{
			find = find->next;
		}

		//尾节点,链接新节点
		find->next = NewNode;
	}

}

链表的头插函数

//头插
void SListPushFront(SLTNode** pps, DataType x)
{
	//扩容一个节点
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	NewNode->data = x;
	NewNode->next = NULL;

    //将该节点的next指向链表中首节点的地址，当链表为空时指向NULL
	NewNode->next = *pps;
    //将该节点存入链表
	*pps = NewNode;
}

链表的头删函数

//头删
void SListPopFront(SLTNode** pps)
{
	if (*pps == NULL)
	{
		printf("空的!\n");
	}
	else
	{
		//先将第二个节点的地址保存
		SLTNode* next = (*pps)->next;
		//然后释放第一个节点的空间
		free(*pps);
		//最后将第二个节点的地址赋给释放后的链表
		*pps = next;
	}
}

链表的尾删函数

//尾删
void SListPopBack(SLTNode** pps)
{
	//空
	if (*pps == NULL)
	{
		printf("空的!\n");
	}
	//一个节点
	else if ((*pps)->next == NULL)
	{
		free(*pps);
		*pps = NULL;
	}
	//多个节点
	else
	{
		//先找到倒数第二个节点
		//定义俩个变量，一个在前，一个在后
		
		SLTNode* head = NULL;
		SLTNode* next = *pps;

        //先将后面的地址赋给前面的
		//然后后面的向前走一步
		//最后结束的时候
		//后面的就指向最后一个节点的地址
		//前面的就指向倒数第二个节点的地址
		while (next->next != NULL)
		{
			head = next;
			next = next->next;
		}
		//然后释放最后一个节点的空间
		free(next);
		//将倒数第二个节点指向的地址置空
		head->next = NULL;

	}
}

链表的查找

//查找
SLTNode* SListFind(SLTNode** ps, DataType x)
{
	SLTNode* cur = *ps;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

链表在pos节点前插入一个节点（与查找函数结合使用）

//在节点pos前面插入一个x
void SListInsert(SLTNode** pps, SLTNode* pos, DataType x)
{
	//头插
	if (pos == *pps)
	{
		SListPushFront(pps, x);
	}
	else
	{
		//扩容一个节点
		SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
		NewNode->data = x;
		NewNode->next = NULL;
        
        //寻找到pos节点前一个节点的地址
		SLTNode* cur = *pps;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
        //将插入的节点地址赋给找到的节点的next
		cur->next = NewNode;
        //将pos节点的地址赋给插入节点的next
		NewNode->next = pos;
	}
}

?使用时

//在1前面插入一个30
	SLTNode* pos = SListFind(&plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}

删除pos节点（与查找函数结合使用）

//删除pos位置的值
void SListErase(SLTNode** pps, SLTNode* pos)
{
	//头删
	 if (pos==*pps)
	{
		 SListPopFront(pps);
	}
	 else
	 {
        //找到pos节点前一个节点的地址
		 SLTNode* cur = *pps;
		 while (cur->next != pos)
		 {
			 cur = cur->next;
		 }
        //将pos节点的next赋给找到的节点的next
		 cur->next = pos->next;
        //释放pos节点的内存
		 free(pos);
	 }
}

使用时

//删除3
	SLTNode* pos = SListFind(&plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}

总体实现

void Test1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 0);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);

	//在1前面插入一个30
	SLTNode* pos = SListFind(&plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}
	SListPrint(plist);
	//删除3
	pos = SListFind(&plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	//删除30
	pos = SListFind(&plist, 30);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

int main()
{
	Test1();

	return 0;
}

运行结果

?