回到正题,继上次出了数据结构线性表的内容上以后,这次又给大家更新啦。这次介绍的是单链表和静态链表的内容,话不多说,开始我们的正题。
【注:代码下载请移步留言区】
*
内容提要:
*预备知识
*顺序表(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