数据结构-实验一-一元多项式相加.docx

数据结构实验报告实验一：一元多项式相加姓 名： 周 成 学 号： 专 业： 软件工程 任 课 教 师： 马慧珠 2013年12 月01 日1.实验名称：一元多项式相加2.实验目的:如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。3.实验要求：对一元多项式能实现输入、输出，以及两个一元多项式相加及结果显示。4.实验内容：一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。运算规则如下：相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：（1）qa-exp大于qb-exp,则qa继续向后扫描。（2）qa-exp等于qb-exp,则将其系数相加。若相加结果不为零，将结果放入qa-coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。然后qa、qb继续向后扫描。（3）qa-exp小于qb-exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果表上。所得pa指向的链表即为两个多项式之和。5.实验程序代码及运行结果：#includestdafx.h#includestdio.h#includestdlib.h#includemalloc.h#includestdio.h#define NULL 0typedefstruct NODE{float coef; //系|ì数oyint expn; //指?数oystruct NODE *next; }NODE;NODE *Creat(int n);void print(NODE *head);NODE *AddPolyn(NODE *head1, NODE *head2);NODE *Delfirst(NODE *head, NODE *q);void InsertBefore(NODE *p1, NODE *p2);int compare(int a, int b);/*创???建?§链￠??表à¨a*/NODE *Creat(int n){ NODE *current, *previous, *head;int i; head = (NODE *)malloc(sizeof(NODE)); /*创???建?§头a?¤结¨￠点ì?*/ previous = head;for(i = 0; i n; i++){ current = (NODE *)malloc(sizeof(NODE)); printf(请?输o?入¨?系|ì数oy和¨a指?数oy : ); scanf(%f%d, current-coef, current-expn); previous-next = current; previous = current; } previous-next = NULL;return head;}/*一°?元a多¨¤项?式o?的ì?想?加¨?，ê?总á¨1体??考?虑?，ê?可¨|分¤?qa的ì?指?数oy比ਨqb小?，ê?或¨°等쨨于?¨2pb(如¨?果?系|ì数oy相¨¤加¨?等쨨于?¨20和¨a不?等쨨于?¨20),或¨°大?¨?于?¨2pb里¤?面?由?¨|InsertBefore和¨aDelfirst两￠?个?小?模?ê块¨|组á¨|成¨|一°?部?分¤?*/NODE *AddPolyn(NODE *head1, NODE *head2){ NODE *ha, *hb, *qa, *qb;int a, b;float sum; ha = head1; /*ha和¨ahb指?向¨°头a?¤结¨￠点ì?*/ hb = head2; qa = ha-next; /*qa和¨aqb指?向¨°头a?¤结¨￠点ì?的ì?下?一°?个?结¨￠点