博客作业05--查找

时间:2022-08-23 21:57:05

1.学习总结

1.1查找的思维导图

 博客作业05--查找

 

1.2 查找学习体会

查找这一章节整体的思路比较清晰,几种不同的查找方式都提高了对数据查找的速度,减少了时间复杂度。可以通过查找的ASL是来选择合适的算法。

2.PTA实验作业

2.1 题目1:6-2 是否二叉搜索树

2.2 设计思路(伪代码或流程图)

if(T为空树)返回正确

else if(左子树不为空但有键值大于其根结点的键值) 返回错误

else if(右子树不为空但有键值小于其根结点的键值) 返回错误

再次返回调用左子树和右子树

2.3 代码截图

 博客作业05--查找

 

2.4 PTA提交列表说明。

博客作业05--查找

 

编译错误是因为PTA的编程环境和我用的DEV不一样,有些地方不能通用

部分正确是因为左右都是,但答案是NO这个情况我没有考虑

2.1 题目26-3 二叉搜索树中的最近公共祖先

2.2 设计思路(伪代码或流程图)

if(T是空树) 返回error

if(查找不到u,v)返回error

if(u,v有一个是根节点)返回根节点的关键字

 if(u,v一个在左子树,一个在右子树)返回根节点的关键字

if(都在右子树)继续调用,节点变成右节点

if(都在左子树)继续调用,节点变成左节点

2.3 代码截图

 博客作业05--查找

 

2.4 PTA提交列表说明。

 博客作业05--查找

 

编译错误是函数名称搞错了,找不到子函数报错

部分正确是因为返回值搞错了,程序计算出错

2.1 题目37-1 QQ帐户的申请与登陆

2.2 设计思路(伪代码或流程图)

定义字符串型变量x,y,z   

If x==L

map里没有找到则账号不存在,否则继续在map里查找密码     

If x==N   

map里找到则账号存在,否则将账号密码进map

2.3 代码截图

 博客作业05--查找

 

2.4 PTA提交列表说明。

 博客作业05--查找

PTA的编程环境选错了,要选c++环境才能运行

3.截图本周题目集的PTA最后排名(3分)

3.1 PTA排名(截图带自己名字的排名)

 博客作业05--查找

 

4. 阅读代码(必做,1分)

HashMap中红黑树的查找函数find()实现

 博客作业05--查找

 

 博客作业05--查找

 

 

哈希表查找红黑树查找比较

哈希表需要考虑hash函数和operate==,而红黑树需要考虑operate<。这其中速度取决于hash函数与operate<的计算成本。一般情况下,两者的成本是相同的,因此哈希表查找会比红黑树查找要快。