#includestdio.h
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、雅安服务器托管、营销软件、网站建设、镇巴网站维护、网站推广。
#includeconio.h
#includeiostream.h
#includestring.h
#includestdlib.h
#define
MAXVALUE
10000
/*权值最大值*/
#define
MAXLEAF
30
/*叶子最多个数*/
#define
MAXNODE
MAXLEAF*2-1
/*
结点数的个数*/
#define
MAXBIT
50
/*编码的最大位数*/
typedef
struct
node
/*结点类型定义*/
{
char
letter;
int
weight;
int
parent;
int
lchild;
int
rchild;
}HNodeType;
typedef
struct
/*编码类型定义*/
{
char
letter;
int
bit[MAXBIT];
int
start;
}HCodeType;
typedef
struct
/*输入符号的类型*/
{
char
s;
int
num;
}lable;
void
HuffmanTree(HNodeType
HuffNode[],int
n,lable
a[])
{
int
i,j,m1,m2,x1,x2,temp1;
char
temp2;
for
(i=0;i2*n-1;i++)
/*结点初始化*/
{
HuffNode[i].letter=0;
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for
(i=0;in-1;i++)
for
(j=i+1;jn-1;j++)
/*对输入字符按权值大小进行排序*/
if
(a[j].numa[i].num)
{
temp1=a[i].num;
a[i].num=a[j].num;
a[j].num=temp1;
temp2=a[i].s;
a[i].s=a[j].s;
a[j].s=temp2;
}
for
(i=0;in;i++)
{
HuffNode[i].weight=a[i].num;
HuffNode[i].letter=a[i].s;
}
for
(i=0;in-1;i++)
/*构造huffman树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for
(j=0;jn+i;j++)/*寻找权值最小与次小的结点*/
{
if
(HuffNode[j].parent==-1HuffNode[j].weightm1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else
if
(HuffNode[j].parent==-1HuffNode[j].weightm2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
/*权值最小与次小的结点进行组合*/
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
}
void
HuffmanCode(int
n,lable
a[])
{
HNodeType
HuffNode[MAXNODE];
HCodeType
HuffCode[MAXLEAF],cd;
int
i,j,c,p;
HuffmanTree(HuffNode,n,a);
for
(i=0;in;i++)
/*按结点位置进行编码*/
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while
(p!=-1)
{
if
(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for
(j=cd.start+1;jn;j++)
/*储存编码*/
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
for
(i=0;in;i++)
{
HuffCode[i].letter=HuffNode[i].letter;
printf("
%c
",HuffCode[i].letter);
for
(j=HuffCode[i].start+1;jn;j++)
printf("%d",HuffCode[i].bit[j]);
printf("\n");
}
}
int
main()
{
lable
data[30];
char
s[100],*p;
int
i,count=0;
for
(;;)
{
cout"
/
求哈夫曼编码,直到输入为end结束!
/"endl;
printf("
Input
some
letters:");
scanf("%s",s);
if
(!strcmp(s,"end"))
exit(0);
for
(i=0;i30;i++)
{
data[i].s=0;
data[i].num=0;
}
p=s;
while
(*p)
/*计算字符个数与出现次数(即权值)*/
{
for
(i=0;i=count+1;i++)
{
if
(data[i].s==0)
{
data[i].s=*p;
data[i].num++;
count++;
break;
}
else
if
(data[i].s==*p)
{
data[i].num++;
break;
}
}
p++;
}
printf("\n");
printf("
different
letters:%d\n",count);
for
(i=0;icount;i++)
{
printf("
%c
",data[i].s);
printf("weight:%d\n",data[i].num);
}
HuffmanCode(count,data);
count=0;
}
getch();
}
这是我们的软件实习答案，希望对你有帮助!
#include stdio.h
#include string.h
/*
本题要求各函数的参数使用指针
假设字母a、b、c、d、e、f的霍夫曼编码分别是1、00、011、0100、01010、01011。那么字符串“abcdef”的编码显然就是字符串“10001101000101001011”。
（1）编写编码函数实现对字符串“abcdef”的编码，显示编码结果。
（2）编写译码函数对刚才得到的编码进行译码，显示译码结果。
（3）假设有一段编码“010111011010100100010010100”，请对其译码，并显示译码结果。
*/
char hufman[6][10] = {
{"a1"},
{"b00"},
{"c011"},
{"d0100"},
{"e01010"},
{"f01011"},
};
void code(char *src,char *dest)
{
int i;
int len = 0;
while(*src != '\0')
{
for(i=0;i6;i++)
{
if(*src == hufman[i][0])
{
strcpy(dest + len,hufman[i]+1);
len += strlen(hufman[i]+1);
break;
}
}
src ++;
}
}
void decode(char *src,char *dest)
{
int i;
int len = 0;
while(*src != '\0')
{
for(i=0;i6;i++)
{
if(strncmp(src,hufman[i]+1,strlen(hufman[i]+1)) == 0)
{
dest[len++] = hufman[i][0];
src += strlen(hufman[i]+1);
break;
}
}
}
dest[len] = 0;
}
int main(int argc,char *argv[])
{
char *str = "abcdef";
char *str1 = "010111011010100100010010100";
char res[100] = {0};
char decodeRes[20];
code(str,res);
printf("%s\n",res);
decode(res,decodeRes);
printf("%s\n",decodeRes);
decode(str1,decodeRes);
printf("%s\n",decodeRes);
}
霍夫变换（Hough Transform）是图像处理领域中，从图像中识别几何形状的基本方法之一。主要识别具有某些相同特征的几何形状，例如直线，圆形，本篇博客的目标就是从黑白图像中识别出直线。
翻阅霍夫直线变换的原理时候，橡皮擦觉得原理部分需要先略过，否则很容易在这个地方陷进去，但是问题来了，这个原理略过了，直接应用函数，里面有些参数竟然看不懂。例如极坐标，角度扫描范围，这种函数就属于绕不过去的知识点了，所以本文转移方向，死磕原理，下面的博文将语无伦次的为你展示如何学习原理知识。
因为数学知识的贫乏，所以在学习阶段会涉及到很多基础概念的学习，一起来吧。
首先找到相对官方的资料，打开该 地址
下面是一个数学小白对原理的学习经验。
教材说：众所周知，一条直线在图像二维空间可由两个变量表示。
抱歉，小白还真不知道……即使学习过，这些年也早已经还给老师了。
一开始难道要学习笛卡尔坐标系，不，你低估小白的能力了，我第一个查询的是 θ 读作 西塔 ，是一个希腊字母。
什么是笛卡尔坐标系？
这个比较简单，直角坐标系。
斜率和截距
斜率，亦称“角系数”，表示一条直线相对于横坐标轴的倾斜程度。
一条直线与某平面直角坐标系横坐标轴正半轴方向的夹角的正切值即该直线相对于该坐标系的斜率。
如果直线与 x 轴互相垂直，直角的正切直无穷大，故此直线不存在斜率。
对于一次函数 y=kx+b ， k 就是该函数图像的斜率。
在学习的时候，也学到如下内容：
截距：对 x 的截距就是 y=0 时， x 的值，对 y 的截距就是 x=0 时， y 的值，
截距就是直线与坐标轴的交点的横（纵）坐标。 x 截距为 a ， y 截距 b ，截距式就是： x/a+y/b=1（a≠0且b≠0） 。
斜率：对于任意函数上任意一点，其斜率等于其切线与 x 轴正方向所成的角，即 k=tanα 。 ax+by+c=0中，k=-a/b 。
什么是极坐标系？
关于极坐标系，打开 百度百科 学习一下即可。
重点学到下面这个结论就行：
找资料的时候，发现一个解释的比较清楚的 博客 ，后续可以继续学习使用。
继续阅读资料，看到如下所示的图，这个图也出现在了很多解释原理的博客里面，但是图下面写了一句话
在这里直接蒙掉了，怎么就表示成极坐标系了？上面这个公式依旧是笛卡尔坐标系表示直线的方式呀，只是把 k 和 b 的值给替换掉了。
为何是这样的，具体原因可以参照下图。
centerchou 图/center
继续寻找关于霍夫变换的资料，找到一个新的概念 霍夫空间 。
在笛卡尔坐标系中，一条直线可以用公式 表示，其中 k 和 b 是参数，表示的是斜率和截距。
接下来将方程改写为 ，这时就建立了一个基于 k - b 的笛卡尔坐标系。
此时这个新的方程在 k - b 坐标系也有一个新的直线。
你可以在纸上画出这两个方程对应的线和点，如下图所示即可。
centerchou 图/center
新的 k - b 坐标系就叫做霍夫空间，这时得到一个结论，图像空间 x - y 中的点 对应了 霍夫空间 k - b 中的一条直线 ，即图像空间的点与霍夫空间的直线发生了对应关系。
如果在图像空间 x - y 中在增加一个点 ，那相应的该点在霍夫空间也会产生相同的点与线的对应关系，并且 A 点与 B 点产生的直线会在霍夫空间相交于一个点。而这个点的坐标值 就是直线 AB 的参数。
如果到这里你掌握了，这个性质就为我们解决直线检测提供了方法，只需要把图像空间的直线对应到霍夫空间的点，然后统计交点就可以达到目的，例如图像空间中有 3 条直线，那对应到霍夫空间就会有 3 个峰值点。
遍历图像空间中的所有点，将点转换到霍夫空间，形成大量直线，然后统计出直线交会的点，每个点的坐标都是图像空间直线方程参数，这时就能得到图像空间的直线了。
上述的内容没有问题，但是存在一种情况是，当直线趋近于垂直时，斜率 k 会趋近于无穷大，这时就没有办法转换了，解决办法是使用法线来表示直线。
上文提及的斜截式如下：
通过第二个公式，可以得到下述公式：
此时，我们可以带入一些数值进行转换。
图像空间有如下的几个点：
转换后的函数，都可以在霍夫空间 θ - ρ （横坐标是 θ ，纵坐标是 ρ ）进行表示。
原理这时就比较清晰了：
除了一些数学知识以外，经典的博客我们也有必要记录一下，方便后面学习的时候，进行复盘。
本部分用于记录本文中提及的相关数学原理，后续还要逐步埋坑。
今天涉及了一点点数学知识，能力限制，大家一起学习，有错误的地方，可以在评论区指出，不胜感激。
希望今天的 1 个小时（今天内容有点多，不一定可以看完），你有所收获，我们下篇博客见~
相关阅读
技术专栏
逗趣程序员
//* * * * * * * * * * * * * * * * * * * * * * * *
//哈夫曼树的构造哈夫曼树,哈夫曼编码 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include dos.h
#include conio.h
#include stdio.h
#include stdlib.h
#include string.h
typedef struct
{unsigned int weight; //结点权值
unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
void CreateHuffmanTree(HuffmanTree ,unsigned int*,int ); //生成一棵哈夫曼树
void HuffmanCoding(HuffmanTree,HuffmanCode ,int ); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码
void Select(HuffmanTree,int,int,int); //在数组中寻找权值最小的两个结点
void main()
{HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
int n,i; //n是哈夫曼树叶子结点数
unsigned int *w; //w存放叶子结点权值
char j='y';
textbackground(3); //设定屏幕颜色
textcolor(15);
clrscr();
//程序解说
printf("本程序将演示构造哈夫曼树.\n");
printf("首先输入叶子结点数目.\n例如:8\n");
printf("然后输入每个叶子结点的权值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");
printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n");
printf(" 23---00\n 3---0111\n 11---010\n");
while(j!='N'j!='n')
{printf("请输入叶子结点数目:");
scanf("%d",n); //输入叶子结点数
if(n=1) {printf("该数不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值
printf("请输入各叶子结点的权值:\n");
for(i=0;in;i++) scanf("%d",w[i]); //输入各叶子结点权值
CreateHuffmanTree(HT,w,n); //生成哈夫曼树
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
PrintHuffmanCode(HC,w,n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c",j);
}
}
void CreateHuffmanTree(HuffmanTree HT,unsigned int *w,int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n=1) return;
m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用
for(p=HT+1,i=1;i=n;++i,++p,++w) //进行初始化
{p-weight=*w;
p-parent=0;
p-lchild=0;
p-rchild=0;
}
for(;i=m;++i,++p)
{p-weight=0;
p-parent=0;
p-lchild=0;
p-rchild=0;
}
for(i=n+1;i=m;++i) //建哈夫曼树
{Select(HT,i-1,s1,s2);
//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2结点的父指针parent
HT[i].lchild=s1; HT[i].rchild=s2; //修改i结点的左右孩子指针
HT[i].weight=HT[s1].weight+HT[s2].weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)
{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i,c,f,start;
char *cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针向量
cd=(char *)malloc(n*sizeof(char)); //开辟一个求编码的工作空间
cd[n-1]='\0'; //编码结束符
for(i=1;i=n;++i) //逐个地求哈夫曼编码
{start=n-1; //编码结束位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
if(HT[f].lchild==c) cd[--start]='0'; //若是左孩子编为'0'
else cd[--start]='1'; //若是右孩子编为'1'
HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(HC[i],cd); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("HuffmanCode is :\n");
for(i=1;i=n;i++)
{printf(" %3d---",w[i-1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT,int t,ints1,ints2)
{//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2
int i,m,n;
m=n=10000;
for(i=1;i=t;i++)
{if(HT[i].parent==0(HT[i].weightm||HT[i].weightn))
if(mn)
{n=HT[i].weight;s2=i;}
else {m=HT[i].weight;s1=i;}
}
if(s1s2) //s1放较小的序号
{i=s1;s1=s2;s2=i;}
}
重庆分公司
重庆分公司
