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

数据结构实验报告实验一：一元多项式相加姓 名： 周 成 学 号： 13083511 专 业： 软件工程 任 课 教 师： 马慧珠 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.实验程序代码及运行结果：#include stdafx.h#include #include #include #include #define NULL 0typedef struct NODE float coef; /系数y int expn; /指?数y struct 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);/*创建链表*/NODE *Creat(int n) NODE *current, *previous, *head; int i; head = (NODE *)malloc(sizeof(NODE); /*创建头结点?*/ previous = head; for(i = 0; i coef, ¤t-expn); previous-next = current; previous = current; previous-next = NULL; return head;/*一?元a多项?式?的?想?加，?总体?考?虑?，?可分?qa的?指?数y比qb小?，?或等于pb(如?果?系数y相加等于0和不?等于0),或大于pb里?面?由InsertBefore和Delfirst两?个?小?模块组成一?部?分?*/NODE *AddPolyn(NODE *head1, NODE *head2) NODE *ha, *hb, *qa, *qb; int a, b; float sum; ha = head1; /*ha和hb指?向头结点?*/ hb = head2; qa = ha-next; /*qa和qb指?向头结点?的?下?一?个?结点?*/ qb = hb-next; while(qa & qb) /*qa和qb均非?空?*/ a = qa-expn; b = qb-expn; switch(compare(a, b) case -1 : /*qa-expn expn*/ ha = qa; qa = qa-next; break; case 0 : sum = qa-coef + qb-coef; /*系数y的?和*/ if(sum != 0.0) /*如?果?不?是?0.0*/ qa-coef = sum; /*改?变?系数y*/ ha = qa; else free(Delfirst(ha, qa); free(Delfirst(hb, qb); qa = ha-next; qb = hb-next; /*qb释放?后要a重?新?赋3值*/ break; case 1 : /*如?果?qa- expn qb - expn*/ Delfirst(hb, qb); InsertBefore(ha, qb); /*把?qb插?入?到?ha下?一?个?结点?之?前*/ qb = hb-next; ha = ha-next; break; if(qb) ha-next = qb; /*插?入?剩余的?pb*/ free(head2); return head1; /*比较?*/int compare(int a, int b) if(a b) return 1; else return 0;/*删?除y结点?q*/NODE *Delfirst(NODE *p1, NODE *q) p1 - next = q - next; return (q); /*插?入?结点?,引y入?结点?p,可以?让?p插?入?到?p2和p1之?间?*/void InsertBefore(NODE *p1, NODE *p2) NODE *p; p = p1-next; p1-next = p2; p2-next = p;/*打印?,为a了?美观?程序分?开a打印?*/void print(NODE *head) NODE *current; current = head-next; while(current-next != NULL) printf(%0.f * x%d + , current-coef, current-expn); current = current - next; printf(%0.f * x%d, current-coef, current-expn); /system（pause); int main() NODE *head1, *head2, *head3; int n1, n2; printf(请?输?入?你?需要a的?多项?式?的?项?数y n1 : ); scanf(%d, &n1); head1 = Creat(n1); printf(第一?个?多项?式?的?显?示? : n); print(head1); printf(n请?输?入?你?需要a的?多项?式?的?项?数y n2 : ); scanf(%d, &n2); head2 = Creat(n2); printf(n第二t个?多项?式?的?显?示? : n); print(head2); head3 = AddPolyn(head1, head2); printf(n合?并后的?多项?式?的?显?示? : n); print(head3); printf(n);运行结果：实验数据1如图：输入一个四次二项式X3+2X4，一个五次二项式X4+2X5，输出如图：实验数据2如图：输入一个五次四项式X2+X3+X4+X5，还有一个五次五项式1+X+X3+2X4+2X5输出如图所示实验数据3如图：输入一个七次三项式1+2x5+3X7，还有一个五次四项式1+2X2+3X4+4X5,输出如图：6.实验总结本来我对编程很没有信心，做这样一个课程设计感觉有点吃力，虽然有些人觉得很简单，但是我还是坚持做下来了，我不断的看书，翻阅资料，询问同学，上网搜索，总算有模有样地把这个