【数据结构】第二章——线性表(5)

导言

大家好，很高兴又和大家见面啦！！！
在上个章节中，咱们介绍了单链表的基本概念，以及如果初始化带头结点的单链表与不带头结点的单链表，相信大家现在对这一块内容都是比较熟悉的了。下面我们先来一起回顾一下单链表的初始化，为了方便理解，这里我们还是通过数据域为整型且带有头结点的单链表来进行介绍；

一、单链表的初始化

在对单链表进行初始化之前，我们还是需要按照以下步骤一步一步执行：

1. 定义单链表类型
2. 定义指向单链表的头指针
3. 初始化单链表

将这些步骤转化成C语言，如下所示：

//定义单链表类型
typedef struct LNode
{
	int data;//数据域
	struct LNode* next;//指针域
}LNode, * LinkList;
//单链表初始化
bool InitList(LinkList* L)
{
	//创建头结点
	*L = (LNode*)calloc(1, sizeof(LNode));
	//判断是否成功创建头结点
	if (!(*L))
		return false;
	(*L)->next = NULL;//初始化头结点
	return true;
}
int main()
{
	LinkList L;//定义指向单链表的头指针
	InitList(&L);//初始化单链表
	return 0;
}

现在咱们就成功的创建了单链表的头指针与头结点，并且为了防止头结点的指针域为野指针，我们这里对其初始化成了空指针。有了头指针和头结点后，我们现在就可以创建一个单链表了。

二、单链表的创建

我们在创建单链表时有两种创建方式——头插法创建单链表与尾插法创建单链表。下面我们通过图解来介绍一下这两种创建方式：

为了方便大家理解，这里我们将链表的第一个元素称为表头元素，链表的最后一个元素我们称为表尾元素，对应的头插法与尾插法我们就可以理解为新元素插入后的位置：

• 在创建链表时，将新元素插入为表头元素，这种插入方法我们就称为头插法
• 在创建链表时，将新元素插入为表尾元素，这种插入方法我们就称为尾插法

从上图中，我们还可以看到，对于头插法而言，元素插入的顺序是逆序插入的，也就是头插法相当于对元素进行了逆置。

我们在创建链表前，链表都是一个空表，此时的头结点的指针域指向的是NULL，那我们应该如何通过C语言来实现这两种链表的创建方式呢？下面我们就来一一介绍一下；

2.1 采用头插法建立单链表

在上图中我们也有对头插法的步骤进行说明，我们在插入新的表头元素时，首先应该让新元素的指针域指向头结点的指针域指向的对象：

• 对于空表来说，此时头指针的指针域指向的是NULL；
• 对于已有元素的链表来说，头指针的指针域指向的是链表的表头元素；

对于单链表而言，它并不是一个能够进行随机存取的存储结构，所以我们要想得到链表中的某个元素，我们都是只能从头指针开始往后遍历直到找到该元素，因此，我们要想让新元素的指针域指向表头元素，我们只能通过头结点的指针域才能找到链表的表头元素，转化为C语言则是：

New_next->Head_next;//将新结点的指针域指向头结点的指针域所指向的元素
Head_next->New;//头结点的指针域指向新的元素

因此我们就可以得到头插法的基本格式：

//头插法的基本格式
LinkList List_HeadInsert(LinkList* L)//头插法建立单链表
{
	LNode* s;//指向新结点的指针
	ElemType x;//存放数据域信息的变量
	……;//获取数据信息
	while (x != EOF)//通过EOF给循环设置一个结束条件，也可以设置为其它内容
	{
		s = (LNode*)calloc(1, sizeof(LNode));//创建新的结点
		s->data = x;//将数据元素放入新结点的数据域中
		s->next = (*L)->next;//将头结点的指针域中存放的信息放入新结点的指针域中
		(*L)->next = s;//将新结点的地址存放进头结点的指针域中
		……;//获取新的数据元素
	}
	return(*L);//将创建好的单链表返回给函数
}

从这个基本格式中我们可以看到，要将一个新的结点插入链表中，那这个新结点的数据域和指针域的内容都是不能忽视的，所以大家一定不要忘记了将新结点的数据域中存放对应的数据元素。下面我们通过整型数据元素来尝试着使用头插法创建一个链表，如下所示：

可以看到，此时我们就很好的通过头插法创建了一个单链表，并且单链表的各个元素是逆置的，对应的代码如下所示：

//使用头插法创建单链表
LinkList List_HeadInsert(LinkList* L)//头插法建立单链表
{
	LNode* s;//指向新结点的指针
	int x;//存放数据域信息的变量
	scanf("%d", &x);//通过scanf来获取新结点数据域的元素，也可以通过其它方式
	while (x != 9999)//通过9999给循环设置一个结束条件，也可以设置为其它内容
	{
		s = (LNode*)calloc(1, sizeof(LNode));//创建新的结点
		s->data = x;//将数据元素放入新结点的数据域中
		s->next = (*L)->next;//将头结点的指针域中存放的信息放入新结点的指针域中
		(*L)->next = s;//将新结点的地址存放进头结点的指针域中
		scanf("%d", &x);//获取新的数据元素
	}
	return(*L);//将创建好的单链表返回给函数
}
//打印单链表
void Print_LinkList(LinkList L)
{
	LNode* s = L;//指向结点的指针
	LNode* r = L;//指向结点的指针
	printf("打印单链表的各个元素:>");
	for (int i = 0; r->next; i++)
	{
		s = r->next;//将r存放的下一个结点的信息赋值给指针s
		r = s;//指针r通过指针s找到下一个结点
		printf("%d ", r->data);
	}
	printf("\n");
}
int main(){
	LinkList L;//定义指向单链表的头指针
	if(InitList(&L));//初始化单链表
	{
		L = List_HeadInsert(&L);//创建单链表
		Print_LinkList(L);//打印单链表
	}
	return 0;
}

2.2 采用尾插法创建单链表

与头插法不同的是，尾插法是从空表开始依次将元素插入到单链表的表尾：

• 当单链表为空表时，插入的第一个元素既是表头元素也是表尾元素；
• 当单链表不为空表时，新的元素将会插入到表尾；

尾插法的实现与头插法相似，只不过此时的表尾指向的对象为NULL，我们每次要插入一个新的元素，就需要找到链表的表尾元素，因此这里我们需要借助表尾指针来完成，如下所示：

当链表为空表时，表尾指针指向的是头结点，我们对其进行尾插法的步骤则是：

1. 将新结点的指针域指向表尾指针的指针域指向的对象；
2. 将表尾指针的指针域指向新结点；
3. 新结点赋值给表尾指针；

从这个步骤中我们可以看到，其实尾插法与头插法的思路是一样的，只不过多了一个赋值操作，前面两步是在完成插入的步骤，最后一步是在完成表尾指针移动的过程，通过C语言表示出来则是：

New_next->Tail_next;//将新结点的指针域指向表尾结点的指针域所指向的元素
Tail_next->New;//表尾结点的指针域指向新的元素
Tail = New;//表尾指针指向新结点

因此我们就可以得到尾插法的基本格式：

//尾插法的基本格式
LinkList List_TailInsert(LinkList* L)
{
	LNode* s;//指向新结点的指针
	LNode* r;//指向表尾结点的指针
	ElemType x;//存放数据域信息的变量
	……;//获取数据信息
	while (x != EOF)//给循环设置一个结束条件，可以自行设置
	{
		s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
		s->data = x;//将数据信息存放入新结点的数据域中
		s->next = r->next;//将表尾结点的指针域中存放的信息放入新结点的指针域中
		r->next = s;//将新结点的地址存放入表尾结点的指针域中
		r = s;//将表尾指针指向新结点，新结点成为新的表尾结点
		……;//获取新的数据元素
	}
	return(*L);
}

可以看到，尾插法相比于头插法其实就多了一个步骤，表尾指针的移动，之所以头插法不需要，是因为头结点是不会改变的，因此，尾插法从这种插入方式上其实与头插法是一样的，下面我们就通过尾插法来实现一下创建链表：

可以看到使用尾插法创建的单链表的元素是顺序排列的。因此当我们需要将元素逆置排列的话，我们可以通过头插法来实现，当我们需要将元素顺序排列的话，我们可以通过尾插法来实现。

2.3 单链表创建的时间复杂度

可以看到我们在创建单链表时，不管是头插法还是尾插法，循环中代码执行的次数与节点的个数是一致的，因此单链表创建的时间复杂度为O(n)。

对于不带头结点的单链表在创建时，对于首元素的处理逻辑与带头结点的单链表创建时首元素的处理逻辑是稍有差异的，有兴趣的朋友可以下去尝试着编写一下不带头结点的单链表通过头插法与尾插法的方式进行创建。

结语

咱们今天的内容到这里就结束了，希望大家在阅读完今天的内容后，能够掌握单链表创建的这两种方式。在下一篇内容中，我们会继续介绍单链表的其它基本操作，大家记得关注哦！

最后感谢各位的翻阅，咱们下一篇再见！！！