《程序设计：数据结构实验》由会员分享，可在线阅读，更多相关《程序设计：数据结构实验（33页珍藏版）》请在金锄头文库上搜索。
1、程序设计：数据结构实验福建农林大学金山学院本科实验报告规范（暂行）程序设计类一、每个实验项目一份实验报告。二、实验报告内容一般包括以下几个内容：1、 实验项目名称：2、 实验目的和要求:3、 实验内容和原理:4、实验环境：本次上机实验所使用的软硬件平台。5、算法描述及实验步用算法、流程图或者源代码的形式表达算法设计 思想与算法实现步骤。6、 调试过程：详细记录程序在调试 过程中出现的问题及解决方法。7、 实验结果：记录测试数据及程序 执行的结果。8、 总结：对上机实验结果进行分析、 上机的心得体会及改进意见。9、 附录（调试正确的源程序清单） 说明：1、2、3、4、5属于实验预习报告的内 容，
2、每次实验需经指导教师检查签字后才能进行实验。三、实验报告格式见附件二（可打印）。四、每学期将拟存档的学生实验报告按 课程、学生装订成册，即每个学生每门课程所有实验报告装订成一本。装订线在左侧,第一页加订实验报告封皮。五、福建农林大学计算机与信息学院实 验报告封皮范本见附件一。六、福建农林大学计算机与信息学院实 验报告范本见附件二。附件一:笳建感林大孽金d孽陵（程序设计类课程）实验报告课程名称: 姓 名: 系:专 业: 年 级: 学 号: 指导教师: 职 称:线性表及其应用计算机科学与技术08级林敏讲师2010 年 4 月 18 H实验项目列表序号实验项目名称成绩指导教师1线性表及其应用2哈夫曼
3、树及哈夫曼编码译码 的实现3Prim最小生成树4实现Fibonacci检索算法5快速、堆、基数排序算法的 设计6789101112福建农林大学金山学院实验报告系（教研室）：专业：计算机科学与技术 年级:08 一实验课程: 姓名：学号：实验室号：计算机号：实验时间：指导教师签字：成绩：实验一：完成多项式的相加运算（验证性、4学时）一、实验目的和要求完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问（3）熟悉线性表的的存储方法二、实验内容和原理1 .实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项
4、式；（2）输出 多项式；（3）多项式的相加运算。利用单链表实 现。2 .实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1） Windows XP中文操作系统（2） VC6. 0四、算法描述及实验步骤1、 描述：加法：输入建立一元多项式，进行简单加法运 算，输出结果；通过建立单链表A和B分别 存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中 存放数据运算结果；该过程通过定义指针变量P和q使它们分别指向两个多项式的 第一个节点，之后依次比较它们所指向的项的指数，即一
5、种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除P和q各自所指；情况二，P当前项指数大于q当前项，将q所指插入P所指 之前作为结果项之一；情况三，P当前项指 数小于q当前项,P所指作为多项式和的一 项，移动P指向下一项，进行比较，在移 动p, q至其中以个链空，把另一个链余下 节点插在P所指之后；乘法:定义指针P,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加,系数相乘，将值赋给新节点各自域，构成新的链表,最后返回头结点。可这样有一个问题，即新生成的链表，即 最终结果混乱，没有对数据进行过滤，相 同指数项应在执行加法运算，所
6、以可以这样实现，通过A链表的每一项与B链表各 项相乘的新生成节点单独构成一链表，并 将第一个链表加入另一新链表，循环此操 作将后生成的链表加之先前的链表，即可 实现排序问题。1）加法算法如下:polynomial * polyadd(polynomial * A, polynomial *B) 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
7、=p；p=p-next;elsex=(p-coef) + (q-coef);/*if (x!=0)p-coef=x;s=p；elses-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)/*核心算法实现两链表的乘法运算*/ polynomial * p, * q, * n, * head,* r, * temp, * m;/定义当前指针P，q风别指向两
8、链 表和头指针，尾指针，及新生成节 点nint exp;定义整型指数 float coef;/定义浮点型系数 head=(polynomial *)malloc(size of (polynomial) ;/创头节点为新生链表准备 head-next=NULL;置空链表r=head;临时变量，为后移指针做准备 p=A-next;当前指针跳过A链表头指向实际运算数while (p!=NULL)控制操作，循环A链表与内部while所控制B链表进行项之间的运算temp=(polynomial *)malloc(s izeof (polynomial);在内部创头节点为新生链表准备即A中 每一项与B中
9、各项相乘构成一新链 表t emp-next=NULL;置空链表/m=temp;临时变量，为后移指针做准备q=B-next;/ 当前指针跳过B链表头指向实际运算数 while(q!=NULL)(n=(polynomial *)malloc(siz eof (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;链表下一
10、项后移控制B/printf (%f %d ”, coef, exp); 调试用)p=p-next;控制A链表下一项m-next=NULL;链表尾置空 /head=head-next;/polyadd(head, temp);)return head;2、1）加法算法流程图polynomial *p, *q, *s, *r; float x;p=A-next;q=B-next;s=p;(D!=NULL)&(q!=NULL)Y_tr=exDy(a-exD)r=qa-next=o:x=(n-coef)+(a-s 二s-next=a:Yx! =0D；s=q；p-coes-next=Q=r;p=s-ne
11、xt;r=q;q= q!=NULL二Q r IIVfa vQ； 2）乘法算法流程图Dolvnomial * D, * q, * n, * head, * r, * temp, *int exp； float coef；head=(polynomialp=A-next;p!二NULL;temp= (polynomialt emp-next=NULL;nl=NTTT T -n=(polynomialext)二t)一ext)+cip;coef-dcoef*o-coef ,d=next 上JaJr IXv 、J TT TT m-next=NULL：return head;3、 代码（注释）仅作参考re
12、dbatzero#include stdio.h#include Minalloc.hutypedef struct linkiiode /*定义节点*/(float coef;int exp;struct linknode next;Ipolynomial;polynomial / creatlistO/*创建单链表号(float x;/*节点中存放项系数和指数*/int z;polynomial *head,*r*n;/*下指针,分别是头指针、尾指针和新建立节点的指针*/head=(polynomial )nalloc(sizeof(polynomial);/*malloc 分配内存单元给
13、头指针申请空间列head-next=NULL;六头指针next指向空位空链表状态*/r=head;printf建立一元多项式:(以系数0结束打印文字提醒用户输入*/while(x0)产建立单链表列(n=(polynomial *)malloc(sizeof(polynomial);/*建立新节点,将用户输入的数据分别作为项(各节点)的系数和指数*/n-x?oef=x;nxxp=z;r-next=n;六为指针指向下一新建节点*/r=r-next;/*后移尾指针*/r=n;printf(请按升号输入系数和指数:)；scanfr%f%d,&x,&z);r-next=NULL;head=head-next;/*链接节点使之勾成锥表*/return (head);/*还回head指针(链表头标志或是说地址)给函数调用者*/)void print( polynomial * head) /*打印输出函数”/polynomial *p;产为传入的链表设立当前指针引p=head.next:六将指针后移指向包含实际数据的节点*/wh
