dom.cpp

Ex3-23 亲兄弟问题 &laquo 问题描述： 给定n 个整数0 1 1 , , , n- a a &#61516 a 组成的序列。序列中元素i a 的亲兄弟元素k a 定义为： min{

#include <fstream>
#include <iostream>
#include <stack>
using namespace std;
typedef struct{
	int num;	//记录数值
	int order;	//记录数值的下标
}Num;
typedef stack<Num> Stack1;
void dom(Num &a,int *b,Stack1 &numStack);//判断堆栈中的数值是否以a为亲兄弟
void main()
{
	ofstream out("output.txt");
	ifstream in("input.txt");
	int i;
	in>>i;
	Num a;
	int * b=new int[i];
	Stack1 numStack;
	for(int j=0;j<i;j++)
	{
		in>>a.num;
		a.order=j;
		dom(a,b,numStack);
	}
	while(!numStack.empty())//堆栈内的剩余元素无亲兄弟
	{
		b[numStack.top().order]=-1;
		numStack.pop();
	}
	for(j=0;j<i;j++)
	{
		out<<b[j]<<" ";

	}
	out<<endl;
	delete []b;
}
void dom(Num &a,int *b,Stack1 &numStack)
{

	while(!numStack.empty()&&a.num>=numStack.top().num)
	{
		b[numStack.top().order]=a.order;
		numStack.pop();
	}
	numStack.push(a);
}