实验报告二：线性表及其基本操作实验(2学时)

实验报告实验二线性表及其基本操作实验(2学时)实验目的：(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；(3)掌握线性表的顺序存储结构和动态存储结构之区分。实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算；(4)约瑟夫问题的求解。注：存储结构可以选用静态数组、动态数组、静态链表或动态链表之一。对链表也可以采用循环链表（含单向或双向）。实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验过程：（一元多项式的加法）【算法描述】定义两个指针qa和qb，分别指向多项式A和多项式B当前进行比较的某个结点，然后比较2个结点中的指数项，则有以下三种结果：指针qa所指结点的指数值小于指针qb所指结点的指数值，则应摘取指针qa所指的结点插入到“和多项式”链表当中去；指针qa所指结点的指数值大于指针qb所指结点的指数值，则应摘取指针qb所指的结点插入到“和多项式”链表当中去；指针qa所指结点的指数值等于指针qb所指结点的指数值，则将两个结点的系数相加，若和数不等于零，则修改qa所指结点的系数值，同时释放qb所指结点。反之，从多项式A的链表删除相应结点，并释放指针qa和qb所指结点。【源程序】#include<stdlib.h>#include<stdio.h>typedefstruct{floatcoef;intexpn;}term;typedefstructLNode{termdata;structLNode*next;}LNode,*LinkList;typedefLinkListpolynomial;intcmp(terma,termb){intflag;if(a.expn<b.expn)flag=-1;elseif(a.expn==b.expn)flag=0;elseflag=1;returnflag;}voidCreatPoly(polynomial*p,intm){inti;polynomialr,s;termpara;(*p)=(LNode*)malloc(sizeof(LNode));r=(*p);for(i=0;i<m;i++){ s=(LNode*)malloc(sizeof(LNode)); printf("pleaseinputcoefandexpn:\n"); scanf("%f%d",¶.coef,¶.expn); s->data.coef=para.coef; s->data.expn=para.expn; r->next=s; r=s;}r->next=NULL;}polynomialAddPoly(polynomial*pa,polynomial*pb){polynomialnewp,p,q,s,r;floatsum;p=(*pa)->next;q=(*pb)->next;newp=(LNode*)malloc(sizeof(LNode));r=newp;while(p&&q){ switch(cmp(p->data,q->data)) { case-1: s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case0: sum=p->data.coef+q->data.coef; if(sum!=0.0) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=sum; s->data.expn=q->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case1: s=(LNode*)malloc(sizeof(LNode)); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }}while(p){ s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next;}while(q){ s=(LNode*)malloc(sizeof(LNode)); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next;}r->next=NULL;returnnewp;}voidPoly(polynomialp){polynomials;s=p->next;while(s){ printf("%.2fx^%d",s->data.coef,s->data.expn); s=s->next;}printf("\n");}voidmain(){intm,n;polynomialp,q,newp;clrscr();printf("pleaseinputpa'sitem:\n");scanf("%d",&m);CreatPoly(&p,m);printf("pleaseinputpb'sitem:\n");scanf("%d",&n);CreatPoly(&q,n);Poly(p);