单链表（上）

07-07 1332阅读

单链表

在这之前我们已经学习了顺序表，为什么还会有链表的存在呢？这是因为顺序表有一些自身的缺陷，而链表恰好可以弥补这些缺陷。

我们先来看看顺序表的这些缺陷：

顺序表的问题以及思考

  1. 中间/头部的插入删除，会涉及到移动数据（已有数据整体向后移动），时间复杂度为O(N)。

  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的开销。

  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入5个数据，后面没有数据插入了，就浪费了95个数据空间。

    思考：如何解决上述问题呢？

而链表正好可以解决顺序表的中间/头部插入效率低下、增容降低运行效率、增容造成空间浪费这三个问题。

链表的概念

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

链表也是线性表的一种。

线性表指的是一类具有相同特性的数据结构的集合。线性表在逻辑结构上一定是线性的，在物理结构上不一定是线性的。

我们此前学的顺序表在物理结构和逻辑结构上都是线性的，因为其底层是数组，数组在物理空间上是连续的。

而链表在物理结构上不是线性的。

比如：

int a = 10;
float f = 0.1;

变量a和变量f的物理空间不一定是连续的。也有可能连续，取决于操作系统。

对于链表，我们常用的比喻是火车。火车有火车头和车厢。

我们先看车厢。车厢之间通过钩子连接在一起，而且可以将某一节车厢取下来或者挂上去。所以我们可以说车厢之间并不是连续的，这恰好符合链表的特性。

正如火车是由一节一节的车厢组成，链表是由一个一个的结点的组成：

单链表（上）

每个结点我们都可以独立地向操作系统去申请。当我们需要往链表中插入数据时再去申请新的结点，这就解决了之前顺序表的增容造成运行效率低下和空间浪费的问题。

动态开辟的空间都在堆上。但是顺序表和链表在堆上申请空间的方式是不同的，示意图：

单链表（上）

链表是由一个个结点组成的，那么结点是由什么组成的呢？

我们可以在上一张图里看出来结点有两个部分，一部分是存储的数据，第二部分是指针，存储着下一个结点的地址（而这个结点自身也是有地址的）。

所以我们要定义链表，就是要去定义链表的结点的结构，再将它们连接在一起，就变成了链表。

定义结点结构

首先还是要分成三个文件，一个头文件SList.h，一个源文件SList.c，这两个文件来定义链表的结构以及方法的声明和定义，还有一个用来测试的源文件test.c。

那么我们先在.h文件里定义结点的结构：

struct SListNode
{
    int data;//存储数据
    struct SListNode* next;//指向下一个结点的指针
};

List表示的是链表，S表示的是single，单链表，Node是结点。

这里定义的指针，我们是要指向下一个结点，所以这个指针的数据类型是struct SListNode*。

但是我们在顺序表中就已经知道，为了让顺序表或者链表能够存储多种类型的数据，我们在定义时最好将当前使用的数据类型重命名;

此外，为了方便后续定义结点，我们将结点的结构定义也重命名。

typedef int SLDatatype;
typedef struct SListNode
{
    int data;//存储数据
    struct SListNode* next;//指向下一个结点的指针
}SLTNode;

链表的各种方法

创建结点

因为链表是我们需要一个新结点时再去开辟，而不是像顺序表一样不够了去增容，所以我们这里使用的是malloc而不是calloc。

我们可以先来创建上4个结点：

(在SList.c文件中)

#include"SList.h"
void SListTest01()
{
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
}
int main()
{
	SListTest01;
	return 0;
}

但是此时4个结点之间还没有连接起来。

//连接
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
打印方法

我们再创建一个指针plist，让它指向第一个结点，作为链表头：

//调用链表的打印
SLTNode* plist = node1;
SLTPrint(plist);

单链表（上）

打印方法：

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

打印效果：

单链表（上）

最关键的就是让pcur指针往后走的这一句。

插入结点

上面我们已经尝试创建了4个结点，但是我们一般不是这样手动地去插入结点而是使用链表的插入方法。

顺序表有头插和尾插，链表也是一样。

尾插

我们可以先写出这样的代码：

//申请新节点的空间
SLTNode* SLTBuyNode(SLDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);//给个非零退出码
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLTPushBack(SLTNode* phead, SLDatatype x)
{
	SLTNode* newnode = SLTBuyNode(x);//直接调用封装好的申请结点的函数
	//要先找尾结点
	SLTNode* ptail = phead;
	while (ptail->next)//这样找得到的才是尾结点
	{
		ptail = ptail->next;
	}
	//此时ptail指向的就是尾结点
	ptail->next = newnode;
}

但是此时这个代码是有问题的。

我们知道，对空指针解引用，代码是会报错的。而当我们的链表为空链表想要插入结点时，ptail=phead都为NULL，而while括号中的->是解引用，这就造成了对空指针的解引用。

所以我们要处理空链表的情况：

对于空链表我们不需要找尾结点，而是要让phead不再指向NULL，而是指向新的结点。

//尾插
void SLTPushBack(SLTNode* phead, SLDatatype x)
{
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);//直接调用封装好的申请结点的函数
	if (phead == NULL)//说明为空链表
	{
		phead = newnode;
	}
	else
	{
		//要先找尾结点
		SLTNode* ptail = phead;
		while (ptail->next)//这样找得到的才是尾结点
		{
			ptail = ptail->next;
		}
		//此时ptail指向的就是尾结点
		ptail->next = newnode;
	}
}

这个代码此时看着已经非常正确了，但其实还是有问题。我们可以在test.c文件中去写测试代码，并且通过打印方法来观察：

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(plist, 1);
	SLTPrint(plist);
}
int main()
{
	SListTest02();
	return 0;
}

打印结果：

单链表（上）

我们可以看到，我们明明已经插入了一个1了，打印结果却仍是NULL，说明我们并没有成功插入结点。

我们可以再调试来看看具体是哪个环节出了问题：

单链表（上）

可以看到退出函数SLTPushBack的调用后，本来应该plist发生改变，但却只有phead得到了改变。本质上也就是形参发生了改变而实参没有变化，说明我们使用的是传值调用。

为什么我们明明确实传递的是地址，却仍然是传值调用呢？

注意看SLTPushBack(plist,1);这一句，我们传的是plist而不是&plist，而只有传&plist才叫做传址调用，只传plist尽管plist本身是地址，仍然是属于传值调用。

形参的改变想要影响实参，就需要传地址。我们想改变phead（形参）从而达到确实改变plist（实参）的效果，所以我们要传递的是&plist，那么接收就要用二级指针来接收。

我们可以区分一下这三个概念：

第一个结点				 *plist	
指向第一个结点的指针		   plist	
指向第一个结点的指针的地址	&plist

如果我们将原先的函数头改为：void SLTPushBack(SLTNode** pphead, SLDatatype x)，那么我们现在可以再看看这些对应的概念：

第一个结点				 *plist    	**pphead   对二级指针解引用两次得到结点变量
指向第一个结点的指针		   plist        *pphead	对二级指针解引用一次得到一级指针
指向第一个结点的指针的地址	&plist	      pphead	  二级指针

前面一列是实参的三种形式，后面一列则是形参的三种形式。

修正后的尾插函数定义：

//尾插
void SLTPushBack(SLTNode** pphead, SLDatatype x)
{
	//*pphead就是指向第一个结点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);//直接调用封装好的申请结点的函数
	if (*pphead == NULL)//说明为空链表
	{
		*pphead = newnode;
	}
	else
	{
		//要先找尾结点
		SLTNode* ptail = *pphead;
		while (ptail->next)//这样找得到的才是尾结点
		{
			ptail = ptail->next;
		}
		//此时ptail指向的就是尾结点
		ptail->next = newnode;
	}
}

运行效果：

单链表（上）

多插入几个结点：

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}
int main()
{
	SListTest02();
	return 0;
}

运行结果：

单链表（上）

单链表（上）

最后记得在函数体最前面加上断言：assert(pphead);。pphead不能为NULL否则就是造成对空指针解引用，而*pphead可以为空因为也就是plist为NULL，说明是个空链表。

回溯一下插入结点函数定义的思路：首先断言，然后分为非空链表和空链表两种情况处理。

头插

同样头插也可能链表为空，为空时插入的这个结点就是头结点。

正常情况下我们头插就是要让插入的这个新结点连上原来的第一个结点，然后让新的这个结点变为新的头结点。

//头插
void SLTPushFront(SLTNode** pphead, SLDatatype x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

而对于链表为空的情况，这个代码也行得通。

我们可以测试一下头插：

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//测试头插
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	SLTPushFront(&plist, 7);
	SLTPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPrint(plist);
}
int main()
{
	SListTest02();
	return 0;
}

运行效果：

单链表（上）

到此，本文结束。🐙

VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]