数据结构实验报告

浙江科技学院《数据结构》实验报告年级班级学号姓名任课老师实验指导教师实验地点信息学院实验一线性表操作（一元多项式的运算）实验目的：1、定义线性表的链式存储2、实现对线性表的一些基本操作和具体函数定义实验要求：1、定义线性表的链式存储；2、实现对线性表的一些基本操作和具体函数定义。3、定义输出一元多项式的函数；4、编写主程序调用上面的函数实现一元多项式的加减。数据输入输出要求：输入示例：323345752133-344657（说明：第一个数据3表示该第一个一元多项式的项数为3，后面的23表示第一项的系数为2指数为3；按指数递增的次序输入）输出示例：一元多项式1：2x(3)+3x(4)+5x(7)一元多项式2：2x(1)+3x(3)-3x(4)+4x(6)+5x(7)加的结果：2x(1)+5x(3)+4x(6)+10x(7)减的结果：-2x(1)-1x(3)＋6x(4)-4x(6)程序代码：#includemap#includecstdlib#includeiostream#includealgorithm#definenullNULL#definepolymal(poly*)malloc(sizeof(poly))usingnamespacestd;structpoly{pairint,intdata;poly*next;};voidread(poly*a){poly*poi=a;intn,xs,cs;cinn;for(inti=0;in;i++){poly*nex=polymal;cincsxs;nex-data=make_pair(xs,cs);poi-next=nex;poi=poi-next;}poi-next=null;}voidadd(poly*a,poly*b,poly*ans){poly*apo=a-next,*bpo=b-next,*cpo=ans;while(apo&&bpo){poly*sum=polymal;if(apo-data.firstbpo-data.first){sum-data=apo-data;apo=apo-next;}elseif(apo-data.firstbpo-data.first){sum-data=bpo-data;bpo=bpo-next;}else{sum-data=make_pair(apo-data.first,apo-data.second+bpo-data.second);apo=apo-next,bpo=bpo-next;if(!sum-data.second){free(sum);continue;}}cpo-next=sum;cpo=cpo-next;}while(apo){poly*sum=polymal;sum-data=apo-data;cpo-next=sum;cpo=cpo-next;apo=apo-next;}while(bpo){poly*sum=polymal;sum-data=bpo-data;cpo-next=sum;cpo=cpo-next;bpo=bpo-next;}cpo-next=null;}voidsub(poly*a,poly*b,poly*ans){poly*apo=a-next,*bpo=b-next,*cpo=ans;while(apo&&bpo){poly*ex=polymal;if(apo-data.firstbpo-data.first){ex-data=apo-data;apo=apo-next;}elseif(apo-data.firstbpo-data.first){ex-data=make_pair(bpo-data.first,-bpo-data.second);bpo=bpo-next;}else{ex-data=make_pair(apo-data.first,apo-data.second-bpo-data.second);apo=apo-next,bpo=bpo-next;if(!ex-data.second){free(ex);continue;}}cpo-next=ex;cpo=cpo-next;}while(apo){poly*sum=polymal;sum-data=apo-data;cpo-next=sum;cpo=cpo-next;apo=apo-next;}while(bpo){poly*sum=polymal;sum-data=make_pair(bpo-data.first,-bpo-data.second);cpo-next=sum;cpo=cpo-next;bpo=bpo-next;}cpo-next=null;}voidout(poly*a){if(!a-next){cout0;return;}poly*poi=a-next;coutpoi-data.second;if(poi-data.first)coutx(poi-data.first);poi=poi-next;while(poi){if(poi-data.second0)cout+;coutpoi-data.second;if(poi-data.first)coutx(poi-data.first);poi=poi-next;}}intmain(){poly*a,*b,*sumout,*subout;a=polymal;b=polymal;sumout=polymal;subout=polymal;read(a);read(b);cout一元多项式1:;out(a);coutendl一元多项式2:;out(b);add(a,b,sumout);sub(a,b,subout);coutendl加的结果:;out(sumout);coutendl减的结果:;out(subout);return0;}运行结果：一元多项式1:2x(3)+3x(4)+5x(7)+6x(8)一元多项式2:2x(1)+3x(3)-3x(4)+4x(6)+5x(7)加的结果:2x(1)+5x(3)+4x(6)+10x(7)+6x(8)减的结果:-2x(1)-1x(3)+6x(4)-4x(6)+6x(8)实验二哈夫曼编码和译码实验目的：1、熟悉二叉树的顺序存储结构；2、熟悉二叉树的顺序存储结构和具体实现；3、熟悉哈夫曼编码和译码，及其在顺序存储结构下的实现实验要求：1、根据输入构造一棵哈夫曼树，要求该哈夫曼树的左子树小于等于右子树；2、根据构造的哈夫曼树给出对应的编码；左子树的编码为0，右子树的编码为1；3、输出各个字符对应的编码与平均编码长度；4、根据输入的编码，结合构造的哈夫曼树给出对应的译码5、对带有不同权值的字符进行编码；使用自己实现的编码表对输入的‘0’‘1’代码进行译码数据输入输出要求：输入示例：5A8B20C30D15E270101101110#（说明：第一个数据5表示共有5个字符要编码，后面的“A8”表示A的权为8，字符个数不超过20个；数据0101101110＃是要解码的数据，最后以＃结束）输出示例：编码为：A010B00C11D011E10平均编码长度为：2.23对应的译码为：ACDE程序代码：#includemap#includequeue#includevector#includestring#includeiomanip#includecstdlib#includeiostream#includealgorithm#defineINF0x3f3f3f3f#defineBinarytree_malloc(Binarytreepointer)malloc(sizeof(Binarytree))usingnamespacestd;typedefstructBinarytree{intdata;charch;Binarytree*leftson,*rightson;voidleaf_create(charch){this-ch=ch;cindata;leftson=nullptr;rightson=nullptr;}voidfather_create(Binarytree*leftson,Binarytree*rightson){this-leftson=leftson;this-rightson=rightson;this-data=leftson-data+rightson-data;}}Binarytree,*Binarytreepointer;structBinarytreepointer_cmp{booloperator()(constBinarytreepointera,constBinarytreepointerb)const{return(a-data)(b-data);}};queuecharleaf_ch;mapchar,stringhuffman_codes_map;priority_queueBinarytreepointer,vectorBinarytreepointer,Binarytreepointer_cmpheap_sort;voidread_leafnode(){intn;cinn;while(n--){charch;cinch;Binarytreepointerleafnode=Binarytree_malloc;leafnode-leaf_create(ch);leaf_ch.push(ch);heap_sort.push(leafnode);}}Binarytreepointerhuffman_bulid(){Binarytreepointerleft_son=heap_sort.top();heap_sort.pop();if(heap_sort.empty())returnleft_son;Binarytreepointerright_son=heap_sort.top();heap_sort.pop();Binarytreepointerfather=Binarytree_malloc;father-father_create(left_son,right_son);heap_sort.push(father);returnhuffman_bulid();}pairint,intget_huffman_codes(Binarytreepointerroot,stringprefix){if(root-leftson){pairint,intleft_average_coding_length=get_huffman_codes(root-leftson,prefix+0);pairint,intright_average_coding_length=get_huffman_codes(root-rightson,prefix+1);returnmake_pair(left_average_coding_length.first+right_average_coding_length.first,left_average_coding_length.second+right_average_coding_length.second);}huffman_codes_map[root-ch]=prefix;returnmake_pair(root-data*prefix.size(),root-data);}voidprint_huffman_codes(Binarytreepointerroot){