数据结构课程设计实验报告
专业班级：
学号：
姓名：
2011年1月1日
题目：一元多项式的运算
1、题目描述
一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。
在数学上，一个一元n次多项式P n(X)可按降序写成：
P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0
它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示：
P=(P n，P(n-1)，......，P1，P0)
每一项的指数i隐含在其系数P i的序号里。
假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示：
Q=(q m,q(m-1)，.....，q1，q0)
不是一般性，假设吗吗m R n(X)= P n(X)+ Q m(X) 很显然，可以对P,Q和R采用顺序存储结构，使得多项式相加的算法定义和实现简单化。然而，在通常的应用中，多项式的次数可能变化很大而且很高，使得顺序存储结构的最大长度很难确定。特别是在处理项数少且次数特别高的情况下，对内存空间的浪费是相当大的。因此，一般情况下，都采用链式存储结构来处理多项式的运算，使得两个线性链表分 别表示一元多项式P n(X)和Q m(X)，每个结点表示多项式中的一项。 通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就是去了意义，在计算机内要表示一个多项式，至少具有以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形成一个多项式。 2、任务要求 系数定义的是float型，范围是3.4*10^-38~3.4*10^38;指数定义的是int型，范围是-2147483648~+2147483647；输入多项式系数及指数，系统会自动将系数转化为浮点型。 功能： （1）．提示输入数据。要求先输入多项式的项数。 （2）．创建多项式。接收输入的数据，并保存到链表中。 （3）．显示已经创建好的多项式。 （4）．实现加、减法运算。 （5）.退出程序 3、概要设计 (1)链表结点的类型定义 (2)建立有序链表void CreatPolyn(LinkList &L,int n) (3)多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) (4)多项式链表的输出void printList(LinkList L) 4、详细设计 (1)链表结点的类型定义 typedef struct //在struct前使用关键字typedef，表示是声明新类型 { float coef; //系数 int expn; //指数 }DataType; //DataType是新类型 typedef struct node //单链表的存储 { DataType data; //数据域 struct node *next; //指向下一个结点 }ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型 (2)建立有序链表 要实现多项式的加法运算，首先要建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作LocateNode有所不同，二是结点的插入操作InsertNode不同，这两个操作算法分别如下： //结点的查找定位 int LocateNode(LinkList L,DataType e,int &q) { ListNode *p=L->next; q=0;//记录结点位置序号 while(p&&e.expn { p=p->next; q++; } if(p==NULL||e.expn!=p->data.expn) return 0; else return 1; } void InsertNode(LinkList &L,DataType e,int q)函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。将s节点插入到e所指向的链表。在该函数的操作中，要注意指针是如何移动的。 //有序链表结点的插入 void InsertNode(LinkList &L,DataType e,int q) { ListNode *s,*p; int i=0; p=L; while(p->next && i { p=p->next; i++; }//查找插入位置 s=(ListNode*)malloc(sizeof(ListNode)); s->data.coef=e.coef; s->data.expn=e.expn; s->next=p->next; p->next=s; } 有了上述两个“结点的查找定位算法”和“有序链表结点的插入算法”， int n保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为n时，将不再提示用户继续输入多项式的系数和指数。建立一个一元多项式的单链表的具体算法如下： //多项式链表的建立 void CreatPolyn(LinkList &L,int n) { LinkList pa; //定义一个头指针为pa链表 int i,q; //i用来计输入的项数，q指结点的位置序号 DataType e; //插入的值e pa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点 pa->next=NULL; for(i=1;i<=n;i++) { scanf("%f,%d",&e.coef,&e.expn); if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项 InsertNode(pa,e,q); //调用InsertNode函数插入结点 } L=pa; } (3)多项式链表的相加 根据一元多项式相加的运算规则：对于一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中相应的位置。 根据以上运算规则，其实现算法思路如下： 假设pc为指向“和多项式链表”当前尾结点的指针，指针pa和pb分别指向两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项值，有下面三种情况： 1.若指针pa所指结点的指数值大于指针pb所指结点的指数值，则取pa指针所指向的结点插入到pc指针所指结点之后，分别修改指针pa和pc，使之指向链表的下一个结点； 2.若指针pa所指结点的指数值小于指针pb所指结点的指数值，则取pb指针所指向的结点插入到pc指针所指结点之后，分别修改指针pb和pc，使之指向链表的下一个结点； 3.若指针pa所指结点的指数值等于指针pb所指结点的指数值，则将两结点中的系数相加，如果其和数不为零，则修改pa指针所指结点中的系数值，将其结点插入到pc指针所指结点之后，分别修改pa、pb和pc，使之指向各自链表的下一个结点，同时删除并释放指针pb原先指向各自链表的下一个结点；如果和数为零，保存pa和pb所指向的结点，修改pa和pb指针使之指向各自链表的下一个结点，然后释放保存的两个结点。再比较指针pa 和pb指向节点中的指数项值，分3种情况进行处理….. 这样的操作一直继续到pa或pb等于NULL为止。最后将未结束的链表后面剩余的节点连接到pc指针所指向结点之后。 上述多项式的相加过程和两个有序链表合并的过程类似，不同之处仅在于多项式的比较多了相等比较后的操作。因此，多项式相加的过程完全可以利用线性链表的基本操作来实现。具体实现多项式相加的算法如下： //多项式链表的相加 void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) { //两个有序链表La和Lb表示的多项式相加 ListNode *pa,*pb,*pc,*s; float sum; pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while (pa&&pb) { if(pa->data.expn > pb->data.expn) { pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn < pb->data.expn) { pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef+pb->data.coef; if(fabs(sum)>0) { //系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else{ s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } pc->next=pa?pa:pb;//插入链表剩余部分 free(Lb);//释放Lb的头结点 } (4) 多项式链表的输出 void printList(LinkList L)函数功能：显示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。因此，输出多项式链表的算法实现如下： //多项式链表的输出 void printList(LinkList L) { ListNode *p; p=L->next; while(p) { printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn); p=p->next; } printf("\n"); } 源程序代码： #include #include #include //多项式链表结点类型定义 typedef struct //在struct前使用关键字typedef，表示是声明新类型 { float coef; //系数 int expn; //指数 }DataType; //DataType是新类型 typedef struct node //单链表的存储 { DataType data; //数据域 struct node *next; //指向下一个结点 }ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型 //结点的查找定位 int LocateNode(LinkList L,DataType e,int &q) { ListNode *p=L->next; q=0;//记录结点位置序号 while(p&&e.expn { p=p->next; q++; } if(p==NULL||e.expn!=p->data.expn) return 0; else return 1; } //有序链表结点的插入 void InsertNode(LinkList &L,DataType e,int q) { ListNode *s,*p; int i=0; p=L; while(p->next && i { p=p->next; i++; } s=(ListNode*)malloc(sizeof(ListNode)); s->data.coef=e.coef; s->data.expn=e.expn; s->next=p->next; p->next=s; } //多项式链表的建立 void CreatPolyn(LinkList &L,int n) { LinkList pa; //定义一个头指针为pa链表 int i,q; //i用来计输入的项数，q指结点的位置序号 DataType e; //插入的值e pa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点 pa->next=NULL; for(i=1;i<=n;i++) { scanf("%f,%d",&e.coef,&e.expn); if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项 InsertNode(pa,e,q); //调用InsertNode函数插入结点} L=pa; } //多项式链表的输出 void printList(LinkList L) { ListNode *p; p=L->next; while(p) { printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn); p=p->next; } printf("\n"); } //多项式链表的相加 void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) { //两个有序链表La和Lb表示的多项式相加 ListNode *pa,*pb,*pc,*s; float sum; pa=La->next;pb=Lb->next;//pa和pb分别指向两个链表的开始结点Lc=pc=La;//用La的头结点作为Lc的头结点 while (pa&&pb) { if(pa->data.expn > pb->data.expn) { pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn < pb->data.expn) { pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef+pb->data.coef; if(fabs(sum)>0) {//系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else{ s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } pc->next=pa?pa:pb;//插入链表剩余部分 free(Lb);//释放Lb的头结点 } //主控函数 void main() { LinkList La,Lb,Lc; int n; printf("输入第一个多项式的项数:"); scanf("%d",&n); printf("输入第一个多项式的每一项的系数,指数:\n"); CreatPolyn(La,n); printf("第一个多项式为:"); printList(La); printf("输入第二个多项式的项数:"); scanf("%d",&n); printf("输入第二个多项式的每一项的系数,指数:"); CreatPolyn(Lb,n); printf("第二个多项式为:"); printList(Lb); AddPolyn(La,Lb,Lc); printf("\n相加后的和多项式为:"); printList(Lc); } 5、调试分析 此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若想计数多个多项式的和或者差的话，必须退出界面重新开始计算。在补充程序里面，解决了程序没有的选择功能表的功能，及其多项式的乘法运算。 6. 测试结果 输入多项式的项数，并且显示多项式及其两个多项式的和： 补充程序： 多项式运算程序具有以下基本功能： 1．界面输出，提示如何输入数据。要求先输入多项式的项数。 2．创建多项式。接收输入的数据，并保存到链表中。 3．显示程序的功能表，允许使用者选择运算类型。 4．显示已经创建好的多项式。 5．实现加法运算。 6．实现减法运算。 7．实现乘法运算。 8．清除内存内容，销毁创建的链表，退出程序。 该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。 源程序代码： #include #include /***************以下函数实现链表的定义********************/ /*该函数的功能:在计算机内要表示一个多项式，至少以下数据信息--系数信息、指数信息和指向下一个单项式的指针。 通过指针，我们就可以把多个单项式连接起来，形式一个多项式.*/ typedef struct Polynomial { float coef; //系数 int expn; //指数 struct Polynomial *next; //指向下一个结点 }*Polyn,Polynomial; //Polyn为结点指针类型 /**************以下函数用来实现链表的顺序排列和合并相同的项***************/ /*该函数的功能:实现链表的顺序排列和合并相同的项。将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。 将p节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。*/ void Insert(Polyn p,Polyn h) { if(p->coef==0) free(p); //系数为0的话释放结点 else //如果系数不为0 { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn) //将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef) //系数为0的话释放结点 { q1->next=q2->next; free(q2); } } else //指数为新时将结点插入 { p->next=q2; q1->next=p; } } }//Insert /******************以下函数实现建立一个多项式*************************/ /*该函数功能:创建新的多项式链表。 int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。*/ Polyn CreatePolyn(Polyn head,int m)//建立一个头指针为head、项数为m的一元多项式,int m 是保存的多项式的项数 { //在主程序初始时，先输入的多项式中的项数m、n 在这里为m。主程序中的pa、pb 在此为head int i;//定义int i计数，当i Polyn p; //定义一个p链表 p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据,用到分配空间的函数malloc()为新建链表分配空间 printf("请输入第%d项的系数与指数:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head; }//CreatePolyn /**********************以下函数实现多项式的销毁**********************/ /*该函数的功能:销毁掉创建的两个链表，释放内存。以辅助退出程序*/ void DestroyPolyn(Polyn p)//销毁多项式p { Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) { free(q1); q1=q2; //指针后移 q2=q2->next; } } /*******************以下函数实现显示输出多项式**************** ***/ /*该函数的功能:显示多项式链表。在该函数中较复杂的是如何控制链表的输出,尤其是第一项的输出，同时还有符号的控制。 在输出第一项时要判断是不是常数项,若是,则不要输出字符x。*/ void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器,flag=1表示为第一项 if(!q) //若多项式为空,输出0 { putchar('0'); printf("\n"); return; } while (q) { if(q->coef>0&&flag!=1)//系数大于0且不是第一项 putchar('+'); if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf("%g",q->coef); if(q->expn==1) putchar('X'); else if(q->expn) printf("X^%d",q->expn); } else{ if(q->coef==1) { if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf("X^%d",q->expn); } if(q->coef==-1) { if(!q->expn) printf("-1"); else if(q->expn==1) printf("-X"); else printf("-X^%d",q->expn); } } q=q->next; flag++; }//while printf("\n"); }//PrintPolyn /*********************在下面的辅助乘法和加法运算****************/ /*该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。用来辅助加法和乘法运算。*/ int compare(Polyn a,Polyn b)//a、b两个多项式 { if(a&&b)//a、b多项式均非空 { if(!b||a->expn>b->expn) //a的指数大于b的指数 return 1; else if(!a||a->expn return -1; else //a的指数等于b的指数 return 0; } else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 }//compare /*********************以下函数实现加法*********************/ /*该函数功能:实现两个多项式pa、pb相加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。 在加法计算中要求pa与pb的幂次序都是升序，否则可能得到错误的结果。*/ Polyn AddPolyn(Polyn pa,Polyn pb)//求解并建立多项式a+b，返回其头指针 { Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial));//malloc()函数为其分配内存空间 switch(compare(qa,qb)) { case 1: //a的指数大于b的指数，a、b多项式不会实现相加运算 { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: //a的指数等于b的指数，系数和为a、b多项式的系数相加之和，指数即为其两者相同的指数 { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: //a的指数小于b的指数，a、b多项式不会实现相加运算 { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } }//switch if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 }//while return headc; }//AddPolyn /********************以下函数实现减法***********************/ /*该函数功能:实现两个多项式pa、pb相减，其原理根加法类似，将指数相同的系数相减。与加法不同的是在送在减法中，创建了新的链表来存放结果，并返回该链表的头指针。*/ Polyn SubtractPolyn(Polyn pa,Polyn pb)//求解并建立多项式a+b，返回其头指针 { Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p){ //将pb的系数取反 p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1; return pd; }//SubtractPolyn /*******************以下函数实现乘法*********************/ /*该函数功能:实现两个多项式相乘，A(X) * B(x) 。 计算时运用单项式与多项式相乘的法则，然后再次运用单项式与多项式相乘的法则。*/ Polyn MultiplyPolyn(Polyn pa,Polyn pb)//求解并建立多项式a*b，返回其头指针(该函数实现乘法) { Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next){ for(qb=pb->next;qb;qb=qb->next){ pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf; }//MultiplyPolyn /********************主函数实现显示与功能选择**********************/ /*该函数功能:main函数用来实现提示使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main（）函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过if语句来实现功能的选择， 从而对整个程序流程进行控制。*/ int main() { int m,n,flag=0;//m、n为分别为a、b两个多项式的项数 Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL //pc头指针所在的多项式用在加法中作为结果，pd用在加法中，pf乘法中 printf("*******************欢迎使用一元多项式运算程序*****************\n"); printf("请输入第一个多项式a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m); //建立第一个多项式a printf("请输入第二个多项式b的项数:"); scanf("%d",&n); pb=CreatePolyn(pb,n); //建立第二个多项式b //输出菜单 printf("**************************************************************\n"); printf("请选择您要进行的操作：\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n"); printf("\t4.计算多项式a*b的值\n\t5.退出\n"); for(;;flag=0){ printf("\n"); scanf("%d",&flag); if(flag==1){ printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb); continue; } if(flag==2){ pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc); continue; } if(flag==3){ pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd); continue; } if(flag==4){ pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf); continue; } if(flag==5) break; if(flag<1||flag>5) printf("Error!!!\n"); continue; }//for DestroyPolyn(pa); DestroyPolyn(pb); return 0; } 7、收获体会 通过这次课程设计练习，使我更深刻地理解了对链表的操作，加深了对数据结构的理解和认识。由于自己的知识水平有限，在完成课程设计的过程作查阅了相关资料，学习别人的算法，进行认真的分析，在学习别人的算法的过程中，发现自己的不足并加以改正。 计算多项式的加、减、乘法运算，需要用到链表的储存，还要使用到指针等知识，对我以前学到的知识能够进行复习，认识体会到自己的不足之处，在以后的学习中，能够注重于算法的学习。认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。 经过这次课程设计，我深刻认识到自己在以前的学习数据结构的过程中，还有许多的不足，需要自己以后更加努力学习数据结构，让自己在以后的其他专业课的学习中，不会因为自己没学好数据结构而掉队。在这个寒假里面，学习自己没有好好学到的数据结构的知识。 输入第一、二个多项式的项的系数及其指数，再选择要进行的5种操作： 1.1设计内容及要求 1)设计内容 （1）使用顺序存储结构实现多项式加、减、乘运算。 例如： 10321058)(2456+-+-+=x x x x x x f ,x x x x x x g +--+=23451020107)( 求和结果：102220128)()(2356++-+=+x x x x x g x f （2）使用链式存储结构实现多项式加、减、乘运算， 10305100)(1050100+-+=x x x x f ，x x x x x x g 320405150)(10205090+++-= 求和结果：1031040150100)()(102090100++-++=+x x x x x x g x f 2）设计要求 （1）用C 语言编程实现上述实验内容中的结构定义和算法。 （2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）用switch 语句设计如下选择式菜单。 ***************数据结构综合性实验**************** *******一、多项式的加法、减法、乘法运算********** ******* 1.多项式创建 ********** ******* 2.多项式相加 ********** ******* 3.多项式相减 ********** ******* 4.多项式相乘 ********** ******* 5.清空多项式 ********** ******* 0.退出系统 ********** ******* 请选择（0—5） ********** ************************************************* *请选择（0-5）: 1.2数据结构设计 根据下面给出的存储结构定义： #define MAXSIZE 20 //定义线性表最大容量 中国计量学院实验报告 实验课程：算法与数据结构实验名称：一元二项式班级：学号： 姓名：实验日期： 2013-5-7 一．实验题目： ①创建2个一元多项式 ②实现2个多项式相加 ③实现2个多项式相减 ④实现2个多项式相乘 ⑤实现2个多项式相除 ⑥销毁一元多项式 实验成绩：指导教师： 二．算法说明 ①存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储 空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 ②加法算法 三．测试结果 四．分析与探讨 实验数据正确，部分代码过于赘余，可以精简。 五．附录：源代码#include<> #include<> #include<> typedef struct Polynomial { float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; 出多项式a和b\n\t2.多项式相加a+b\n\t3.多项式相减a-b\n"); printf("\t4.多项式相除a*b\n\t5.多项式相除a/b\n\t6.销毁多项式\n"); printf("\t7.退出 \n*********************************** ***********\n"); printf("执行:"); scanf("%d",&flag); switch(flag) { case(1): printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);break; case(2): pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break; case(6): DestroyPolyn(pa); DestroyPolyn(pb); printf("成功销毁2个一元二项式\n"); printf("\n接下来要执行的操作:\n1 重新创建2个一元二项式 \n2 退出程序\n"); printf("执行:"); scanf("%d",&i); if(i==1) { // Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);// 建立多项式a printf("请输入b的项 一元稀疏多项式计数器预习报告 ：刘茂学号0062 一、实验要求 (1)输入并建立多项式； (2)输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列； (3)多项式a和b相加，建立多项式a+b； (4)多项式a和b相减，建立多项式a-b。 （5）多项式求值； （6）多项式求导； （7）求多项式的乘积。 二、测试数据： 1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); 2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15 )=(-7.8x^15-1.2x^9+12x^-3-x); 3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); 4、(x+x^3)+(-x-x^3)=0; 5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200); 6、(x+x^2+x^3)+0=x+x^2+x^3. 7、互换上述测试数据中的前后两个多项式。 三、思路分析 用带表头结点的单链表存储多项式。 本程序要求输入并建立多项式，能够降幂显示出多项式，实现多项式相加相减的计算问题，输出结果。 采用链表的方式存储链表，定义结点结构体。运用尾差法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b。 为实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q 结点的指数项。 ①若p->expn 数据结构中实现一元多项式简单计算： 设计一个一元多项式简单的计算器。 基本要求： 一元多项式简单计算器的基本功能为： （1）输入并建立多项式； （2）输出多项式； （3）两个多项式相加，建立并输出和多项式； （4）两个多项式相减，建立并输出差多项式； #include 课程设计成果 学院: 计算机工程学院班级: 13计科一班 学生姓名: 学号: 设计地点（单位）： 设计题目：一元多项式的计算 完成日期：年月日 成绩(五级记分制): _________________ 教师签名:_________________________ 目录 1 需求分析 ......................................................................... 错误!未定义书签。 2 概要设计 ......................................................................... 错误!未定义书签。 2.1一元多项式的建立 ............................................................... 错误!未定义书签。 2.2显示一元多项式 ................................................................... 错误!未定义书签。 2.3一元多项式减法运算 ........................................................... 错误!未定义书签。 2.4一元多项式加法运算 ........................................................... 错误!未定义书签。 2.5 设计优缺点.......................................................................... 错误!未定义书签。3详细设计 .......................................................................... 错误!未定义书签。 3.1一元多项式的输入输出流程图........................................... 错误!未定义书签。 3.2一元多项式的加法流程图................................................... 错误!未定义书签。 3.3一元多项式的减法流程图.................................................. 错误!未定义书签。 3.4用户操作函数....................................................................... 错误!未定义书签。4编码 .................................................................................. 错误!未定义书签。5调试分析 .......................................................................... 错误!未定义书签。4测试结果及运行效果...................................................... 错误!未定义书签。5系统开发所用到的技术.................................................. 错误!未定义书签。参考文献 ............................................................................. 错误!未定义书签。附录全部代码................................................................... 错误!未定义书签。 C语言一元多项式计算集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN# #include <> #include <> #include <> #define LEN sizeof(node) //结点构造 typedef struct polynode { int coef; //系数 int exp; //指数 struct polynode *next; }node; node * create(void) { node *h,*r,*s; int c,e; h=(node *)malloc(LEN); r=h; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); while(c!=0) { s=(node *)malloc(LEN); s->coef=c; s->exp=e; r->next=s; r=s; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); } r->next=NULL; return(h); } void polyadd(node *polya, node *polyb) { node *p,*q,*pre,*temp; int sum; p=polya->next; q=polyb->next; pre=polya; while(p!=NULL&&q!=NULL) { if(p->exp>q->exp) { pre->next=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 { temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p; else pre->next=q; } void print(node * p) { 一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 1.引言 2.需求分析 3.概要设计 4.详细设计 5.测试结果 6.调试分析 7.设计体会 8.结束语 一:引言: 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数 降序排列。 二：需求分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 三：概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1．单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ 数据结构课程设计实验报告 专业班级： 学号： 姓名： 2011年1月1日 题目：一元多项式的运算 1、题目描述 一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。 在数学上，一个一元n次多项式P n(X)可按降序写成： P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0 它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示： P=(P n，P(n-1)，......，P1，P0) 每一项的指数i隐含在其系数P i的序号里。 假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示： Q=(q m,q(m-1)，.....，q1，q0) 不是一般性，假设吗吗m 长沙学院课程设计说明书 题目一元多项式计算问题系(部) 计算机系 专业(班级) 10级软件D班 姓名向栋良 学号2010022D08 指导教师邓旭东 起止日期2011.9.4-2011.9.8 课程设计任务书 课程名称：数据结构与算法 设计题目：一元多项式计算问题 已知技术参数和设计要求： 问题描述： 设计一个稀疏多项式简单计算器 基本要求： (1)输入并分别建立多项式A和B (2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列 (3)完成两个多项式的相加、相减，并将结果输出； 测试数据： (1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 (3) A+B A=x3+x1B=-x3-x1 (4) A+B A=0 B=x7+x5+x3+x1 (5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x 选作内容： （1）.多项式在x=1时的运算结果 （2）求多项式A和B的乘积 设计工作量： 40课时 日期节次地点设计方式9月4日（周日）1-4 科1408 讲授内容 9月4日（周日）5-8 科1608 答疑 9月5日（周一）1-4科1408上机调试 9月5日（周一）5-8 科1608 答疑 9月6日（周二）1-4科1408上机调试 9月6日（周二）5-8 科1608 答疑 9月7日（周三）1-4科1408上机调试 9月7日（周三）5-8 科1608 答疑 9月8日（周四）1-4科1608答疑 9月8日（周四）5-8 科1408 答辩 一元多项式计算器 目录 摘要 (1) 1绪论 (1) 2系统分析 (1) 2.1功能需求 (1) 2.2数据需求 (1) 2.3性能需求 (1) 3总体设计 (2) 3.1系统设计方案 (2) 3.2功能模块设计 (2) 4详细设计 (3) 4.1建立多项式 (4) 4.2多项式相加 (4) 4.3多项式相减 (5) 4.4多项式相乘 (5) 4.5计算器主函数 (6) 5调试与测试 (7) 5.1调试 (7) 5.2测试 (8) 6结论 (9) 结束语 (9) 参考文献 (9) 附录1－用户手册 (10) 附录2－源程序 (12) 摘要 随着生活水平的提高，现代科技也日益发达。日常生活中多位计算再所难免，因此设计一个简单计算器可解决许多不必要的麻烦。 开发这样一个程序主要运用了C的结点，链表等方面知识。系统主要实现了多项式的建立，多项式的输入输出，以及多项式加减乘等运算。 报告主要从计算器的程序段，对输入输出数据的要求，计算器的性能，以及总体的设计来介绍此计算器程序的实现过程。 关键词：多项式；链表；结点 1绪论 随着日益发达的科技，计算器已应用于各行各业。设计一个计算器需要运用C中多方面知识，更是以多项式的建立，输入输出，以及结点，链表为主。（扩充） 任务书。。。。。 2系统分析 2.1 功能需求 多项式的建立多项式输入输出多项式加减乘等运算 2.2数据需求 在输入过程中，首先要确定输入的数据，数据不能是字母，只能是数字。不能连续输入数据，必须按要求配以空格输入要计算的数据。 (1) 链节节点数字 (2) 数字 2.3 性能需求 系统必须安全可靠，不会出现无故死机状态，速度不宜过慢。 项目一一元多项式的计算问题 1.1设计题目与要求 1.1.1设计题目 1）一元多项式计算 任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入； 基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数； ③如何将输入的两个一元多项式显示出来。 ④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 1.1.2、任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。 a：输入多项式的项数并建立多项式； b：输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b。 e：多项式的输出。 1.2 数据结构的选择和概要设计： 1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式 和一元多项式。从图中可见，每个结点表示多项式中的一项。 图1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct node{ int xs; /*系数*/ int zs; /*指数*/ struct node * next; /*next指针*/ }Dnode,* Dnodelist; C：设计本程序需用到八个模块，用到以下八个子函数如下： 1.Dnodelist Creat_node(void) /*链表初始化*/ 2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/ 3.Dnodelist Creat_Dmeth(int length) /*创建多项式*/ 4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/ 5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/ 6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/ 7void Show(Dnodelist D) /*显示（输出）函数*/ 8void main()主程序模块调用链一元多项式的各种基本操作模块。 1.2.2 多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； 1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。 院系：计算机科学学院 专业：软件工程 年级： 2013级 课程名称：数据结构 姓名：韦宜（201321092034）指导教师：宋中山 2015年 12 月 15日 题目：设计一个一元稀疏多项式简单计算器 班级：软件工程1301 姓名：韦宜学号：201321092034 完成日期：12月15日 一、需求分析 问题描述：设计一个一元多项式加法器 基本要求： 输入并建立多项式； (2)两个多项式相加； (3)输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第i 项的系数和指数，序列按指数降序排列。 (4)计算多项式在x处的值； (5)求多项式的导函数。 软件环境：Windows，UNIX，Linux等不同平台下的Visual C++ 6.0 硬件环境: 512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。 二、概要分析 本程序有五个函数： PolyNode *Input()(输入函数)； PolyNode *Deri(PolyNode *head)（求导函数）； PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函数）； void Output(PolyNode*head)（输出函数）； int main()（主函数） 本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。 一元多项式计算(数据结构课程设计) 一、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。 (1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P 的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程） 【问题描述】 设计一个一元稀疏多项式简单计算器 【基本要求】 一元多项式简单计算器的基本功能是： 1，输入并建立多项式; 2，输出多项式，输出形式为整数序列:n,c1,e1,c2,c2,...,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列; 3,多项式a和b相加，建立多项式a+b; 4,多项式a和b相减，建立多项式a-b. 【测试数据】 1，(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7) 【实现提示】 用带表头结点的单链表存储多项式。 #include 实习报告 题目：设计一个一元稀疏多项式计算器 班级: 姓名学号__________完成日期：__ 一、课程题目 一元稀疏多项式计算器 二、需求分析 1、一元稀疏多项式简单计算器的功能是： 1.1 输入并建立多项式； 1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en, 其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.3 求多项式a、b的导函数； 1.4 计算多项式在x处的值； 1.5多项式a和b相加，建立多项式a+b； 1.6 多项式a和b相减，建立多项式a-b。 2、设计思路: 2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构 造的一元多项式 3、测试数据： （1）、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); （2）、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15 )=(-7.8x^15-1.2x^9+12x^-3-x); （3）、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); （4）、(x+x^3)+(-x-x^3)=0; （5）、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200); （6）、(x+x^2+x^3)+0=x+x^2+x^3. 三、概要设计 1.有序表的抽象数据类型定义为： ADT List{ 数据对象：D={a i| a i∈R,i=1,2,…,n,n≧0} 数据结构课程设计报告 课题: 一元多项式 姓名： XX 学号： 201417030218 专业班级： XXXX 指导教师： XXXX 设计时间： 2015年12月30日星期三 目录 一、任务目标 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析 (8) 五、源程序代码 (8) 六、程序运行效果图与说明 (15) 七、本次实验小结 (16) 八、参考文献 (16) 一丶任务目标 分析 (1) a.能够按照指数降序排列建立并输出多项式 b.能够完成两个多项式的相加，相减，并将结果输入 要求：程序所能达到的功能： a.实现一元多项式的输入； b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果； 除任务要求外新增乘法： 计算两个一元多项式的乘积并输出结果 （2）输入的形式和输入值的范围： 输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。 输入形式： 2 3 -1 2 3 0 1 2 0 0 输入值的范围：系数为int型，指数为float型 （3）输出的形式： 第一行输出多项式1； 第二行输出多项式2； 第三行输出多项式1与多项式2相加的结果多项式； 第四行输出多项式1与多项式2相减的结果多项式； 第五行输出多项式1与多项式2相乘的结果多项式 二、概要设计 程序实现 a. 功能：将要进行运算的二项式输入输出； b. 数据流入：要输入的二项式的系数与指数； c. 数据流出：合并同类项后的二项式； d. 程序流程图：二项式输入流程图； e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。 武汉理工大学华夏学院课程设计报告书 课程名称：数据结构 题目：用C语言实现多项式简单计算器的设计 系名：信息工程系 专业班级：软件工程1121班 姓名：邓燕蓉 指导教师:王绪梅 2013 年 6月 28日 课程设计任务书 学生姓名：邓燕蓉专业班级：软件工程1121班 指导教师：王绪梅工作单位：华夏学院计算机教研室设计题目：用C语言实现多项式简单计算器的设计 设计目的 1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法； 2.选择合适的数据的逻辑结构和存储结构以及相应操作，实现简单的多项式计算； 3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养； 设计任务（在规定的时间内完成下列任务） 〔问题描述〕输入并建立两个多项式并输出多项式 设计一个程序：对两个多项式进行加、减法及乘法运算,建立一个新多项式并输出. 或设计一个程序对其中一个多项式求导。 〔实现提示〕 选择带头结点的单链表或循环链表存储多项式,头结点中存放多项式的参数及单链表的数据具体要完成的任务是： A.编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B.写出规范的课程设计报告书； 时间安排：6月24日---28日 具体要求 1. 课程设计报告按统一通用格式书写，具体内容如下： ①设计任务与要求 ②总体方案与说明 ③软件主要模块的流程图 ④源程序清单与注释 ⑤问题分析与解决方案（包括调式记录、调式报告，即在调式过程中遇到的主要问题、解决方法 及改进设想）； ⑥小结与体会 附录：①源程序（必须有简单注释）②使用说明③参考资料 2.每位学生应独立完成各自的任务且每天至少在设计室工作半天； 指导教师签名：王绪梅2013 年6月22日 教研室主任（或责任教师）签名：2013年6月24日 合肥学院 计算机科学与技术系 课程设计报告 2008～2009学年第二学期 课程程序设计语言Ⅱ课程设计 课程设计名称多项式的计算 学生姓名王建敏 学号0804013029 专业班级计算机科学与技术（3）班 指导教师张贯虹汪彩梅 2009年6月 一、课程设计题目：多项式（单项链表的应用） 二、分析与设计 1．程序的基本功能 （1）建立多项式 （2）输出多项式 （3）删除多项式以释放空间 （4）删除多项式中的某一项 （5）将多项式合并同类项 （6）拷贝多项式 （7）将多项式按指数升序排列 （8）判断两多项式是否相等 （9）两个多项式相加，建立并输出和多项式 （10）两个多项式相减，建立并输出差多项式 （11）两个多项式相乘，建立并输出积多项式 （12）两个多项式相除，建立并输出商多项式 2．算法设计 本程序主要应用了链表，结构体和类模板。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0 的项，用多项式链表类来实现设定的程序的基本功能。 涉及的主要算法有： （1）使用尾插法创建多项式，即从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志（某一项的系数为零）为止。 （2）输出一个非空的多项式链表，不要输出最后一项，即输入系数为零的结束项，用if……else语句判断。 （3）删除整个多项式是一项一项的删，使用链表删除其结点的方法，使用free（）函数释放存储空间。在删除非空的多项式的某一项时，定义k来找到要删除的那一项的位置，再使用delete 将其删除。 （4）在对多项式合并同类项时，主要有两点，一是看两项指数是否相等，若相等则合并成一项，二是看两项系数和是否为零，若为零则去掉这两项。在对多项式排序时，先合并同类项，再按指数值从小到大排序。 （5）在拷贝多项式时使用重载函数，将系数和指数都拷贝给新的多项式。 （6）在判断两多项式是否相等时，先分别对两多项式进行排序，再从头项开始，一项一项的比较其系数和指数，一旦有一个不相等就结束，即这两多项式不相等，否则相等。 （7）计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa 指数大于多项式pb指数时，则将pa结点副本插入到和多项式PolyC尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式PolyC尾部，最后插入剩余结点。 一元稀疏多项式简单计算器 一、设计课题 设计一元稀疏多项式简单计算器。 二、需求分析 2.1 输入的形式和输入值的范围： 输入是从键盘输入的，输入的内容为多项式的系数和指数，数为任意的整数，指数为大于等于0的整数 2.2 输出的形式 从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值。 2.3 程序所能达到的功能 a：输入并建立多项式； b：输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数，ci和ei 分别是第i项的系数和指数，序列按指数降序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b； 2.4 测试数据 （1）(2x+5x^8-3.1x^11)+(7-5x^8+11x^9) = (-3.1x^11+11X^9+2X+7) （2）(X+X^3)+(-X-X^3)=0 （3）(X+X^2+X^3)+0= X+X^2+X^3 三、概要设计 3.1 设计思路 A：数据结构的选用 为了实现任意多项式的加法、减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；单链表抽象结构类型定义见附录2。 B：多项式的输入 采用头节点插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非00时就继续，当输入00时，就结束一个多项式的输入； C：2个多项式的加法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中。当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生 D：2个多项式的减法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。 p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。顺序链式一元多项式加法、减法、乘法运算的实现
一元多项式加减乘除运算
一元稀疏多项式计算器实验(报告+程序)
数据结构中实现一元多项式简单计算
数据结构一元多项式的计算
C语言一元多项式计算
一元多项式的计算数据结构课程设计
一元多项式的运算
一元多项式计算问题课程设计
一元多项式计算器
数据结构 一元多项式的计算
一元稀疏多项式计算器(数据结构)
一元多项式计算(数据结构课程设计)
一元稀疏多项式计算器(数据结构)
一元稀疏多项式计算器实习报告
数据结构实验报告-一元多项式
用C语言实现多项式简单计算器的设计
一元多项式的计算课程设计报告
一元多项式计算器设计与实现
相关主题
文本预览