单链表的创建

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

    单链表的创建

    大家好,今天来详细说一下单链表的创建过程。

    单链表是我们在学习数据结构时见到的第一种动态内存分配的结构,而这也是单链表和数组之间最大的区别,因为数组被分配的内存是固定的,而单链表的内存是在执行时分配的。

    因此,想要给单链表分配内存,我们就得首先知道函数malloc(),即memory allocate(内存分配)的缩写,它是c语言标准函数库中的函数,用法是void *malloc(unsigned int size)。其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的返回值是分配区域的起始地址(即指向该分配域的开头位置的指针)

    了解了malloc函数以后,我们来创建链表中最重要的部分:结点(node)。每个结点中都存储了数据,但是,每个结点并不是独立存在的,因为链表是由多个结点连接组成,那么我们该怎么连接每一个结点呢?我们需要用到指针(pointer),用指针来指向另一个(下一个)结点的地址,这样就可以将每个结点按自己的想法连接起来。所以,每个结点都至少由两部分组成:数据和指向下一个节点地址的指针。

    知道了如何抽象地去创建链表之后,我们将用C语言代码来创建链表。

    首先,我们需要用到结构体(structure)来定义结点node:里面包括一个int类型的数据data,struct node类型的指针link。

    接下来,我们首先用malloc函数创建第一个长度为结点大小的连续空间,用来存储结点中的数据和指针。我们把这个连续空间定义为head,即头结点。我们在头结点中输入数据,再定义指针link的值为null,即不指向任何地址。这样,我们就创建了一个独立的结点。

    我们可以用同样的方法,创建第二个(current1),第三个(current2),直到我们需要数量的独立结点。如下图所示,我们创建了三个独立节点。

    但是,我们在之前已经知道,多个独立结点并不能称之为链表,链表是需要将结点连接起来的,所以我们还需要用代码来将他们连接起来。

    我们已经知道,head结点的指针不指向任何地址。现在,我想让他指向第二个结点current1,以此来连接第一个结点和第二个结点,形成一个只有两个结点的链表。我们只需要再后面添加一句:head->link = current1。即link的值是current1的地址。用同样的方法,我们可以连接第二个和第三个结点current2,即

    current1->link = current2。如下图代码所示。

    但是,按照我们上面的这种方法。如果我们需要创建一万个结点,那岂不是需要创建一万个指针指向各自的下一个结点?这样的方法非常的繁琐且占用内存空间,因此,我将介绍第二种方法,只需要两个指针就可以完成所有结点的连接。

    创建前两个结点的方法同上,两个结点分别为head,current1。创建第三个结点时不同的是,我们需要再次使用指针current1。在给第三个结点分配空间后,令current1 = malloc(sizeof(struct node)),即current1不再是第二个结点空间的首地址,而是第三个结点空间的首地址。这样,我们可以用和第二个节点同样的方法赋值第三个结点的data和link,另外一个不同的地方就是:我们将第三个结点的地址(current1)赋值给head->link->link,即可完成第二节点和第三结点的连接。示意图和代码如下。

     

     

     

     

     综上,我们创建了一条具有三个结点的单链表。现在,我们可以对链表进行增、删、改、查等一系列操作了!

     

     

     

     

     

     

     

     

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6