2022年程序设计：数据结构实验 .pdf

《2022年程序设计：数据结构实验 .pdf》由会员分享，可在线阅读，更多相关《2022年程序设计：数据结构实验 .pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、福建农林大学金山学院本科实验报告规范（暂行）程序设计类一、每个实验项目一份实验报告。二、实验报告内容一般包括以下几个内容：1、实验项目名称：2、实验目的和要求：3、实验内容和原理：4、实验环境：本次上机实验所使用的软硬件平台。5、算法描述及实验步骤：用算法、 流程图或者源代码的形式表达算法设计思想与算法实现步骤。6、调试过程：详细记录程序在调试过程中出现的问题及解决方法。7、实验结果：记录测试数据及程序执行的结果。8、总结：对上机实验结果进行分析、上机的心得体会及改进意见。9、附录（调试正确的源程序清单）说明： 1、2、3、4、5 属于实验预习报告的内容，每次实验需经指导教师检查签字后才能进行

2、实验。三、实验报告格式见附件二（可打印）。四、每学期将拟存档的学生实验报告按课程、学生装订成册， 即每个学生每门课程所有实验报告装订成一本。装订线在左侧，第一页加订实验报告封皮。五、福建农林大学计算机与信息学院实验报告封皮范本见附件一。六、福建农林大学计算机与信息学院实验报告范本见附件二。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 20 页附件一：福建农林大学金山学院（程序设计类课程）实验报告课程名称：线性表及其应用姓名：系：专业：计算机科学与技术年级：08 级学号：指导教师：林敏职称：讲师2010 年4 月18 日精选学习资料 -

3、 - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 20 页实验项目列表序号实验项目名称成绩指导教师1 线性表及其应用2 哈夫曼树及哈夫曼编码译码的实现3 Prim 最小生成树4 实现 Fibonacci 检索算法5 快速、堆、基数排序算法的设计6 7 8 9 10 11 12 福建农林大学金山学院实验报告系（教研室） ：专业：计算机科学与技术年级：08 实验课程：姓名：学号：实验室号： _ 计算机号：实验时间：指导教师签字：成绩：实验一：完成多项式的相加运算（验证性、4 学时）一、 实验目的和要求精选学习资料 - - - - - - - - - 名师归纳

4、总结 - - - - - - -第 3 页，共 20 页完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、 实验内容和原理1. 实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式； （ 2）输出多项式； （3）多项式的相加运算。利用单链表实现。2. 实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。三、 实验环境硬件： （1）学生用微机（ 2）多媒体教室或远程教学（3）局域网环境软件： （1）Windows XP中文操作系统（2）VC6.

5、0 四、 算法描述及实验步骤1、描述：加法：输入建立一元多项式,进行简单加法运算,输出结果； 通过建立单链表A 和B 分别存放多项式的a和 b 的各项系数及指数；并且利用A 使得不产生新的节点而在 A 中存放数据运算结果；该过程通过定义指针变量p 和 q 使它们分别指向两个多项式的第一个节点，之后依次比较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p 所指项的系数 （和） ，同时删除 q 所指项，若和为零则同时删除p 和 q 各自所指；情况二，p 当前项指数大于q 当前项，将q所指插入p 所指之前作为结果项之一；情况三，p 当前项指数小于q 当前项， p 所指作为多项

6、式和的一项，移动p 指向下一项，进行比较，在移动p，q 至其中以个链空，把另一个链余下节点插在p 所指之后；乘法：定义指针p,q 指向所操作节点，通过A 链表的每一项与B 链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A 链表的每一项与B 链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序问题。1）加法算法如下：polynomial * polyadd(polyn

7、omial *A, polynomial *B) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 20 页 polynomial *p,*q,*s,*r; float x; p=A-next; q=B-next; s=p; while(p!=NULL)&(q!=NULL) if(p-exp)(q-exp) r=q-next; q-next=p; s-next=q; s=q; q=r; else if(p-exp)exp) s=p; p=p-next; else x=(p-coef)+(q-coef); /*if(x!=0) p-coef

8、=x; s=p; else s-next=p-next; free(p);*/ p=s-next; r=q; q=q-next; free(r); if(q!=NULL) s-next=q; free(B); return A; 2） 乘法算法polynomial * polyand(polynomial *A, polynomial *B) /*核心算法实现两链表的乘法运算*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 20 页 polynomial * p,* q,* n,* head,* r,* temp,* m; /定义当

9、前指针 p，q 风别指向两链表和头指针，尾指针，及新生成节点n int exp; /定义整型指数float coef; /定义浮点型系数head=(polynomial *)malloc(sizeof(polynomial); /创头节点为新生链表准备head-next=NULL; /置空链表 r=head; /临时变量，为后移指针做准备p=A-next; /当前指针跳过A链表头指向实际运算数while(p!=NULL) /控制操作，循环A链表与内部while 所控制 B链表进行项之间的运算 temp=(polynomial *)malloc(sizeof(polynomial); /在内部创

10、头节点为新生链表准备即 A中每一项与B中各项相乘构成一新链表 temp-next=NULL; /置空链表 m=temp; /临时变量，为后移指针做准备 q=B-next; /当前指针跳过B链表头指向实际运算数 while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新节点exp=p-exp+q-exp; /进行系数相加操作coef=p-coef*q-coef; / /进行指数相乘操作n-coef=coef; /赋值新节点的系数域n-exp=exp; /赋值新节点的指数域m-next=n; /链接节点至头结点，构成链表m=m-ne

11、xt; /后移指针，为下一节点做准备q=q-next; /控制 B链表下一项/printf(%f %d ,coef,exp); /调试用 p=p-next; /控制 A链表下一项 m-next=NULL; /链表尾置空/head=head-next; polyadd(head,temp); / return head; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 20 页2、1）加法算法流程图2）乘法算法流程图polynomial *p,*q,*s,*r; float x; p=A-next;q=B-next;s=p; Y (p-e

12、xp)(q-exp) N r=q-next; s-next=q; free(B); return A; p=s-next;r=q;q=q-next; free(r); x=(p-coef)+(q-coef);q-next=p; s-next=q; Y x！=0 N s=q; (p-exp)exp)N Y (p!=NULL)&(q!=NULL)q=r;p-coef=x; s=p;s-next=p-next;free(p); s=p; p=p-next;q!=NULLY 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 20 页3、代码(注释

13、) 仅作参考 -redbatzeropolynomial * p,* q,* n,* head,* r,* temp,* m;int exp；float coef；head=(polynomial *)malloc(sizeof(polynomial); head-next=NULL;p=A-next; temp=(polynomial *)malloc(sizeof(polynomial);temp-next=NULL; m=temp;q=B-next;n=(polynomial *)malloc(sizeof(polynomial);exp=p-exp+q-exp; coef=p-coef

14、*q-coef; n-coef=coef; n-exp=exp; m-next=n; m=m-next; q=q-next;p!=NULL; q!=NULL; p=p-next; m-next=NULL; polyadd(head,temp);return head; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 20 页#include stdio.h #include malloc.h typedef struct linknode /*定义节点 */ float coef; int exp; struct linknode *

15、next; polynomial; polynomial * creatlist() /* 创建单链表 */ float x; /*节点中存放项系数和指数*/ int z; polynomial *head,*r,*n; /* 下指针 ,分别是头指针、尾指针和新建立节点的指针*/ head=(polynomial *)malloc(sizeof(polynomial); /*malloc 分配内存单元给头指针申请空间*/ head-next=NULL; /* 头指针 next 指向空位空链表状态*/ r=head; printf( 建立一元多项式:(以系数 0 结束)n);/* 打印文字提醒用

16、户输入*/ while(x!=0) /* 建立单链表 */ n=(polynomial *)malloc(sizeof(polynomial); /*建立新节点 ,将用户输入的数据分别作为项(各节点 )的系数和指数 */ n-coef=x; n-exp=z; r-next=n; /*为指针指向下一新建节点*/ r=r-next; /*后移尾指针 */ /r=n; printf( 请按升幂输入系数和指数:); scanf(%f%d,&x,&z); r-next=NULL; head=head-next; /*链接节点使之勾成链表*/ return (head); /*还回 head指针 (链表头

17、标志或是说地址)给函数调用者 */ void print( polynomial * head) /*打印输出函数 */ polynomial *p; /* 为传入的链表设立当前指针*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 20 页p=head-next; /*将指针后移指向包含实际数据的节点*/ while(p!=NULL) /*判断需要打印的链表是否为空*/ printf(%.2fX(%d) ,p-coef,p-exp);/* 打印当前指针所指项的数据*/ p=p-next; /* 后移指针指向下一节点*/ printf

18、(n); polynomial * polyadd(polynomial *A, polynomial *B) /* 核心算法实现两链表的加法运算并将结果保存在A 中*/ polynomial *p,*q,*s,*r; /* 为链表设立指针分别指向链表A 和链表 B(多项式 A 和 B)，s 为临时存放为后续移动指针做地址保留*/ float x; p=A-next; q=B-next; s=A;/*/ /*s 作为 p 的前驱 */ while(p!=NULL)&(q!=NULL) /*判断所比较链表是否为空不同时为空时反复执行下列函数*/ if(p-exp)(q-exp) /*将 q 插入

19、 p 之前 */ r=q-next; /*保存当前 q的下一结点地址为r 后移作准备*/ q-next=p; /* 将 p 接到到 q 之后 */ s-next=q; /*将 q 彻底的插入到A 链表中 p 之前作为结果项之一 */ s=q; /*修改当前指针为下一节点作比较准备*/ q=r; else if(p-exp)exp) /*将 p 作为结果项之一，后移p 进行下一结点比较 */ s=p; /*后移 s*/ p=p-next; /* 后移当前指针p 指向下一节点 */ else /*当前链表中节点的指数相等进行系数加法运算*/ 精选学习资料 - - - - - - - - - 名师归

20、纳总结 - - - - - - -第 10 页，共 20 页x=(p-coef)+(q-coef); /* 实现系数相加赋给x，节点中的系数单元*/ if(x!=0) /* 判断系数和是否为零,不为零执行系数替换原有数据 */ p-coef=x; s=p; /*p 的前驱指针后移 */ else /*系数和为零 */ s-next=p-next; /*为释放 p 准备 */ free(p); p=s-next; /*p 指针指向下一节点*/ r=q; /*为释放 q 作准备 */ q=q-next; /*q 指向下一节点 */ free(r); if(q!=NULL) /*循环结束将q 中剩余

21、节点直接插入p 的为节点之后作为结果项 */ s-next=q; free(B); /*运算结束释放B 链锁占空间 */ return A; /* 还回 A 链给函数调用者*/ polynomial * polyand(polynomial *A, polynomial *B) /* 核心算法实现两链表的乘法运算*/ polynomial * p,* q,* n,* head,* r,* temp,* m; /定义当前指针p，q 风别指向两链表和头指针，尾指针，及新生成节点n int exp; /定义整型指数float coef; /定义浮点型系数head=(polynomial *)mall

22、oc(sizeof(polynomial); /创头节点为新生链表准备head-next=NULL; /置空链表r=head; /临时变量，为后移指针做准备p=A-next; /当前指针跳过A 链表头指向实际运算数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 20 页while(p!=NULL) /控制操作，循环A 链表与内部while 所控制 B 链表进行项之间的运算 temp=(polynomial *)malloc(sizeof(polynomial); /在内部创头节点为新生链表准备即A 中每一项与B 中各项相乘构成一新链表

23、temp-next=NULL; /置空链表m=temp; /临时变量，为后移指针做准备q=B-next; /当前指针跳过B 链表头指向实际运算数while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新节点exp=p-exp+q-exp; /进行系数相加操作coef=p-coef*q-coef; / /进行指数相乘操作n-coef=coef; /赋值新节点的系数域n-exp=exp; /赋值新节点的指数域m-next=n; /链接节点至头结点，构成链表m=m-next; /后移指针，为下一节点做准备q=q-next; /控制 B

24、 链表下一项/printf(%f %d ,coef,exp); /调试用 p=p-next; /控制 A 链表下一项m-next=NULL; /链表尾置空/head=head-next; polyadd(head,temp); / return head; void selet( polynomial * A,polynomial * B) int p; polynomial * C; printf(1 、实现相加运算 n2、实现相乘运算 n); printf( 请选择运算 :); scanf(%d,&p); while(p!=1&p!=2) 精选学习资料 - - - - - - - - -

25、名师归纳总结 - - - - - - -第 12 页，共 20 页printf( 输入错误 ,请重新选择 :n); scanf(%d,&p); if(p=1) C=polyadd(A,B); else if(p=2) C=polyand(A,B); printf(The result is:n); print(C); /* 调用输出打印函数，打印运算结果*/ int main() /* 主函数 */ polynomial * A,* B; /*设立指针分别指向多项式链表A 和链表 B 以及 C 作为结果 */ A=creatlist(); /*建立打印多项式A*/ print(A); B=cr

26、eatlist(); /* 建立打印多项式B*/ print(B); selet(A,B); return 0; /*还回系统调用0，结束整个程序*/ 4、调试过程1 打印输出调试：输入（3, 4） （-2 ,5） （2.6 ,7） 即 3x4-2x5+2.6x6 输出 3.00 x(4) -2.00 x(5) 2.60 x(6) 如图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 20 页输出正常；2 加法运算调试输入数据：（2,3） （3,4） （4,5）和（1,2） （3,4） （-5,5）即 2x3+3x4+4x5和 x2+

27、3x4-5x5并没有项预期的一样实现加法运算，而是在打印出各项数据后程序终止。如图：输入数据：（2,3） （3,4） （4,5）和（ 1,3） （3,4） （-5,5）即 2x3+3x4+4x5 和x3+3x4-5x5结果和项预期的一样实现了加法运算，如图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 20 页对比得知数据和唯一不同的是的第一项的的指数大于的第一项指数因此应该想到程序在执行比较第一项之后并不能进行该有的操作即而之后的第二项第三项却可以执行有暗示着实现 (p-exp)(q-exp) 并没内部错误：因此矛头指向了poly

28、nomial *p,*q,*s,*r; float x; p=A-next; q=B-next; s=p;/* 出错原因 */ 而其中正是出错所在了，是作为的前驱而不是p -next 的前驱，故而该是s=A；修改后正常的实现了改算法；但由于程序以实现该算法的核心思想为主因此并没有过多注意的在用户界面上实现和排序问题和出错等处理。因此对用户输入的要求严格。3 乘法运算调试通过以上改正后进行测试测试数据（3,4） （4,5） （5,6）和（ 2，4） （3，6） （6,7）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 20 页未能得到预

29、期结果；分析：可知第一项6.00 x(8)并没能出现可能有两个原因，一是执行运算时跳过了B 链表第一项；二是运算了单没能打印出；有后面的数据8.00 x(9)可知 ,是第二种可能；因此在执行运算后用printf(%f %d ,coef,exp); 得结果如图：可以确定错误出处了，经检查知运算后多了head=head-next;将其删除即可。六、实验结果测试数据（ 1）：2,3 3,4 5,6 和 1,2 2,3 3,4 5,7 即 2x3+3x4+5x6 和 1x22x3+3x4+5x7实验结果（ 1）：加法 1.00 x(2) 4.00 x(3) 6.00 x(4) 5.00 x(5) 5.

30、00 x(7) 即 1.00 x2+4.00 x3+ 6.00 x4+ 5.00 x5+ 5.00 x7 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 20 页乘法9.00 x(8) 12.00 x(9) 15.00 x(10) 38x(11) 30 x(13)即 9x2+12x3+15 x4+38x5+30 x(13) 实验截图（ 1） ：加法乘法测试数据（ 2） ：加法1,2 2,3 3,5 和-3,2 2,3 4,4 0.4 ,5 即 1x2 +2x3+3x5 和 -3x2 +2x3+4x4+0.4 x5 乘法：精选学习资料

31、- - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 20 页3,4 5,6 0.5,7和5,6 -3,7 -0.8,8 即3x4+5x6+0.5x7和5x6-3x7-0.8x8 实验结果（ 2） ：加法-2.00 x(2) 4.00 x(3) 4.00 x(4) 3.4x(5) 即-2.00 x2+4.00 x3 +4 .00 x4+ 3.4x5 乘法15.00 x(10) -9.00 x(11) 22.60 x(12) -12.50 x(13) -5.50 x(14) -0.40 x(15) 即 5.00 x10-9.00 x11+22.60 x12

32、-12.50 x13-5.50 x14-0.40 x15 实验截图（ 2） ：加法乘法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 20 页七、总结在设计该算法时， 由于过于依赖书本上的例子， 导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果， 而是再度利用了链表之一来进行节点的比较插入删除等操作。大大压缩了程序代码，节省了程序空间使用，但不能避免的是必须要求输入数据时按

33、升幂排序的不足当然可在数据的输入后先做一个节点的排序函数， 通过对链表排序后再进行之后加法或乘法运算也是可以的。 但它也给后续乘法的实现提供了便利，当前我们的重点是实现单链表的加法乘法运算，故而，我选择了这个算法，并真正的实现了它。设计中让我更深的体会到了动手能力的重要性，在实现乘法时虽然花了我很多时间去研究书上虽然错误的算法，但那提高了我的洞察能力，并让我独自思考，最终虽然很局限（数据输入上）的实现了一元精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 20 页多项式的加乘法运算，可是我学到了远远不止这些。附录：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 20 页