C++ 分治法解决邮局选址问题

C++ 分治法解决邮局选址问题 包含了代码、算法分析、测试文件和结果，非常详尽，值得拥有！

#include 
#include 
#include 
using namespace std;


struct City//定义城市结构体
{
	int  coordinate;//某一维方向的城市坐标
	double weight;//城市的权值
};


int Get_pivot（City* c int low int high double& leftsum double& rightsum）
{
	int pivot = c[high]. coordinate;//设置枢轴值为最后一个数组的元素值
	int i = low - 1;//定义最终要得到的枢轴位置
	leftsum = 0;//一开始的枢轴左边的权值之和为0
	rightsum = 0;//一开始的枢轴右边的权值之和为0
	
	for （int j = low; j <= high - 1; j++）//j指向第一个元素到倒数第二个元素进行循环
	{
		if （c[j]. coordinate		{
			i++;//i指向要交换的较大元素位置
			//交换高低位置的元素，较大的数放右边，较小的数放左边
			City temp = c[j];
			c[j] = c[i];
			c[i] = temp;
			//同时，左边小于枢轴值的元素其权重累加求和
			leftsum += c[i].weight;
		}
		else//如果该元素不小于最后一个数组的元素值
		{
			//右边大于等于枢轴值的元素其权重累加求和
			rightsum += c[j].weight;//这里，不需要交换元素，i不移动并在之后的某个循环中准备指向该较大元素的位置，并进行与之后j指向的较小值元素的交换
		}
	}
	//循环结束时，所有小于枢轴值的元素都在枢轴位置的左边
	i++;//i指向最后不小于枢轴值的元素
	//将数组最后一个元素和i指向的不小于枢轴值的元素进行位置交换，这样所有不小于枢轴值的元素就都在枢轴的右边了
	City temp = c[high];
	c[high] = c[i];
	c[i] = temp;
	//返回枢轴位置
	return i;


}



//带权中位数的查找
City Get_Weighted_Median（City* c int low int high double leftsummax double rightsummax）
{
	double leftsum rightsum;
	if （low	{
		int pivot = Get_pivot（c low high leftsum rightsum）;//得到枢轴的位置，以及按照枢轴位置排序的数组和枢轴左右各个元素的权值之和		
		if （leftsum < leftsummax and rightsum <= rightsummax）//已经满足带权中位数条件
			return c[pivot];//返回该枢轴值
		else//否则
		{
			if （leftsum >= leftsummax）//如果左边的权值之和大于等于上界，说明带权中位数在枢轴左侧区间
			{
				rightsummax = rightsummax - rightsum - c[pivot].weight;//当前左侧区间中的右侧区间权值之和上限等于当前右侧权值之和最大值减去右侧权值之和再减去枢轴的权值
				return Get_Weighted_Median（c low pivot - 1 leftsummax rightsummax）;//得到左侧区间[lowpivot-1]的带权中位数
			}
			else//如果右边的权值之和大于上界，说明带权中位数在枢轴右侧区间
			{
				leftsummax = leftsummax - leftsum - c[pivot].weight;//当前右侧区间中的左侧区间权值之和上限等于当前左侧权值之和最大值减去左侧权值之和再减去枢轴的权值
				return Get_Weighted_Median（c pivot + 1 high leftsummax rightsummax）;//得到右侧区间[pivot+1high]的带权中位数
			}
		}
	}
	//数组左右边域数值相同则返回同时指向的元素
	return c[low];
}

//显示从文件中读取的个城市坐标，并保存到输出文件中
void showCity（City c_xCity c_y）
{
	fstream output;
	output.open（“Result.txt“ ios::app | ios::out）;
	output << “（“ << c_x. coordinate << ““ << c_y. coordinate << “）“ << “ “;
	cout << “（“ << c_x. coordinate << ““ << c_y. coordinate << “）“ << “ “;
	output << c_y.weight << endl;
	cout << c_y.weight << endl;
	output.close（）;
}
//将邮局位置结果保存到输出文件中
void ResultLocation（City c_x City c_y）
{
	fstream output;
	output.open（“Result.txt“ ios::app | ios::out）;
	output << “结果为：“ << endl;
	cout << “结果为：“ << endl;
	output << “（“ << c_x. coordinate << ““ << c_y. coordinate << “）“ << “ “;
	cout << “（“ << c_x. coordinate << ““ << c_y. coordinate << “）“ << “ “;
	output << endl;
	cout << endl;
	output.close（）;
}


int main（int argc char** argv）
{
	int n = 0;
	fstream inputoutput_sigclear_txt;
	std::string finput;
	std::string assign1 = “input_assign01_0“;
	std::string assign2 = “123456“;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-03-13 16:10  分治法解决邮局选址问题 C++\
     文件        1899  2019-03-13 16:49  分治法解决邮局选址问题 C++\Readme.txt
     文件         603  2018-10-12 20:12  分治法解决邮局选址问题 C++\Result.txt
     文件         115  2018-10-05 23:08  分治法解决邮局选址问题 C++\input_assign01_01.dat
     文件           9  2018-10-05 23:40  分治法解决邮局选址问题 C++\input_assign01_02.dat
     文件          19  2018-10-05 23:40  分治法解决邮局选址问题 C++\input_assign01_03.dat
     文件          33  2018-10-05 23:50  分治法解决邮局选址问题 C++\input_assign01_04.dat
     文件          40  2018-10-05 23:49  分治法解决邮局选址问题 C++\input_assign01_05.dat
     文件          51  2018-10-05 23:41  分治法解决邮局选址问题 C++\input_assign01_06.dat
     文件        5230  2018-10-06 15:18  分治法解决邮局选址问题 C++\main.cpp
     文件      117760  2018-10-06 15:18  分治法解决邮局选址问题 C++\postoffice.exe
     文件      693944  2018-10-06 15:18  分治法解决邮局选址问题 C++\postoffice.ilk
     文件      888832  2018-10-06 15:18  分治法解决邮局选址问题 C++\postoffice.pdb