定制网站建设的释义,珠海做网站的公司有哪些,常德企业网站建设,网站建设维保合同文章目录一、C语言能干大事1. C语言下Huffman树的计算过程分析2. C语言下Huffman树的编程二、C#语言也不赖1. C#下Huffman类的设计2. C#中界面设计3. 建立测试数据并显示Huffman树4. 输入任意一组数据#xff0c;完成构造Huffman树三、JavaScript语言不爱听了1. JavaScript下H…
文章目录一、C语言能干大事1. C语言下Huffman树的计算过程分析2. C语言下Huffman树的编程二、C#语言也不赖1. C#下Huffman类的设计2. C#中界面设计3. 建立测试数据并显示Huffman树4. 输入任意一组数据完成构造Huffman树三、JavaScript语言不爱听了1. JavaScript下Huffman类的设计2. 把权重数据显示在一个表格里3. 为表格添加命令按钮4. 编写添加一行的程序5. 编写删除一行的程序6. 用表格中的数据生成Huffman树表7. 显示Huffman树表中的树一、C语言能干大事 1. C语言下Huffman树的计算过程分析
例1 有权重集合分别是5、29、7、8、14、23、3、11计算Huffman树。
这个题目的计算过程如下
1首先是把数据填写在以下表格里 这个在编程中一定注意空白格子里是NULL这点不要搞错。
首先是寻找到两个最小权重的结点找到的是第7、1号结点权重合计是8我们先标记这两个结点s1(代表已经处理过了)并生成第9号结点权重是8并让第7、1号结点的父结点是9第9号结点的左、右孩子分别是第7、1结点就是如下表 重复上面的过程从头寻找s0的结点里、权重最小的两个结点、就是第3、4号结点权重合计是15这样标记这两个结点s1并生成第10号结点权重是15而第7、8的父结点是第10号结点第10号结点的左右孩子是第3、4号结点就是下表 重复这个过程处理到第15个结点使其权重合计为100就是 最终这个树的计算到此结束在这样的表中计算出的过程以及结果就是我们下面编程的主要依据。
2. C语言下Huffman树的编程
针对前面介绍的表格用C语言描述这样的表就是
struct Huffman
{int W,Parent,lChild,rChild,S;
};对Huffman树由于它是正则二叉树所以有n个权重数据则必然有2*n-1个树结点。
有了表的C语言定义则首先是寻找未标记的、权重最小的结点如果这个表是H则全部代码就是
int FindMinNode(struct Huffman *H,int N)
{int i,W,Node;W100;Node0;if(HNULL) return -1;for(i0;iN;i){if(H[i].W0H[i].WWH[i].S0){WH[i].W;Nodei;}}H[Node].S1;return Node;
}
第6至第12行是一个典型的数组中求最小值的算法在第13行则必须标记这个结点的S1说明该结点已经使用过最后则返回这个结点的编号。
有了这个函数后首先要对H表进行两次求最小值的操作就是
min1FindMinNode(H,N); min2FindMinNode(H,N);如第i行是新增的一个结点则让该表第i行的权重为
H[i].WH[min1].WH[min2].W;然后就是设置这个结点的左右孩子结点为min1、min2就是
H[i].Parent-1; H[i].lChildmin1; H[i].rChildmin2;最后就是设置编号min1、min2的结点的父结点是第i个结点。
H[min1].Parenti; H[min2].Parenti;全部就是
int ConstructHuffmanTree(struct Huffman *H,int n)
{int i;int min1,min2,N;if(n0) return -1;if(HNULL) return -2;N2*n-1;for(in;iN;i){min1FindMinNode(H,N);min2FindMinNode(H,N);H[i].WH[min1].WH[min2].W;H[min1].Parenti;H[min2].Parenti;H[i].Parent-1;H[i].lChildmin1;H[i].rChildmin2;}return 0;
}注意这个函数第8行它是从第n个结点开始循环的。
有了这两个函数后用一个测试的main()来测试它们
main()
{int n,N,i,*D;struct Huffman *H;n8;//组织scanf()输入N2*n-1;D(int *)malloc(sizeof(int)*n);//组织scanf()输入。D[0]5;D[1]29;D[2]7;D[3]8;D[4]14;D[5]23;D[6]3;D[7]11;H(struct Huffman *)malloc(sizeof(struct Huffman)*N);for(i0;iN;i) {H[i].W0;H[i].Parent0;H[i].lChild0;H[i].rChild0;H[i].S 0;}for(i0;in;i)H[i].W D[i];ConstructHuffmanTree(H,n);printf(ID\tW\tP\tL\tR\n);for(i0;iN;i)printf(%d\t%d\t%d\t%d\t%d\n,i,H[i].W,H[i].Parent,H[i].lChild,H[i].rChild);
}
运行结果如下图所示 Huffman树的C语言程序到此为止。
二、C#语言也不赖 1. C#下Huffman类的设计
仅仅针对前面C语言中的计算方法设计一个类来完成计算过程这个类就是 class Huffman{public int W, pChild, lChild, rChild, s;public Huffman(){W pChild lChild rChild -1;s 0; }public Huffman(int Weight, int PChild, int LChild, int RChild, int Select){W Weight; PChild pChild; lChild LChild; rChild RChild; s Select; }}
2. C#中界面设计
有了这个类以后我们可以在界面设计上拖进两个命令按钮button1button2然后再拖进一个treeView1控件和imageList1控件然后开始以下设置
(1) 选择imageList1控件找到属性images加入文件夹MyIcon中的两个小图标
(2) 选择treeView1控件让imageList属性选中imageList1控件
(3) 选择treeView1控件让SelectImageIndex1(打开书的图标);
(4) 选择treeView1控件让ImageIndex0(关闭书的图标);
(5) 选择button1控件修改text属性为”简单测试”
(6) 选择button2控件修改text属性为”结束”
3. 建立测试数据并显示Huffman树
设有权重数据为5,29,7,8,14.23.3.11注意权重数据和必须是100。首先是编写从Huffman类数组中取得最小权重结点的函数这个函数编写在Form1程序中鼠标双击button1注意在button1_click()前面补充这样的函数就是 在这个函数中H是Huffman结点对象数组而N是这个数组的数据个数如果是上例则N15。 现在开始补充代码如下
int FindMinNode(Huffman[] H,int N){ int i,W,Node;W100;Node0;if(Hnull) return -1;for(i0;iN;i){if(H[i].W0H[i].WWH[i].s0){WH[i].W;Nodei;}}H[Node].s1;return Node;}这个函数同C的几乎没什么差别同样返回这个结点的下标。有这个函数后就可以构造Huffman树跟随着上面的函数继续输入就是
int ConstructHuffmanTree(Huffman[] H,int n){int i;int min1,min2,N;if(n0) return -1;if(Hnull) return -2;N2*n-1;for(in;iN;i){min1FindMinNode(H,N);min2FindMinNode(H,N);H[i].WH[min1].WH[min2].W;H[min1].pChildi;H[min2].pChildi;H[i].pChild-1;H[i].lChildmin1;H[i].rChildmin2;}return 0;}
其基本算法和C语言的也没什么差别。
但这个Huffman类的树是不能显示在treeView1中的控件treeView1只能显示TreeNode类型的树所以要按这个表格的内容构造TreeNode类对象的树。
在treeView1控件中显示的结点个数同Huffman类的结点个数是一致的而每个TreeNode类结点的Text内容则是权重于是紧跟着上面的函数写以下函数就是 void dTree(Huffman[] H){int i,n,a,b;n H.Count();TreeNode[] T new TreeNode[n];for(i0;in;i)T[i]new TreeNode(H[i].W.ToString());for (i 0; i n; i){a H[i].lChild;
b H[i].rChild;if (a 0) T[i].Nodes.Add(T[a]);if (b 0) T[i].Nodes.Add(T[b]);}treeView1.Nodes.Add(T[n-1]); }
最后就是补充button1下的程序按实验数据有
这组数据一共8个所以Humman树一共将有2*8-115个结点鼠标双击button1写进以下程序
private void button1_Click(object sender, EventArgs e){Huffman[] H new Huffman[15];H[0] new Huffman(5, -1, -1, -1, 0);H[1] new Huffman(29, -1, -1, -1, 0);H[2] new Huffman(7, -1, -1, -1, 0);H[3] new Huffman(8, -1, -1, -1, 0);H[4] new Huffman(14, -1, -1, -1, 0);H[5] new Huffman(23, -1, -1, -1, 0);H[6] new Huffman(3, -1, -1, -1, 0);H[7] new Huffman(11, -1, -1, -1, 0);for (int i 8; i 15; i) H[i] new Huffman();ConstructHuffmanTree(H, 8);dTree(H);}
到此简单的Huffman树的测试程序设计完成。最后在button2_click()中补充代码this.close();让程序能正常结束。
4. 输入任意一组数据完成构造Huffman树
为完成这个要求首先要在界面设计中再补充控件有
1 补充listBox1控件
2 补充button3控件修改Text属性为“输入确认”
3 补充button4控件修改Text属性为”生成Huffman树”
4 补充button5控件修改Text属性为”清除”
5 补充textBox1控件
有了上述控件后我们首先设计操作过程是
在textBox1控件中输入数据按下button3按钮“输入确认”则输入的数据显示在listBox1控件中直到所有数据输入完成于是这样的操作要求的程序就是
private void button3_Click(object sender, EventArgs e){listBox1.Items.Add(textBox1.Text); }
listBox1控件是个数据容器你可以不断追加进很多数据这些数据全部可以保存在这个控件中。直到按下button4”生成Huffman树”才开始计算。所以button4的程序就是 private void button4_Click(object sender, EventArgs e){int n listBox1.Items.Count;Huffman[] H new Huffman[2*n-1];for (int i 0; i 2 * n - 1; i)H[i] new Huffman();for(int i0;in;i){int wint.Parse( listBox1.Items[i].ToString()) ;H[i].W w; }ConstructHuffmanTree(H, n);dTree(H);}表7中第3行相当于从listBox1控件中获得数据项的个数在第9行就是逐个取得每个数据项并转换成int类型、赋值给Huffman类对象数组中每个对象的权重W。最后按同样的方式计算并显示在treeView1中。
注意这个程序实际很不理想没判断输入的数据是否有负值、是否是非数字的字符串、是否和为100等等这些详细的判断留给同学们自己去完成。
对于button5”清除”的编程非常简单就是
private void button5_Click(object sender, EventArgs e)
{listBox1.Items.Clear();treeView1.Nodes.Clear();textBox1.Text ;
} 程序运行效果 三、JavaScript语言不爱听了 1. JavaScript下Huffman类的设计
针对前面C语言中的计算方法设计一个类来存储数据如果你使用的Ext系统则强烈建议直接使用Ext.data.ArrayStore类对象直接构造它这样的好处是显示在表格里非常方便于是说明对象tstore为
var tstore new Ext.data.ArrayStore({data:[[0,5 ,-1, -1,-1,0],[1,29,-1, -1,-1,0],[2,7 ,-1, -1,-1,0],[3,8 ,-1, -1,-1,0],[4,14,-1, -1,-1,0],[5,23,-1, -1,-1,0],[6,3 ,-1, -1,-1,0],[7,11,-1, -1,-1,0]],fields: [{name: id ,type:int},{name: w ,type:int},{name: pChild,type:int},{name: lChild,type:int},{name: rChild,type:int},{name: s ,type:int}]});
运行效果 这个程序非常直观它说明有一个表名称是tstore其中右6列data下说明了数据在field下说明了各个列的名称、分别是id,w,pChild,lChild,rChild,s这样的6列如同下表 2. 把权重数据显示在一个表格里
但这个表用来显示在界面上则非常不好看我们需要一个友好的界面所谓友好的界面就是说用汉字显示、而不是奇怪符号显示的界面如 我们一般把表2成为逻辑表表3称为显示表它们两者之间的关系应该是一一对应的唯独列名称不一样。造成这样的结果主要原因是程序计算过程中我们期望变量名都是英语字符这样非常方便编程但显示则必须是汉字的表头。
把这两者统一起来就是说让“结点编号”指向逻辑表的“id”列要用到Ext.grid.ColumnModel类型的对象如该对象的名称是colM则定义如下
var colMnew Ext.grid.ColumnModel([
{列对象1属性},
{列对象2属性},
…
{列对象n属性}
]);
注意JavaScript中、一旦出现[ ]则代表是数组所以这些个列对象也就相当于数组中的各个元素。
一个典型的设置就是如将表格第1列显示为“结点编号”、并和数据逻辑表tstore中的id关联起来、并在该列上提供排序、而且该列可以编辑则就是
{header:结点编号,dataIndex:id,sortable:true,editor:new Ext.form.TextField()
}实际就是设置了列对象的4个属性。这仅仅是为第一列如果是所有列则
var colMnew Ext.grid.ColumnModel([{header:结点编号,dataIndex:id,sortable:true,editor:new Ext.form.TextField()},{header:结点权重,dataIndex:w,sortable:true,editor:new Ext.form.TextField()},{header:父结点编号,dataIndex:pChild,sortable:true,editor:new Ext.form.TextField()},{header:左结点编号,dataIndex:lChild,sortable:true,editor:new Ext.form.TextField()},{header:右孩子编号,dataIndex:rChild,sortable:true,editor:new Ext.form.TextField()},{header:选择状态,dataIndex:s,sortable:true,editor:new Ext.form.TextField()}]);
注意在最后一个列对象定义完后、第37行后没有”,”这点初学者一定要记着。
有了数据、有了列定义以后就可以显示表格了显示表格用的是Ext.grid.EditorGridPanel类对象就是按下面的语句
var gridnew Ext.grid.EditorGridPanel({表对象属性});含义是定义了一个表对象grid而该表的显示属性则由表对象属性中说明。如
var gridnew Ext.grid.EditorGridPanel({renderTo:hello,title:Huffman树,height:400,width:620,cm:colM,store:tstore});
其中属性:
renderTo:说明这个表格显示在哪里在表5中是在”hello”中这个hello实际是用HTML语言定义的一个分区就是有了这个分区grid就将显示在该区域里title:表示该表格的标题height:表示该表格的高度width:表示该表格的宽度cm:表的列定义需要一个列对象来说明各个列如表4store:表示该表显示的数据来自哪里在我们的程序中数据来自表1定义的tstore。 将上述程序代码合并到一个函数里就是
function fun(){var tstore new Ext.data.ArrayStore({data:[[0,5 ,-1, -1,-1,0],[1,29,-1, -1,-1,0],[2,7 ,-1, -1,-1,0],[3,8 ,-1, -1,-1,0],[4,14,-1, -1,-1,0],[5,23,-1, -1,-1,0],[6,3 ,-1, -1,-1,0],[7,11,-1, -1,-1,0]],fields: [{name: id ,type:int},{name: w ,type:int},{name: pChild,type:int},{name: lChild,type:int},{name: rChild,type:int},{name: s ,type:int}]});//表格上列名称显示、以及表格上数据处理方式。var colMnew Ext.grid.ColumnModel([{header:结点编号,dataIndex:id,sortable:true,editor:new Ext.form.TextField()},{header:结点权重,dataIndex:w,sortable:true,editor:new Ext.form.TextField()},{header:父结点编号,dataIndex:pChild,sortable:true,editor:new Ext.form.TextField()},{header:左结点编号,dataIndex:lChild,sortable:true,editor:new Ext.form.TextField()},{header:右孩子编号,dataIndex:rChild,sortable:true,editor:new Ext.form.TextField()},{header:选择状态,dataIndex:s,sortable:true,editor:new Ext.form.TextField()}]);//表格开始显示数据。var gridnew Ext.grid.EditorGridPanel({renderTo:hello,title:Huffman树,height:400,width:620,cm:colM,store:tstore});}
Ext.onReady(fun);
有了表7的程序我们打开m.html这个程序是一个调用Ext类库的模板程序把表7的程序补充到这个程序里的fun()函数里即可执行结果将显示一个表。
注意第72行不是这个函数中的语句而是一条独立的JavaScript语句。现在就可以以m.html为模板文件加入表7的程序。
3. 为表格添加命令按钮
如果一个程序仅仅能计算一组数据那么这个程序实际没什么意义为此我们要给表格上加入三个命令按钮就是添加、删除、生成Huffman树使其能添加一行、删除一行并能根据新的数据生成Huffman树。
给表格上添加三个命令按钮就是给grid对象上再说明一个工具条、并显示出三个命令按钮。也就是说给该对象的tbar属性说明命令按钮对象的属性说明就是 tbar:[{按钮对象1属性},{按钮对象2属性},…{按钮对象n属性} ] 对一个命令按钮属性比如产生一个叫”新增”的命令按钮则可以是这样来说明
{ text: 新增, iconCls: add, handler: function(){ //以下写进新增加一行的代码} }text:表明这个按钮上显示的字符如VB6中Command控件上的Caption属性
iconCls:这个按钮上要显示的图标
handler:function() { }:就是按下这个按钮后的响应程序
同VB6的设计思路是一致的但这里完全没有VB6那样的编程环境所以逐个属性只能自己在键盘上输入。
现在我们要在表格对象grid上的工具栏tbar中说明三个按钮则就是一下的程序
var gridnew Ext.grid.EditorGridPanel({renderTo:hello,title:Huffman树,height:400,width:620,cm:colM,store:tstore,tbar: [ { text: 新增, //iconCls: add, handler: function(){ //以下写进新增加一行的代码} }, { text: 生成Huffman树, //iconCls: refresh, handler: function(){ //以下写进生成新Huffman树的代码} }, { text: 删除一行, //iconCls: delete, handler: function(){ //以下写进表格中删除一行的代码} } ]});
注意同表5的对比。新增加的三个命令按钮在执行h1.html的时候则就会看到。当然它们目前是什么都不会执行仅仅是有三个命令按钮。
运行效果 执行h0.html和h1.html看看这两个网页的差异。
4. 编写添加一行的程序
编写这个程序实际就是为表8的第15行处补充代码补充这样的代码首先要获得表格中当前有几行这个数据要从tstore中去获得就是
var ntstore.getCount();然后构造一个默认的数据行用的是
var defData{id:n,pChild:-1,lChild:-1,rChild:-1,s:0};就是说id的值是n,pChildlChildrChild-1,s0,让权重w为空白。
最后构造一个第n行的记录并插入到tstore中去就是
var rnew tstore.recordType(defData,n);
tstore.insert(tstore.getCount(),r);一旦数据插入tstore则在grid中会自动显示结果。完整的函数就是
Handler: function(){ var ntstore.getCount();var defData{id:n,pChild:-1,lChild:-1,rChild:-1,s:0};var rnew tstore.recordType(defData,n);tstore.insert(tstore.getCount(),r);}
运行效果 5. 编写删除一行的程序
删除一行数据首先要选中表中的一行如果没有选中则要给出提示。
var record grid.getSelectionModel().selection.record; 如果正常获得了选中的行则要找到这一行数据是在tstore中的哪一行就是在对象tstore中按record来查找:
var index tstore.indexOf(record); 这样index就是表格中对应的行号有了行号就可以
tstore.removeAt(index);来删除这一行。
但一定要注意假如你没有选中表格中的任何一行执行上面的过程则会发生错误这个是非常重要的事情否则删除操作会让程序经常崩溃。为此这段程序要加入到JavaScript语言的try过程中就是 try { //这里加入要尝试着做的程序段落 } catch(err) { //如果尝试着做的程序段无法正常执行则在这里给出错误的提示 err对象中有 //错误的描述。 } 注意这个语句在C#中也有同样的语句这个语句非常重要经常会出现在一些需要尝试着做的工作中诸如在涉及到硬件访问、用户操作不确定的场合下按这个语句的过程来执行程序则是必须的。有了这个过程则完整的删除程序就是
handler: function(){ try{var record grid.getSelectionModel().selection.record; var index tstore.indexOf(record); tstore.removeAt(index); }catch(err){Ext.MessageBox.alert(删除错误提示,未选中任何行不能删除.);return;}
}
注意表10的程序是添加在表8的第32行处这个程序在这里是完整的但它是对象grid说明的一个组成部分。
现在运行h2.html则可以测试加入一行数据、并删除一行数据了。 6. 用表格中的数据生成Huffman树表
要生成一个Huffman树则首先要从表格中计算各个结点的权重值为此又首先要获得表格中未用过结点的最小权重结点为此编写函数如下
function FindMinNode(astore){var i,n,w100,m-1;nastore.getCount();for(i0;in;i){if(astore.getAt(i).get(s)0wastore.getAt(i).get(w)){wastore.getAt(i).get(w);mi;}}astore.getAt(m).set(s,1);return m;}
这个函数的参数是astore函数是逐行读这个对象中s0的那些行找到最小权重行的下标值、并存在m中查找完后在第12行把该行的s列修改为1然后返回这个下标值。这个算法的原理和C#是一致的。
有这个函数后就可以在“生成Huffman树”按钮下的响应程序里补充这些代码构造一个Huffman树就是:
handler: function(){ var ntstore.getCount();for(in;i2*n-1;i) {var min1FindMinNode(tstore);var min2FindMinNode(tstore);tstore.getAt(min1).set(pChild,i);tstore.getAt(min2).set(pChild,i);var nwtstore.getAt(min1).get(w)tstore.getAt(min2).get(w);var newNode{id:i,w:nw,pChild:-1,lChild:min1,rChild:min2,s:0};var rnew tstore.recordType(newNode,i);tstore.insert(tstore.getCount(),r);}dTree(tstore);}
在第6、7行每次获得对象tstore中两个最小权重结点
在第8、9行修改tstore表中第min1、min2两行的pChild列使这两个行的父结点等于新的这一行(第i行)
在第10行则是读第min1、min2行的权重求和、结果在nw中;
在第11行按新的权重nw构造一个结点其左孩子是min1右孩子是min2s0;
在第12、13行则是把这一行新的记录插入到tstore中同时也会显示在grid对象中
最后在第15行调用dTree(tstore)函数显示在一个treeView对象中。
注意这个函数实际是在表9的第23行处补充的。
7. 显示Huffman树表中的树
显示一个树在Ext系统中首先要构造Ext.tree.TreeNode类型的结点这里和C#中的概念是一样的Ext.tree.TreeNode类型的结点个数和Huffman表tstore中的行数是一致的为此就是这样的过程来构造这些Ext.tree.TreeNode类型的结点并显示出来
function dTree(astore)
{var i,n;var TAnew Array();nastore.getCount();for(i0;in;i)TA[i]new Ext.tree.TreeNode({id:astore.getAt(i).get(id),text:astore.getAt(i).get(w)}); for(i0;in;i){var a astore.getAt(i).get(lChild); var b astore.getAt(i).get(rChild);if (a 0) TA[i].appendChild(TA[a]);if (b 0) TA[i].appendChild(TA[b]);}treeView1new Ext.tree.TreePanel({renderTo:Tree,root:TA[n-1],width:300,height:400});
}
这个函数的算法和C#中的完全一致没有差别只不过一些语句修改成JavaScript语句而已。 到这里一个完整的Huffman树生成、显示程序完成了。
一定保留好这个程序的所有代码这样的代码在随后的数据库课程中使用的非常广泛它不仅仅是一个简单的树的问题很多应用都需要类似的界面。而这个程序里最关键的数据对象tstore在数据库中则要用Ajax技术来从数据库服务器中、通过一种叫WebServices的程序系统来获得其中相当多数的WebServices程序是由C#来编写的由Ext执行结果也要通过C#的WebServices作用到数据库服务器中去。一个华丽的数据库应用系统必须是在华丽的外观下实现的而C#、Ext系统则是这个系统中最重要的组成部分。
随后在数据库的课程中我们将在VS2008中、使用C#、JavaScript Ext、SQLServer系统来完成这样的开发所以这样的基础知识是非常关键的。
相关文章：
