//计算点(x1,y1)和点(x2,y2)两点单距离平方和
int getDisSqrt(int x1, int y1, int x2, int y2)
{
return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
//升序输出所有可以触发雷
void printTriggeredMines()
{
bool *triggered = new bool[numMines];//触发表,即访问表
int i,j;
int *stack = new int[numMines];//建栈,交大轻递归,注意掌握栈来代替递归
int top = 0;
for(i=0; i<numMines; i++)
{
triggered = false;//赋初值
}
stack[top++] = FirstTrigger;//触发雷入栈,开始深度遍历
while(top>0)
{
i = stack[--top];//弹出栈顶
triggered = true;
for(j=0;j<numMines;j++)
{
if(disGraph[j]==true&&triggered[j]==false)
{
stack[top++] = j;//所有未触发邻结点入栈
}
}
}
bool isFirst = true;//控制输出,第一个数前面不输出空格,其它需要输出空格
for(i=0; i<numMines; i++)
{
if(triggered)
{
if(isFirst)
{
cout<<i+1;//注意,由于矩阵下标和触发标志表都从0开始,输出序号时要+1
isFirst = false;
}
else
{
cout<<'' ''<<i+1;
}
}
}
cout<<endl;
delete []stack;//注意归还空间
delete []triggered;//养成良好习惯
return;
}
}; int main()
{
int num;
int* listMinesPos;
int first;
cin>>num;//输入雷数
listMinesPos = new int[2*num];//分配空间
int i;
//读入所有雷的坐标
for(i=0;i<num;i++)
{
cin>>listMinesPos[2*i]>>listMinesPos[2*i+1];
}
//读入触发雷序号
cin>>first;
first--;//由于数组序号从0开始,需要-1校正
Mines M1(num,listMinesPos,first);//初始化问题实例
M1.printTriggeredMines();//输出结果
delete []listMinesPos;//归还空间
return 0;
}
//-------------------------------------------------------------------------------------
程序C:
#include<iostream>
#include<string>
using namespace std;
//前序序列第一个为树的根
//然后在中序序列中找到这个字母,则其左边的为左子树的中序遍历序列
//右边的为右子树的中序遍历
//同时可以算出左右子树的结点个数
//通过个数可以在前序序列中确定左右子数的前序遍历的位置
const string noResult = "-_-bbb";//无结果输出串
//工作记录结构,用来指示当前步该做什么
struct PreInCharPos
{
int preStart;//树前序序列在MrBean::preOrder中的开始序号
int inStart;//树中序序列在MrBean::preOrder中的开始序号
int Length;//序列升序即结点长度
};
class MrBean
{
public:
string preOrder;//前序序列
string inOrder;//中序序列
string postOrder;//后序列
int num;//结点数
MrBean()//构造
{
cin>>preOrder>>inOrder;//读入前序和中序序列
if(preOrder.size()==inOrder.size())
{
num = preOrder.size();//结点数即为序列长度
}
else
{
num = 0;//两者不等,非法串,让num=0来表示
}
}
//parent指示父结点的前序序列和后序序列位置,
//用LChild和RChild返回左右子树的前序序列和后序序列位置
bool getChild(PreInCharPos parent, PreInCharPos &LChild, PreInCharPos &RChild)
{
//先找出根结点
char root = preOrder[parent.preStart];
int i;
//i定位在中序序列中根的位置
for(i=parent.inStart;
(i<parent.inStart+parent.Length)
&&(inOrder!=root);
i++);
if(i==parent.inStart+parent.Length)
return false;//找不到根,非法序列,返回false
LChild.Length = i - parent.inStart;//通过i的位置算出左右子树结点数
RChild.Length = parent.Length - 1 - LChild.Length;
LChild.inStart = parent.inStart;//中序起始位置
RChild.inStart = i + 1;
LChild.preStart = parent.preStart + 1;//后序起始位置
RChild.preStart = LChild.preStart + LChild.Length;
return true;//正确返回
}
//找后序序列,在从根开始逐步分解序列,可以得到反序的后序遍历,从后往前装入postOrder
//算法可能不好懂,先看后序序列倒装就是先根再右子树再左子树,类似于交换左右子树
//访问顺序的先序遍历,估且称为变化的先序遍历,用栈实现
//考交大一定要重点掌握非递归的树的各种遍历
//也可以先建树再用后序遍历输出结果,但效率就不高了
bool getPostOrder()
{
if( num == 0 )
{
return false;//结点为0或者非法串,即两串不等长,肯定无对应后序串,返回false
}
bool finish = false;//指示循环是否结束
postOrder.resize(num);//调整postOrder长度
PreInCharPos work,lc,rc;//工作空间
PreInCharPos *stack = new PreInCharPos[num];//建栈分配空间
int top = 0;//SP
int postCount = num - 1;//反序完成后序序列
work.inStart = work.preStart = 0;//整个树的工作状态
work.Length = num;
stack[top++] = work;//将树入栈
while(!finish&&top>0)
{
work = stack[--top];
if(!getChild(work,lc,rc))
finish = true;//如果无法分出左右子树,则出错,循环结束
else
{
postOrder[postCount--] = preOrder[work.preStart];//将根填入postOrder
if(lc.Length>0)//左子树不空则入栈
{
stack[top++] = lc;
}
if(rc.Length>0)//右子树不空则入栈,由于是先右后左遍历,所以右儿子后入栈,先出栈被访问
{
stack[top++] = rc;
}
}
}
delete []stack;//归还空间
return !finish;//finish=flase则正常遍历完退出循环,得到合法后序序列,返回ture
//finish=ture是由于分左右子树时失败而退出循环,无法得到
//合法后序序列,返回fasle.总之返回!finish
}
//输出结果
void printPostOrder()
{
if(getPostOrder())//求后序
{
cout<<postOrder;//成功则输出后序
}
else
{
cout<<noResult;//否则输出无结果串
}
return;
}
};
int main()
{
MrBean mb;//构造实例
mb.printPostOrder();//输出结果
return 0;
}
