CMU154452023 Spring - Project 0. C++ Primer
系列笔记
环境配置
Project 0. C Primer
Project 1. Buffer Pool
Project 2. B Tree
作业链接
作业链接(2020,废)
作业链接
p0就是一个C 水平测试,很简单 2023的明显难不少。
TASK 1
先简单说一下看到这个数据结构时自己想到的一些问题与自己的思考:
- 为啥Put的实现这么奇葩,要求返回一颗新树,不会很耗资源吗?
显而易见Put是比较耗资源的,但是没有想象中的那么耗资源,因为Trie其实不负责具体资源的分配的,Trie代表的仅仅是一些索引而已,里面只存了一堆指针。 - 为啥Get的实现要求先dynamic_cast到const TrieNodeWithValue<T>*,不嫌麻烦吗?*
这其实是为了实现异类集合,想想就知道了。
Get
Get实现没啥难度,直接扫一遍key指针跟着跑就行,唯一个一个地个小坑点是root_是个shared_ptr,不能直接做cast到裸指针,需要通过.get获取裸指针然后再做cast。
Put
Put实现开始就有点麻烦了,这个题目的主要问题是想要修改一棵树,根据题目要求,这个Put是要返回一颗新Trie的,拿官方例子中的添加[“ad”, 2]为例,如果我们自顶向下构造new trie,首先建立new root,然后我们在new root里添加一个[‘a’, Node2],然后在Node2里添加一个[‘d’, 2],这一步就卡住了——我们在root里存的node2的指针是指const的,加不了!
想清楚这一点就很好解决了,我们就自底向上构建树,先从头到尾扫一遍key,公共结点一路clone下来,非公共结点新建资源,存到栈里,然后使用最后的那个结点的child与函数参数value构造一个TrieNodeWithValue,再反向遍历key并依次弹出stack,利用map::operator[]建立一颗树即可。
Remove
Remove也就差不多的操作,首先扫一遍key,如果发现key不在Trie里或者key对应的结点压根没value,直接返回root无事发生,否则的话就入栈,然后用最后遍历到的那个结点的children去构造一个TrieNode并修改栈顶,然后依此出栈并erase掉children为empty的结点。
Task 2
没啥好说的,照着伪代码写就行,只要Task1没问题,Task2就不会有太大问题,记得写Put的时候别忘了move传value就行。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhibekaf
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22