数据结构-线性表|顺序表|链表(中)

回到正题,继上次出了数据结构线性表的内容上以后,这次又给大家更新啦。这次介绍的是单链表和静态链表的内容,话不多说,开始我们的正题。

【注:代码下载请移步留言区】

内容提要:

*预备知识

*顺序表(Sequential List)

*单链表(Singly Linked List )

*静态链表(Static list )

*循环链表(circular linked list)

*双向链表(doubly linked list)

03 单链表(Singly Linked List )

3.1 什么是单链表?

单链表是一种链式存储的结构。动态地为节点分配存储单元。当有节点插入时,系统动态的为结点分配空间。在结点删除时,应该及时释放相应的存储单元,以防止内存泄露。由于是链式存储,所以操作单链表时,必须知道头结点或者头指针的位置。并且,在查找第i个节点时,必须找到第i-1个节点。

3.2 单链表的存储结构代码描述

对于链式存储,通过上一节的讲解相信大家已经了解得够清楚了。如下图所示:

下面我们来看看单链表存储是如何用代码来实现的:

由上面的结构我们可以看出,一个节点由存放数据的数据域和存放地址的指针域组成。假如p指向了第i个节点,那么p->data就是该节点存放的数据,而p->pnext自然就是指向下一个节点的指针。如下图所示:

那么接下来我们看看单链表的各个操作具体实现吧。(只讲几个关键步骤)

备注:下面的代码基于这样的一个单链表:

1) 有一个头指针phead

2) 有一个头结点node

3) 头指针指向头结点,头结点位置记为0

3.3 单链表的读取

在拿到头指针以后,单链表的读取也并非一件难事。我们的做法是一开始设置一个计数变量,不断遍历链表,让计数器自增。找到合适的位置将数据读取出来。具体代码实现如下:

3.4 单链表的插入

01

3.4.1 指定位置后插

其实链表的插入和删除都是很简单的操作,初学者只要抓住指针指向的节点,并加以区分开来,就很easy了。如下图:

图中,假如此时p指向了我们要插入的节点的位置。那么,怎样把我们的S节点给插入到p指向的节点之后?在这里我们先不要惊动p以及p后面的节点:

1) 我们先让S节点指向p之后的节点(步骤①)

2) 之后我们切断p和p后面那个节点的关系(步骤②)

3) 最后让p节点的指针域指向s节点(步骤③),搞定

算法描述:

1) 声明一个指针p指向链表头结点,向后遍历p=p->next,找到正确的位置。

2) 新建一个结点s。

3) s->next = p->next ①.

4) p->next = s ②③

具体代码如下:

3.4.1 指定位置前插

02

咳咳,聪明的小伙伴,用脑子想想。指定位置前插 == 指定位置的前一个位置进行后插。懂了吧?直接看具体代码:

3.5 单链表的删除

单链表的删除其实也是很简单。只要比如要删除p指向的节点,只需要让p之前的节点的指针域直接指向p之后的节点,再把p给free就OK了。如下图:

算法描述:

1) 声明一个指针p指向链表头结点,向后遍历p=p->next,找到要删除的节点位置。

2) q = p->next

3) p->next = q->next ①②

4) free(q) ③④

具体代码如下:

代码应该不难,相信大家都能很容易看懂。

3.6 单链表的完整代码

好了,前面介绍了几个重要的操作,接下来请大家看看完整的代码吧。小编为了使用方便,就用C++的class和template将整个链表封装到了一个类里面,通过模板实现泛型编程。

【注:代码下载请移步留言区】

04 静态链表(circular linked list)

4.1 什么是静态链表?

我们把线性表的元素存放在数组中,这些元素由两个域组成:

数据域data

指针域cur

数据域是存放数据的,而指针域,这里和链表不同是,它存的不再是指向下一个节点的内存地址。而是下一个节点在数组中的下标。我们就把这种用数组描述的链表称为静态表,该方法也称之为游标实现法。如下图所示:

由上图我们需要注意以下几点:

1) 我们对数组的第一个元素和最后一个元素做特殊处理,不存放数据。

2) 把未使用的数组元素称为备用链表。

3) 数组的第一个元素(下标为0)的cur域存放备用链表第一个节点的下标。

4) 数组的最后一个元素的cur域存放第一个有数据的节点的下标,相当于链表中头结点的存在。链表为空时,其值为0。

如下图:

引出的问题:数组的长度定义的问题,无法预支。所以,为了防止溢出,我们一般将静态表开得大一点。

4.2 静态链表存储的代码描述

基于上面的讲解,我们来看看代码是怎么描述这种存储结构的:

接下来我们讲解几个重要的操作实现。

4.3 静态链表的插入操作

前面我们讲动态链表的时候说过,增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。但是现在由于我们操作的是静态表,它可是用数组存的,可没有这种操作了。因此我们首先来自己实现一个静态表的malloc和free。

那么怎么辨别数组中哪些空间没有被使用呢?一个好的解决办法是,将所有未使用或者被删除的空间串成一个备用链表插入节点时便可以从备用链表获取第一个未使用的空间的下标。因此我们在初始化的时候会做这样的工作:

分配内存

上面的代码应该是没有难度的。写完了这个函数,我们来看看静态表中具体如何插入:

注意几点:

1) 首先我们让k指向了要插入节点(记为X)的前一个位置(记为Y节点),前插法。

2) 然后我们在静态表内申请空间,存放新的节点(记为N)。

3) 把数据放进新申请的节点里面。

4) 新节点N的cur域指向X节点,然后让Y节点指向N节点。

该过程不难理解。就不上图了……

4.4 静态链表的删除操作

删除同样需要自己实现free函数,我们来看看代码:

回收内存

删除以后记得把空间重新挂载到备用链表上以便下一次使用。下面我们实现删除的代码:

其实代码也很好理解了。假如X、Y、Z……等等排列,我们要删除Y。无非就是告诉X,你不要指向Y了,你直接指向Z,然后我们再把Y给free了。就直接变成了X、Z……简单吧。

4.5 静态链表的完整代码

【注:代码下载请移步留言区】

这次文章代码量有点大哈,希望同学们能耐心坚持看完。关键的几个操作,牢牢把握各个重要的概念,理解也不成问题的。代码链接请戳原文链接

END

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2018-02-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十八)——直接插入排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半...

35310
来自专栏我是攻城师

JDK8中LinkedList的工作原理剖析

33512
来自专栏我叫刘半仙

原荐你知道么?static关键字有5种用法。

     说到static,静态变量和静态方法大家随口就来,因为他们在实际开发中应用很广泛,但他们真正在使用的时候会存在很多问题,而且它的使用不只那两种:   ...

4536
来自专栏决胜机器学习

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八)——赫夫曼树实现字符串编解码(实践2) (原创内容,转载请注明来源,谢谢) 公众号规定不能超过3000字,只能分两篇,见谅。 由于需要分两篇...

3506
来自专栏Albert陈凯

JAVA基础面试题

JAVA 说出ArrayList, Vector, LinkedList的存储性能和特性(集合类:ArrayList与 LinkedList的区别,为什么JAV...

3507
来自专栏王磊的博客

javascript数组去重方法汇总

前言 ---- 数组去重已经是一个老生常谈的问题了,依然经久不息,经过岁月的变迁es标准的升级迭代,似乎有越来越多的方法和方式供我们使用,那么那种方式才是最...

2839
来自专栏Java编程技术

诡异的类型转换

最近在做应用迁移时候遇到了一个诡异的类型转换问题,感觉比较有意思,就记录下来和大家分享下。

912
来自专栏mathor

二分查找与二分答案(1)

1995
来自专栏数据结构与算法

集合的前N个元素

集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下:     (1)数1属于M;     (2)如果X属于M,则Y=2*x+1和Z=...

2674
来自专栏Java编程技术

并发队列中迭代器弱一致性原理探究

并发队列里面的Iterators是弱一致性的,next返回的是队列某一个时间点或者创建迭代器时候的状态的反映。当创建迭代器后,其他线程删除了该元素时候并不会抛出...

1491

扫码关注云+社区

领取腾讯云代金券