[数据结构与算法]链表的实现(C语言)

目录

链表是什么：

节点与结构体：

节点与链：

头结点与头指针：

多节点的链表：

链表是什么：

????????链表是链式存储结构的典例，相邻两个节点间是靠链相连的。与链式存储结构相对应的是顺序存储结构，我们所熟知的数组便是顺序存储结构。顺序存储结构的一个明显特点便是需要提前在内存中分配好一定大小的空间，而空间是否充足在数据完全被导入前是不知道的，最终的结果可能是未充分利用已分配的内存空间而造成浪费或者是分配的内存空间不足而导致数据的溢出。这都是我们不愿看到的，于是链式存储结构出现了。

????????在出现新的一个节点时（这个节点内的部分分为数据域和指针域，数据域用来存放各种实际的数据，指针域用来存放上一个或下一个节点的地址），我们只需要将这个新的节点纳入到这条数据链当中来。而具体用的方法，便是让每个节点有上一个或下一个节点的地址，而这个就是开头说到的链。

????????可以看到，链表的实现依赖于节点的建立，而节点的建立又依赖于结构体的应用。

节点与结构体：

? ? ? ? 前面讲到，链表中每个节点由数据域和指针域组成，这也就是说，对应的结构体包含了某些数据类型的变量以及与该结构体同类型的指针变量。

举一个小例子：?

struct stu
{
int iScore;
char cName[10];
struct stu* pNext;
};

????????这个结构体包含了一个整型变量、一串字符以及一个与该结构体同类型的指针变量。然后我们继续在 main() 函数中定义两个变量 stu1 以及 stu2 ，为它们赋值：

int main()
{
	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName,"log");
	stu1.pNext = NULL;
	printf("%d %s", stu1.iScore, stu1.cName);
    
    struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;
	printf("%d %s", stu2.iScore, stu2.cName);
	
    return 0;
}

我们运行一下，得到结果：

节点与链：

如何让这两个变量建立链接呢？我们可以让 stu1 这个结点的指针域储存 stu2 这个结点的首地址，即添加语句

stu1.pNext = &stu2;

使得整个程序变为：

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName,"log");
	stu1.pNext = NULL;
	printf("%d %s\n", stu1.iScore, stu1.cName);
	
	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;
	
	stu1.pNext = &stu2;
	printf("%d %s", stu1.pNext->iScore, stu1.pNext->cName);
	return 0;
}

????????而我们这个程序原本的目的就是将 stu1 和 stu2 两个结点数据域内储存的值打印出来，那在上述操作的基础上已经建立起这两个结点间的链，我们是不是可以直接定义一个 struct stu 类型的辅助变量并通过它和首元结点 stu1 就能够访问 节点 stu2 呢？例如：

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;

	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName, "log");
	stu1.pNext = NULL;

	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;

	stu1.pNext = &stu2;
	stu_temp.pNext = &stu1;
	while (stu_temp.pNext != NULL)
	{
		printf("%d %s\n", stu_temp.pNext->iScore, stu_temp.pNext->cName);
		stu_temp.pNext = stu_temp.pNext->pNext;
	}
	return 0;
}

????????在这段代码中，我们定义了一个临时的变量 stu_temp ，并将 stu1 的地址添加到了 stu_temp 的指针域，通过一个 while循环 ，我们可以按序打印出这条链上所有非空结点的数据。

????????另外，我们称 stu1 为首元结点，当然也可以叫队头结点或是其它的；而 stu_temp 被称为头结点，需要注意的是，头结点的数据域是空域，而它的指针域储存着首元结点的地址。

图示的逻辑关系为：?

其中，头结点 stu_temp 的数据域为空，用希腊字母?∧ 表示。

头结点与头指针：

????????与头结点相对应的概念为头指针，头结点是可有可无的，若设置头结点，那么头指针的值为头结点的地址；若不设置头结点，那么头指针的值为队头结点的地址。逻辑关系是这样的：

?????????一般说来，头指针有标识作用，可以用头指针表示链表的名字。这么说的原因是在编写程序时对两个或两个以上的链表进行数据的读入、修改或是连接两个装有同种类型元素的链表等操作时可以很简单地区分出不同的链表。并且，头指针是链表的必要元素，无论链表是否为空，头指针都不为空。

? ? ? ? 头结点则是为了方便起见，放在队头结点之前，其数据域一般无意义。说到头结点带来的方便，主要体现在有了头结点后，如果我们要在队头结点前插入一个新的结点或是删除队头结点使其下一个结点成为新的队头结点时都是很有帮助的。

????????上面的代码添加头指针后变为：

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;
	struct stu* pHead=NULL;

	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName, "log");
	stu1.pNext = NULL;

	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;

	stu1.pNext = &stu2;
	stu_temp.pNext = &stu1;
	stu_temp.iScore = -1;
	pHead = &stu_temp;
	while (pHead != NULL)
	{
		if (pHead->iScore == -1)
		{
			pHead = pHead->pNext;
			continue;
		}
		printf("%d %s\n", pHead->iScore, pHead->cName);
		pHead = pHead->pNext;
	}
	return 0;
}

? ? ? ? pHead 是我们定义的头指针，在为 stu1 和 stu2 两个结点赋初值后，我们将 stu2 的地址存放到 stu1 的指针域，将 stu1 的地址存放到 stu_temp 的指针域，并将 stu_temp 的数据域中的 iScore 的值设置为 -1 用以表明其为头结点。

多节点的链表：

? ? ? ? ?在上文中，我们看到在连接较少的结点时，直接采取先定义各个结点，然后将它们连接起来的方式是可行的。可是，当我们要连接起来的节点的数量不在一个具体的范围时，需要采取的工作量是不确定的，也许你会说可以采取分配一块固定大小的内存来存储这些数据，这就回到了我们在文章开头提到的顺序存储结构，违背了建造链式存储结构的目标。

? ? ? ? 那么我们完全可以只定义一个代表该节点的变量，然后通过给这个节点不断赋新值，然后将这个节点纳入到已有的链当中来。按照前面的思路，是建立起已有的 n 个结点之间的链接，而新的思路则是建立一个新结点就将它纳入到前 n 个结点构成的链当中来。

? ? ? ? ?这也就是说，我们需要重复使用同一个变量来开辟新的结点，即以一种不定义新的变量的方式来不断开辟空间的。这话有点拗口，我们以上面的代码为例，我们开辟 stu1 和 stu2 这两个结点是通过定义这两个变量的方式，如果我们要定义 stu3 、stu4 ······ stu n 这一系列结点，就要有 n 条定义变量的语句，显得重复啰嗦。而定义变量的目的就是为这 n 个结点开辟内存空间，如果有另外一种方式可以使我们不用这么啰嗦的方式就为各个结点开辟内存空间，肯定是采用其它的。

? ? ? ? 我们可以利用 <stdlib.h> 中的函数 malloc() 或 calloc() 来开辟一定大小的内存空间，其中常用 malloc() 函数。

????????malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存，且分配的大小就是程序要求的大小。一般它需和free函数配对使用。free函数能释放某个动态分配的地址，表明不再使用这块动态分配的内存了，实现把之前动态申请的内存返还给系统。? ? ? ? ? ? ? ? ???????????????————Baidu

malloc() 函数的原型为：

void *malloc(unsigned int size);

返回值是一个指定类型的指针。

例如，使用 malloc() 函数分配一个整型内存空间：

int *pInt;

pInt=(int*)malloc(sizeof(int));

注意 malloc() 前面连接的是返回值转化成的指针类型，括号内的是数据类型的字节数目。

????????calloc() 函数则是在 malloc() 函数的基础上增加了一个参数 n ，其原型为：

void *calloc(unsigned n,unsigned size);

意为分配 n 块 size 字节大小的连续的内存空间，有点像数组。

????????利用 malloc() 函数，我们可以改变上述代码得：

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;
	struct stu* pHead=NULL;

	struct stu* stu_new=(struct stu*)malloc(sizeof(struct stu));
	struct stu* stu_end=NULL;

	stu_temp.pNext = stu_new;
	//将队头结点与头结点连接起来
	stu_temp.iScore = -1;
	pHead = &stu_temp;

	while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)
	//输入-1，循环停止
	{
		scanf("%s", stu_new->cName);
		stu_end = stu_new;
		stu_new= (struct stu*)malloc(sizeof(struct stu));
		stu_end->pNext = stu_new;
	}

	stu_end->pNext = NULL;
	free(stu_new);

	printf("打印结果:\n");
	while (pHead != NULL)
	{
		if (pHead->iScore == -1)
		{
			pHead = pHead->pNext;
			continue;
		}
		printf("%d %s\n", pHead->iScore, pHead->cName);
		pHead = pHead->pNext;
	}
	return 0;
}

我们先来打印一下输出结果：

注：上面代码中 stu_new 、stu_end 为指向某个特定结点的指针，为方便起见，以下称某个特定结点的名字就是指向该特定结点的指针的名字，例如将指向某个特定结点的指针 stu_new 作为该特定结点的名字。

????????下面的这些语句最为重要：

while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)
	//输入-1，循环停止
	{
		scanf("%s", stu_new->cName);
		stu_end = stu_new;
		stu_new= (struct stu*)malloc(sizeof(struct stu));
		stu_end->pNext = stu_new;
	}

	stu_end->pNext = NULL;
	free(stu_new);

????????这段语句用来开辟一个新节点 stu_new，然后在设置好了该新结点的数据域后，将 stu_end 作为该结点的另一个名字，然后利用下面这个语句继续开辟一个新的内存空间：

stu_new= (struct stu*)malloc(sizeof(struct stu));

????????开辟成功后，用 stu_new 来命名这个新空间，即这个新结点的名字为 stu_new 。再来看一下这个循环的终止条件：

while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)

????????将下面这个赋值语句放置在这个终止条件中，可以很方便地在后面通过 stu_new->iScore 是否等于 -1 来决定是否终止，故只有当我们为 stu_new->iScore 赋的值不为 -1 时才能开辟新的结点并将这个新结点纳入到旧链当中来：

scanf("%d", &stu_new->iScore)

? ? ? ? 当跳出循环时，说明这个新结点的数据域的 iScore 为 -1 ，我们不需要这个新结点，不用将它纳入到旧链当中来。而已有的旧链最后一个结点为 stu_end ，我们将它的指针域设置为 NULL ，意即 stu_end 后面不再连接新结点，同时我们将为新结点开辟的空间还给系统，就有了下面的语句：

stu_end->pNext = NULL;
free(stu_new);

????????截取的这段关键代码的逻辑图示为：

?

?

?

直到下图的出现，4、5过程才不会继续：

?

单向链表的讲解就到此为止，在后续的博客里博主会谈谈对循环链表和双向链表的理解。

欢迎指正我的上一篇博客：实现简单的网络通讯(C语言)

我的下一篇博客：待续