【昊昊带你学】基本数据结构(下)

【昊昊带你学】基本数据结构(下)

ID:16301689

大小:111.78 KB

页数:5页

时间:2018-08-09

【昊昊带你学】基本数据结构(下)_第1页
【昊昊带你学】基本数据结构(下)_第2页
【昊昊带你学】基本数据结构(下)_第3页
【昊昊带你学】基本数据结构(下)_第4页
【昊昊带你学】基本数据结构(下)_第5页
资源描述:

《【昊昊带你学】基本数据结构(下)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、链表前面大家用队、栈的时候用的都是数组。数组挺好用的,不过蛋疼的是,数组里面要增、删数据就蛋疼了。不过咱们有链表,下面我来丑陋地给大家画个链表~哈哈,说了画给大家,就果断要亲手画,果然很丑陋的说O_o我来简单给大家先说一下链表的每个节点都是怎么个结构~看中间那一坨,这就是一个节点,prev部分指向它的前驱,而next则指向它的后继。这样,该节点就成功得与前后向链接了。而中间那个data(不是dota哟~)就是这个节点的数据部分,当然不一定只有一个,画成一个比较清晰而已。大家看到最右边节点的后继中是个“/”,这代表着指向null,即空

2、。碰到这种情况,就是说,这已经是链表的一端了。当然头和尾都有可能。最左边那个head()就是这个链表的头指针,头指针可以让你能够找到链表中的第一个元素,大家应该明白,链表不像数组,可以通过下标直接找到节点(优化除外~),这时候,你要用链表中某一个节点的时候就得从头指针往后遍历。我们可以看到,链表比数组好在它能够很方便的在某处增加节点或删除节点,但同时,数组对于每个元素的定位又更加快速~两个数据结构都各有千秋,大家要结合实际问题灵活选用。下面来将一些具体的函数:LIST-SEARCH(L,k)X←head[L]Whilex≠NILan

3、dkey[x]≠kDox←next[x]ReturnxPS:这是在链表中搜索某结点的一个方法。L是一个链表,k是我们要搜索的KEY,我们先把L的头指针给x,然后当x还指向链表中节点并且没有发现KEY值的时候做x←next[x]这件事,那这件事是什么意思呢?有的孩纸应该看明白了,就是将x指向当前节点的后继,从而达到链表遍历的目的。LIST-INSERT(L,x)next[x]←head[L]Ifhead[L]≠NILThenprev[head[L]]←xHead[L]←xPrev[x]←NILPS:这是在链表头插入节点的方法。L是一个

4、链表,x是一个节点(这个时候x还是孤零零的一个~)。我们先让x的后继指向本来的头结点。如果头结点不为空,就将它的前驱指向x(之前前驱为空)。此时,头指针指向x。最后将x的前驱赋为空。大家可以自己在草稿纸上画一下上述过程。如果是在链表中插入结点,类似,希望童鞋们自行考虑该如何操作,只要注意四个地方的指向(可能会有点绕,不过结构是很对称的):前驱,后继,前驱的后继,后继的前驱。搞清楚这四个的关系,其实也是链表最核心的东西~LIST-DELETE(L,x)Ifprev[x]≠NILThennext[prev[x]]←next[x]Else

5、head[L]←next[x]Ifnext[x]≠NILThenprev[next[x]]←prev[x]PS:这是在链表中删除一个节点。L是一个链表,x是一个节点。首先如果x的前驱不为空,那么就将前驱的后继指向x本来的后继,否则x是头结点,那么直接将头指针指向x的后继。接下来,如果后继不为空则将后继的前驱指向x本来的前驱,当然如果是空的话,你不用理会。删除操作的核心,还是我们刚刚提到的四点:前驱,后继,前驱的后继,后继的前驱。大家看一眼下图,这是在链表中删除节点的情况。①所对应的就是第一个if的操作,它将前驱(prev[x])的后

6、继(next[prev[x]]==next[x])指向了原本的后继(next[x])。第二步类似。对于链表还有一种哨兵的优化,如果大家有兴趣可以自行百度谷歌,也可以联系我来讨论哈。树(二叉树)链表整完了,咱们来说说树,这里我们重点讲二叉树。树的每个节点结构与链表挺类似的,只是原来的前驱、后继变为了父亲、左右孩子。在网上给大家粘了个图下来,L就是左孩子,R就是右孩子,这个图没有把父亲的域画出来,大家应该可以明白是什么意思。我们以后再画二叉树就不会再带着左右两个域,请大家注意。最顶端的节点叫做根,当然也有单独把根拿出来的情况,个人感觉看

7、情况吧。而最底层的节点(没有孩子节点)的叫做叶子节点。有了链表的基础,我相信这里的增、删、查找大家应该可以自行完成,就算不会我估计看代码也可以看得懂了,我就不再这矫情地一点一点分析了。直接来给大家讲一讲二叉树的一种建树方法,以及依靠递归来实现的三序遍历。首先来提一下三序遍历:先序遍历:首先访问根结点然后遍历左子树,最后遍历右子树。什么意思呢?遍历一棵树我们可以把问题分解开。遍历一整棵树,我们可以先访问根节点(这显然可以做到),然后遍历左子树,最后遍历右子树。可以看到我们把原来的问题分划成了三个子问题:第一个访问根节点,我们已经解决。

8、后两个问题是,分别遍历左右子树。(场外观众小贤:咦?这不是原来的问题?)bingo!我们把原来的问题分成了三个规模更小的问题,一个已经解决,另两个跟原来的问题一样。这就是传说中的分治算法,分而治之!对于遍历左子树的问题,我们同样可以先

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。