计算机数据结构实验报告.docx

《计算机数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《计算机数据结构实验报告.docx（20页珍藏版）》请在第一文库网上搜索。

1、实验一线性表操作(一元多项式的运算)实验目的1、定义线性表的链式存储；2、实现对线性表的一些基本操作和具体函数定义。实验要求1、定义一个建立一元多项式的函数；2、定义一元多项式加法和减法函数；3、定义榆出一元多项式的函数；4、编写主程序调用上面的函数实现一元多项式的加减。数据输入与输出要求输入示例：323345752 13 3-344 65 7(说明：第一个数据3表示该第一个一元多项式的项数为3,后面的23表示第一项的系数为2指数为3；按指数递增的次序输入)输出示例：一元多项式1:2x(3)+3x(4)+5x(7)一元多项式2：2x(1)+3x(3)-3x(4)+4x(6)+5x(7)加的结果

2、:2x(1)+5x(3)+4x(6)+1Ox(7)减的结果：-2x(1)-1x(3)+6x(4)-4x(6)数据结构设计结点结构体定义typedefstructpo1ynodef1oatcoef;/系数intexpn;指数structpoIynode*next;JpoIynode,*po1yIist;voidcreate(po1yIist&1);创建链表voiddisp1ay(po1yIist1);/显示链表内容两个链表的加，要求不修改相加的两个表voidadd(po1yIist1a,po1yIist1b,po1yIist&1c);两个链表的减，要求不修改相减的两个表voidsubtract(

3、po1yIist1a,po1yIist1b,po1yIist&1c);程序模板# incIude# incIude# incIudetypedefstructpo1ynodef1oatcoef;/系数intexpn;/指数structpo1ynode*next;poIynode,*po1yIist;voidcreate(po1yIist&1);创建链表voiddisp1ay(po1yIist1);/显示链表内容voidadd(po1yIist1a,po1yIist1b,po1yIist&1c);voidsubtract(po1yIist1a,po1yIist1b,po1yIist&1c);vo

4、idmain()# po1yIist1a,1b,1c,1d;create(1a);disp1ay(1a)create(1b);disp1ay(1b);add(1a,1b,1c);disp1ay(1c);subtract(1a,1b,1d);disp1ay(1d);)补齐代码日期：教师签字:程序模板调试情况教师评阅实验二哈夫曼编码和译码实验目的1、熟悉二叉树的顺序存储结构；2、熟悉二叉树的顺序存储结构和具体实现；3、熟悉哈夫曼编码和译码，及其在顺序存储结构下的实现。实验要求1、根据输入构造一棵哈夫曼树，要求该哈夫曼树的左子树小于等于右子树；2、根据构造的哈夫曼树给出对应的编码；左子树的编码为0,

5、右子树的编码为1；3、榆出各个字符对应的编码与平均编码长度；4、根据榆入的编码，结合构造的哈夫曼树给出对应的译码；5、对带有不同权值的字符进行编码；使用自己实现的编码表对输入的01代码进行译码。数据输入与输出要求输入示例：5A8B20C30D15E270101101110#（说明：第一个数据5表示共有5个字符要编码，后面的“A8”表示A的权为8,字符个数不超过20个；数据OIoIIo1110#是要解码的数据，最后以#结束）输出示例：编码为：A010B00C11D011E10平均编码长度为：2.23对应的译码为：ACDEtypedefstruct(charch;字母intweight;权重数in

6、tparent,Ichi1d,rchi1d;父亲与左右孩子HTNode,*HuffDianTree;据typedefchar*HuffmanCode;函数原型声明结构造HuffmanTreevoidCreateHuffmanTree(HuffmanTree&HT,intw1,charch,intn);构选择两个权重最小的无父亲的结点voidSe1ect(HuffmanTreeHT,intn,int&s1,int&s2);设利用HuffmanTree对字符编码voidHTCoding(HuffmanTreeHT,HuffmanCode&HC,intn);计voidPrintCode(Huffma

7、nCodeHC,intn,charch);输出编码求平均编码长度doub1eAverage1enght(HuffmanTreeHT,HuffmanCodeHC,intn);/求平均编码长度voidDeCode(HuffmanTreeHT,intn);解码#inc1ude#inc1ude#inc1udeinc1udetypedefstruct(charch;字母与编码程intweight;权重intparent,Ichi1d,rchi1d;父亲与左右孩子序HTNode,*HuffmanTree;typedefchar*HuffmanCode;以下为函数原型声明voidCreateHuffmanT

8、ree(HuffmanTree&HT,intw1,charch,intn);模板构造HuffmanTreevoidSe1ect(HuffmanTreeHT,intn,int&s1,int&s2);选择两个权重最小的无父亲的结点voidHTCoding(HuffmanTreeHT,HuffmanCode&HC,intn);利用HuffmanTree对字符编码voidPrintCode(HuffmanCodeHC,intn,charch口);输出编码doub1eAverage1enght(HuffmanTreeHT,HuffmanCodeHC,intn);求平均编码长度voidDeCode(Huf

9、fmanTreeHT,intn);解码voidmain()intn;inti;chararrch20;intarrweight20;doub1eav1ength;charch;HuffmanTreeHT;HT是一个指针变量，用于指向HUffnIanTreeHuffmanCodeHC;HC是一个指针变量,用于存放对应字符的编码SCanf;输入字符个数whi1e(ch=getchar()!=n,);if(n20n2)exit(O);输入的字符数超出要求范围退出；for(i=0;in;i+)输入字符和对应的权重(scanf(zz%czz,&arrchi);scanf(zz%dzz,&arrweigh

10、ti);whi1e(ch=getchar()!=n,);)程序模板CreateHuffmanTree(HT,arrweight,arrch,n);构造HuffmanTreeHTCoding(HT,HC,n);利用HuffmanTree对字符编码PrintCode(HC,n,arrch);输出编码av1ength=verage1enght(HT,HC,n);求平均编码长度Printf(平均编码长度为：%fn,av1ength);DeCode(HT,n);解码释放申请的空间for(i=0;i0),构造哈夫曼树HT,inti,m,si,s2;m=2*n-1;HT=(HuffmanTree)ma1Io

11、c(m+1)*sizeof(HTNode);/O号单元不用设有一组权值存放于数组w中，对应的字符在数组ch中for(i=1;i=n;i+)(HTi.weight=wi-1;HTi.parent=O;HTi.Ichi1d=O;HTi.rchi1d=O;HTi.ch=chi-1;数组HT后n-1个元素先清空for(i=n+1;i=m;i+)(HTi.weight=O;HTi.parent=0;HTi.Ichi1d=O;HTi.rchi1d=O;HTi1ch=0,;)for(i=n+1;i=m;i+)/建哈夫曼树(/在HT1.iT中选择parent为0且weight最小的两个结点,/其序号分别为S1

12、和S2。程序模板Se1ect(HT,i-1,si,s2);HTs1.parent=i;HTs2.parent=i;HTi.Ichi1d=si;HTi.rchi1d=s2;HTi.weight=HTs1.weight+HTs2.weight;/endHuffmanCoding选择两个权重最小的无父亲的结点，且下标S1对应的权小于等于s2的权voidSe1ect(HuffmanTreeHT,intn,int&s1,int&s2)/补充完整/end_Se1ect利用HuffmanTree对字符编码voidHTCoding(HuffmanTreeHT,HuffmanCode&HC,intn)/从叶子到

13、根逆向求每个字符的哈夫曼编码inti,j,k,start;intf;intc;char*cd;HC=(HuffmanCode)ma11oc(n)*sizeof(char*);cd=(char*)ma11oc(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.1chi1d=c)cd一start=,0,;e1secd一start=,;HCi-1=(char*)ma1Ioc(n-start)*sizeof(char);/为第i个字符编码分配空间for(j=start,k=0;jn;j+,k+)/从cd复制编码(串)到HCHCi-1k=cdj;free(cd);/释放工作空间/endHTCodingvoidPrintCode(HuffmanCodeHC,intn,cha