一、实验题目
二叉树两种存储结构的应用
二、实验目的和要求
1． 掌握二叉树的遍历思想及二叉树的存储实现。
2． 掌握二叉树的基本操作：建立二叉树、二叉树的遍历
3． 选择一种形式完成二叉树的显示
4． 掌握二叉树的常见算法的程序实现
5． 实验报告中要写出测试数据、错误分析以及收获
三、需求分析
本程序在c++6.0中运行，实现哈夫曼编码/译码系统
1.输入的形式和输入值的范围：由于本程序主要运用于字符的编码及译码，所以输入的值最好为字母；
2.输出的形式：发送信息的输出是由字符信息编辑赫夫曼代码，而接受者是由赫夫曼代码翻译的字符信息；
3.程序实现的功能：模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。；
4.测试数据：
a.输入字符及其相应的权值,例如“a 2 ,s 4 ,d 1”，建立赫夫曼树，输出各字符相应的赫夫曼编码,例如“字符：a 编码：01 字符：s,编码：1 字符：d 编码： 00”；
b.输入发送的信息“assdaaaasd”，输出“0111000101010100”；
c.输出接受到得信息是“assdaaaasd”。
四、概要设计
为了实现上述程序功能，需要定义二叉树an的抽象类型如下：
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素的集合。
数据关系R：
若D=Φ，则R=Φ，称BinaryTree为空二叉树；
若D≠Φ,则R={H},H是如下二元关系：
⑴在D中存在唯一的称为根的数据元素root，他在关系H下无前驱；
⑵若D-{root}≠Φ，则存在D-{root}={D1，Dr}，且D1∩Dr＝Φ；
⑶若D1≠Φ，则D1中存在唯一的元素x1,<root ,x1>∈H,且存在D1上的关系H1 H；若D≠Φ，则Dr中存在唯一的元素xr,<root, xr>∈H 且存在Dr上的关系Hr H；H={<root,x1>,<root,xr>,H1,Hr};
⑷(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是一棵符合本定义的二叉树，称为根的右子树。
基本操作：
InitBiTree(&T)
操作结果：构造空二叉树。
DestroyBiTree(&T)
初始条件：二叉树T存在。
操作结果：销毁二叉树。
CreateBiTree(&T，definition)
初始条件：definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
ClearBiTree(&T)
初始条件：二叉树T存在。
操作结果：将二叉树T清为空树。
Root(T)
初始条件：二叉树T存在。
操作结果：返回二叉树T的根。
BiTreeDepth(T)
初始条件：二叉树T存在。
操作结果：返回二叉树T的深度。
}ADT BinaryTree
2、本程序分为四个模块
a、主程序模块：
实现对函数的调用；
b、赫夫曼树模块：
实现赫夫曼树的建立；
c、编码模块：
将字符信息编码为二进制代码；
d、译码模块：
将二进制代码译码为字符信息。
3、各模块间的关系：
主程序模块
编码模块 译码模块
赫夫曼树模块
五、详细设计
1、定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子
typedef struct{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode;
存放赫夫曼树编码的结构体
typedef struct
{char bit[N];
char start;
}HuffmanCode;
2、赫夫曼树的基本操作
HuffmanCode* HuffmanCoding(HTNode *HT,char *character,int *w,int n)
//赫夫曼树的建立，及编码
void Decoding(HTNode *HT,int n)
//译码
void showcode(HuffmanCode *HC,int n)
//赫夫曼树编码的输出
部分操作的伪代码：
HuffmanCode* HuffmanCoding(HTNode *HT,char *character,int *w,int n)
{
int m,i,s1,s2;
HTNode *p;
int f,c,start;
char *cd;
HuffmanCode *HC;
m=2*n-1;
for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)
{p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}
for(;i<=m;++i,++p) {p->ch=0;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[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
{
HC=(HuffmanCode*)malloc((n+1)*sizeof(HuffmanCode));
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';
else cd[--start]='1';
strcpy(HC[i].bit,&cd[start]);
HC[i].start=HT[i].ch;
}
free(cd);
}
return HC;}
3、其它函数
void main()
//主函数
Void welcome()
//界面设计
select(HTNode *HT,int j,int *s1,int *s2)
//从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号
void find(HTNode *HT,char *code,char *text,int i,int m)
//译码时根据01字符串寻找相应叶子节点的递归算法
部分操作的伪代码
void select(HTNode *HT,int j,int *s1,int *s2)
{
int i;
//找weight最小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s1=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
*s1=i;
HT[*s1].parent=1;
//找weight次小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s2=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))
*s2=i;
}
4、函数间的调用关系
main
welcome
HuffmanCoding showcode Decoding
select find
六、调试分析
1、 本程序在编辑过程中遇到不少麻烦例如给字符数组一个一个赋值时，要考虑输入回车的情况，在多次试验及上网查询时加了getchar()这一步骤才得以实现；
2、 本程序的模块划分简单而合理,在操作方面比较容易，能很快了解线性表的顺序存储和链式存储结构下的基本运算；
3、 本实验程序设计中，将程序分为四个模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。
七、使用说明
1、程序名为树.exe，运行坏境为DOS.程序执行后显示
***************************************************
***********欢迎使用哈夫曼编码/译码系统*************
***************************************************
*** a-----创建赫夫曼树 ***
*** b----- 发 送 信 息 ***
*** c----- 接 受 信 息 ***
*** d----- 退 出 系 统 ***
***************************************************
请输入您所选内容的代号：
2、输入a进入创建赫夫曼树，然后编辑字符信息发送信息，并将信息存入文件中，然后接受者就能的到信息
八、测试结果
点击运行，进入菜单
1、输入“a”,按提示输入“3”再输入字符及其相应的权值 “a 2 ,s 4 ,d 1”输出 “字符：a 编码：01 字符：s,编码：1 字符：d 编码： 00”；
2、输入“b”，输入发送的信息“assdaaaasd”输出“0111000101010100”；
3、输入“c”输出接受到得信息是“assdaaaasd”。
4、输入d，退出系统。
九、实验总结
1、通过这次实验，对赫夫曼树的建立和赫夫曼编码及译码有了一定的了解；
2、在对字符串的复制时，要注意回车符号。
3、对一些大型实验，应该分工明确，各尽其职。
注：
第二篇：实验总结报告
实验报告
专业：______ 姓名：______ 学号：______日期：______ 桌号：______________ 课程名称： 模拟电子技术基础实验 指导老师： 成绩：________________ 实验名称： 实验总结报告
一、体会与收获
在这个学期中，我们一共完成了从常用电子仪器的使用到EDA 半导体器件特性仿真等五个实验课题。具体的实验情况在实验报告中已经很清楚的反映了。在此我想谈谈我的体会与收获。
首先，我们在试验中面临着很多问题。实验仪器就是其中之一。实验室中的很多仪器：示波器、交流毫伏表，确实是由于年代久远而不能正常工作。但我发现，很多同学在实验现象没出来的情况下就借口说是实验仪器的问题。其实不然。很多情况下，仪器没有调试好，导致现象不明显或者与理论相差甚远。
在做基本运算电路设计实验时，通过老师上课精彩的讲解使我感受到了一种“新的世界观”，认识到了理论学习和实验的区别，在以后做实验的时候要对所有器械保持怀疑的心态，坚持“自己测的才是准的”原则。
通过解决每一次实验出现的问题，我在做实验的时候变得更加有耐心。在连接电路前，都会认真分析一下实验原理。然后根据实验书和老师的ppt上的步骤一步一步的来做。果然，出现错误的几率小了很多。其次，做实验要养成好的习惯。很多同学在做实验的时候态度很随便。没有注意诸如：连线之前检查导线是否导通、用万用表测电阻时不质疑短接调零、链接电路是带电操作等等。也许，在很多人看来这些都是小问题。但真正每一次都做到一丝不苟，养成良好的习惯的同学并不多。
接下来，我想说的是实验的目的。刚开始，我认为实验是一项任务，只要完成了就行。无非就是照着课本连连线、得出个已经计算好的结果就行了。但自从自己做功放后我改变了这种看法。在做功放的时候，虽然原理图都是被人提前设计好的。但是在做得时候总是会需要自己去调试、布线。有时候看似连接的很完美的电路，可能会因为某个地方的虚焊而不能工作。这种情况非常锻炼你能力。在找错误的地方的时候你自然而然的明白了电路的原理。而且，当做好一个自己独立完成的功放后，会有一种成就感。
最后，我想说实验跟课本的理论相结合，在课本中学习，在实验中检验。在实验中发现，用课本知识去分析。兴趣就在这一个个的实验中激发了。当然，我明白大学的最终目的不是让我们去做一些诸如功放之类的东西，而是锻炼我们去探索、去发现、去学习的能力。可能我们做的某项东西很简单或者没有做成功，但那并不是失败，因为你已经学习到了许多。耐心并且细心的去做每一步，坚持严谨的态度做到最后。每一个人都是成功者。
二、意见与建议
对模电实验的建议：
①老师在讲课过程中的实物演示部分，可以用幻灯片播放拍摄的操作短片，或是在大屏幕上放出实物照片进行讲解，因为用第一排的仪器或元件直接讲解的话看的不是很清楚。
②实验室里除了后面的几台，前面也时不时有示波器故障，如果没有发现示波器已故障的话会给实验带来麻烦。因此希望老师可以教几个识别示波器是否故障的方法。
1
③选题方面，从元件的认识逐渐过渡到焊电路板进行实验，内容涵盖面合理，没有更多的建议了。
感谢老师半学期来的教诲和指导！
三、课程评价
在大学二年级的第一学期，我们按课程计划，完成了模电实验课程的学习，我感到收获很大。 老师在讲解实验课程时：教学内容丰富，授课生动、详细，思路清晰，富有逻辑性、启发性，而且善于激励学生兴趣，经常产生师生互动；他理论知识功底深厚，实践经验丰富，并且能够理论联系实际，举例生动形象，对模电的理论学习有很大帮助；教学方式得当，能够因材施教，给学生一个相对自我发展的空间。
他讲课时语言幽默，平易近人，关心学生，深受同学好评；讲课过程中认真负责，严格要求，把教书育人很好地结合起来。
通过模电实验课程，增强了我的动手能力，帮助我在以后的学习生活中能够顺利解决一些难题。希望学校今后能够为学生多开类似的课程，让在校的学生得到更多的锻炼机会。
2