1.1N皇后问题求解
N皇后问题是一个经典的问题，作为回溯的经典案例，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击），有多少摆法。有递归和非递归两种实现方式，现在用递归方法。
这里用一个N*N的矩阵来存储棋盘：a）算法开始, 清空棋盘，设当前行为第一行，当前列设为第一列； b）在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第d步；c ）在当前位置上满足条件的情形：在当前位置放一个皇后，若当前行是最后一行，则记录下来；若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个大测位置；若当前行是最后一行，当前列不是最后一列，当前列设为下一列；若当前行是最后一行，当前列是最后一列，回溯，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；以上返回到第b步；d）在当前位置上不满足条件的情形：若当前列不是最后一列，当前列设为下一列，返回到第b步；若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第b步;
具体实现
1.2判断能否放置
bool place(int* paraSolution, int paraT){
for (int j = 1; j < paraT; j ++)
{
if ((abs(paraT - j) == abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] == paraSolution[paraT]))
{
return false;
}
}//Of for
return true;
}//Of place
1.3回溯操作
void backtracking(int* paraSolution, int paraN, int paraT){
int i;
if (paraT > paraN)
{
for (i = 1; i <= paraN; i ++)
{
printf("%d ", paraSolution[i]);
}
printf("rn");
}else{
for (i = 1; i <= paraN; i ++)
{
paraSolution[paraT] = i;
if (place(paraSolution, paraT))
{
backtracking(paraSolution, paraN, paraT + 1);
}
}//Of for i
}//Of if
}//Of backtracking
1.4完整代码
#include#include #include //Place it there, applicable? bool place(int* paraSolution, int paraT){ for (int j = 1; j < paraT; j ++) { if ((abs(paraT - j) == abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] == paraSolution[paraT])) { return false; } }//Of for return true; }//Of place //Backtracking. void backtracking(int* paraSolution, int paraN, int paraT){ int i; if (paraT > paraN) { for (i = 1; i <= paraN; i ++) { printf("%d ", paraSolution[i]); } printf("rn"); }else{ for (i = 1; i <= paraN; i ++) { paraSolution[paraT] = i; if (place(paraSolution, paraT)) { backtracking(paraSolution, paraN, paraT + 1); } }//Of for i }//Of if }//Of backtracking //Title: n queens.
void nQueen(int paraN){ int i; int* solution = (int*)malloc((paraN + 1) * sizeof(int)); for (i = 0; i <= paraN; i ++) solution[i] = 0; backtracking(solution, paraN, 1); }//Of nQueen //The entrance. int main(){ nQueen(4); return 1; }//Of main
1.5运行结果
1 3 5 2 4 1 4 2 5 3 2 4 1 3 5 2 5 3 1 4 3 1 4 2 5 3 5 2 4 1 4 1 3 5 2 4 2 5 3 1 5 2 4 1 3 5 3 1 4 2 -------------------------------- Process exited after 0.1284 seconds with return value 1 请按任意键继续. . .
改变数据为四
2 4 1 3 3 1 4 2 --------------------------------
2.1哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优哈夫曼树。树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。权值就是定义的路径上面的值。可以这样理解为结点间的距离。二叉树的一种特殊情况。学长代码理解临摹。
实现：输入字符喘后统计每个字符出现次数，构造哈夫曼树，选择权重最小的两个节点，创建哈夫曼编码01，将读入的文件编码，写到txt文件 ，读入编码文件，解码 ，同样规则原样输出。
2.2具体实现
2.2.1结构体定义与初始化
typedef struct NODE
{
char c;
//结点权重
int weight;
//记录结点表示的二进制，左0右1
int binary;
//是否已经创建该结点，1为创建，0为未创建
int flag;//判断
struct NODE *lchild, *rchild, *parent;
} NODE, *PNODE;
typedef struct
{
int valuse[MAXSIZE];
int top;
} STACK;
//栈的相关操作
void initStack(STACK &stack)
{
stack.top = 0;
}
void push(STACK &stack, int value)
{
stack.valuse[stack.top++] = value;
}
int pop(STACK &stack)
{
if (stack.top == 0)
return -1;
stack.top--;
return stack.valuse[stack.top];
}
//初始化树结点
void initNode(PNODE node)
{
node->lchild = NULL;
node->parent = NULL;
node->rchild = NULL;
node->flag = 0;
node->weight = 0;
node->c = -1;
node->binary = 0;
}
2.2.2创建结点，param 新节点的权重
PNODE createNode(int weight)
{
PNODE node = (PNODE)malloc(sizeof(NODE));
if (node)
{
initNode(node);
node->weight = weight;
}
return node;
}
2.2.3进行字符，字符串的编码
对一棵具有n个叶子结点的哈夫曼树，若对树中的每个左分支赋0，右分支赋1（或左1右0），则从根到每个叶子的通路上，各个分支的赋值分别构成一个二进制串，哈夫曼编码为最优前缀编码，能使各种报文对应的二进制串的平均长度最短。param c 欲编码的字符 param childrenNodes 叶子结点的集合param lenOfNodes 叶子结点的个数return 返回保存该叶子结点路径的栈，param str 欲编码的字符串 ，param childrenNodes 哈夫曼树的叶子节点的集合，param lenOfNodes 叶子结点的个数， return 返回编码后的二进制字符串
STACK charEncode(char c, PNODE childrenNodes, int lenOfNodes)
{
STACK stack;
initStack(stack);
for (int i = 0; i < lenOfNodes; i++)
{
if (c == childrenNodes[i].c)
{
PNODE tmp = &childrenNodes[i];
while (tmp->parent != NULL)
{
push(stack, tmp->binary);
tmp = tmp->parent;
}
break;
}
}
return stack;
}
char *strEncode(char *str, PNODE childrenNodes, int lenOfNodes)
{
char *result = (char *)malloc(sizeof(char) * MAXSIZE * lenOfNodes);
int len = 0;
while (*str != ' ')
{
STACK stack = charEncode(*str, childrenNodes, lenOfNodes);
while (stack.top > 0)
{
result[len++] = pop(stack) + '0';
}
str++;
}
result[len] = ' ';
return result;
}
2.2.4获取权重最小节点
PNODE getMinWeightNode(PNODE nodes, int lenOfNodes)
{
PNODE node;
int min = 0, i;
//对已创建过的结点进行过滤
while (min < lenOfNodes)
{
if (nodes[min].flag == 0)
{
break;
}
min++;
}
if (min == lenOfNodes)
{
return NULL;
}
//查找未创建的结点中权重最小的结点
for (i = min + 1; i < lenOfNodes; i++)
{
if (nodes[i].flag == 0 && nodes[i].weight < nodes[min].weight)
{
min = i;
continue;
}
}
nodes[min].flag = 1;
return &nodes[min];
}
2.2.5进行创建通过叶子结点数创建哈夫曼树
PNODE createHuffmanTree(PNODE nodes, int lenOfNodes, PNODE childNode)
{
PNODE minWeightNode, parentNode;
minWeightNode = getMinWeightNode(nodes, lenOfNodes);
if (!minWeightNode)
return childNode;
if (!childNode)
{
parentNode = minWeightNode;
}
else
{
parentNode = createNode(childNode->weight + minWeightNode->weight);
if (childNode->weight < minWeightNode->weight)
{
parentNode->lchild = childNode;
parentNode->rchild = minWeightNode;
}
else
{
parentNode->rchild = childNode;
parentNode->lchild = minWeightNode;
}
parentNode->lchild->binary = 0;
parentNode->rchild->binary = 1;
childNode->parent = minWeightNode->parent = parentNode;
}
createHuffmanTree(nodes, lenOfNodes, parentNode);
}
2.2.6据字符出现频率创建哈夫曼树
PNODE readFromSource(const char *filePath, char *buff, PNODE childrenNodes, int &lenOfNodes)
{
//记录字符串长度
int lenOfStr = 0, i;
//记录当前读取的字符
char c;
FILE *file = fopen(filePath, "rb");
if (file == NULL)
{
puts("Can't find source file!");
exit(0);
}
//一个字符一个字符读入本地文本
c = fgetc(file);
while (!feof(file))
{
c = charTolowercase(c);
//初始化结点
initNode(&childrenNodes[lenOfNodes]);
buff[lenOfStr++] = c;
for (i = 0; i < lenOfNodes; i++)
{
if (childrenNodes[i].c == c)
{
childrenNodes[i].weight++;
break;
}
}
if (i == lenOfNodes)
{
childrenNodes[lenOfNodes].c = c;
childrenNodes[lenOfNodes++].weight++;
}
c = fgetc(file);
}
buff[lenOfStr] = ' ';
fclose(file);
return createHuffmanTree(childrenNodes, lenOfNodes, NULL);
}
2.2.7编码后的存入文件
void writeResult(const char *filePath, char *result)
{
FILE *fp = fopen(filePath, "sc");
if (fputs(result, fp) >= 0)
{
printf("生成结果成功rn");
}
fclose(fp);
}
2.2.8解压
char *strDecode(const char *str, PNODE TreeRoot)
{
const char *tmp = str;
char *result = (char *)malloc(sizeof(char) * MAXSIZE);
//用来记录结果字符串的长度
int len = 0;
while (*tmp != ' ')
{
PNODE tmpNode = TreeRoot;
while (tmpNode->lchild && tmpNode->rchild)
{
tmpNode = *tmp == '0' ? tmpNode->lchild : tmpNode->rchild;
tmp++;
}
result[len++] = tmpNode->c;
}
result[len] = ' ';
return result;
}
