C语言基础

          第四节 简单链表

 

 

        在今天我们来学习一个非常重要的数据结构，线性链表。其实链表本身并不复杂，我们说它重要，是因其设计理念非常重要，它使用结构体与指针相互结合完成独特功能的数据结构。如果你对数据结构还不是很熟悉，也不用过于担心，我们今天会一起学习并实现一个简单的线性链表。

一、内存申请与释放

        我们想要学习设计并使用链表，首先需要学习两个非常重要函malloc()函数和free()函数。

        malloc()函数可以向系统申请一块内存区域，如果申请成功则返回这个内存区域的指针，如果申请失败则返回空指针NULL。例如：

void *p = malloc(8);

        其中malloc的参数表示向系统申请多少个字节。

        free函数与malloc正好相反，它负责向系统释放之前申请过的内存区域，例如：

free(p);

        其中p为malloc申请的内存指针。注意，使用free函数释放内存时，只能释放之前申请成功的内存，如申请失败，则不可以使用free释放NULL。并且对于同一块内存不能使用free释放多次。

        有了malloc和free这两个函数，我们就可以灵活的像系统申请内存了，申请的内存可以转为我们想到的变量，并与普通变量一样使用。例如：

 

//申请4个字节给int型指针
int *p_i = malloc(sizeof(int));
//申请16个字节给int型指针
int *p_arr = malloc(sizeof(int) * 4);
//申请一个点类型结构体内存
struct point *p0 = malloc(sizeof(struct point));
//释放申请过的内存
free(p0);
free(p_arr);
free(p_i);

 

        需要说明的是，通常情况下malloc与free都是成对使用，即：申请内存后，使用完毕则需要将其释放。

 

二、线性链表

        下面我们就来看看简单的线性链表的设计，定义一个链表节点的数据结构：

 

typedef struct s_node
{
	int num;
	struct s_node *next;
} s_node;

 

        我们希望这个链表中每一个节点中都可以存放一些数值（int num），同时还可以存放下一个节点内存地址（struct s_node *next)。这样我们就可以通过num来读取链表中的有效数据，并可以通过next指针来找到下一个节点的内存地址。我们可以使用一个图形化的表示方法来描述这个线性链表。

        关于这样的设计是一种非常高明的理念，我们可以使用一个指针变量来保存这个链表的头节点地址，而之后的所有节点地址均由其前面节点中的next指针来确定。这样我们就5可以使用“顺藤摸瓜”的办法，从链表的头部，逐个访问整个链表。

        当然，我们现在还不能这样使用，我们需要先创建这样的一个链表：

 

s_node* list_create()
{
	s_node *header = malloc(sizeof(s_node));
	header->num = 0;
	header->next = NULL;
	s_node *p = header;

	for (int i = 1; i < 10; i++)
	{
		p->next = malloc(sizeof(s_node));
		p = p->next;
		p->num = i;
		p->next = NULL;
	}
	return header;
}

 

        在这里我们使用malloc函数在循环程序中申请了10个链表的节点，并将这些节点通过其next指针连接起来。每个节点中的num都存放了这个节点数值。最后我们记录了这个链表的第一个节点的地址，并将其命名为header。有了链表之后，我们就可以“顺藤摸瓜”的访问其所有的内容了：

void list_visit(s_node *header)
{
	while(header != NULL)
	{
		printf("num: %d\n", header->num);
		header = header->next;
	}
}

 

        注意，这样的一个线性链表，在访问时只能顺序访问，而不能像数组那样根据下标任意访问其节点。

        在使用完链表之后，我们还需要使用free函数将其申请的所有内存释放掉：

 

void list_destory(s_node *header)
{
	while(header != NULL)
	{
		s_node *p = header;
		header = header->next;
		free(p);
	}
}

 

        最后我们来说一说使用这种数据结构的好处，在文章开始时我们已经说过，这是一个非常重要的设计理念，它可以通过其节点本身的指针来指向下一个节点，在《数据结构》课程中，几乎所有的数据结构都是基于这样的设计理念的，例如：队列、树、图等等。一个好的数据结构可以提高程序的执行效率，数据结构是程序算法的基础，所以希望大家在这里打好基础。我们会在后续的教程中一起学习《数据结构》。