N项多项式乘法

课程设计(论文)题目名称n元多项式乘法课程名称数据结构课程设计学生姓名学号系、专业信息工程系、信息类指导教师2012年12 月23 日摘要功能：完成两个n元多项式作乘法，给出明确的等式形式。

分步实施：1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2．完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。

3．进一步要求：实现三元二次多项式的乘法。

有兴趣的同学可以自己扩充系统功能。

要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

1 问题描述完成两个n元多项式作乘法，给出明确的等式形式。

2 需求分析1)初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2)完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。

3) 进一步要求：实现三元二次多项式的乘法。

有兴趣的同学可以自己扩充系统功能。

1)界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

3 概要设计定义单链表的抽象数据类型：ADT LinkList{数据对象：D={ai|ai∈ElemSet,i=1,2,3,…，n>=0}数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}//----------------------------------------线性表的单链表基本操作------------------------------------------// LinkList InitList(void);构造一个空的线性表void DestroyList(LinkList *L);初始条件：线性表L已存在。

操作结果：销毁线性表L。

LinkList MakeEmpty(LinkList L)‘初始条件：线性表L已存在。

操作结果：将线性表L重置为空表。

int IsEmpty(LinkList L);初始条件：线性表L 已存在。

操作结果：判断线性表是否为空表。

int ListLength(LinkList L);初始条件：线性表L 已存在。

操作结果：返回线性表L 结点的个数。

LNode IsLast(LinkList L);初始条件：线性表L 已存在。

操作结果：返回线性表L 的最后一个结点（尾结点）。

LNode NewLNode(ElemType X);构造一个数据域为X 的新结点LNode FindPrefious(ElemType X, LinkList L);初始条件：线性表L 已存在。

操作结果：在线性表L 中寻找值为X 的结点，若找到则返回该结点的前驱，否则返回NULL 。

void ListDelete(LNode Pre);初始条件：线性表L 中结点P 已找到。

操作结果：删除该结点。

链表的结点结构: ┌──┬──┐ │data│next│ └──┴──┘data 域--存放结点值的数据域next 域--存放结点的直接后继的地址（位置）的指针域（链域）此题定义系数和指数结构如下：020406080100第一季度第三季度东部西部北部coe f exp nex t//------------------------------------------线性表的单链表存储结构-----------------------------------//Typedef struct Lnode{ElemType data;//结点的数据域Struct Lnode *next;//结点的指针域}Lnode, *LinkList;//----------------------基本操作-------------------------------------------------------------------// InitArray(&A, n, bound1, ..., boundn)操作结果：若维数 n 和各维长度合法则构造相应数组 A 。

DestroyArray(&A)初始条件：数组 A 已经存在。

操作结果：销毁数组 A。

Value(A, &e, index1, ..., indexn)初始条件：A 是 n 维数组，e 为元素变量， n 个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。

Assign(&A, e, index1, ..., indexn)初始条件：A 是 n 维数组，e 为元素变量，n 个下标值。

操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。

} ADT Array3．1抽象数据类型定义void DestroyList(LinkList *L);初始条件：线性表L已存在。

操作结果：销毁线性表L。

LinkList MakeEmpty(LinkList L)‘初始条件：线性表L已存在。

操作结果：将线性表L重置为空表。

int IsEmpty(LinkList L);初始条件：线性表L已存在。

操作结果：判断线性表是否为空表。

int ListLength(LinkList L);初始条件：线性表L已存在。

操作结果：返回线性表L结点的个数。

LNode IsLast(LinkList L);初始条件：线性表L已存在。

操作结果：返回线性表L的最后一个结点（尾结点）。

3．2模块划分1）n元多项式的表示。

2）n元多项式的存储。

3) n元多项式的输出4 详细设计4．1数据类型的定义1）链表型#include<stdlib.h>#include<stdio.h>#include<ctype.h>#include<iostream>2）数组型#include "stdio.h"#define N 100static int k=1;/4．2主要模块的算法描述系统流程图查询函数流程图如图3.2所示。

开始输入多项式a,b 多项式c=a*b输出多项式c结束Pa==NUL Pb==NULL Pa 为多项式a 指向结点的下一个点的指针data 为数据域，Pb 指向链表的数据域，Pb 为多项式b 指向头指针的下一个节点的指针。

开始Pb->data.varible==data.v arible data.expn+=pb->data.expn; pb=pb->nexb 无操作 Inslast(Vatric.data); Pa=pa->next Pb==NULL Pb=b.head->next Pb=c.head->next 123图3.2 无操作 Flag=0Pb==NULL Pa->data.Varible==pb->data .Varible Break 跳出当前循环 flag=1 Pa=pa->next Flag==0 Data=pb->data InslatVarl(c.data); 无操作 结束 Return cPb=pb->next 12 3*程序源代码：*/单链表表示#include<stdlib.h>#include<stdio.h>#include<ctype.h>#include<iostream>#define null 0using namespace std;typedef struct term{//项的表示，多项式的项作为LinkList的数据元素float coef; //系数int expn; //指数struct term *next;}term;int Empty(term *L){if(L->next!=null)return 1;return 0;}term *CreatePoly(){term *head,*r,*s;int m,n,num,i=1;head=(term *)malloc(sizeof(term));//建立一个头结点cout<<"请输入多项式的项数:"<<endl;cin>>num;head->coef=num;head->expn=1;r=head;while(i<=num) //n不为0时建立多项式链表{s=(term *)malloc(sizeof(term));//建立一个新结点cout<<"输入第"<<i<<"组系数和指数:"<<endl;cin>>n>>m;s->expn=m;s->coef=n;r->next=s;r=s;i++;}r->next=null;return(head);}term *PolyMulti(term *f,term*g){term *p1,*p2,*p,*r,*head;head=(term *)malloc(sizeof(term));head->coef=null;head->expn=null;r=head;for(p1=f->next;p1!=null;p1=p1->next){for(p2=g->next;p2!=null;p2=p2->next){p=(term *)malloc(sizeof(term));(p->coef)=(p1->coef)*(p2->coef);(p->expn)=(p1->expn)+(p2->expn);r->next=p;r=p;}r->next=null;return head;}void Delete(term * L,term * p){term * s,*q;s=L;q=L->next;while(p!=q){s=q;q=q->next;}s->next=q->next;free(q);}void Print(term * L){term * p;cout<<"两个多项式相乘的结果为："<<endl<<"P(x)=";if(Empty(L)){for(p=L->next;p!=null;p=p->next)cout<<"("<<p->coef<<")"<<"x"<<"^"<<p->expn<<"+";cout<<"\b";}elsecout<<"0";}void Merge_Same(term *f){term *p,*q;for(p=f->next;p!=null;p=p->next)for(q=p->next;q!=null;q=q->next)if(p->expn==q->expn){(p->coef)=(p->coef)+(q->coef);Delete(f,q);}if(p->coef==0){Delete(f,p);break;}}}term* CreatPolyn(term *P,int m){// 输入m项的系数和指数，建立表示一元多项式的有序链表Pif(m <= 0) return NULL;term *h = P = (term*)malloc(sizeof(term)), *q;P->coef = 0.0;int i;printf("依次输入%d个数（前一个为系数，后一个为指数）\n",m*2);for (i = 1; i <= m; ++i){ // 依次输入m个非零项scanf("%f%d",&P->coef,&P->expn);if(P->coef)q = P;P = P->next = (term*)malloc(sizeof(term));}q->next = NULL;free(P);return h;} // CreatPolynterm* selsort(term *h){term *g, *p, *q;if(!h) return NULL;float f;int i, fini = 1;for(g = h;g->next&&fini;g = g->next){fini = 0;for(p = h,q = h->next;q;p = p->next,q = q->next)if (p->expn < q->expn){f = p->coef;i = p->expn;p->coef = q->coef;p->expn = q->expn;q->coef = f;q->expn = i;fini = 1;}}for(g = h,p = g->next;p;)if(g->expn==p->expn){g->coef += p->coef;g->next = p->next;q = p;p = p->next;free(q);}else if(g->next){g = g->next;p = p->next;}return h;}void PrintfPoly(term *P){term *q = P;if(!q){putchar('0');return;}if(q->coef!=1){printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);q = q->next;while (q){if(q->coef > 0) putchar('+');if(q->coef!=1){printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);q = q->next;}}int Compare(term *a, term *b){if (a->expn < b->expn) return -1;if (a->expn > b->expn) return 1;return 0;}term* APolyn(term *Pa, term *Pb){// 多项式加法：Pa = Pa＋Pb，利用两个多项式的结点构成"和多项式"。