L2-012 关于堆的判断 (25 分)-白红宇的个人博客

L2-012 关于堆的判断 (25 分)

发布日期：2021-06-29 22:18:35 浏览次数：2 分类：技术文章

本文共 1970 字，大约阅读时间需要 6 分钟。

将一系列给定数字顺序插入一个初始为空的小顶堆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），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。输出格式：对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。输入样例：5 446 23 26 24 1024 is the root26 and 23 are siblings46 is the parent of 2323 is a child of 10输出样例：FTFT

/*本题思路：先将输入的数据逐个存储到整形数组u当中。 u[i]：10 23 26 46 24i：   1  2  3  4  5 .....然后将u[i]数组中的值保存到map集合当中map
   
     v,形成一个：v[u[i]]：10 23 26 46 24value  ：1  2  3  4  5关系如下四种：         x和y是兄弟节点，v[x]/2==v[y]/2x是根节点，v[x]==1x是y的子节点,v[x]/2==v[y]y是x的子节点,v[y]/2==v[x] 小顶堆：任意一个节点小于其左子节点和右子节点; */#include
    
     #include
     #include
      
       using namespace std;map
       
         v; const int MAXN=1005;//将小顶堆存储在一维数组当中; //记得赋空值!!! int u[MAXN]={
   0};int cnt=0;//构建小顶堆的方法;void create(int x){
   	//数组下标要从1开始存储; 	u[++cnt]=x;	int t = cnt;	//需满足任何一个节点的值小于左右子节点的值; 	while(t>1&&u[t/2]>u[t])	{
   		swap(u[t/2],u[t]);		t=t/2;		}}int main(){
   	int n=0,m=0,i=0,j=0,num=0;	cin>>n>>m;	for(i=1;i<=n;i++)	{
   		cin>>num;		create(num);	}	//将数组中的值存储在map集合当中，并将下标与之对应; 	for(i=1;i<=n;i++)	{
   		v[u[i]]=i;	}	int x=0,y=0;	string str1="",str2="",str="";	while(m--)	{
   		cin>>x>>str1;		if(str1[0]=='a')		{
   			/*			字符串需要输入完全，否则将会出现案例后两个			输入不进去的情况！！！ 			*/ 			cin>>y>>str1>>str2;			//兄弟节点的父节点应该是相同的; 			if(v[x]/2==v[y]/2)			{
   				cout<<"T";			}			else			{
   				cout<<"F"; 			}		}		else		{
   			cin>>str1>>str2;			if(str2[0]=='r')			{
   				//判断x是否是根节点; 				if(v[x]==1)					{
   					cout<<"T";				} 				else				{
   					cout<<"F";					}			}			else if(str2[0]=='p')			{
   				cin>>str>>y;				//判断x是否是y的父节点; 				if(v[x]==v[y]/2)				{
   					cout<<"T";					}				else				{
   					cout<<"F";					}				}			else if(str2[0]=='c')			{
   				cin>>str>>y;				if(v[x]/2==v[y])				{
   					cout<<"T";				}				else				{
   					cout<<"F";					} 			}		}		cout<

转载地址：https://dingshijie.blog.csdn.net/article/details/115676427 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：L1-064 估值一亿的AI核心代码 (20 分)

下一篇：L1-072 刮刮彩票 (20 分)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章