软件开发工具论文.docx
《软件开发工具论文.docx》由会员分享，可在线阅读，更多相关《软件开发工具论文.docx（18页珍藏版）》请在冰点文库上搜索。
软件开发工具论文
学号：
课程论文
课程名称
《软件开发工具》
论文题目
《对于赫夫曼编码的心得》
学院
计算机科学与技术学院
专业
软件工程
班级
姓名
指导教师
张能力
2012——2013学年第1学期
在大二学期开的一门数据结构课程，在大一的时候就听学长们说，数据结构这门课程很重要，学好了可以为以后的课程奠定下良好的基础，于是心中牢记着学长的这种叮咛，我抱着很认真地态度开始了这门课程的学习。
（1）结点的开辟。
（2）实现对输入字符串中出现的不同字符及其出现字数的信息记录。
（3）用叶子结点构造赫夫曼树。
（4）获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。
（5）输出各叶子结点元素及其对应的赫夫曼编码。
输出入的字符串的赫夫曼编码。
（6）调用各子函数
在算法的设计上，由于之前仅仅只是接触的书本上的赫夫曼树的编码，不仅显得有一些单薄，为了做好这个程序，我又在图书馆借阅了大量讲解赫夫曼编码的书籍。
首先按照课本中的定义，定义结构体node，其数据成员包括，字符型的元素a和整型元素b和指向node的next指针，来存储叶子结点的内容和权值。
定义三个指向node的指针head、p1、p2和字符指针n、t、h，调用setnode（）函数开辟一个结点让head指向该结点，p1=head,让n指向输入字符串的第一个元素，当n指向的内容不是‘\0’时，如果n指向字符串的第一个字符，则开辟一个结点，让p2指向该结点，让t指向字符串的第一个元素，当*t!
=‘\0’并且*t==*n则r++（r为整型，初始值为0），把p2->a=*n,p2->b=r,p1->next=p2,p1=p2,n++,t回到字符串首；否则i++（i为整型，初始值为1）r=0，j=1；让t指向字符串第一个元素，当*t！
=‘\0’，如果*t==*n，r++，t++；让h指向字符串的第一个元素，当h！
=n时如果*h==*n就跳出此循环，否则，j++，h++如果i==j则开辟新的结点p2->a=*n,p2->b=r,p1->next=p2,p1=p2
;n++,当把最后一个结点连入链表中，p1->next=NULL,然后把p1=head->next,当p!
=NULL时输出结点中叶子结点的元素和对应的权值；最后返回head。
在对于设置节点的算法时候遇见了麻烦，不知道是该怎样开辟一个新的节点，用new函数对于节点使用后的释放有一定的影响，经过查资料之后，我选择了setnode算法。
//setnode（）函数的算法：
设指向node的指针p，用malloc开辟一个node结点并让p指向该结点，返回p。
接下来便是重头戏----构造赫夫曼树了，定义结构体node1，其数据项字符型a（存放叶子结点元素）、整型weight（存放对应权值）、整型sign（起标记作用）、和指向左、右孩子及父母结点的指针lchild、rchild和parent。
整体的构思为，定义指向node1的指针p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=head->next，当p！
=NULL，n++，p=p->next，开辟可以存储2*n个node1的顺序表，让p0指向表头，p1=p0,p=head->next,当p！
=NULL时p1->a=p->a,p1->weight=p->
p1的指向左、右孩子及父母的指针指空，p=p->next，p1++；p1++,p=p->next;i=1,当i<=n-1,j=0,当j<2，如果j==0把‘‘1’赋给k1；否则把‘1’赋给k2；p2=p0，当p2！
=p1时，如果p2->sign==NULL并且m=p2->weight用break结束循环否则p2++；p2=p0，当p2！
=p时，如果m>=p2->weight并且p2->sign==NULL,把p2->weight赋给m，否则p2++；把p0赋给p2，当p2不等于p1时，如果m等于p2->weight并且p2->sign等于NULL，把‘1’赋给p2->sign,如果j=0，把p2赋给p1->lchild,p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j==1，则把p2赋给p1->rchild,p1->weight加p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j等于0，k1++，p2++；如果j等于1，k2++，p2++；j++；如果k1大于k2把p1->lchild赋给p3，p1->rchild赋给p4，p4赋给p1->lchild,p3赋给p1->rchild,p1->sign=NULL,p1++,i++;然后p--，把p1->parent=NULL,p1++,把p0赋给p2，当p2不等于p时输出p2的各数据项，拍p2++；返回p0。
接下来的步骤便是输出赫夫曼编码了。
其中，输出叶子结点的赫夫曼编码思路为设指向huffmancode的指针p，指向code的指针和指向字符型的指针base、top；把head1（函数的形参）赋给p，当p->a!
=NULL时，把0赋给n，p->head->next赋给h，当h！
=NULL时n++，h=h->next，开辟一个可以存储n+1个字符的栈，让base指向栈底，top=base,把h=p->head->next，当h！
=NULL时，*top=h->a，top++，h=h->next；top--，当to不等于base时，输出*top，top--;输出*top；p++。
然后，输出字符串的赫夫曼编码设计思路为设指向huffmancode的指针p1，指向code的指针h和指向字符型的指针base，top，p2，让p2指向字符串的第一个元素，当*p2！
=‘\0’时，输出*p2，p2++；当*p！
=‘\0’时（p为函数的形参），把0赋给n（n为整型）p1=p0（p0为形参）当p1->a!
=NULL时，如果p1->a等于*p把p1->head->next赋给h，当h！
=NULL时，h=h->next,base指向可以存储n+1个字符的栈底，top=base，把p1->head->next赋给h，当h！
=NULL，*top=h->a,top++,h=h->next，top自减，当top！
=base，输出*top，top--，输出*top，用break结束循环，p++。
在主函数中，我选择的是调用control（）函数。
在想好了设计之后，为了接下来的工作有条不紊的进行，我绘制了一个流程图。
在最后，我还有自己的一点想法想要说的，虽然我对于赫夫曼编码非常感兴趣，但是实际操作起来才深切的感受到，课本上讲的知识在对于实际操作起来，还是有很大的差距的。
如果想真的座椅电动吸出来，必须阅读大量的资料，参考大量的文献书籍，才能够实现举一反三，正正的做出东西来。
并且，学软件这一行的必须要亲自动手，不能坐享其成，毕竟软件是从国外流入中国的，既然学习了国外的先进知识，那么在于此同时，我们必须也要尊崇他们的传统，那就是支持原创！
合理的编程方法是我这次课程设计的最大收获。
附录：
主函数
//程序的编译环境是Visualstudio2010
//把统计叶子结点元素和权值的函数放在“计算权值.h”中
#include
usingnamespacestd;
typedefstructnode//存储叶子结点元素及其权值的结构体
{
chara;//叶子结点的元素
int
{
listnodehead,p1,p2;
char*n,*t,*h;
inti=1,j=1,r=0;
head=setnode（）;
p1=head;
for（n=a;*n!
='\0';n++）
{
if（n==a）
{
p2=setnode（）;
for（t=n;*t!
='\0';t++）//统计相同的字符在字符串中出现的次数
if（*t==*n）
r++;
p2->a=*n;
p2->b=r;
p1->next=p2;
p1=p2;
}
else
{
i++;
r=0;
j=1;
for（t=a;*t!
='\0';t++）
if（*t==*n）
r++;
for（h=a;h!
=n;h++）
{
if（*h==*n）
break;
else
j++;
}
if（i==j）
{
p2=setnode（）;//调用setnode（）函数开辟结点
p2->a=*n;
p2->b=r;
p1->next=p2;
p1=p2;
}
}
}
p1->next=NULL;
cout<<"电文的长度为：
"<cout<<"------------------------------------------------"<p1=head;
cout<<"叶子结点"<<"\t"<<"权值"<for（p1=p1->next;p1!
=NULL;p1=p1->next）
cout<a<<"\t\t"<b<cout<<"------------------------------------------------"<returnhead;
}
intcoutdata（listnodehead）//统计叶子结点的个数
{
listnodep;
intn=0;
for（p=head->next;p!
=NULL;p=p->next）
n++;
returnn;
}
//把构造赫夫曼树的函数放在头文件“构造赫夫曼树.h”中
#include
#include"计算权值.h"
usingnamespacestd;
typedefstructnode1//赫夫曼树的结点结构体
{
chara;//结点元素
intweight,sign;//结点的权值和结点的标记
structnode1*parent,*lchild,*rchild;//指向父母结点和左、右孩子的指针
}*listnode1;//指向node1的指针
listnode1settree（listnodehead）//构造赫夫曼树的函数
{
listnodep;
listnode1p0,p1,p2;
intm,n,i,j,k1,k2;
structnode1*p3,*p4;
n=0;
for（p=head->next;p!
=NULL;p=p->next）
n++;
p0=（listnode1）malloc（2*n*sizeof（node1））;//开辟可以存储2n个赫夫曼树结点的顺序表
p1=p0;
for（p=head->next;p!
=NULL;p=p->next）//把叶子结点的信息读入到顺序表中
{
p1->a=p->a;
p1->weight=p->b;
p1->lchild=NULL;
p1->parent=NULL;
p1->rchild=NULL;
p1->sign=NULL;
p1++;
}
for（i=1;i<=n-1;i++）
{
for（j=0;j<2;j++）
{
if（j==0）
k1=1;
elseif（j==1）k2=1;
for（p2=p0;p2!
=p1;p2++）
if（p2->sign==NULL）
{
m=p2->weight;
break;
}
for（p2=p0;p2!
=p1;p2++）
if（m>=p2->weight）
if（p2->sign==NULL）
m=p2->weight;
for（p2=p0;p2!
=p1;p2++）
{
if（m==p2->weight）
if（p2->sign==NULL）
{
p2->sign=1;
if（j==0）//把先找到的权值最小的作为左孩子
{
p1->lchild=p2;
p1->weight=p2->weight;
p2->parent=p1;
}
elseif（j==1）//把后找到的权值最小的最为右孩子
{
p1->rchild=p2;
p1->weight=p1->weight+p2->weight;
p2->parent=p1;
}
break;
}
if（j==0）
k1++;//标记先找到的权值最小的结点在顺序表中的位置
elseif（j==1）
k2++;//标记后找到的权值最小的结点在顺序表中的位置
}
}
if（k1>k2）/*如果先找到的权值最小的结点在顺序表中的位置在后找到的后面
{则他们父母结点的左右孩子指针交换*/
p3=p1->lchild;
p4=p1->rchild;
p1->lchild=p4;
p1->rchild=p3;
}
p1->sign=NULL;
p1++;
}
p1--;
p1->parent=NULL;
p1++;
p2=p0;
cout<<"叶子结点"<<"\t"<<"权值"<<"\t"<<"左孩子"<<"\t\t"<<"父母结点"<<"\t"<<"右孩子"<while（p2!
=p1）
{
cout<a<<"\t\t"<weight<<"\t"<lchild<<"\t"<parent<<"\t"<rchild<p2++;
}
cout<<"------------------------------------------------"<returnp0;
}
//把叶子结点赫夫曼编码的获取的函数放在头文件“获得赫夫曼编码.h”中
#include
#include"构造赫夫曼树.h"
usingnamespacestd;
typedefstructcode//存储赫夫曼编码的结构体
{
chara;//存储‘0’、‘1’编码
structcode*next;//指向链表下一个结点的指针
}*listcode;//指向该结构体的指针
typedefstructhuffmancode//存储叶子结点元素和赫夫曼编码链表的头指针的结构体
{
chara;//叶子结点的元素
listcodehead;//指向存储赫夫曼编码链表的指针
}*listhuffmancode;
listcodesetcode（）//开辟存储‘0’、‘1’编码结点的函数
{
listcodep;
p=（listcode）malloc（sizeof（code））;
returnp;
}
listhuffmancodegethuffmancode（listnode1p）//把得到的叶子结点及其{赫夫曼编码存到顺序表中的函数
listnode1p1,p2,p4;
intn=0;
listhuffmancodel,l1;
listcodeh,h1;
for（p2=p;p2->lchild==NULL&&p2->rchild==NULL;p2++）
n++;
l=（listhuffmancode）malloc（（n+1）*sizeof（huffmancode））;//开辟可以存储n+1个叶子结点信息的顺序表
l1=l;
for（p4=p;p4->lchild==NULL&&p4->rchild==NULL;p4++）
{
p1=p4;
h1=setcode（）;
l1->head=h1;
for（;p1->parent!
=NULL;p1=p1->parent）
{
if（p1==p1->parent->lchild）
{
h=setcode（）;
h->a='0';
h1->next=h;
h1=h;
}
elseif（p1==p1->parent->rchild）
{
h=setcode（）;
h->a='1';
h1->next=h;
h1=h;
}
}
h1->next=NULL;
l1->a=p4->a;
l1++;
}
l1->a=NULL;
returnl;
}
//把输出赫夫曼编码的函数放在头文件““输出赫夫曼编码.h”中
#include
#include"获得赫夫曼编码.h"
usingnamespacestd;
voidprinthuffmancode（listhuffmancodehead1）//输出叶子结点及其赫夫曼编码{的函数
listhuffmancodep;
p=head1;
listcodeh;
intn;
char*base,*top;
cout<<"叶子结点"<<"\t"<<"权值"<for（p=head1;p->a!
=NULL;p++）
{
cout<a<<"\t\t";
n=0;
h=p->head;
for（h=h->next;h!
=NULL;h=h->next）
n++;
base=（char*）malloc（（n+1）*sizeof（char））;
top=base;
h=p->head;
for（h=h->next;h!
=NULL;h=h->next）
{
*top=h->a;
top++;
}
top--;
for（;top!
=base;top--）
cout<<*top;
cout<<*top;
cout<}
cout<<"------------------------------------------------"<}
voidprint（char*p,listhuffmancodep0）//输出输入字符串的赫夫曼编码
{
listhuffmancodep1;
listcodeh;
intn;
char*base,*top,*p2;
cout<<"电文内容：
";
for（p2=p;*p2!
='\0';p2++）
cout<<*p2;
cout<cout<<"电文的赫夫曼编码：
";
for（;*p!
='\0';p++）
{
n=0;
for（p1=p0;p1->a!
=NULL;p1++）
if（p1->a==*p）
{
h=p1->head;
for（h=h->next;h!
=NULL;h=h->next）
n++;
base=（char*）malloc（（n+1）*sizeof（char））;
top=base;
h=p1->head;
for（h=h->next;h!
=NULL;h=h->next）
{
*top=h->a;
top++;
}
for（--top;top!
=base;top--）
cout<<*top;
cout<<*top;
break;
}
}
}
//把control函数放在头文件“控制函数.h”中
#include
#include"输出赫夫曼编码.h"
usingnamespacestd;
voidcontrol（）//调用各个功能函数
{
cout<<"数据结构课程设计"<cout<<"------------------------------------------------"<chara[20];
intn;
cout<<"接受到的电文内容（不超过20个字符）：
";
cin>>a;
listnodep;
p=getdata（a）;
n=coutdata（p）;
if（n==1）//如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树
{
p=p->next;
cout<<"该树只有一个叶子结点即根结点（根结点没有赫夫曼编码）>>"<cout<<"根结点"<<"\t\t"<<"权值"<cout<a<<"\t\t"<b<cout<<"------------------------------------------------"<}
else
{
listnode1p1;
p1=settree（p）;
listhuffmancodep2;
p2=gethuffmancode（p1）;
printhuffmancode（p2）;
print（a,p2）;
}
cout<}
//主函数放在源文件“赫夫曼编码.cpp“中
#include
#include"控制函数.h"
usingnamespacestd;
voidmain（）
{
control（）;//调用control函数
}
升级会员 