SinglyLinkedList单链表的实现

链表基本概念及讨论

链表允许数据不连续存储，并将每个数据链接起来，它弥补了数组表的一些局限，当需要增加一个数据时我们只需要申请存储它所需要的空间，因此不会导致空间浪费问题，并且数组表在插入数据时需要将表的部分或全部移动，花费线性时间，而链表只需要将新的数据与表链接起来即可，一般来说是在头上链接只花费常数时间，当然也有在尾上链接，此时就需要遍历链表中所有元素，花费线性时间。

单链表的实现

基本思想

一个变量用于存储数据，另外一个指针用于链接下一个表元

以下是结构声明与函数 *** 作的声明

为了减少指针的*号，我们可以使用typedef关键字定义类型

#include
#include
#include
typedef int DataType;
typedef struct SListNode SListNode;
typedef struct SListNode* PtrToNode;
typedef PtrToNode SList;
typedef PtrToNode Position;
struct SListNode
{
	DataType data;
	PtrToNode next;
};

PtrToNode BuyListNode(DataType x);
void SListPushBack(SList* list,DataType x);
void SListPushFront(SList* list, DataType x);
void SListPrint(SList list);
void SListPopFront(SList* list);
void SListPopBack(SList* list);
void SListInsertAfter(Position pos, DataType x);
void SListEraseAfter(Position pos);
Position SListFind(SList list, DataType x);
void SListDestroy(SList* list);
int IsEmpty(SList list);
int IsLast(Position pos);

这里我们可以发现头插、头删、尾插、尾删的函数中表的参数为二级指针，此处是个很值得讨论的问题，对于链表我们知道它可以有表头也可以无表头，表头即是在链表最前面的结点，它不用于存储数据，能避免一些程序设计过程中的问题。我们这里实现的是无表头的链表，对于无表头的链表来说，是有可能需要改变链表最开始的起始端的地址的。我们可以创建一个指针用于指示链表的地址，指针的改变就意味着链表地址（或首地址）的改变（因为拿到首地址就相当于拿到了整个链表），比如一开始创建了一个结点地址为0x12345678，随后删除之后链表为空，也就没有地址，又创建一个结点的地址可能为0x87654321，这就说明无表头的链表的地址是可能改变的，所以我们需要二级指针以改变指示链表地址的那个指针的值。再来看对于有表头链表，无论链表是否为空，表头结点一直存在，那它的地址也不会改变，而链表又可以通过表头去访问，可以认为链表的地址是不会改变的，所以对于有表头的链表来说是不需要传递二级指针的。

尾插与尾删

void SListPushBack(SList* list, DataType x)
{
	if (IsEmpty(*list))
		*list = BuyListNode(x);
	else
	{
		Position cur = *list;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = BuyListNode(x);
	}
}
void SListPopBack(SList* list)
{
	assert(list);
	if (!IsEmpty(*list))
	{
		if ((*list)->next == NULL)
		{
			free(*list);
			*list = NULL;
		}
		else
		{
			Position prev = NULL;
			Position cur = *list;
			while (cur->next != NULL)
			{
				prev = cur;
				cur = cur->next;
			}
			free(cur);
			prev->next = NULL;
		}
	}
}

头插与头删

void SListPushFront(SList* list, DataType x)
{
	if (IsEmpty(*list))
		*list = BuyListNode(x);
	else
	{
		PtrToNode newNode = BuyListNode(x);
		newNode->next = *list;
		*list = newNode;
	}
}
void SListPopFront(SList* list)
{
	assert(list);
	if (!IsEmpty(*list))
	{
		Position head = *list;
		*list = (*list)->next;
		free(head);
	}
}

判断空与判断是否最后一个表元

int IsEmpty(SList list)
{
	return list == NULL;
}
int IsLast(Position pos)
{
	return pos->next == NULL;
}

打印与创建结点

PtrToNode BuyListNode(DataType x)
{
	PtrToNode newNode = (PtrToNode)malloc(sizeof(SListNode));
	if (newNode == NULL)
		exit(-1);

	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
void SListPrint(SList list)
{
	Position cur = list;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

查找与销毁

Position SListFind(SList list, DataType x)
{
	Position cur = list;
	while (cur != NULL)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}
	return NULL;
}
void SListDestroy(SList* list)
{
	assert(list);
	if (!IsEmpty(*list))
	{
		Position cur = *list;
		PtrToNode tmp;
		while (cur != NULL)
		{
			tmp = cur->next;
			free(cur);
			cur = tmp;
		}
		*list = NULL;
	}
}

向后插入与向后删除

void SListEraseAfter(Position pos)
{
	assert(pos);
	if (!IsLast(pos))
	{
		Position next = pos->next;
		pos->next = next->next;
		free(next);
	}
}
void SListInsertAfter(Position pos, DataType x)
{
	assert(pos);
	PtrToNode newNode = BuyListNode(x);
	Position next = pos->next;
	newNode->next = next;
	pos->next = newNode;
}