单链表（一）

通过对顺序表的学习，我们可以发现顺序表有以下几点缺陷： 1.空间不够时需要扩容，扩容尤其是用realloc进行异地扩容时，是有一定代价的，其次还可能存在一定空间浪费。 2.头部或者中间插入删除，需要挪动数据，效率低下。 那我们可以对其所具有的缺陷进行优化：可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。==但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表==。

一、单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 </br> 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，物理结构中指针域存储的是下一个结点的地址；而且链式结构的结点一般都是从堆上申请出来的；从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。链表存储数据的区域可分为数据域和指针域： </br>

用代码表示链表中的数据域和指针域如下：

typedef int STLDataType;//typedef定义数据类型
typedef struct SListNode
{
	SLTDataType data;//结点的数据
    //STLNode* next;//不能这样定义，typedef定义在这里还没起作用，这里不能用
	struct SListNode* next;//next指针指向下一个结点
}STLNode;

思考：为什么在申请的时候需要申请堆上的空间？因为堆上申请的空间存储数据的时候不会因为函数销毁而销毁，堆上的空间需要的时候就申请，不需要的时候就释放；函数栈帧上开辟的空间存储的数据会因为函数栈帧的销毁而释放，后面在进行尾插和头插时候新的结点不能链接到表上。

二、单链表的基本操作

我们在创建链表结点的时候不能使用下面这种方式：

void TestSList
{
    SLTNode node;
}

因为node是在TestSList函数内创建的，属于局部变量，局部变量作用域仅限于函数内，出函数作用域就失效了，函数结束的时候会被销毁。

如当我们往链表中插入结点时使用SLTNode node往链表中插入结点，结点存在栈帧中，函数结束局部变量就销毁了。

1.创建单个结点

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//申请空间
	if (newnode == NULL)//判断是否为空
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;//赋值
	newnode->next = NULL;//next指针指向空
	return newnode;//返回创建的结点
}

2.创建具有n个结点的链表

SLTNode* CreateSList(int n) 
{
	int i = 0;
	SLTNode* ptail = NULL,*phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i); //创建新节点
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode; //链接
			ptail = newnode;
		}
	}
	return phead; //返回头节点
}
//没有返回值，形参使用的是二级指针改变头指针指向的地址。
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}

上述代码中提供了两种实现方式，没有注释的是返回头指针的，注释内容是没有返回值，形参使用的是二级指针改变头指针指向的地址。

【文章转自：美国站群服务器 http://www.558idc.com/mgzq.html处的文章,转载请说明出处】