share.cpp

旅行商问题问题的二叉树求解方法

#include "share.h"
#include "graph.h"

/************************************************************************/
/*对一个数组进行排序
/************************************************************************/
void sort(arc * a,int n)//使用快速排序的方法
{
	Qsort(a,0,n-1);
}
/************************************************************************/
/* 对数组进行快速排序
/************************************************************************/
void Qsort(arc* a,int st,int en)
{
	int midd;
	if(st>=en){
		return;
	}else
	{
		midd = pati(a,st,en);//按照中间数据对数组进行调整
		Qsort(a,st,midd-1);//循环调用
		Qsort(a,midd+1,en);
	}
}

/************************************************************************/
/* 将数组中的数据分成两部分，以期中的一个数位中点
/************************************************************************/
int pati(arc * a,int st,int en)
{
	arc at = a[(st+en)/2];//取一个中间数据
	int i=st;
	int j=en;
	while (true) {
		while (a[i].weight<at.weight) {i++; }//选择和合适的数据调整位置
		while (a[j].weight>=at.weight) {j--;}
		if (i<j) {
		swap(a,i,j);
		}else break;
	}
	for (int t=st;t<en;t++) {
		if (a[t].weight==at.weight) {//将中间数据调整到合适的位置
			swap(a,i,t);
			break;
		}
	}
	return(i);
}
/************************************************************************/
/*交换数组中两个数据的位置
/************************************************************************/
void swap(arc* a,int i,int j)
{
	arc temp;
	temp.start = a[i].start;
	temp.end = a[i].end;
	temp.weight = a[i].weight;

	a[i].start = a[j].start;
	a[i].end = a[j].end;
	a[i].weight = a[j].weight;

	a[j].start = temp.start;
	a[j].end = temp.end;
	a[j].weight = temp.weight;

}