软件开发工具论文文档格式.docx
《软件开发工具论文文档格式.docx》由会员分享，可在线阅读，更多相关《软件开发工具论文文档格式.docx（18页珍藏版）》请在冰点文库上搜索。
最后返回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++；
=p时，如果m>
=p2->
weight并且p2->
sign==NULL,把p2->
weight赋给m，否则p2++；
把p0赋给p2，当p2不等于p1时，如果m等于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->
如果j等于0，k1++，p2++；
如果j等于1，k2++，p2++；
j++；
如果k1大于k2把p1->
lchild赋给p3，p1->
rchild赋给p4，p4赋给p1->
lchild,p3赋给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->
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->
=NULL时，如果p1->
a等于*p把p1->
=NULL时，h=h->
next,base指向可以存储n+1个字符的栈底，top=base，把p1->
=NULL，*top=h->
a,top++,h=h->
next，top自减，当top！
=base，输出*top，top--，输出*top，用break结束循环，p++。
在主函数中，我选择的是调用control（）函数。
在想好了设计之后，为了接下来的工作有条不紊的进行，我绘制了一个流程图。
在最后，我还有自己的一点想法想要说的，虽然我对于赫夫曼编码非常感兴趣，但是实际操作起来才深切的感受到，课本上讲的知识在对于实际操作起来，还是有很大的差距的。
如果想真的座椅电动吸出来，必须阅读大量的资料，参考大量的文献书籍，才能够实现举一反三，正正的做出东西来。
并且，学软件这一行的必须要亲自动手，不能坐享其成，毕竟软件是从国外流入中国的，既然学习了国外的先进知识，那么在于此同时，我们必须也要尊崇他们的传统，那就是支持原创！
合理的编程方法是我这次课程设计的最大收获。
附录：
主函数
//程序的编译环境是Visualstudio2010
//把统计叶子结点元素和权值的函数放在“计算权值.h”中
#include<
iostream>
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!
t++）//统计相同的字符在字符串中出现的次数
if（*t==*n）
r++;
p2->
a=*n;
b=r;
p1->
next=p2;
p1=p2;
}
else
i++;
r=0;
j=1;
for（t=a;
t++）
if（*t==*n）
r++;
for（h=a;
h!
=n;
h++）
if（*h==*n）
break;
j++;
if（i==j）
//调用setnode（）函数开辟结点
next=NULL;
cout<
<
"
电文的长度为：
i<
endl;
------------------------------------------------"
叶子结点"
\t"
权值"
for（p1=p1->
p1!
=NULL;
p1=p1->
next）
p1->
a<
\t\t"
b<
returnhead;
intcoutdata（listnodehead）//统计叶子结点的个数
listnodep;
intn=0;
for（p=head->
p!
p=p->
n++;
returnn;
//把构造赫夫曼树的函数放在头文件“构造赫夫曼树.h”中
#include"
计算权值.h"
typedefstructnode1//赫夫曼树的结点结构体
{
//结点元素
intweight,sign;
//结点的权值和结点的标记
structnode1*parent,*lchild,*rchild;
//指向父母结点和左、右孩子的指针
}*listnode1;
//指向node1的指针
listnode1settree（listnodehead）//构造赫夫曼树的函数
listnode1p0,p1,p2;
intm,n,i,j,k1,k2;
structnode1*p3,*p4;
n=0;
p0=（listnode1）malloc（2*n*sizeof（node1））;
//开辟可以存储2n个赫夫曼树结点的顺序表
p1=p0;
next）//把叶子结点的信息读入到顺序表中
a;
b;
lchild=NULL;
parent=NULL;
rchild=NULL;
sign=NULL;
p1++;
for（i=1;
=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;
if（m>
weight）
if（p2->
m=p2->
if（m==p2->
{
p2->
sign=1;
if（j==0）//把先找到的权值最小的作为左孩子
{
p1->
lchild=p2;
weight=p2->
p2->
parent=p1;
}
elseif（j==1）//把后找到的权值最小的最为右孩子
rchild=p2;
weight=p1->
weight+p2->
break;
if（j==0）
k1++;
//标记先找到的权值最小的结点在顺序表中的位置
elseif（j==1）
k2++;
//标记后找到的权值最小的结点在顺序表中的位置
if（k1>
k2）/*如果先找到的权值最小的结点在顺序表中的位置在后找到的后面
{则他们父母结点的左右孩子指针交换*/
p3=p1->
lchild;
p4=p1->
rchild;
lchild=p4;
rchild=p3;
}
p1--;
p2=p0;
左孩子"
\t\t"
父母结点"
右孩子"
//输出构造的赫夫曼树
while（p2!
=p1）
p2->
weight<
lchild<
parent<
rchild<
p2++;
returnp0;
//把叶子结点赫夫曼编码的获取的函数放在头文件“获得赫夫曼编码.h”中
构造赫夫曼树.h"
typedefstructcode//存储赫夫曼编码的结构体
//存储‘0’、‘1’编码
structcode*next;
//指向链表下一个结点的指针
}*listcode;
//指向该结构体的指针
typedefstructhuffmancode//存储叶子结点元素和赫夫曼编码链表的头指针的结构体
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;
lchild==NULL&
&
rchild==NULL;
l=（listhuffmancode）malloc（（n+1）*sizeof（huffmancode））;
//开辟可以存储n+1个叶子结点信息的顺序表
l1=l;
for（p4=p;
p4->
p4++）
p1=p4;
h1=setcode（）;
l1->
head=h1;
for（;
parent!
parent）
if（p1==p1->
parent->
lchild）
h=setcode（）;
h->
a='
0'
h1->
next=h;
h1=h;
elseif（p1==p1->
rchild）
1'
h1->
a=p4->
l1++;
a=NULL;
returnl;
//把输出赫夫曼编码的函数放在头文件““输出赫夫曼编码.h”中
获得赫夫曼编码.h"
voidprinthuffmancode（listhuffmancodehead1）//输出叶子结点及其赫夫曼编码{的函数
listhuffmancodep;
p=head1;
listcodeh;
intn;
char*base,*top;
cout<
for（p=head1;
p->
p++）
h=p->
head;
for（h=h->
h=h->
n++;
base=（char*）malloc（（n+1）*sizeof（char））;
top=base;
*top=h->
top++;
top--;
for（;
top!
=base;
top--）
cout<
*top;
voidprint（char*p,listhuffmancodep0）//输出输入字符串的赫夫曼编码
listhuffmancodep1;
listcodeh;
char*base,*top,*p2;
电文内容：
*p2!
*p2;
电文的赫夫曼编码：
*p!
for（p1=p0;
p1++）
if（p1->
a==*p）
h=p1->
for（h=h->
n++;
base=（char*）malloc（（n+1）*sizeof（char））;
top=base;
*top=h->
top++;
for（--top;
cout<
cout<
}
//把control函数放在头文件“控制函数.h”中
输出赫夫曼编码.h"
voidcontrol（）//调用各个功能函数
数据结构课程设计"
chara[20];
intn;
接受到的电文内容（不超过20个字符）：
cin>
>
p=getdata（a）;
n=coutdata（p）;
if（n==1）//如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树
p=p->
该树只有一个叶子结点即根结点（根结点没有赫夫曼编码）>
根结点"
listnode1p1;
p1=settree（p）;
listhuffmancodep2;
p2=gethuffmancode（p1）;
printhuffmancode（p2）;
print（a,p2）;
endl<
程序结束................"
//主函数放在源文件“赫夫曼编码.cpp“中
控制函数.h"
voidmain（）
control（）;
//调用control函数
升级会员 