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);
	}
}

 

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

 

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号