基础实验4-2.5 关于堆的判断 (25分)
将一系列给定数字顺序插入一个初始为空的小顶堆H[]
。随后判断一系列相关命题是否为真。命题分下列几种:
x is the root
:x
是根结点;x and y are siblings
:x
和y
是兄弟结点;x is the parent of y
:x
是y
的父结点;x is a child of y
:x
是y
的一个子结点。
输入格式:
每组测试第1行包含2个正整数N
(≤ 1000)和M
(≤ 20),分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[内的N
个要被插入一个初始为空的小顶堆的整数。之后M
行,每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式:
对输入的每个命题,如果其为真,则在一行中输出T
,否则输出F
。
输入样例:
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10
输出样例:
F T F T
题意分析,该题意在建立一个最小堆,让你判断堆中数据之间的关系。
小顶堆概念:见百度
小顶堆数组建立办法:
void build(int x[], int n){ //x[]为按顺序输入建立的满二叉树,未排序,n为元素个数 for (int i = 1; i < n; i++) { int t = i; while (t != 0 && dataa[(t - 1) / 2] > x[t]) { swap(x[t], dataa[(t - 1) / 2]);//若左右节点值小于根节点值,对其进行交换。 t = (t - 1) / 2; //让小值节点上冒,再将指针指到交换后的根节点,一直判断交换,直到到树根为止 } } //该函数用数组模拟堆。 //数组堆的特性:数组中的数据对应每一个节点。 //该节点的(下标值-1)/2即为其根节点的数组下标值 }
完整代码:注释的比较清楚,易于理解,通过草稿纸演算一遍就能看明白
/*XAN不会coding PT关于堆的判断 2020.12.03*/ #include<iostream> #include<stack> #include<stdio.h> #include<stdlib.h> #include<vector> #include<queue> #include<string> #include<map> #include <algorithm> #define swap(a,b) {a=a^b;b=a^b;a=a^b;} using namespace std; int dataa[1005]; map<int, int>mp; void build(int x[], int n){ for (int i = 1; i < n; i++) { int t = i; while (t != 0 && dataa[(t - 1) / 2] > x[t]) { swap(x[t], dataa[(t - 1) / 2]);//若左右节点值小于根节点值,对其进行交换。 t = (t - 1) / 2; //让小值节点上冒,再将指针指到交换后的根节点,一直判断交换,直到到树根为止 } } //该函数用数组模拟堆。 //数组堆的特性:数组中的数据对应每一个节点。 //该节点的(下标值-1)/2即为其根节点的数组下标值 } int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> dataa[i]; } getchar();//常规操作,消去换行字符 build(dataa, n); //以下是本题关键,用map来映射节点值与数组下标。如此做,在得到一个值时,可快速得知其在数组中(堆)的位置。 //该位置的性质决定了它与其他节点的关系 for (int i = 0; i < n; i++) mp[dataa[i]] = i; while (m--) { string a, b, c, d, e, f;//这里进行字符读取 cin >> a >> b; if (b[0] == 'i') { //字符处理发现语句规律 cin >> c >> d; switch (d[0]) { case 'r': dataa[0] == atoi(a.c_str())? cout << 'T' : cout << 'F'; break; case 'p': cin >> e >> f; ((mp[atoi(f.c_str())] - 1) / 2 == mp[atoi(a.c_str())]) ? cout << 'T' : cout << 'F'; break; case 'c': cin >> e >> f; ((mp[atoi(a.c_str())] - 1)/ 2 == mp[atoi(f.c_str())]) ? cout << 'T' : cout << 'F'; break; } } else { cin >> c>>d>>e; ((mp[atoi(a.c_str())] - 1) / 2 == (mp[atoi(c.c_str())] - 1) / 2 )? cout << 'T' : cout << 'F'; } cout << endl; } return 0; }
//end
谢谢观看,如果有问题可评论提出。如果觉得有帮助,也十分感谢您的点赞!