一元稀疏多项式相加.doc

课 程 设 计课程名称： C语言、数据结构 课题名称：一元稀疏多项式相加 班 级： 南湖07级电信1班 姓 名： 陈 理 指导教师： 吴岳芬 2010年 6月26日湖南理工学院信息与通信工程系一、 实验目的本课程设计是为了配合数据结构课程的开设，通过数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法，设计出一个对两个一元稀疏多项式进行相加,然后输入结果的程序。程序所能达到的功能:输入两个一元稀疏多项式，能够输出相加后的值。二、 实验任务及要求实验任务：设计一元稀疏多项式加法器。实验要求：一元稀疏多项式加法器的基本功能是： (1)输入并建立多项式； (2)输出多项式：n, c1, e1, c2, e2, cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。(3)两个多项式相加； (4)输出加法结果。三、需求设计3.1主程序的流程(1)输入第一个一元稀疏多项式.(2)输入第二个一元稀疏多项式.(3)对两个一元稀疏多项式进行相加.(4)输出两个一元稀疏多项式相加后的结果.3.2程序模块(1)项数的结构体Term(2)建立一元稀疏多项式函数 CreatPloy(void).(3)对两个一元稀疏多项式相加函数AddPolyn(&Pa,&Pb).(4)输出相加后值的函数PrintPloyn(P).3.3各模块之间的调用关系(1)主函数调用Term结构体(2)调用两次GreatPloy函数建立一元稀疏多项式(2)调用AddPolyn函数，对两个多项式进行相加(3)调用PrintPloyn函数，输出结果四、概要设计程序流程图(1)主函数流程图输入第一个一元稀疏多项式. CreatPloy(void)输入第二个一元稀疏多项式. CreatPloy(void)对两个一元稀疏多项式进行相加. AddPolyn(&Pa,&Pb)输出两个一元稀疏多项式相加后的结果. PrintPloyn(P)(2)GreatPloy函数流程图 输入项数n head=p1=p2=(struct term*)malloc(LEN); 输入第一项的系数和指数 coef expni=2 to i=n ;i+ p1=(struct term*)malloc(LEN);scanf(%d,%d,&p1-coef,&p1-expn);p1-next=NULL;p2-next=p1;p2=p2-next;return head(3) PrintPloyn函数流程图int m=0;while(p!=NULL)m+;printf(c%d=%d,e%d=%dn,m,p-coef,m,p-expn);p=p-next;printf(number=%dn,m);(4) AddPolyn函数流程图int n=0;struct term *p3,*head;while(p1!=NULL&p2!=NULL)n=n+1;n=1真假比较p1和p2所指结点指数建立头结点 head比较p1和p2所指结点指数把指数大的结点连入head把p1或p2剩下的结点连入head中返回head五、详细设计5.1抽象数据类型定义ADT Polynomial数据对象：D=ai|aiTermSet,i=1,2,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|ai-1,aiD，且ai-1中的指数值ai中的指数值,i=2,nCreatPloy(void)107数据结构课程设计_两个一元稀疏多项式相加操作结果：输入M项的系数和指数，建立一元多项式P。PrintPloyn(P)初始条件：一元二项式P存在。操作结果：输出一元二项式P。AddPolyn(&Pa,&Pb)初始条件：一元二项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb。ADT Polynomial5.2基本操作的算法描述(1)项数的结构体typedef struct/项的表示，多项式作为LinkList的数据元素 int coef;/系数 int expn;/指数Term；(2)输入M项的系数和指数，建立一元多项式Pstatus CreatPolyn(void) scanf(n); head=p1=p2=(elemtype*)malloc(LEN); scanf(p1-coef,p1-expn); for(i=2;icoef,p1-expn); p1-next=NULL; p2-next=p1; p2=p2-next; /for return(head); /CreatPolyn(3)完成多项式相加运算，即：Pa=Pa+Pbstatus AddPolyn(Term p1,Term p2) n=0; if(n=1) if(p1-expnp2-expn) head=p3=p1;p1=p1-next; /*if*/ else if(p1-expn=p2-expn) p1-coef=p1-coef+p2-coef; if(p1-coef=0)n=0;p1=p1-next;p2=p2-next; if(!p1)head=p2; if(!p2)head=p1; if(!p1&!p2) printf(answer is 0n); head=NULL;/*if*/ /*if*/else head=p3=p1;p1=p1-next;p2=p2-next; /*else*/ /*else if*/ elsehead=p3=p2;p2=p2-next; /*else*/ /*if*/else if(p1-expnp2-expn) p3-next=p1;p1=p1-next;p3=p3-next; /*if*/ else if(p1-expn=p2-expn) p1-coef=p1-coef+p2-coef; if(p1-coef=0) p1=p1-next;p2=p2-next; /*if*/else p3-next=p1;p1=p1-next;p2=p2-next;p3=p3-next; /*else*/ /*else if*/ else p3-next=p2;p2=p2-next;p3=p3-next;/*else*/ /*else*/ /*while*/ while(p1!=NULL) return(head);/*daapolyn*/(4)输出一元二项式Pstatus PrintPolyn(p) while(p) m+;printf(cm=p-coef,em=p-expn)/输出c1,e1,c2,e2cm,em,c为系数，e为指数 /while print(m);/输出项数/PrintPolyn六、调试分析运行方法如下1.根据提示输入第一个一元稀疏多项式的项数和各项数的系数和指数。如图1图1输入显示图2.根据提示输入第二个一元稀疏多项式的项数和各项数的系数和指数。如图23.输出两个一元二项式的相加后的结构，如图3七、测试结果第一组：输入2x+5x8-3.1x11 和7-5x8+11x9输出结果为。如图4第二组：输入6x-3-x+4.4x2-1.2x9和-6x-3+5.4x2-x2+7.8x1输出结果为。如图5第三组：输入1+x+ x2+x3 +x4+x5和- x3 -x4输出结果为。如图6通过上述3组实验证明该程序，在正确输入数据的前提条件下，能够按要求输出正确的结果，并按指定的输出格式输出。八、课程设计总结一元稀疏多项式相加是我选择的课程设计题目，在这次设计中我学到了很多实际应用的知识。 当得到课程设计指导书时，我认真分析了这一题目及相关要求，然后根据数据结构课所学写出相映算法，再后运用C 语言的知识将算法写成程序，进行修改，最后在Turbo C环境下进行运用，修改。 这次设计让我真切地感受到往往一个细节会决定整个程序的命运。所以在编程过程中理论与实践的结合是十分重要的，细节问题也是不容忽视的。九、参考文献1.晋良颍.数据结构M.人民邮电出版社，2002.05 34-412.徐孝凯,魏荣.数据结构M.机械工业出版社，1996.07 56-623.徐孝凯.数据结构简明教程.M.清华大学出版社，1995.04 106-1134.陈文博，朱青.数据结构与算法M，机械工业出版社，1996.09 125-127十、源代码#include#include#include#define LEN sizeof(node)typedef struct polynode /*用单链表存储多项式的结点结构*/ int coef; /*多项式的系数*/ int exp; /*指数*/ struct polynode *next; /*next是struct polynode类型中的一个成员，它又指向 struct polynode类型的数据，以此建立链表*/node;/*若定为node,*list;，意即node*与list同为结构指针类型*/node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/ node *h,*r,*s; int c,e; h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/ r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ printf(coef:); scanf(%d,&c); /*输入系数*/ printf(exp: ); scanf(%d,&e); /*输入指针*/ while(c!=0) /*输入系数为0时，表示多项式的输入结束*/ s=(node *)malloc(LEN); /*申请新结点*/ s-coef=c; /*申请新结点后赋值*/ s-exp=e; /*申请新结点后赋值*/ r-next=s; /*做尾插，插入新结点*/ r=s; /*r始终指向单链表的表尾*/ printf(coef:); scanf(%d,&c); printf(exp: ); scanf(%d,&e); r-next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/ return(h);void polyadd(node *polya, node *polyb)/*一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/ node *p,*q,*pre,*temp; int sum; p=polya-next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/ q=polyb-next; pre=polya; /*位置指针，指向和多项式polya*/ while(p!=NULL&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/ if(p-expexp) /*若p指向的多项式指数小于q指的指数*/ pre-next=p; /*将p结点加入到和多项式中*/ pre=pre-next; p=p-next; else if(p-exp=q-exp) /*若指数相等，则相应的系数相加*/ sum=p-coef+q-coef; if(sum!=0) p-coef=sum; pre-next=p;pre=pre-next;p=p-next; temp=q;q=q-next;free(temp); else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/ temp=p-next;free(p);p=temp; temp=q-next;free(q);q=temp; else /*若p指数大于q指数*/ pre-next=q; /*p结点不动，将q结点加入到和多项式中*/ pre=pre-next; q=q-next; if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ pre-next=p; else /*否则将B的结点加入到和多项式中*/ pre-next=q; void print(node * p) /*输出函数，打印出一元多项式*/ while(p-next!=NULL) p=p-next; printf( %d*x%d,p-coef,p-exp); main() /*主函数*/ node * polya,* polyb; printf(Welcome to use!n); printf(nPlease input the ploya include coef & exp:n); polya=create(); /*调用建立链表函数，创建多项式A*/ print(polya); printf(nPlease input the ployb include coef & exp:n); polyb=create(); /*同理，创建B*/ print(polyb); printf(nSum of the poly is:n); polyadd(polya,polyb); /*调用一元多项式