N皇后问题

一、问题描述

在n行n列的棋谱上，放n个棋子，保证：这n个棋子任意两个不在同一行，不在同一列，并且也不在对角线上，这样的摆法有多少种？

二、解题思路

该代码的核心在于弄懂如何构建哈夫曼树和生成哈夫曼树编码。主要通过找出两个最小值开始作为最底端叶节点，由下到上构建出哈夫曼树。

代码实现

#include 
#include 

using namespace std;

const int MAXSIZE=20;
int *t=new int[MAXSIZE];
int sum=0;

bool place(int i){
    if(i<=1){
        return true;
    }
    for(int s=1; sn){
        cout<<"(";
        for(int k=1;k<=n;k++){
            if(k==n){
                cout<>n;
    backTrack(1,n);
    cout< 
 
 
哈夫曼树 
基本介绍
 
1.给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度1(wpl)达到最小，称这样的二叉树为哈夫曼树(HuffmanTree)
 
代码实现
 
#include 
#include 
#include 
 
typedef struct HTNode
{
	double weight;
	int parent;
	int lc, rc; 
}*HuffmanTree;
 
typedef char **HuffmanCode;
 
HuffmanTree initHuffmanTree(HuffmanTree& HT,int n)
{
	int i;
	int m = 2 * n - 1;
	HT = (HuffmanTree)malloc(sizeof(HTNode)*(m + 1));
	for(i = 0; i <= m; i++)
	{
		HT[i].lc = 0;
		HT[i].parent = 0;
		HT[i].rc = 0;
		HT[i].weight = 0;
	}
	return HT;
}
 
void Select(HuffmanTree& HT, int n, int& min1, int& min2)
{
	int min;
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0)
		{
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)
			min = i;
	}
	min1 = min;
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && i != min1)
		{
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && HT[i].weight < HT[min].weight&&i != min1)
			min = i;
	}
	min2 = min;
}
 
void CreateHuff(HuffmanTree& HT,double* w, int n)
{
	int m = 2 * n - 1; 
	for (int i = 1; i <= n; i++)
	{
		HT[i].weight = w[i - 1];
	}
	for (int i = n + 1; i <= m; i++)
	{
		int min1, min2;
		Select(HT, i - 1, min1, min2);
		HT[i].weight = HT[min1].weight + HT[min2].weight; 
		HT[min1].parent = i; 
		HT[min2].parent = i;
		HT[i].lc = min1; 
		HT[i].rc = min2;
	}
	printf("Huffman is: n");
	printf("subscript    weight     parent   lchild   rchildn");
	printf("0                                  n");
	for (int i = 1; i <= m; i++)
	{
	    printf("%-4d         %-6.2lf      %-6d     %-6d   %-6dn", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
	}
	printf("n");
}
 
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
	HC = (HuffmanCode)malloc(sizeof(char*)*(n + 1));
	char* code = (char*)malloc(sizeof(char)*n);
	code[n - 1] = '';
	for (int i = 1; i <= n; i++)
	{
		int start = n - 1; 
		int c = i; 
		int p = HT[c].parent; 
		while (p)
		{
			if (HT[p].lc == c) 
				code[--start] = '0';
			else
				code[--start] = '1';
			c = p;
			p = HT[c].parent; 
		}
		HC[i] = (char*)malloc(sizeof(char)*(n - start));
		strcpy(HC[i], &code[start]); 
	}
	free(code);
}
 
void test()
{
	int n = 0;
	printf("input the number of data: ");
	scanf("%d", &n);
	double* w = (double*)malloc(sizeof(double)*n);
	if (n >= 0)
	{
		printf("input the data: ");
	    for (int i = 0; i < n; i++)
	    {
	    	scanf("%lf", &w[i]);
	    }
    	HuffmanTree HT;
    	HT = initHuffmanTree(HT,n);
    	CreateHuff(HT, w, n); 
 
    	HuffmanCode HC;
    	HuffCoding(HT, HC, n); 
 
    	for (int i = 1; i <= n; i++)
    	{
    		printf("The data %.2lf code is:  %sn", HT[i].weight, HC[i]);
    	}
    	free(w);	
	}
	else
	{
		printf("malloc failn");
		return;
	}
}
 
int main()
{
	test();
	return 1;
}