数据结构+实验报告+线性表及其应用(多项式相加、相乘)等

福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：算法与数据结构姓名：谢飞乐系：计算机专业：计算机科学与技术年级：2007学号：071152032指导教师：宁正元职称：教授2009年6月1日实验项目列表序号实验项目名称成绩指导教师1线性表及其应用(多项式相加、相乘)2哈弗曼树及哈弗曼编码译码的实现3Dijkstra最短路径或Prim最小生成树4（快速、堆、归并）排序算法的设计5构造平衡二叉排序树67891011121福建农林大学计算机与信息学院实验报告系：计算机系专业：计算机科学与技术年级：2007姓名：谢飞乐学号：071152032实验室号_田_513_计算机号25实验时间：09.3.25下午10、11节指导教师签字：宁正元成绩：实验一线性表及其应用一、实验目的和要求1、掌握线性表的插入、删除、查找等基本操作设计与实现2、学习利用线性表提供的接口去求解实际问题3、熟悉线性表的的存储方法二、实验内容和原理1、实验内容：设计一个一元多项式的简单计算器，其基本功能有①输入并建立多项式；②输出多项式；③多项式相加。可利用单链表或单循环链表实现之。2、实验原理：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。三、实验环境VisualC++6.0及PC机四、算法描述及实验步骤思想算法：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。例如构造两个多项式ha:5X3+4X2+3X+2hb:X2+X+1多项式加法：定义指针p,q分别指向ha,hbi.p-exp==q-exp,r-coef=p-coef+q-coef,pa,pb下移;ii.p-expq-exp,r-coef=q-coef;r-exp=q-exp;,q下移2iii.pa-exppb-exp,r-exp=p-exp;r-coef=p-coef;,p下移iv.p!=NULL,pb==NULL.相当于iii.V.q==NULL,pb!=NULL.相当于ii.其流程图如下：多项式乘法：定义指针fp,gp分别指向f,g1.将两多项式最大指数相加并赋于maxp，并置g2.用for循环求指数等于maxp时相乘的系数3.(fp!=NULL)&&(gp!=NULL),p=fp-exp+gp-exp1.pmaxp,fp=fp-next;2.pmaxp,gp=gp-next;3.p=maxp,x+=fp-coef*gp-coef;fp=fp-next;gp=gp-next;3五、调试过程将主函数中的多项式相乘的函数hd=polymult(ha,hb);/*ha和hb相乘*/的polymult(ha,hb)改为polymulti(ha,hb)即可。六、实验结果1.分别输入两个多项式:5X3+4X2+3X+2和X2+X+1,然后输出结果如下:2.分别输入两个多项式：6X4+4X2+2和5X+6，然后输出结果如下：4七、总结此次上机实验应用了线性表实现了一次实际操作，完成了一个一元多项式的简单计算器，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。附录：1.建立多项式列表代码如下：mulpoly*creatpoly()/*建立多项式列表*/{mulpoly*head,*r,*s;/*设中间变量*/intm,n;head=(mulpoly*)malloc(sizeof(mulpoly));/*头结点申请空间*/printf(\ninputcoefandexp:\n);scanf(%d%d,&n,&m);/*输入多项式系数和指数*/r=head;/*尾指针指向头指针*/while(n!=0)/*将输入的多项式存放在S中*/{s=(mulpoly*)malloc(sizeof(mulpoly));s-coef=n;s-exp=m;r-next=s;r=s;/*printf(inputcoefandexp:\n);*/scanf(%d%d,&n,&m);/*再次输入多项式系数和指数*/}r-next=NULL;/*将尾指针置空*/5head=head-next;/*将head哑结点向前跑一个结点，使其不为空*/return(head);/*返回多项式*/}2.两个多项式相加代码如下：mulpoly*polyadd(mulpoly*ha,mulpoly*hb)/*两个多项式相加*/{mulpoly*hc,*p,*q,*s,*r;/*声明结构体型*/intx;p=ha;q=hb;hc=(mulpoly*)malloc(sizeof(mulpoly));/*申请结点空间*/s=hc;while((p!=NULL)&&(q!=NULL))/*两多项式不为空*/if(p-exp==q-exp)/*指数相等*/{x=p-coef+q-coef;/*系数相加*/if(x!=0)/*系数不为零*/{r=(mulpoly*)malloc(sizeof(mulpoly));/*结果放r中存放*/r-exp=q-exp;r-coef=x;s-next=r;s=r;}p=p-next;/*多项式前进一项*/q=q-next;/*多项式前进一项*/}elseif(p-expq-exp)/*比较指数大小*/{r=(mulpoly*)malloc(sizeof(mulpoly));r-coef=q-coef;r-exp=q-exp;s-next=r;s=r;q=q-next;}else{r=(mulpoly*)malloc(sizeof(mulpoly));r-exp=p-exp;r-coef=p-coef;s-next=r;s=r;p=p-next;}while(p!=NULL)/*当多项式p中不为空时照抄*/{r=(mulpoly*)malloc(sizeof(mulpoly));r-exp=p-exp;6r-coef=p-coef;s-next=r;s=r;p=p-next;}while(q!=NULL)/*当多项式q中不为空时照抄*/{r=(mulpoly*)malloc(sizeof(mulpoly));r-exp=q-exp;r-coef=q-coef;s-next=r;s=r;q=q-next;/*将最终尾指针置空*/}s-next=NULL;r=hc;hc=hc-next;free(r);/*释放r*/return(hc);/*返回结果*/}3.两个多项式相乘代码如下：mulpoly*polymulti(mulpoly*f,mulpoly*g)/*两个多项式相乘*/{mulpoly*fp,*gp,*hp,*q,*h;intmaxp,p,r,x;mulpoly*reverse(mulpoly*q);/*函数声明*/maxp=f-exp+g-exp;/*将两多项式最大指数相加并赋于maxp*/h=(mulpoly*)malloc(sizeof(mulpoly));hp=h;g=reverse(g);/*逆置g*/for(r=maxp;r=0;r--)/*循环求指数等于r时相乘的系数*/{x=0;/*设x初始值为0*/fp=f;gp=g;while((fp!=NULL)&&(gp!=NULL))/*循环求相乘之后指数为r时的系数*/{p=fp-exp+gp-exp;/*f的指数加上g逆置后的指数并给p*/if(pr)/*比较p，r*/fp=fp-next;/*p大，fp到下一个结点，以确保p等于r*/elseif(pr)gp=gp-next;/*p小，gp到下一个结点，以确保p等于r*/else/*p等于r*/{x+=fp-coef*gp-coef;/*将相乘之后指数为r时的系数给x*/fp=fp-next;gp=gp-next;7}}if(abs(x)1e-6)/*条件限制，使得所求多项式系数绝对值不能太小*/{q=(mulpoly*)malloc(sizeof(mulpoly));q-exp=r;q-coef=x;q-next=NULL;hp-next=q;hp=q;}/*将所求结果给hp，h*/}hp=h;h=h-next;/*将h的哑结点前进，使不为空*/free(hp);/*释放hp*/returnh;/*返回结果*/}4.定义链表逆置函数mulpoly*reverse(mulpoly*q)/*定义链表逆置函数*/{mulpoly*p1,*p2;if(q!=NULL)/*确保所要逆置多项式不为空*/{p1=q-next;/*使p1指向下一个结点*/q-next=NULL;/*将q-next为空*/while(p1!=NULL)/*循环使相邻两个结点逆置，直到最后一个逆置为头结点*/{p2=p1-next;p1-next=q;q=p1;p1=p2;}}returnq;/*返回逆置结果*/}5.输出多项式代码如下：voidpolyout(mulpoly*head)/*输出多项式*/{mulpoly*q,*p;/*p=head-next;*/p=head;while(p!=NULL)/*循环输出多项式的系数和指数*/{printf(%dx%d,p-coef,p-exp);p=p-next;}printf(\n);}8福建农林大学计算机与信息学院实验报告系：计算机系专业：计算机科学与技术年级：2007姓名：谢飞乐学号：071152032实验室号_田_513_计算机号25实验时间：09.3.25下午10、11节指导教师签字：宁正元成绩：实验二哈弗曼树及哈弗曼编码译码的实现一、实验目的和要求1、掌握树的有关图相关操作算法;2、熟悉树的基本存储方法;3、学习利用树求解实际问题。二、实验内容和原理1、实验内容：（1）构造哈弗曼树；（2）对单个结点编码；（3）输出树；（4）编码；（5）译码。2、实验原理：通过树的有关图的相关操作算法，以及树的基本存储方法，利用树来构造哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。三、实验环境VisualC++6.0及PC机四、算法描述及实验步骤思想算法：一棵有n个叶子结点的哈夫曼树有2n-1个结点，所以可用大小为2n-1个元素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。结点的结构可以这样来考虑，由于每个叶子结点都有一个权重，构造哈夫曼树的过程中每个分枝结点的权重等于两个孩子结点权重的和，所以应该有一个权重域和指向左右孩子的两个指针域；另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。由此可知，每个结点至少应该有一个权重域weight和3个指针域parent,lchild和rchild，也是就是说，要用静态三叉链表来表示哈夫曼树。9由于在实际构造哈夫曼树时，是由叶子结点的权重逐级构造最后生成树根，且在构造过程中公与叶子结点的权重有关而与叶子结点的数据域外无关，所以构造算法的实现中可以不考虑叶子结点的数据域，并且在静态三叉链表中从叶子结点开始存放，然后不断地反两棵权重最小的子树合并成为一棵权值为其和的较大的子树，逐步生成各内部结点直到树根。在建立哈夫曼树的算法描述中，有效地利用了每个结点的双亲域parent的值是否为了-1来区分该结点是否是哈夫曼森林中一棵树的根结点，每次是在根结点中找出两