1.本周学习总结）
1.思维导图
2.谈谈你对查找运算的认识及学习体会。
本章是学习查找的知识，本来以为查找在以前的代码都用过了，已经是没有什么更新的东西，但是开始学习到二叉搜索树的时候就发现了新的以前从未接触过的东西，到了平衡二叉树的时候就感觉到难度了，虽然没做代码要求，但是调整也是非常容易弄错，经过课堂派的练习也是稳固了这一块的东西，B树算是这一章学的最不好的一部分的，也是要在考前会再看一遍的。其它的通过pta的练习也基本掌握，本章总体难度不是很的，加上stl中的一些函数的辅助，让本章的代码量也是下降了不少。
2.PTA实验作业
2.1.题目1：6-2 是否二叉搜索树
2.1.1设计思路
IsBST函数传入二叉树T 定义静态整型变量s=-1 定义bool类型变量result if T为空 then 返回true end if 递归遍历左孩子,result接收返回值 if result为false 返回 false end if else if T->Data大于s then s=T->Data end else if else 返回false end else 递归遍历右孩子,result接收返回值
2.1.2代码截图
2.1.3本题PTA提交列表说明。
- Q1:刚开始用层次遍历，以为只要判断当前结点比左结点大，比右结点小就行，结果有测试点过不了
- A1:后来想到上课的时候老师说过用中序遍历，所以对代码进行了修改
- Q2:结果想了很久，采用了全局变量可以过
- A2:后来参考同学代码，发现了更加简洁的办法
2.2 题目2：6-4 jmu-ds-哈希表操作集
2.2.1设计思路
void CreateHT(HashTable ha, KeyType x[], int n, int m, int p) //建立哈希表 对哈希表数组进行初始化，关键字置为NULLKEY for i=0 to i=n-1 do 下标at=x[i]%p 找到at的位置，若key不为NULLKEY，则at=(at+1)%m，直到找到NULLKEY 在找到位置存入x[i]关键字，计算出探测次数并存入探测次数 end forint SearchHT(HashTable ha, int p, KeyType k) //寻找关键字 下标at=k%p //k为要寻找的关键字 if ha[at].key等于NULLKEY then 令uns_count为1并返回-1 end if if ha[at].key等于k then 返回at end if //直接找到 for循环寻找k所在位置 if 找不到 then 计算出探测次数存在uns_count并返回-1 end if 返回k所在位置
2.2.2代码截图
2.2.3本题PTA提交列表说明。
- Q1:在测试完样例后，第一次提交出现了答案错误，非常意外
- A1:进行多组测试数据的测试，找到发现是把题目的变量搞混了，把n当成m
- Q2:继续提交过了两个测试点，查找不成功的测试点没过
- A2:返回题目，发现题目还需要统计查找不成功的次数，对代码进一步修改后过了
2.3 题目3：7-2 航空公司VIP客户查询
2.3.1设计思路
定义long long型变量 len存里程，ID存身份证定义哈希表链的结点指针变量p定义哈希表数组Hash对哈希表中每一条链表进行初始化输入用户数量N和最小里程Kwhile N-- do 输入ID if ID小于18位 then getchar() end if //把x给消掉 输入里程len if len小于K then len=K end if sum=ID%100000 //哈希函数，sum为下标 p指向下标sum的链表的第一个结点 while p不为空 do 寻找相同身份证号，找到则对里程进行修改 end while if 找不到相同身份证 then 则新建一个结点，将结点插在下标sum链表头部 end ifend while输入查询人数Nwhile N-- do 输入ID if ID小于18位 then getchar() end if //把x给消掉 sum=ID%100000 //哈希函数，sum为下标 p指向下标sum的链表的第一个结点 while p不为空 do 寻找对应身份证号，找到输出里程并退出循环 end while if p为空 then 输出找不到 end ifend while
2.3.2代码截图
2.3.3本题PTA提交列表说明。
- Q1:看到这题，很自然的想到用map来写，写完运行超时
- A1:查资料发现改成scanf可以减少耗时
- Q2:改完之后依然超时
- A2:想到用哈希表来做因该不会超时，顺便练习一下代码，顺利通过这一题
3、阅读代码
3.1 题目:230. 二叉搜索树中第K小的元素
3.2 解题思路
利用非递归的中序遍历对二叉树进行遍历，借助了vector和栈的容器，将遍历结果存在vector中，最后就可以得到一个中序遍历所得到的中序序列，而第k-1的位置就是第k小的结点
3.3 代码截图
3.4 学习体会
1.本题如果自己写的话可能会不知所措，因为我绝对不会去采用非递归的中序遍历，而题解中的代码采用了这种方法也是为我的这类问题的解决提供了一种新的思路2.vector容器可以控制数组的长度，有效的防止数组越界的问题，熟练的掌握vector容器我认为是非常有必要的