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

福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：算法与数据结构姓 名：谢飞乐系：计算机专 业：计算机科学与技术年 级：2007学 号：071152032指导教师：宁正元职 称：教授 2009 年 6 月 1 日实验项目列表序号实验项目名称成绩指导教师1线性表及其应用(多项式相加、相乘)2哈弗曼树及哈弗曼编码译码的实现3Dijkstra最短路径 或Prim最小生成树4（快速、堆、归并）排序算法的设计5构造平衡二叉排序树6789101112福建农林大学计算机与信息学院实验报告系： 计算机系 专业： 计算机科学与技术 年级： 2007 姓名： 谢飞乐 学号： 071152032 实验室号_ 田_513_ 计算机号 25 实验时间： 09.3.25下午10、11 节 指导教师签字： 宁正元 成绩： 实验一 线性表及其应用一、 实验目的和要求1、掌握线性表的插入、删除、查找等基本操作设计与实现2、学习利用线性表提供的接口去求解实际问题3、熟悉线性表的的存储方法二、 实验内容和原理1、实验内容：设计一个一元多项式的简单计算器，其基本功能有输入并建立多项式；输出多项式；多项式相加。可利用单链表或单循环链表实现之。2、实验原理：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的 结点之后，即线性表的元素按指数递增有序排列。三、 实验环境Visual C+ 6.0 及PC机四、 算法描述及实验步骤思想算法：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。例如构造两个多项式ha: 5X3+4X2+3X+2 hb: X2+X+1多项式加法：定义指针p,q分别指向ha,hbi.p-exp=q-exp ,r-coef=p-coef+q-coef,pa,pb下移;ii.p-expexp ,r-coef=q-coef;r-exp=q-exp;,q下移iii.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-exp 1.pmaxp, fp=fp-next; 2. pnext; 3.p=maxp, x+=fp-coef*gp-coef; fp=fp-next;gp=gp-next;五、 调试过程将主函数中的多项式相乘的函数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，然后输出结果如下：七、 总结此次上机实验应用了线性表实现了一次实际操作，完成了一个一元多项式的简单计算器，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。附录： 1.建立多项式列表代码如下：mulpoly *creatpoly()/*建立多项式列表*/ mulpoly *head,*r,*s;/*设中间变量*/ int m,n; head=(mulpoly *)malloc(sizeof(mulpoly);/*头结点申请空间*/ printf(ninput coef and exp: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(input coef and exp:n);*/ scanf(%d%d,&n,&m);/*再次输入多项式系数和指数*/ r-next=NULL;/*将尾指针置空*/ head=head-next;/*将head哑结点向前跑一个结点，使其不为空*/ return (head);/*返回多项式*/ 2.两个多项式相加代码如下：mulpoly *polyadd(mulpoly *ha,mulpoly *hb)/*两个多项式相加*/ mulpoly *hc,*p,*q,*s,*r;/*声明结构体型*/ int x; 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;/*多项式前进一项*/ else if(p-expexp)/*比较指数大小*/ 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; r-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; int maxp,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*/ else if(pnext;/*p小，gp到下一个结点，以确保p等于r*/ else/*p等于r*/ x+=fp-coef*gp-coef;/*将相乘之后指数为r时的系数给x*/fp=fp-next;gp=gp-next; 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*/ return h;/*返回结果*/ 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; return q;/*返回逆置结果*/ 5.输出多项式代码如下：void polyout(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); 福建农林大学计算机与信息学院实验报告系： 计算机系 专业： 计算机科学与技术 年级： 2007 姓名： 谢飞乐 学号： 071152032 实验室号_ 田_513_ 计算机号 25 实验时间： 09.3.25下午10、11 节 指导教师签字： 宁正元 成绩： 实验二 哈弗曼树及哈弗曼编码译码的实现一、 实验目的和要求1、掌握树的有关图相关操作算法;2、熟悉树的基本存储方法;3、学习利用树求解实际问题。二、 实验内容和原理1、实验内容：（1）构造哈弗曼树；（2）对单个结点编码；（3）输出树；（4）编码；（5）译码。2、实验原理：通过树的有关图的相关操作算法，以及树的基本存储方法，利用树来构造哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。三、 实验环境Visual C+ 6.0 及PC机四、 算法描述及实验步骤思想算法：一棵有n个叶子结点的哈夫曼树有2n-1个结点，所以可用大小为2n-1个元素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。结点的结构可以这样来考虑，由于每个叶子结点都有一个权重，构造哈夫曼树的过程中每个分枝结点的权重等于两个孩子结点权重的和，所以应该有一个权重域和指向左右孩子的两个指针域；另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。由此可知，每个结点至少应该有一个权重域weight和3个指针域parent,lchild和rchild，也是就是说，要用静态三叉链表来表示哈夫曼树。由于在实际构造哈夫曼树时，是由叶子结点的权重逐级构造最后生成树根，且在构造过程中公与叶子结点的权重有关而与叶子结点的数据域外无关，所以构造算法的实现中可以不考虑叶子结点的数据域，并且在静态三叉链表中从叶子结点开始存放，然后不断地反两棵权重最小的子树合并成为一棵权值为其和的较大的子树，逐步生成各内部结点直到树根。在建立哈夫曼树的算法描述中，有效地利用了每个结点的双亲域parent的值是否为了-1来区分该结点是否是哈夫曼森林中一棵树的根结点，每次是在根结点中找出两个权重值weight最小的树作为左右子树构造一棵更大的树。求哈夫曼编码的方法是，在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一位哈夫曼编码值，由于每个叶子结点的哈夫曼编码是从根结点到相应叶子结点的路径上各代码所组成的0，1序列，所以先得到的代码为所求编码的低位码而后得到的为高位码。对于每个叶子结点的哈夫曼编码可以考虑用一个一维数组bit从后向前依次保存所求得的各位编码值，并用start记住编码在数组bit中的开始位置。如下面例子，有4个数2，4，5，8。将其构造成哈夫曼树。 算法设计分析select(int t,int *s1,int *s2)函数用来实现选取最小和次最小的权重的下标，其流程图如下：create_ht_hc()函数用来构造树和码，其流程图如下：showtree(int root,int tab)为用凹入法显示树，其流程图如下：showcode(int n)用来显示01代码，其流程图如下：code2char(char t,char s)函数用来译码。char2code(char s,char t)函数用来编码，其流程图如下：五、 调试过程将程序的代码输入，再进行编译，发现以下错误。1.修改方法：在代码开头加入头文件#include即可正常编译和组建，最后再进行运行。2.问题：当输出各个字符的编码后，程序没有提醒“the chars are:”.而是只能自己输入一串字符后，才进行提示。下一步的译码也是如此。六、 实验结果输入5个叶子结点a,s,d,f,g。其权重分别为7，13，16，4，10。得出结果如下：七、 总结本次实验让我更加了解了哈夫曼树的构造和生成方法，以及如何用顺序存储结构来存储哈夫曼树及构树过程的信息，如何进行编码、译码。也感知到模块程序设计在大程序设计使用中的普遍性，该实验是最好的证明，通过模块程序设计，能够使得程序可度可写性明显加强。通过本次实验，使我初步掌握了二叉树的结构特性以及各种存储的结构的特点及适用范围，掌握了哈夫曼树的定义和思想，以及哈夫曼编码的代码实现，初步掌握了用凹入法显示树。不过程序仍有树的显示部分不够完善的缺点，在今后的学习中会注意改变。附录： 选择最小和次最小的权重函数如下：void select(int t,int *s1,int *s2) /*在1t之间选取w最小的下标s1，次最小的下标为s2*/ int i,w1,w2; /*最小的权重为w1，次最小的权重为w2*/ w1=w2=32767; /*初始化为无穷大*/ for(i=1;i=t;i+) if(hti.parent=0) /*选取最小的和次最小的*/ if(hti.ww1) /*如果出现一个比w1还小的权，则把原先的w1传给w2，把新的权重赋给w1*/ w2=w1;*s2=*s1;w1=hti.w;*s1=i; else if(hti.ww2) /*如果出现一个比w2还小的权，则把新的权重赋给w2，并记住其下标*/ w2=hti.w;*s2=i;构造哈夫曼树的代码如下：void create_ht_hc() /*构造树和码*/ int i,s1,s2,child,parent,w; char ch; coutn; m=2*n-1; /*总结点数*/ for(i=1;i=n;i+) /*输入数据*/ coutchw; hti.w=w; /*把初始的数据送入存储空间*/ hci.ch=ch; for(i=n+1;i=m;i+) /*建树*/ select(i-1,&s1,&s2); /*选取最小的和次最小的权重*/ hts1.parent=hts2.parent=i; /*把最小的和次最小的权连成树*/ hti.lch=s1; /*左孩子为最小的，右孩子为次最小的*/ hti.rch=s2; hti.w=hts1.w+hts2.w; /*parent的权为孩子之和*/ for(i=1;i=n;i+) /*建码*/ child=i; hci.start=0; /*初始化开始位置*/ while(child!=m) /*对叶子结点逐一求哈夫曼编码*/ parent=htchild.parent; if(child=htparent.rch) /*左0右1*/hci.codehci.start=1; elsehci.codehci.start=0; hci.start+; child=parent; /*从下往上编*/用凹入法显示树的代码如下：void showtree(int root,int tab) /*凹入法显示树，tab为凹入的字符数*/if(root) /*如果树非空*/ int i; for(i=1;i=tab;i+) /*输出空格*/ cout ; couthtroot.w; if(htroot.lch=0) /*如果为叶子结点，则输出叶子结点*/cout”(”hcroot.ch”)”;coutendl; /couthtroot.w; /*输出权值*/ showtree(htroot.lch,tab+3); showtree(htroot.rch,tab+3);显示各字母的代码：void showcode(int n) /*显示01代码，从start-1开始输出*/ int i,j; for(i=1;i=n;i+) couthci.ch=0;j-) couthci.codej; coutendl;对输入的字符进行编码：void char2code(char s,char t) /*编码，若s=abcd,则t=000110101*/ int i,j,k,x=0; for(i=0;istrlen(s);i+)/*扫描s*/ for(j=1;j=0;k-) tx+=hcj.codek+48; /*把整型转换为字符型*/ tx=0; /*字符串结束标志*/ 对输入的数码进行译码：void code2char(char t,char s) /*译码，若t=000110101，则s=abcd*/*用指针扫描t，从根m开始向下遇0向左，遇1向右，直到找到叶子结点，并输出再返回根，从头开始循环*/ int i=0,j=0,parent=m;/child; while(si) if(si=1) parent=htparent.rch; else parent=htparent.lch; if(htparent.lch=0) tj+=hcparent.ch; parent=m; i+; tj=0; /*字符串结束标志*/ 福建农林大学计算机与信息学院实验报告系： 计算机系 专业： 计算机科学与技术 年级： 2007 姓名： 谢飞乐 学号： 071152032 实验室号_ 田_513_ 计算机号 25 实验时间： 09.3.25下午10、11 节 指导教师签字： 宁正元 成绩： 实验三 Dijkstra最短路径 或Prim最小生成树（二选一）一、 实验目的和要求1、 掌握图的有关图相关操作算法。2、 熟悉图的基本存储方法。3、 了解掌握图的基本术语。二、 实验内容和原理实验内容：通过输入起点、终点和权重构造一个图；通过输入，将一个节点作为起点；找到从起点到各个节点的最短路径；输出图与及到各个节点的最短短径；三、 实验环境Visual C+ 6.0 及PC机四、 算法描述及实验步骤Prim算法是人连通网中的某一个顶点开始，以此作为生成树的初始状态，然后不断地网中的其他顶点添加到生成树上，直到最后一个顶点添加到生成树上时得到最小生成树。（1）从网中任一顶点开始，把该顶点包含生成树中，此时树只有一个顶点。（2）找出一个端点在生成树中另一个端点在生成树外的所有边，并把权值最小的边连同它所关联的另一个顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，选择其中任意一条都可以。（3）反复执行（2），直到所有顶点都包含在生成树中时止。算法中由函数prim定义最小生成树。由函数creat_graph建立无向连通网。算法过程如下图：建立无向连通网的流程图如下： 定义最小生成树的代码如下：五、 调试过程将程序的代码输入，再进行编译，没有发现错误。六、 实验结果实验结果如下七、 总结1). 通过这次实验，使我掌握了用prim算法构造最小生成树的思想。掌握了邻接矩阵的构造思想及其应用。3).掌握图与网的基本概念和基本存储方法。4). 掌握有向及无向连通图的概念及其应用。5). 对编程有了更深的理解与掌握。附录： void creat_graph(graph *p) /*建立无向连通网*/int i,j,n ; int v1,v2,w;/*定义两端点及其权值为整型*/ printf(vertex number of the graph:); /*输入无向网的端点数*/ scanf(%d,&n); p-vnum=n; for(i=1;i=n;i+) /*初始化结构体中的元素*/ for(j=1;jarcsij=0; else /*非对角线上的元素的权值为MAX即99*/ p-arcsij=MAX; do /*执行循环语句*/ printf(edge(vertex1,vertex2,weight):); /*输入两个端点及其权值*/ scanf(%d,%d,%d,&v1,&v2,&w); if(v1=1&v1=1&v2arcsv1v2=w; p-arcsv2v1=w; while(!(v1=8|v2=8); /*当v1，v2其中一个为8时循环终止*/ int prim(graph G,int v, int tree8) /*定义最小生成树*/int i,j,k,p,min,c; /*定义局部变量*/ int lowcostm,closestm; for(i=1;i=G.vnum;i+) closesti=v; /*填边在生成树一端的顶点序号*/ lowcosti=G.arcsvi;/*填边的权值*/ c=1; p=1;/*从v1开始构造最小生成树*/ for(i=1;iG.vnum;i+) /*循环n-1次，选n-1条边于生成树中*/ min=MAX;/*初定min值为上限值99*/ for(j=1;j=G.vnum;j+) /*选最小权值及对应顶点*/ if(lowcostj!=0&lowcostjmin) min=lowcostj; /*最小权值记在min中*/ k=j; /*把与边关联的生成树外的顶点序号记在k中*/ treep1=closestk; /*将所得值存入出发端点*/ treep2=k; /*将k存入另一个端点*/ treep3=min; /*存储两个端点的最小权值*/ p+; c+=min; lowcostk=0;/*将顶点k加入生成树中*/ for(j=1;j=G.vnum;j+) if(G.arcskj!=0&G.arcskj=temp.key)&(ij) j-;/自后向前扫描找小于基准关键字的记录 if(ij) Ri=Rj;/把Rj移入Ri中 i+;/令i指向i+1 while(Ri.key=temp.key)&(ij) i+;/扑克前向后扫描找大于基准关键字的记录 if(ij) Rj=Ri;/把Ri移入Rj中 j-;/令j指向j-1 while(ij);/ Ri=temp;/ return i;/返回基准记录的最终位置i （2）递归的算法如下：void quicksort(recordtype R,int s,int t)/对排序文件Rs.t进行快速排序int i;/定义局部变量 if(slch=p-rch; p-rch=s; s-pf=0; r-pf=0; changeroot();void lrflip() p=r-rch; r-rch=p-lch; p-lch=r; s-lch=p-rch; p-rch=s;switch(p-pf) c