数据库课程设计霍夫曼编码Word格式.docx
《数据库课程设计霍夫曼编码Word格式.docx》由会员分享，可在线阅读，更多相关《数据库课程设计霍夫曼编码Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
展示编码所有数据、编码全过程、霍夫曼编码背景。
●界面展示：
输入窗口：
全部过程显示：
“关于”：
编码窗口：
编码显示窗口：
二、实现思想及部分算法
●基本思想：
1）建立inputting对象，从文本框中接受输入的数据或者随机生成的数据保存在初始数组START中
2）在类card—expl类中，建立Huffman—basic对象h，接受输入窗口传入的数据，初始化最小堆minheap（用数组实现，每个元素是一个节点对象node），并设置h中相应的状态布尔值，调整为开始，未选中
3）在card—expl类中初始化卡片布局，并将graphics对象调用trap（即单步执行）方法画好图的jpanel添加在卡片中
4）弹出编码窗口，点击“上一步”、“下一步”即可翻到卡片的上一页下一页，察看选中、新建的二叉树及其霍夫曼编码
●单步运行方式：
使用huffuman类中的trap算法实现。
Huffuman中有两个布尔变量分别标识当前霍夫曼树的运行状态（是否执行，选中还是合并），以此进入traping（选中）或trap2（合并）方法：
Traping方法中，将最小堆中的前两个元素（即两个最小的元素）标记为已选中，trap2方法中将删除最小堆中两个元素并将二者的权值相加合并为新元素，原来两节点作为左右子树（左小右大）重新插入最小堆。
●画图方式：
graphics—basic类继承jpanel，实现每一个node节点的画图；
其中递归调用方法draw（intx,inty,nodem,Graphicsg）传入变量分别为起始的x，y坐标，二叉树，Graphics对象，图面板的大小通过node变量的左右延伸来确定：
上一层每一边比下一层多出2^（level-2）-1宽度
●编码实现方式：
最小堆中每一个节点分别递归，coding（noderoot,Strings）递归遍历节点——左子树编码参数加“0”，右子树编码参数加“1”。
（s为编码参数）
程序基本架构：
privateclassListenerimplementsActionListener//察看编码监听器（调用）coding
Publicclassnode
intweight;
//权重introoty_n;
//1是叶节点，0不是叶节点intselected;
//0为未选中叶节点，1为选中的最小节点，2为新合并节点intlevel;
//树的层数intleft_width,right_width;
//树的左右横向延伸最大宽度nodeleft;
//左子树noderight;
//右子树Stringcode;
//霍夫曼编码
publicnode（intweight）//node构造函数，传入权重
publicvoidcoding（noderoot,Strings）//编码过程
publicclassgraphics_basicextendsJpanel
Graphicsg;
nodem;
//将要画的树
JButtonjb//察看当前编码按钮
publicvoidpaint（Graphicsg）
publicvoiddraw（intx,inty,nodem,Graphicsg）//画图方法，递归实现，传入变量分别为起始的x，y坐标，二叉树，Graphics对象
publicclassminheap
node[]weights;
//最小堆数组
intcurrentSize;
//当前堆大小
publicvoidinitialize（int[]weight）//最小堆初始化
publicvoidinsert（nodewei）//插入元素，并调整至最小堆
publicnodedeletemin（）//删除最小元素，并重新调整至最小堆
publicclassgraphics//画图面板类，继承JPanel
huffuman_basich;
publicgraphics（int[]weights）//构造函数，初始化霍夫曼基础对象
publicJPaneladdingCom（intele_count）//添加根据霍夫曼基础对象里的变量m（即最小堆）中元素利用graphics_basic画图像
publicJPaneltrap（）//单步执行函数，调用traping、traping2
publicclasshuffuman_basic
minheapm;
最小堆
booleanbegin,seORcom;
//单步演示是否开始，演示在选中阶段还是合并阶段
publichuffuman_basic（int[]weight）初始化
publicvoidtraping（）//选中方法，将最小堆中两个最小的元素selected标识为选中
publicvoidtraping2（）//删除并合并
publicnodecombine（nodeleft,noderight）//左右子树合并，新树根节点权重为左右子树权重之和
publicclassinputing//输入窗口构造函数
Stringss="
"
;
//输入的全部数据，（用空格分开）int[]start;
//初始化数组intcounting=0;
//输入数据计数器…//GUI组件
paintComponent（Graphicsg）//添加背景图片
publicint[]randoStart（）//100内随机数50个
publicvoidinit_input（）//输入数据转换为数组，存在START里
…键盘、事件监听器，构造函数
publicclasscard_explextendsJFrame//编码框实现类
graphicsg;
Strings="
//全部编码过程intpointer;
//当前卡片指向intcount;
//总执行步int[]origin;
//初始数组CardLayoutcard;
//卡片布局…//GUI组件
…//构造函数
●
最小堆的插入：
将最小堆得元素插入进最小堆最后一个节点，层层向上比较交换直至根节点（类似于书上的方法不再展示）
●最小堆删除：
仅仅删除根节点，层层比较下移（类似于书上最大堆方法）
●Cardlayout布局使用：
while（g.h.begin）//在对象G还可以单步执行时{
graphicsg0=newgraphics（g）;
//复制当前对象，用复制对象画图，避免所有卡片公用相同对象造成结果失误
JPanelp1=newJPanel（）;
p1=g0.trap（）;
复制对象单步执行g.trap（）;
//原始对象执行下一步
JScrollPanejsp0=newJScrollPane（p1,ScrollPaneConstants.VERTICAL_SCROLLBAR_AS_NEEDED,ScrollPaneConstants.HORIZONTAL_SCROLLBAR_AS_NEEDED）;
jsp0.setPreferredSize（newDimension（1000,600））;
//为P1添加滚动条
JPanelp0=newJPanel（）;
p0.add（jsp0,BorderLayout.WEST）;
pane.add（p0,"
第"
+count+"
步"
）；
//添加至卡片
count++;
//单步计数器加一}
●监听器的使用
1）普通事件监听器：
实现各种不同的功能，多添加在按钮上，实现监听
2）键盘监听器：
if（e.getSource（）.equals（text））//检查事件来自输入框还是显示框
{//来自输入框
charkey=e.getKeyChar（）;
//获得当前输入字符
if（（key<
'
0'
）||（key>
9'
））//在0——9之外时{
text.setText（"
）;
//输入文本框清空textarea.setText（ss）;
//显示框内容不变
if（add）//如果是输入状态，且当前输入不是数字，实现非数字输入切换到输入下一元{
ss=ss+"
"
counting++;
jl.setText（"
请输入第"
+（counting+1）+"
个元素"
}
add=false;
//切换至非输入状态（避免下一个非数字输入继续空格）}
else{//输入的是数字，则在textarea同步显示，并将当前数字加入SS
str=text.getText（）;
str=str+key;
if（（str.toCharArray（）[0]<
）||（str.toCharArray（）[0]>
））//输入框第一个字符不是数字，则忽略
extarea.setText（str.substring
（1））;
else
textarea.setText（str）;
ss=ss+key;
dd=true;
//至输入状态}}
else//事件来自非输入区，内容不变
textarea.setText（ss）}
●复制构造函数：
几乎所有类都加了复制构造函数，必要时重新非配内存空间，避免重复使用某类的不同对象时出现对象公用的情况，造成程序结果错误或者只有最后一步结果
●霍夫曼编码算法：
publicvoidcoding（nodep,Strings）{//每一个霍夫曼树的具体编码过程，递归进行，采用前序遍历
if（p!
=null）
{p.code=newString（s）;
//为编码分配新的空间（避免出现String的指针）//递归遍历节点。
左子树编码参数加“0”，右子树编码参数加“1”
coding（p.left,s+"
0"
coding（p.right,s+"
1"
}
●画每棵树的算法：
publicvoiddraw（intx,inty,nodem,Graphicsg）{//画图方法，递归实现，传入变量分别为起始的x，y坐标，二叉树，Graphics对象
if（m!
=null{
g.setColor（Color.CYAN）;
//若为叶节点，画方形,否则画圆形
//选中画红色，新建画黄色，非新建中间节点画青色
if（m.rooty_n==0）//是否为根节点{
if（m.selected==1）//是否被选中
g.setColor（Color.red）;
if（m.selected==2）
g.setColor（Color.yellow）;
g.fillOval（x-r0,y,2*r0,2*r0）;
else//不是根节点{
if（m.selected==1）
g.setColor（Color.red）;
else
g.setColor（Color.green）;
g.fillRect（x-r0,y,2*r0,2*r0）;
g.setColor（Color.black）;
//写出元素g.drawString（newInteger（m.weight）.toString（）,x-2*r0/3,y+r0+r0/2）;
//当存在左右节点时，画出左右节点的连接线，X坐标修改2^（level-2）*d，y增加定值
if（m.left!
=null）{
g.drawLine（x,y+2*r0,x-（int）Math.pow（2,m.level-2）*d,y+2*r0+5*d）;
g.drawString（"
x-（int）Math.pow（2,m.level-3）*d-r0,y+5*r+2*r0）;
if（m.right!
g.drawLine（x,y+2*r0,x+（int）Math.pow（2,m.level-2）*d+r,y+2*r0+5*d）;
x+（int）Math.pow（2,m.level-3）*d+r0,y+5*r+2*r0）;
//前序递归遍历画出其他节点（需修改X,Y）
draw（x-（int）Math.pow（2,m.level-2）*d,y+2*r0+5*d,m.left,g）;
draw（x+（int）Math.pow（2,m.level-2）*d+r0,y+2*r0+5*d,m.right,g）;
}
三、程序使用说明
1）输入窗口：
打开程序进入输入窗口，输入数据，随机生成数据等按钮均可，输入完毕后，点击“开始编码”，则进入编码窗口
进入编码窗口，点击上下步即可看到每一步的二叉树，可察看当前状态以及编码，关于，全部过程（当前为选中状态）
合并状态
合并之后的编码
全部编码过程展示
“关于”
三、程序调试说明
●输入框输入数据测试（输入字母）或者其他（测试键盘监听器）
1.输入数据显示：
仅显示文本框输入数字，数字以外键盘输入则自动视为输入下一个数，同时显示文本域显示已输入的所有数字
2.输入字母仅仅在输入框的第一位显示（不管输入多少），输入数据依然只显示当前输入数字（限在int位数）
3.点击“随机数据”随机产生50个100之内的随机数，则文本框提示为：
“请输入第N（N>
50）”，点击“随机输入”产生一个100以内的整数
4.重新输入：
所有数据清空
5.一直输入相同的数据（比如0）
目的：
测试监听器是否可用
●输入数据数组转化测试
测试代码（在publiccard_expl（int[]weight）中）：
System.out.println（"
初始数据:
for（inti=0;
i<
origin.length;
i++）
System.out.print（origin[i]+"
6.空数组：
（直接点击开始编码），弹出对话框提示输入数据
7.仅有一个元素（弹出对话框，不可编码）
8.所有元素都相同的编码（以六个2为例）
输入数据保证正确无误
●编码程序测试
9.所有元素相同（以六个2为例）
10.“上一步”“下一步”指针正确性（同上例），自第一步跳至最后一步
11.庞大数据稳定性（图太大，仅用滚动条），画的图更新速度不是特别快
四、实现代码（带注释）
实现代码及背景图片附在压缩包内
五、时间安排
●2月20日—2月22日：
理解课程设计内容、需求，设计数据结构
●2月23日—2月25日：
最小堆、霍夫曼树核心算法代码编写，画图算法编写
●2月25日—2月28日：
美化图形用户界面，修改布局管理，实现基础需求
●3月1日—3月2日：
增加程序特色，修改程序增加注释，设计开发文档
●3月3日：
撰写开发文档
六、心得体会
课程设计已经做了将近两周的时间。
寒假看过了题目，觉得很简单但是真正做起来还是很复杂的。
两周的时间，自己查资料、写代码、不断推翻原先的思想建立新的构架是个很复杂的过程——每一次从基础变量的加减而进行的边界检查，工作相当繁琐——才明白实现一个思想绝非想想的那么容易——从界面到参数，从复制对象到指针对象、内存分配，方方面面都是一个优秀的程序员需要考虑的，然而我远远做不到这一点。
通过课程设计我将更加学会脚踏实地走好每一步，兢兢业业地完成每一项工作——既然选择了，就不该后悔。
升级会员 