数据结构对链表的初步认识（一）

已经两天没有更新了，今天就写一篇数据结构的链表吧，巩固自己也传授知识，不知道各位是否感兴趣看看这一篇有关联表的文章。

链表的概念与结构

单向链表的实现

链表各个功能函数

首先我在一周前发布了一篇有关顺序表的文章，其中我们通过简单的介绍和代码实践，已经基本了解顺序表了，那么即使我们把顺序表弄成动态的顺序表，但其实我们运用顺序表还是有以下问题：

1. 如果空间不够，我们进行增容。但增容回付出一定的性能消耗，其次可能存在一定的空间浪费，因为我们每次增容都是2倍的增容我们可能并用不完这两倍的空间。

2.头部和中部左右两部分的插入效率太低，因为我饿们需要将数据一个一个的往后移，所以效率不高。

那么我们要怎么解决这个问题呢？

1.空间上，按照需求给空间，比如我要101个空间就给我101个空间而不是两倍。

2.不要求物理空间上的连续，这样在头部和中部时我们就不需要挪动数据，那么这种解决方法就是用链表实现。

OK，我们下面就展开展开链表的知识了。

链表的概念与结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

其逻辑结构（这里说的逻辑结构是我们想象出来便于理解的结构）：

上方逻辑结构可以是n个数据和指针，这样我们就完成了，非物理空间上的连续的表。

链表有许多结构我们今天就讲一种简单的结构——————单向链表。

单向链表的实现

我们继续创建一个结构体，里面是数据和指针。

typedef int SLTDataType;
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
};
typedef struct SListNode SLTNode;

代码中将结构体命名为SLTNode是为了方便写代码。

typedef int SLTDataType 为了易于改变数据类型时，只需将int 改成其他类型即可改变，整个链表的数据类型。

struct SListNode* next 这里面储存一个结构体指针用来链接下一个结构体。

既然结构体已经完成了，那么我们现在就简单用函数链接一个链表了。

链表各个功能函数

链表必须要找一个头，即链表的首个结构体，那么我们就将这个头命名为 plist，传给其他函数完成其功能。

现在我们就实现第一个函数，开辟空间的函数。

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

这个函数主要用于链表的增加，在各个部位进行插入数据都需要这个函数开辟空间。

头插函数

如何头插呢？这是我们需要思考的。

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

链表头插即开辟一块新的空间，将这块空间作为头（*pphead = newnode;），而这块空间的next则储存着原来的头结构体（newnode->next = *pphead;）。

注意：这里要改变pist本身则我们就要使用指针进行传址，改变其地址。

头删函数

这个函数也相较简单，我们也是将第一个节点删除，然后将第二个节点设为头节点，而第二个节点就是原来头节点里储存的 next了，我们必须先储存第二节点的地址然后再进行销毁。

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);

	*pphead = next;
}

尾插函数

尾插函数，我们只需先创建一个新空间newnode，然后将原来的尾的结构体中的 next 改为现在newnode 即可。但需要注意当链表还一个节点都没有的时候，原来是没有尾的，这又是一种情况，我们只需将*pphead变为newnode，即可。由此得出下面代码。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}

尾删函数

尾删时我们需要考虑三种情况

1、空
2、一个节点
3、一个以上的节点

空的时候我们不需要任何操作，直接return即可。

一个节点时我们需要用free函数进行销毁空间，然后将该*phead 赋一个NULL。

一个节点i以上我们要考虑的又有些不同，因为当我们将尾节点删除时我们还需将倒数第二个节点赋为NULL不然程序可能会崩掉。我们知道找最后一个尾节点很容易但是我们要找倒数第二个节点很难，这里我们就需要借助第三指针变量，一前一慢进行往后遍历，最后即可得到这两个节点了。

void SListPopBack(SLTNode** pphead)
{
	// 1、空
	// 2、一个节点
	// 3、一个以上的节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		prev->next = NULL;
	}
}

打印函数

以NULL为链表结束标志，即打印结束。

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

下面给大家展示一下这些函数：

void Test()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 8);
	SListPushFront(&plist, 88);
	SListPushBack(&plist, 29);
	// 88 8 29
	SListPrint(plist);
	SListPopBack(&plist);
	SListPushFront(&plist, 5);
	SListPushBack(&plist, 89);
	// 5 88 8 89
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	//88 8 89


}




int main()
{
	Test();
	return 0;
}