n元多项式的乘法

n元多项式的乘法 《数据结构》课程设计 题 目 n元多项式的乘法 学生姓名 指导教师 学 院 专业班级 完成时间 目 录(要求自动生成) 第一章 课程设计目的 ?????????????????????????????????????????????? 2 第二章 课程设计内容和要求 ????????????????????????????????????? 2 第三章 课程设计 ???????????????????????????????????????????????? 3 第四章 算法描述 ???????????????????????????????????????????????????????? 4 第五章 源代码 ???????????????????????????????????????????????????????????? 8 第六章 运行结果分析 ?????????????????????????????????????????????? 13 第七章 结束语 ?????????????????????????????????????????????????????????? 15 第八章 参考文献 ?????????????????????????????????????????????????????? 15 1 第一章 课程设计目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。 具体说来，这次课程设计主要有两大方面目的。 2 一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。 二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C++的知识，提高其编程能力与专业水平。 第二章 课程设计内容和要求 2.1课程设计内容 功能:完成两个n元多项式作乘法，给出明确的等式形式。 分步实施:1)( 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数; 2)( 完成最低要求:建立一个文件，实现两个一元二次多项式作乘法。 3)( 进一步要求:实现三元二次多项式的乘法。 2.1.1 该程序的运行环境为Windows xp系统，Microsoft Visual C++6.0版本。 第三章 课程设计分析 3.1 我们用的存储方式是单链表，单链表在C语言中是一种 3 非常常见的结构，而在C++中的实现却又有不同，在一些地方更简单，更严密。同时，由于C++的一些特点，使它具有C语言所不具有的“安全化”，所以本程序用C++。 有了链表特定的数据类型Mulpoly，接下来就需要建立这个链表。这里我们自定义一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点，存储多项式的信息(项数)，为head分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用c++语言中的malloc来实现;这时输入多项式的项数num，把它赋值给head的coef域，exp域赋值为1，此时再定义一个CreatePoly型的指针变量r指向head头结点。还要用类似的算法建立多项式的其它结点，剩余节点的插入用一个while循环来实现，while循环中的控制变量i从大于0的数n开始递增，直到到达num，此时while循环结束。While 循环的循环体由两部分组成，第一部分是为指针变量s分配存储空间和为其数据域赋值，分配存储空间同样用c++语言中的malloc来实现;第二部分是节点的指针域转换过程，将r的指针域指向新生成的结点s，相当于将生成结点依次用指针连接，然后将最后一个结点的指针域设置为NULL，具体代码如下: MulPoly *CreatePoly(){ MulPoly *head,*r,*s; int m,n,num,i=1; head=(MulPoly *)malloc(sizeof(MulPoly)); cout<<"请输入多项式的项数:"<>num; head->coef=num; head->exp=1; r=head; while(i<=num) //n不为0时建立多项式链表 { s=(MulPoly *)malloc(sizeof(MulPoly)); cout<<"输入第"<>n>>m; s->exp=m; s->coef=n; r->next=s; r=s; i++;} 4 r->next=null; return(head); } 在处理多项式相乘的问题时，定义一个PolyMulti函数实现，需要再建立一个MulPoly型的链表存储相乘之后的链表，定义结果链表的系数等于链表P1的系数乘以链表P2的系数:(p->coef)=(p1->coef)*(p2->coef) 结果链表的指数等于链表P1的指数乘以链表P2的指数:(p->exp)=(p1->exp)+(p2->exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个while循环来完成。具体代码如下: while(p!=q) {s=q; q=q->next;} s->next=q->next; free(q); } 还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。在主函数的开始需要定义三个MulPoly型指针变量，分别用来存储调用CreatePoly函数和PolyMulti函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间，s=(MulPoly *)malloc(sizeof(MulPoly));这条语句便可完成此操作。此条语句运用了c++语言库函数中的malloc函数，这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。调用构建链表函数CreatePoly后链表Pl便构建完成。接下来需要执行m=PolyMulti(p,q);语句，这条语句的目的是把多项式P1和P2相乘的结果多项式存储在链表m当中，然后执行Print(m);语句显示输出。主函数的程序框架如下: int main(){ MulPoly *p,*q,*m; p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); 5 Merge_Same(m); Print(m); system("pause"); } 程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作便是由Delete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个Merge_Same函数，调用Delete函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。 下面我们分析一下程序的性能。在主函数中，首先调用的是构造单链表函数CreatePoly，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的next域，时间复杂度为O(n)。接下来执行一个双重for循环，在内部的for循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点 n的操作都需要m次，共n个结点，则需要m次操作，时间 n复杂度为O(n)。 第四章 算法(数据结构)描述 一、 概要设计 定义单链表的抽象数据类型: 6 ADT LinkList{ 数据对象:D={ai|ai?ElemSet,i=1,2,3,…，n>=0} 数据关系:R={|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的新结点 7 LNode FindPrefious(ElemType X, LinkList L); 初始条件:线性表L已存在。 操作结果:在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 void ListDelete(LNode Pre); 初始条件:线性表L中结点P已找到。 操作结果:删除该结点。 链表的结点结构: ??????? ?data?next? 100 ??????? 80 60东部data域--存放结点值的数据域 西部40北部next域--存放结点的直接后继的地址(位置)的指针20域(链域) 0第一季度第三季度此题定义系数和指数结构如下: cen oexex f p t //------------------------------------------线性表的单链表存储结构-----------------------------------// Typedef struct Lnode{ ElemType data;//结点的数据域 Struct Lnode *next;//结点的指针域 }Lnode, *LinkList; //----------------------基本操作 ---------------------------------------------------------------------------// InitArray(&A, n, bound1, ..., boundn) 8 操作结果:若维数 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 Array 第五章 源代码(源代码必须给注释) 单链表表示 #include #include #include #include #define null 0 using 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; } 9 term *CreatePoly() { term *head,*r,*s; int m,n,num,i=1; head=(term *)malloc(sizeof(term));//建立一个头 结点 cout<<"请输入多项式的项数:"<>num; head->coef=num; head->expn=1; r=head; while(i<=num) //n不为0时建立多项式链表 { s=(term *)malloc(sizeof(term));//建立一个新结点 cout<<"输入第"<>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); 10 (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<<"两个多项式相乘的结果为: "<next;p!=null;p=p->next) cout<<"("<coef<<")"<<"x"<<"^"<expn<<"+"; cout<<"\b";} else cout<<"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) { 11 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项的系数和指数，建立表示一元多项式的有 序链表P if(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; } // CreatPolyn term* selsort(term *h) { term *g, *p, *q; if(!h) return NULL; float f; 12 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) 13 { 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，利用两个多项式的结点 构成"和多项式"。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term)); p->next = NULL; 14 while (qa && qb) { // Pa和Pb均非空 switch (Compare(qa,qb)) { case -1: // 多项式PA中当前结点的指数值小 p->next = qb; p = qb; qb = qb->next; break; case 0: // 两者的指数值相等 sum = qa->coef + qb->coef; if (sum != 0.0) { // 修改多项式PA中当前结点的系数值 p->next = qa; qa->coef = sum; p = qa; qa = qa->next; } else { // 删除多项式PA中当前结点 q = qa; qa = qa->next; free(q); } q = qb; qb = qb->next; free(q); break; case 1: // 多项式PB中当前结点的指数值小 p->next = qa; p = qa; qa = qa->next; break; } // switch } // while 15 if (Pa) p->next = qa; // 链接Pa中剩余结点 if (Pb) p->next = qb; // 链接Pb中剩余结点 q = h; h = h->next; free(q); return h; } // APolyn term* A(term *Pa, term *Pb) { int n; puts("输入第二个一元多项式的项数"); scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); if(Pb && Pb->coef>0) printf(" + "); PrintfPoly(Pb); Pa = APolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; } term* BPolyn(term *Pa, term *Pb) { // 多项式减法:Pa = Pa-Pb，利用两个多项式的结点构 成"差多项式"。 term *p = Pb; while(p) { p->coef *= -1; p = p->next; } return APolyn(Pa,Pb); } // BPolyn term* B(term *Pa, term *Pb) { int n; 16 puts("输入第二个一元多项式的项数"); scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); printf(" - "); putchar('(');PrintfPoly(Pb);putchar(')'); Pa = BPolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; } int main() { term *M,*N; term *p,*q,*m; char s[2]; int i,n; f: puts("\n1:加\n2:乘\n3:下一步"); cin>>i; switch(i) { case 1: puts("一元多项式计算:\n输入第一个一元多项式的项 数"); scanf("%d",&n); M = CreatPolyn(M,n); M = selsort(M); PrintfPoly(M); M = A(M,N); goto f; case 2: p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m); 17 goto f; case 3:break; default:puts("输入有误,请重新输入!"); } } /*程序源代码:*/ 数组表示 #include "stdio.h" #define N 100 //宏定义，为多项式的系数数组开辟空间 static int k=1;//

记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载

多项式的个数 void input(float a[],int na){//多项式a的系数输入，其中 na为次数 int i; printf("请输入多项式P%d(x)的各项系数数(从高次项 到低次项，中间缺项则为0):\n",k); for(i=0;i<=na;i++){//输入各项系数 scanf("%f",&a[i]); } while(a[0]==0){//首项系数不为0 printf("首项系数不能为0，请重新输入首项系数:"); scanf("%f",&a[0]); } printf("P%d(x)=%0.2f*x^%d",k,a[0],na); for(i=1;i方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载