1.学习总结
1.1查找的思维导图
1.2 查找学习体会
查找这一章节整体的思路比较清晰,几种不同的查找方式都提高了对数据查找的速度,减少了时间复杂度。可以通过查找的ASL是来选择合适的算法。
2.PTA实验作业
2.1 题目1:6-2 是否二叉搜索树
2.2 设计思路(伪代码或流程图)
if(T为空树)返回正确
else if(左子树不为空但有键值大于其根结点的键值) 返回错误
else if(右子树不为空但有键值小于其根结点的键值) 返回错误
再次返回调用左子树和右子树
2.3 代码截图
2.4 PTA提交列表说明。
编译错误是因为PTA的编程环境和我用的DEV不一样,有些地方不能通用
部分正确是因为左右都是,但答案是NO这个情况我没有考虑
2.1 题目2:6-3 二叉搜索树中的最近公共祖先
2.2 设计思路(伪代码或流程图)
if(T是空树) 返回error
if(查找不到u,v)返回error
if(u,v有一个是根节点)返回根节点的关键字
if(u,v一个在左子树,一个在右子树)返回根节点的关键字
if(都在右子树)继续调用,节点变成右节点
if(都在左子树)继续调用,节点变成左节点
2.3 代码截图
2.4 PTA提交列表说明。
编译错误是函数名称搞错了,找不到子函数报错
部分正确是因为返回值搞错了,程序计算出错
2.1 题目3:7-1 QQ帐户的申请与登陆
2.2 设计思路(伪代码或流程图)
定义字符串型变量x,y,z
If x==L
map里没有找到则账号不存在,否则继续在map里查找密码
If x==N
在map里找到则账号存在,否则将账号密码进map
2.3 代码截图
2.4 PTA提交列表说明。
PTA的编程环境选错了,要选c++环境才能运行
3.截图本周题目集的PTA最后排名(3分)
3.1 PTA排名(截图带自己名字的排名)
4. 阅读代码(必做,1分)
HashMap中红黑树的查找函数find()实现
用哈希表查找和红黑树查找比较
哈希表需要考虑hash函数和operate==,而红黑树需要考虑operate<。这其中速度取决于hash函数与operate<的计算成本。一般情况下,两者的成本是相同的,因此哈希表查找会比红黑树查找要快。