单链表的实现

本文实现语言：c语言

上篇文章回顾

上几篇博客我们已经实现静态顺序表和动态顺序表的基本功能，在顺序表中存取表元素非常简单，但是插入和删除需要移动大量的数据（时间复杂度O(n) ）非常麻烦；因此今天我们来实现插入和删除都非常方便的链表。

其实链表分为好几类，如下；其中以不带头节点，不循环的单链表和带头节点，循环的双链表最为重要。

本文主要实现不带头节点，不循环的单链表的增，删，插，改等功能。

在实现代码前，有一个重要的问题需要讨论，就是传参问题，什么情况下我们需要传二级指针？

假设形参是普通变量，在传递的时候，如果我们打算对普通变量进行修改，那么我们就需要传递变量的地址；如果我们不打算修改普通变量（比如只是查看一下内容），那么我们的形参传递数值就可以（此时形参是实参的一份临时copy）。

同样的，如果我们的形参是指针变量，如果我们打算修改这个指针变量，那么我们传递的时候就需要二级指针；否则传递一级指针就OK。

这个理论放到链表实现里就是说：我们在设计链表的时候会设计一个头指针pNode，这个头指针pNode会指向头结点（或者指向第一个有效结点），所以头指针里面存的就是头结点的地址。如果我们要修改头结点里面所保存的地址（比如初始化链表时，让头指针指向NULL；再比如头插的时候，头指针保存的地址会发生变化，变成新插入节点的地址）时，在设计函数的时候就需要传递二级指针；如果我们只是查看头指针指向的内容，这样并不会改变头指针本身保存的地址，此时传递一级指针就可以。

所以，一般销毁，初始化，头插等需要用到二级指针；查找，遍历等传递一级指针就OK。

代码：

#define _CRT_SECURE_NO_WARNINGS 1

//-----------------------SList.h---------------
// #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int DataType;

typedef struct SListNode
{
	struct SListNode* next;  //指针域
	DataType data;  //数据域

}SListNode, *pSListNode, **ppSListNode;



pSListNode CreateSListNode(DataType x);//创建一个节点
void SListInit(ppSListNode pphead);//初始化
void SListPrint(pSListNode phead);//打印链表
void SListPushFront(ppSListNode pphead, DataType x);//头插
void SListPushBack(ppSListNode pphead, DataType x);//尾插
void SListInsert(ppSListNode pphead, pSListNode pos, DataType x);//插入
void SListInsert(ppSListNode pphead, size_t pos, DataType x);//将x插入第pos个节点之后
void SListPopFront(ppSListNode pphead);//头删
void SListPopBack(ppSListNode pphead);//尾删
void SListErase(ppSListNode pphead, pSListNode pos);//给定节点删除
void SListRemove(ppSListNode pphead, DataType x);//按值删除，删除遇到的第一个点
void SListRemoveALL(ppSListNode pphead, DataType x);//按值删除，删除所有的
void SListDestory(ppSListNode pphead);//销毁
pSListNode SListFind(pSListNode phead, DataType data);//按值查找，返回第一个找到的结点指针，如果没有找到，返回NULL
int SListEmpty(pSListNode phead);//判断是否为空
int SListSize(pSListNode phead);//算节点数

//-----------------------SList.c---------------

//创建一个节点
pSListNode CreateSListNode(DataType x)
{
	pSListNode node = (pSListNode)malloc(sizeof(SListNode));
	assert(node);
	node->data = x;
	node->next = NULL;
	return node;
}

//初始化：这里使用了二级指针，也可以使用一级指针的引用型参数。
void SListInit(ppSListNode pphead)
{
	assert(pphead);
	*pphead = NULL;
}

//打印链表
void SListPrint(pSListNode phead)
{
	pSListNode cur = phead;
	for(cur = phead; cur != NULL; cur = cur->next)
	{
		printf("%2d->", cur->data);
	}
	printf("NULL\n");
	
}

//头插
void SListPushFront(ppSListNode pphead, DataType x)
{
	assert(pphead);
	//先检查是否为空
	if (NULL == *pphead)
	{
		//链表为空时，创建一个头结点，该节点的next为NULL，指针*pphead指向它。
		*pphead = CreateSListNode(x);		
	}
	else 
	{
		pSListNode pNode = CreateSListNode(x);
		pNode->next = *pphead;
		*pphead = pNode;
	}
	
}

//尾插
void SListPushBack(ppSListNode pphead, DataType x)
{
	assert(pphead);
	if (NULL == *pphead)//先检查是否为空
	{
		pSListNode pNode = CreateSListNode(x);
		return;
	}
	else
	{
		pSListNode cur = *pphead;
		while (NULL != cur->next)
		{
			cur = cur->next;
		}
		cur->next = CreateSListNode(x);
				
	}
}

//给定节点插入：1.先检查pos的合法性 2.创建一个以x为值的新节点newNode（一级指针） 
void SListInsert(ppSListNode pphead, pSListNode pos, DataType x)
{

	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
		return;
	}
	pSListNode newNode = CreateSListNode(x);

#if 0  //如果常量为真，执行程序段1，否则执行程序段2

	//3.在单链表上找到这个位置的前一个节点tmp 4.newNOde的next指向tmp的next 5. tmp的next指向newNode。   此功能主要运算时间耗费在查找上，时间复杂度为O(n)
	pSListNode tmp = *pphead;
	while (tmp->next != pos)
	{
		tmp = tmp->next;
	}
	newNode->next = tmp->next;
	tmp->next = newNode;
#else
	newNode->data = pos->data;
	pos->data = x;
	newNode->next = pos->next;
	pos->next = newNode;

#endif
}

//将x插入第pos个节点之后
void SListInsert(ppSListNode pphead, size_t pos, DataType x)
{
	assert(pphead);
	int size = SListSize(*pphead);
	assert(pos >= 0 && pos <= size);
	pSListNode node = CreateSListNode(x);//创建一个节点
	pSListNode tmp = *pphead;
	if (0 == pos) {//头插
		SListPushFront(pphead, x);
	}
	else 
	{
		while (pos-1)//有疑问
		{
			tmp = tmp->next;
			pos--;
		}
		node->next = tmp->next;
		tmp->next = node;
	}
}

//头删
void SListPopFront(ppSListNode pphead)
{
	assert(pphead);
	assert(*pphead);
	pSListNode tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
}

//尾删
void SListPopBack(ppSListNode pphead)
{
	assert(pphead);
	assert(*pphead);
	//如果只有一个头节点
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	pSListNode first = *pphead;
	while (NULL != first->next->next)
	{
		first = first->next;

	}
	free(first->next);
	first->next = NULL;

}

//给定节点删除：1.先检查pos的合法性  
void SListErase(ppSListNode pphead, pSListNode pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(pphead);
		return;
	}
#if 0

	//2.在单链表上找到删除位置的前一个节点cur 3.cur的next指向删除pos的next    此功能主要运算时间耗费在查找上，时间复杂度为O(n)
	pSListNode cur = *pphead;
	while (pos != cur->next)
	{
		cur = cur->next;
	}
	cur->next = pos->next;
	free(pos);
	pos = NULL;
#else
	if (pos != NULL && NULL != pos->next)
	{
		pSListNode node = pos->next;
		pos->data = pos->next->data;
		pos->next = node->next;
		free(node);
		node = NULL;
	}
	else if (NULL == pos->next)
	{
		//即要删除的是最后一个元素
		SListPopBack(pphead);
	}
#endif
}

//按值删除，删除遇到的第一个点
void SListRemove(ppSListNode pphead, DataType x)
{
	assert(pphead);
	assert(*pphead);
	pSListNode pos = SListFind(*pphead, x);
	if (NULL == pos)
	{
		printf("没有这个数值\n");
	}
	else
	{
		SListErase(pphead, pos);
	}
	
}

//按值删除，删除所有的
void SListRemoveALL(ppSListNode pphead, DataType x)
{
	assert(pphead);
	assert(*pphead);

	pSListNode pos = NULL;
	while (NULL != (pos = SListFind(*pphead, x)))
	{
		SListErase(pphead, pos);
	}

}

//销毁
void SListDestory(ppSListNode pphead)
{
	assert(pphead);
	pSListNode node = *pphead;
	while (node)
	{
		pSListNode newNode = node;
		node = node->next;
		free(newNode);
		newNode = NULL;
	}
	*pphead = NULL;
}

//按值查找，返回第一个找到的结点指针，如果没有找到，返回NULL
pSListNode SListFind(pSListNode phead, DataType data)
{
	assert(phead);
	pSListNode node = phead;
	while (node)
	{
		if (data == node->data)
		{
			return node;
		}
		node = node->next;
	}
	return NULL;

}

//判断是否为空,为空返回0
int SListEmpty(pSListNode phead)
{
	return phead == NULL ? 0 : 1;
}

//算节点数
int SListSize(pSListNode phead)
{
	assert(phead);	
	size_t size = 0;
	pSListNode node = phead;
	while (node)
	{
		node = node->next;
		size++;
	}
	return size;
}

//逆序打印(递归)
void SListReverse(pSListNode phead)
{
	if (NULL == phead)
	{
		return;
	}
	SListReverse(phead->next);
	printf("%2d->", phead->data);
}

//-----------------test.c----------------
void Test()
{
	pSListNode list = NULL;
	SListInit(&list);
	
	SListPushFront(&list, 1);//头插
	SListPushFront(&list, 2);//头插
	SListPushFront(&list, 3);//头插
	SListPushFront(&list, 4);//头插
	SListPrint(list);
	
	SListPushBack(&list, 101);//尾插
	SListPushBack(&list, 102);//尾插
	SListPushBack(&list, 103);//尾插
	SListPushBack(&list, 104);//尾插
	SListPrint(list);

	SListInsert(&list, list->next, 100);//任意位置插
	SListPrint(list);

	SListErase(&list, list->next);//任意位置删
	SListPrint(list);

	int ret = SListSize(list);//算节点数
	printf("节点数%d\n", ret);
	int cur = SListEmpty(list);//判断是否为空
	if (cur == 0)
		printf("链表为空\n");
	else
		printf("链表不为空\n");
	SListInsert(&list, list->next->next, 1);//任意位置插
	SListInsert(&list, list->next->next->next->next, 1);//任意位置插
	SListPushBack(&list, 1);//尾插
	SListPushFront(&list, 1);//头插
	SListPrint(list);
	SListRemove(&list, 1);//删除第一个x
	SListPrint(list);

	SListRemoveALL(&list, 1);//删除所有x
	SListPrint(list);

	SListDestory(&list);//销毁
	SListPrint(list);

	SListPushFront(&list, 1);//头插
	SListPushFront(&list, 2);//头插
	SListPushFront(&list, 3);//头插
	SListPushFront(&list, 4);//头插
	SListPrint(list);

	SListInsert(&list, 1, 100);
	SListPrint(list);

	SListReverse(list);//逆序打印
	printf("NULL\n");
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果：