单链表的创建
单链表的创建
大家好,今天来详细说一下单链表的创建过程。
单链表是我们在学习数据结构时见到的第一种动态内存分配的结构,而这也是单链表和数组之间最大的区别,因为数组被分配的内存是固定的,而单链表的内存是在执行时分配的。
因此,想要给单链表分配内存,我们就得首先知道函数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,即可完成第二节点和第三结点的连接。示意图和代码如下。
综上,我们创建了一条具有三个结点的单链表。现在,我们可以对链表进行增、删、改、查等一系列操作了!
相关文章
- iOS 12.5.1 正式版发布,旧机型专用
- css中sticky属性是什么
- 系统中的大管家—SystemServer进程
- css响应式布局如何理解
- css渐进增强如何理解
- BLE中这些概念,你都了解吗
- css优雅降级是什么意思
- css margin:auto的填充规则
- css中outline方法的使用
- 小程序下的地图还能这么玩,你知道吗?
- css默认样式的整理
- css浏览器的渲染过程
- 如果几亿人改微信号,腾讯扛得住吗?
- css中固定定位fixed是什么
- css中hack是什么
- css中hack的3种表现形式
- 苹果推送iOS 13.6.2要不要升级?手机能用的话建议不升级
- 苹果 15 年大轮回:Mac 选择 ARM,正如当年乔布斯选择 Intel,但变数更多了
- 10个最新且有希望的UI设计趋势
- css中grid布局的使用