计算机软件技术基础试验报告

1、计算机软件基础实验报告姓名学号实验目的1.掌握C®言程序设计方法，并学会上机调试。2,熟悉Huffman编码源程序，并构造Huffman树。实验内容1,试设计一算法，从包括n个元素的数组中，求最大和最小元素，并使得当n个元素为有序排列时，元素之间的比较次数仅为n-1次。2,在给出的Huffman编码源程序基础上，要求画出HuffmanW,求出与等长编码相比时的压缩比。实验要求1 .根据实验内容编写算法，并用C语言进行程序设计。2,将所编程序在计算机上调试通过，并全面测试。实验结果2 .以一个含有8个元素的一维数组1,2,3,5,7,8,9,12为例，设计程序如下：#include&l

2、t;stdio.h>intmaxArray(intx,inty);intminArray(intx,inty);intmain(void)inti=0;intarray8=1,2,3,5,7,8,9,12;printf;doscanf("%d”,&arrayi);i+;while(i<8);intmaxTemp=array0;intminTemp=array0;intmaxindex=0;intminindex=0;for(i=1;i<8;i+)maxTemp=maxArray(arrayi,maxTemp);minTemp=minArray(arrayi,

3、minTemp);)for(i=0;i<8;i+)(if(maxTemp=arrayi)(maxIndex=i;)if(minTemp=arrayi)(minIndex=i;)printf;return0;)运行结果如下：=StartDefauLtBeliavior(Before>=-=123578912=EndDefaultBehauior=Start->Max/Min=最大值二12.最小值二1=End->Max/Min=3 .Huffman编码源程序#include<dos.h>#include<conio.h>#include<std

4、io.h>#include<stdlib.h>#include<string.h>typedefstructunsignedintweight;/结点权值unsignedintparent,lchild,rchild;/结点的父指针，左右孩子指针HTNode,*HuffmanTree;/动态分配数组存储哈夫曼树typedefchar*HuffmanCode;/动态分配数组存储哈夫曼编码表voidCreateHuffmanTree(HuffmanTree&,unsignedint*,int);/生成哈夫曼树voidHuffmanCoding(HuffmanT

5、ree,HuffmanCode&,int);对哈夫曼树进行编码voidPrintHuffmanCode(HuffmanCode,unsignedint*,int);显示哈夫曼编码voidSelect(HuffmanTree,int,int&,int&);/在数组中寻找权值最小的两个结点voidmain()HuffmanTreeHT;/哈夫曼树HTHuffmanCodeHC;/哈夫曼编码表HCintn,i;/n是哈夫曼树叶子结点数unsignedint*w;/w存放叶子结点权值charj='y'printf("演示构造口夫曼树.n");

6、printf("输入需要进行编码的字符数目.n例如:8n");printf("然后输入每个字符出现的次数/权值.n");printf("例如:529781423311n");printf("自动构造一棵哈夫曼树并显示哈夫曼编码.n");printf("5-0110n29-10n7-1110n8-1111n14-110n");printf("23-00n3-0111n11-010n");while(j!='N'&&j!='n')p

7、rintf("请输入字符数目:");scanf("%d",&n);/输入字符数目if(n<=1)printf("该数不合理!n");continue;w=(unsignedint*)malloc(n*sizeof(unsignedint);开辟空间存放权值printf("请输入各字符出现的次数/权值:n");for(i=0;i<n;i+)scanf("%d",&wi);/输入各字符出现的次数/权值CreateHuffmanTree(HT,w,n);生成哈夫曼树Huff

8、manCoding(HT,HC,n);进行哈夫曼编码PrintHuffmanCode(HC,w,n);/显示哈夫曼编码printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");scanf("%c",&j);voidCreateHuffmanTree(HuffmanTree&HT,unsignedint*w,intn)/w存放n个结点的权值，将构造一棵哈夫曼树HTinti,m;ints1,s2;HuffmanTreep;if(n<=1)return;m=2*n-1;/n个叶子结点的哈夫曼树，有2*n-1个结点HT=(Huffman

9、Tree)malloc(m+1)*sizeof(HTNode);/开辟2*n各结点空间for(p=HT+1,i=1;i<=n;+i,+p,+w)/进行初始化p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)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);/从HT1i-1中选择parent00且weight最小的两

10、个结点，其序号分别为s1和s2HTs1.parent=i;HTs2.parent=i;修改s1和s2结点的父指针parentHTi.lchild=s1;HTi.rchild=s2;/修改i结点的左右孩子指针HTi.weight=HTs1.weight+HTs2.weight;/修改权值)voidHuffmanCoding(HuffmanTreeHT,HuffmanCode&HC,intn)/将有n个叶子结点的哈夫曼树HT进行编码，所编的码存放在HC中/方法是从叶子到根逆向求每个叶子结点的哈夫曼编码inti,c,f,start;char*cd;HC=(HuffmanCode)malloc

11、(n+1)*sizeof(char*);/分配n个编码的头指针向量cd=(char*)malloc(n*sizeof(char);开辟一个求编码的工作空间cdn-1='0'/编码结束符for(i=1;i<=n;+i)/逐个地求哈夫曼编码start=n-1;/编码结束位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'若是左孩子编为0'elsecd-start='1'若是右孩子编为1'HCi=(char*)mal

12、loc(n-start)*sizeof(char);/为第i个编码分配空间strcpy(HCi,&cdstart);将编码从cd复制到HC中)free(cd);/释放工作空间)voidPrintHuffmanCode(HuffmanCodeHC,unsignedint*w,intn)/显示有n个叶子结点的哈夫曼树的编码表inti;printf("HuffmanCodeis:n");for(i=1;i<=n;i+)printf("%3d-”,wi-1);puts(HCi);)printf("n");)voidSelect(Huffm

13、anTreeHT,intt,int&s1,int&s2)/在HT1t中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2inti,m,n;m=n=10000;for(i=1;i<=t;i+)if(HTi.parent=0&&(HTi.weight<m|HTi.weight<n)if(m<n)n=HTi.weight;s2=i;elsem=HTi.weight;s1=i;if(s1>s2)/s1放较小的序号i=s1;s1=s2;s2=i;运行结果如下：赖人需要进行输3的字符数目.例如然后输入每个字符出现的次数/权值.例

14、如：529781423311自动构造一棵哈夫曼树并显示哈夫曼编阴.S01102910711108111114110230B3011111010请输入字符数目;输入数据后的运行结果然后瑜入每个字符出现的次数/权值.例如：529781423311自动构造一棵哈夫曼树并显示哈夫曼编码.501102910?1110811111411023003011111010请施入名符数目：8请输入客字符出现的次数/权值：21083172359HuffnanCodeis：21111010110801031111117002310511109011哈夫曼树构造完毕，还要继续吗?实验心得要熟练掌握程序的编写，如果没有一定的想象能力和大量的上机实践是根本无法完成的。首先要做的是多看程序,勤编程序。完整地编写一个准确、严谨的程序绝非易事。大量阅读程序有助于我们掌握编程的常用语法和基本要领。随着阅读量的不断增加，我们大脑中对于知识的积累越来越丰富，对于编程的感觉也越来越敏感。渐渐地，在基本掌握了编程的方法套路后，我们大脑中的“数据库”日益壮大，编写各种类型的程序便会显得得心应