#includestdio.h
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、雅安服務(wù)器托管、營銷軟件、網(wǎng)站建設(shè)、鎮(zhèn)巴網(wǎng)站維護(hù)、網(wǎng)站推廣。
#includeconio.h
#includeiostream.h
#includestring.h
#includestdlib.h
#define
MAXVALUE
10000
/*權(quán)值最大值*/
#define
MAXLEAF
30
/*葉子最多個(gè)數(shù)*/
#define
MAXNODE
MAXLEAF*2-1
/*
結(jié)點(diǎn)數(shù)的個(gè)數(shù)*/
#define
MAXBIT
50
/*編碼的最大位數(shù)*/
typedef
struct
node
/*結(jié)點(diǎn)類型定義*/
{
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++)
/*結(jié)點(diǎn)初始化*/
{
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++)
/*對輸入字符按權(quán)值大小進(jìn)行排序*/
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++)
/*構(gòu)造huffman樹*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for
(j=0;jn+i;j++)/*尋找權(quán)值最小與次小的結(jié)點(diǎn)*/
{
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;
/*權(quán)值最小與次小的結(jié)點(diǎn)進(jìn)行組合*/
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++)
/*按結(jié)點(diǎn)位置進(jìn)行編碼*/
{
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++)
/*儲(chǔ)存編碼*/
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結(jié)束!
/"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)
/*計(jì)算字符個(gè)數(shù)與出現(xiàn)次數(shù)(即權(quán)值)*/
{
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();
}
這是我們的軟件實(shí)習(xí)答案，希望對你有幫助!
#include?stdio.h
#include?string.h
/*
本題要求各函數(shù)的參數(shù)使用指針
假設(shè)字母a、b、c、d、e、f的霍夫曼編碼分別是1、00、011、0100、01010、01011。那么字符串“abcdef”的編碼顯然就是字符串“10001101000101001011”。
（1）編寫編碼函數(shù)實(shí)現(xiàn)對字符串“abcdef”的編碼，顯示編碼結(jié)果。
（2）編寫譯碼函數(shù)對剛才得到的編碼進(jìn)行譯碼，顯示譯碼結(jié)果。
（3）假設(shè)有一段編碼“010111011010100100010010100”，請對其譯碼，并顯示譯碼結(jié)果。
*/
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）是圖像處理領(lǐng)域中，從圖像中識(shí)別幾何形狀的基本方法之一。主要識(shí)別具有某些相同特征的幾何形狀，例如直線，圓形，本篇博客的目標(biāo)就是從黑白圖像中識(shí)別出直線。
翻閱霍夫直線變換的原理時(shí)候，橡皮擦覺得原理部分需要先略過，否則很容易在這個(gè)地方陷進(jìn)去，但是問題來了，這個(gè)原理略過了，直接應(yīng)用函數(shù)，里面有些參數(shù)竟然看不懂。例如極坐標(biāo)，角度掃描范圍，這種函數(shù)就屬于繞不過去的知識(shí)點(diǎn)了，所以本文轉(zhuǎn)移方向，死磕原理，下面的博文將語無倫次的為你展示如何學(xué)習(xí)原理知識(shí)。
因?yàn)閿?shù)學(xué)知識(shí)的貧乏，所以在學(xué)習(xí)階段會(huì)涉及到很多基礎(chǔ)概念的學(xué)習(xí)，一起來吧。
首先找到相對官方的資料，打開該 地址
下面是一個(gè)數(shù)學(xué)小白對原理的學(xué)習(xí)經(jīng)驗(yàn)。
教材說：眾所周知，一條直線在圖像二維空間可由兩個(gè)變量表示。
抱歉，小白還真不知道……即使學(xué)習(xí)過，這些年也早已經(jīng)還給老師了。
一開始難道要學(xué)習(xí)笛卡爾坐標(biāo)系，不，你低估小白的能力了，我第一個(gè)查詢的是 θ 讀作 西塔 ，是一個(gè)希臘字母。
什么是笛卡爾坐標(biāo)系？
這個(gè)比較簡單，直角坐標(biāo)系。
斜率和截距
斜率，亦稱“角系數(shù)”，表示一條直線相對于橫坐標(biāo)軸的傾斜程度。
一條直線與某平面直角坐標(biāo)系橫坐標(biāo)軸正半軸方向的夾角的正切值即該直線相對于該坐標(biāo)系的斜率。
如果直線與 x 軸互相垂直，直角的正切直無窮大，故此直線不存在斜率。
對于一次函數(shù) y=kx+b ， k 就是該函數(shù)圖像的斜率。
在學(xué)習(xí)的時(shí)候，也學(xué)到如下內(nèi)容：
截距：對 x 的截距就是 y=0 時(shí)， x 的值，對 y 的截距就是 x=0 時(shí)， y 的值，
截距就是直線與坐標(biāo)軸的交點(diǎn)的橫（縱）坐標(biāo)。 x 截距為 a ， y 截距 b ，截距式就是： x/a+y/b=1（a≠0且b≠0） 。
斜率：對于任意函數(shù)上任意一點(diǎn)，其斜率等于其切線與 x 軸正方向所成的角，即 k=tanα 。 ax+by+c=0中，k=-a/b 。
什么是極坐標(biāo)系？
關(guān)于極坐標(biāo)系，打開 百度百科 學(xué)習(xí)一下即可。
重點(diǎn)學(xué)到下面這個(gè)結(jié)論就行：
找資料的時(shí)候，發(fā)現(xiàn)一個(gè)解釋的比較清楚的 博客 ，后續(xù)可以繼續(xù)學(xué)習(xí)使用。
繼續(xù)閱讀資料，看到如下所示的圖，這個(gè)圖也出現(xiàn)在了很多解釋原理的博客里面，但是圖下面寫了一句話
在這里直接蒙掉了，怎么就表示成極坐標(biāo)系了？上面這個(gè)公式依舊是笛卡爾坐標(biāo)系表示直線的方式呀，只是把 k 和 b 的值給替換掉了。
為何是這樣的，具體原因可以參照下圖。
centerchou 圖/center
繼續(xù)尋找關(guān)于霍夫變換的資料，找到一個(gè)新的概念 霍夫空間 。
在笛卡爾坐標(biāo)系中，一條直線可以用公式 表示，其中 k 和 b 是參數(shù)，表示的是斜率和截距。
接下來將方程改寫為 ，這時(shí)就建立了一個(gè)基于 k - b 的笛卡爾坐標(biāo)系。
此時(shí)這個(gè)新的方程在 k - b 坐標(biāo)系也有一個(gè)新的直線。
你可以在紙上畫出這兩個(gè)方程對應(yīng)的線和點(diǎn)，如下圖所示即可。
centerchou 圖/center
新的 k - b 坐標(biāo)系就叫做霍夫空間，這時(shí)得到一個(gè)結(jié)論，圖像空間 x - y 中的點(diǎn) 對應(yīng)了 霍夫空間 k - b 中的一條直線 ，即圖像空間的點(diǎn)與霍夫空間的直線發(fā)生了對應(yīng)關(guān)系。
如果在圖像空間 x - y 中在增加一個(gè)點(diǎn) ，那相應(yīng)的該點(diǎn)在霍夫空間也會(huì)產(chǎn)生相同的點(diǎn)與線的對應(yīng)關(guān)系，并且 A 點(diǎn)與 B 點(diǎn)產(chǎn)生的直線會(huì)在霍夫空間相交于一個(gè)點(diǎn)。而這個(gè)點(diǎn)的坐標(biāo)值 就是直線 AB 的參數(shù)。
如果到這里你掌握了，這個(gè)性質(zhì)就為我們解決直線檢測提供了方法，只需要把圖像空間的直線對應(yīng)到霍夫空間的點(diǎn)，然后統(tǒng)計(jì)交點(diǎn)就可以達(dá)到目的，例如圖像空間中有 3 條直線，那對應(yīng)到霍夫空間就會(huì)有 3 個(gè)峰值點(diǎn)。
遍歷圖像空間中的所有點(diǎn)，將點(diǎn)轉(zhuǎn)換到霍夫空間，形成大量直線，然后統(tǒng)計(jì)出直線交會(huì)的點(diǎn)，每個(gè)點(diǎn)的坐標(biāo)都是圖像空間直線方程參數(shù)，這時(shí)就能得到圖像空間的直線了。
上述的內(nèi)容沒有問題，但是存在一種情況是，當(dāng)直線趨近于垂直時(shí)，斜率 k 會(huì)趨近于無窮大，這時(shí)就沒有辦法轉(zhuǎn)換了，解決辦法是使用法線來表示直線。
上文提及的斜截式如下：
通過第二個(gè)公式，可以得到下述公式：
此時(shí)，我們可以帶入一些數(shù)值進(jìn)行轉(zhuǎn)換。
圖像空間有如下的幾個(gè)點(diǎn)：
轉(zhuǎn)換后的函數(shù)，都可以在霍夫空間 θ - ρ （橫坐標(biāo)是 θ ，縱坐標(biāo)是 ρ ）進(jìn)行表示。
原理這時(shí)就比較清晰了：
除了一些數(shù)學(xué)知識(shí)以外，經(jīng)典的博客我們也有必要記錄一下，方便后面學(xué)習(xí)的時(shí)候，進(jìn)行復(fù)盤。
本部分用于記錄本文中提及的相關(guān)數(shù)學(xué)原理，后續(xù)還要逐步埋坑。
今天涉及了一點(diǎn)點(diǎn)數(shù)學(xué)知識(shí)，能力限制，大家一起學(xué)習(xí)，有錯(cuò)誤的地方，可以在評論區(qū)指出，不勝感激。
希望今天的 1 個(gè)小時(shí)（今天內(nèi)容有點(diǎn)多，不一定可以看完），你有所收獲，我們下篇博客見~
相關(guān)閱讀
技術(shù)專欄
逗趣程序員
//* * * * * * * * * * * * * * * * * * * * * * * *
//哈夫曼樹的構(gòu)造哈夫曼樹,哈夫曼編碼 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include dos.h
#include conio.h
#include stdio.h
#include stdlib.h
#include string.h
typedef struct
{unsigned int weight; //結(jié)點(diǎn)權(quán)值
unsigned int parent,lchild,rchild; //結(jié)點(diǎn)的父指針，左右孩子指針
}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹
typedef char **HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表
void CreateHuffmanTree(HuffmanTree ,unsigned int*,int ); //生成一棵哈夫曼樹
void HuffmanCoding(HuffmanTree,HuffmanCode ,int ); //對哈夫曼樹進(jìn)行編碼
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //顯示哈夫曼編碼
void Select(HuffmanTree,int,int,int); //在數(shù)組中尋找權(quán)值最小的兩個(gè)結(jié)點(diǎn)
void main()
{HuffmanTree HT; //哈夫曼樹HT
HuffmanCode HC; //哈夫曼編碼表HC
int n,i; //n是哈夫曼樹葉子結(jié)點(diǎn)數(shù)
unsigned int *w; //w存放葉子結(jié)點(diǎn)權(quán)值
char j='y';
textbackground(3); //設(shè)定屏幕顏色
textcolor(15);
clrscr();
//程序解說
printf("本程序?qū)⒀菔緲?gòu)造哈夫曼樹.\n");
printf("首先輸入葉子結(jié)點(diǎn)數(shù)目.\n例如:8\n");
printf("然后輸入每個(gè)葉子結(jié)點(diǎn)的權(quán)值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("程序會(huì)構(gòu)造一棵哈夫曼樹并顯示哈夫曼編碼.\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("請輸入葉子結(jié)點(diǎn)數(shù)目:");
scanf("%d",n); //輸入葉子結(jié)點(diǎn)數(shù)
if(n=1) {printf("該數(shù)不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //開辟空間存放權(quán)值
printf("請輸入各葉子結(jié)點(diǎn)的權(quán)值:\n");
for(i=0;in;i++) scanf("%d",w[i]); //輸入各葉子結(jié)點(diǎn)權(quán)值
CreateHuffmanTree(HT,w,n); //生成哈夫曼樹
HuffmanCoding(HT,HC,n); //進(jìn)行哈夫曼編碼
PrintHuffmanCode(HC,w,n); //顯示哈夫曼編碼
printf("哈夫曼樹構(gòu)造完畢，還要繼續(xù)嗎?(Y/N)");
scanf(" %c",j);
}
}
void CreateHuffmanTree(HuffmanTree HT,unsigned int *w,int n)
{//w存放n個(gè)結(jié)點(diǎn)的權(quán)值，將構(gòu)造一棵哈夫曼樹HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n=1) return;
m=2*n-1; //n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，有2*n-1個(gè)結(jié)點(diǎn)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //開辟2*n各結(jié)點(diǎn)空間，0號單元不用
for(p=HT+1,i=1;i=n;++i,++p,++w) //進(jìn)行初始化
{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最小的兩個(gè)結(jié)點(diǎn)，其序號分別為s1和s2
HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2結(jié)點(diǎn)的父指針parent
HT[i].lchild=s1; HT[i].rchild=s2; //修改i結(jié)點(diǎn)的左右孩子指針
HT[i].weight=HT[s1].weight+HT[s2].weight; //修改權(quán)值
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)
{//將有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹HT進(jìn)行編碼， 所編的碼存放在HC中
//方法是從葉子到根逆向求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼
int i,c,f,start;
char *cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個(gè)編碼的頭指針向量
cd=(char *)malloc(n*sizeof(char)); //開辟一個(gè)求編碼的工作空間
cd[n-1]='\0'; //編碼結(jié)束符
for(i=1;i=n;++i) //逐個(gè)地求哈夫曼編碼
{start=n-1; //編碼結(jié)束位置
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個(gè)編碼分配空間
strcpy(HC[i],cd); //將編碼從cd復(fù)制到HC中
}
free(cd); //釋放工作空間
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//顯示有n個(gè)葉子結(jié)點(diǎ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且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號分別為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;}
}
重慶分公司
重慶分公司
