12-12.c

含有大量数据结构的源代码 请大家漫漫品味

#include <stdlib.h>  
#include <stdio.h>
#include <malloc.h>
typedef int DataType;
typedef struct {
	int *x, // 到达当前节点的路径
	*bestx, // 目前的最优排列
	*total, // total[j] = 带插槽j的板的数目
	*now, // now[j] = 在含插槽j的部分排列中的板的数目
	bestd, // bestx的密度
	n, //板的数目
	m, // 插槽的数目
	**B; // 板的二维数组
}Board;
void Swap(DataType *a,DataType *b)
{
		DataType *t=a;
		*a=*b;
		*b=*t;
}
void BestOrder(Board *b,int i, int cd)
{// 按回溯算法搜索排列树
	int j,ld,k;
	if (i == b->n) 
	{
		for (j=1; j<=b->n;j++)
			b->bestx[j] = b->x[j];
			b->bestd = cd;
	}
	else // 尝试子树
		for(j = i; j <= b->n; j++) 
		{// 用x[j] 作为下一块电路板对孩子进行尝试
		// 在最后一个插槽更新并计算密度
			ld = 0;
			for (k = 1; k <= b->m; k++) 
			{
				b->now[k]+=b->B[b->x[j]][k];
				if (b->now[k] > 0 && b->total[k] != b->now[k])
					ld++;
			}
			// 更新ld 为局部排列的总密度
			if(cd > ld) 
				ld = cd;
			// 仅当子树中包含一个更优的排列时，搜索该子树
			if(ld <b->bestd) 
			{// 移动到孩子
				Swap(&b->x[i],&b->x[j]);
				BestOrder(b,i+1, ld);
				Swap(&b->x[i], &b->x[j]);
				}
			// 重置
			for (k = 1; k <= b->m; k++)
				b->now[k] -= b->B[b->x[j]][k];

		}
}
int ArrangeBoards(int **B, int n, int m, int bestx[])
{// 返回最优密度
// 在bestx中返回最优排列
	int i,j;
	Board X;
	// 初始化X
	X.x=(int*)malloc(sizeof(int)*(n+1));
	X.total =(int*)malloc(sizeof(int)*(m+1));
	X.now=(int*)malloc(sizeof(int)*(m+1));
	X.B =B;
	X.n = n;
	X.m = m;
	X.bestx = bestx;
	X.bestd = m + 1;
	// 初始化total和now
	for(i = 1; i <= m; i++)
	{
		X.total[i] = 0;
		X.now[i] = 0;
	}
	// 初始化x并计算t o t a l
	for(i = 1; i <= n; i++) 
	{
		X.x[i] = i;
		for(j = 1; j <= m; j++)
			X.total[j]+= B[i][j];
	}
	// 寻找最优排列
	BestOrder(&X,1 , 0 ) ;
	free(X.x);
	free(X.total);
	free(X.now);
	return X.bestd;
}
void main()
{
	int **B,  n,  m, *bestx;
	//初始化B,  n,  m, *bestx
	ArrangeBoards(B,n,m,bestx);
}