一元多项式的计算数据结构课程教学设计报告.doc

!- 数据结构课程数据结构课程 设计报告设计报告 一元多项式的计算一元多项式的计算 ————主要用到的结构是链表主要用到的结构是链表 班班 级级：： 软件 092 班 姓姓 名名：： 熊治景 指导教师指导教师：： 董跃华 井福荣 成成 绩绩： 信息工程学院 年 月 日 !- 摘要摘要 本次试验依据江西理工大学 09 级数据结构实验要求，较完善的对题目进行了 分析，理解和编程，程序思路清晰，考虑全面。 对于此题，应该使用链式存储结构存储多项式的信息，并根据算法用 C 语言编 程。 同时在本书的后面附带了一部分程序源码和对程序的同步解释，为了更直观的 对程序的理解，该书还运用了框架图，使读者能够更好地认识程序。 在用 C 语言编程的时候，要用到的语句主要有函数调用语句，判断语句，输入 和输出语句等。 关键词：一元多项式 线性表 指数 !- 目目录录 1.1.引言引言 ......................................................................................- 4 - 2.2.需求分析：需求分析： ..........................................................................- 5 - 3.3.概要设计概要设计 ..............................................................................- 5 - 4.4.详细设计详细设计 ..............................................................................- 7 - 1.由大到小排序.......................................................................................................................- 7 - 2 两多项式相加.......................................................................................................................- 7 - 3 两多项式相减.......................................................................................................................- 9 - 5 5 测试结果测试结果 .............................................................................- 11 - 1 主菜单.................................................................................................................................- 11 - 2 输入两个多项式.................................................................................................................- 11 - 3 将两多项式进行加减，并退出界面.................................................................................- 12 - 6.6.调试分析调试分析 ............................................................................- 12 - 7.7.设计体会设计体会 ............................................................................- 12 - 8.8.结束语结束语 ................................................................................- 13 - 9.9.参考文献参考文献 ............................................................................- 13 - 10.10.附录附录 ..................................................................................- 13 - !- 一元多项式的计一元多项式的计算算 1.1.引言引言 本次课程设计的目的本次课程设计的目的：是对数据结构所学内容的进一步的理解与巩固，是将计算 机课程与实际问题相联接的关键步骤。通过课程设计，能够提高分析问题、解决 问题，从而运用所学知识解决实际问题的能力。 实验环境实验环境：Window 2000 及以上，c-free 所有版本，Turbo2.0 实验的任务要求实验的任务要求： 任务：任务： 能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入 要求：要求： 1. 完成需求分析 2. 画框架图 3. 编写算法 4. 用 C 语言编写程序 5. 调试 !- 2.2.需求分析：需求分析： 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储 在内存中，能够完成两个多项式的加减运算并输出结果 3.3.概要设计概要设计 存储结构：存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存 储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个 域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表， 对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 基本算法分析与设计：基本算法分析与设计： 1.程序的基本功能： (1) 创建两个一元多项式 (2) 两个多项式相加，得到一个新的多项式 ，可以按指数选择排序方式 (3) 两个多项式相减，得到一个新的多项式，可以按指数选择排序方式 （4）退出 !- 2.系统总框图 菜 单退 出 主 函 数 各功能函数链表结构按指数降序输出 3.定义的函数及说明 compare(term a,term )比较指数 arrange(polynomail pa)由大到小排序 print(polynomail P)输出多项式,求项数 creat(polynomail P,int m) 创建并初始化多项式链表 add(polynomail pa,polynomail pb)两多项式相加 sub(polynomail pa,polynomail pb)两多项式相减 !- 4.4.详细设计详细设计 1.由大到小排序由大到小排序 void arrange(polynomail pa) { polynomail h=pa,p,q,r; if(pa==NULL) exit(-2); for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;)//小的沉底 { for(p=h;p->next!=rp=p->next) if(compare(p->next->next->data,p->next->data)==1) { q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; } r=p; } } } 2 两多项式相加两多项式相加 polynomail add(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r;int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p switch(compare(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef+q->data.coef; !- if(s->data.coef!=0.0) { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }//switch }//while while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; } while(q) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; for(q=newp->next;q->next!=NULL;q=q->next) for(p=q;p!=NULLp=p->next) if(q->data.expn==p->next->data.expn) { q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); } arrange(newp); !- return newp; } 3两多项式相减两多项式相减 polynomail sub(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r,Q; int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p switch(compare(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef-q->data.coef; if(s->data.coef!=0.0) { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }//switch }//while while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; !- r->next=s; r=s; p=p->next; } while(q) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; if(newp->next!=NULLq!=NULL;q=q->next) for(p=q->next,r=q;p!=NULL;) if(q->data.expn==p->data.expn) { q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); } else { r=r->next; p=p->next; } } arrange(newp); return newp;} !- 5 5 测试结果测试结果 1 主菜单主菜单 2 输入两个多项式输入两个多项式 !- 3 将两多项式进行加减，并退出界面将两多项式进行加减，并退出界面 结果表示程序可行。 6.6.调试分析调试分析 本次实验程序少，功能也存在不足。 1.当在菜单界面，要选择操作时，不选菜单中的操作代号，程序只叫你再次选择，但不会 出现字幕提示。 2.准确的说只能实现两个功能就是加减，降次输出是默认，所以本程序只是实现了任务要 求，没有考虑到在此基础上拓展功能。 解决之道： 深入学习编程语言，多研读别人写的好的程序，同时多看书。 7.7.设计体会设计体会 1.经过这次课程设计，我对数据结构这门课程有了进一步的理解，对 C 编程 有了一定的提高。另外也提高了我分析问题、解决问题，从而运用所学知识解决 实际问题的能力。 !- 2.通过这次课程设计，我发现了自己平时学数据结构这门课还有很多没有注 意到的地方。虽然说这次的课题顺利完成了，但我对数据结构这门课的学习还没 有完成，以后还必须对数据结构进行复习巩固。 3.以前在数据结构这门课上，我学到的仅仅是理论知识，但这次的课程设计 让我感受到课上的东西用到实际问题的难处。在今后对计算机方面知识的学习中， 我要注意理论联系实际，这样才可以把学到的东西运用出来，真正的做到学以致 用！ 8.8.结束语结束语 感谢我的数据结构老师董跃华在以往的基础课学习中为我打下良好的基础， 这是我这次课程设计能够顺利完成的前提。 感谢学校能够给我们提供这么好的机房，使我有地方上网查资料，能够有地 方做这次课程设计。 我也很感谢我的同学，我完成我的程序之后，请他们帮我调试，提了不少宝 贵的意见，使我的程序有了进一步的完善。 9.9.参考文献参考文献 1） 谭浩强 《C 语言程序设计》 （第三版 ）清华大学出版社 2） 严慰敏. 《数据结构》（C 语言版）. 清华大学出版社 !- 10.10.附录附录 #include #include typedef struct { float coef; //系数 int expn; //指数 }term; typedef struct LNode { term data; struct LNode *next; }LNode,*LinkList; typedef LinkList polynomail; int compare(term a,term b) { if(a.expn>b.expn) return 1; if(a.expn==b.expn) return 0; if(a.expnnext!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;) { for(p=h;p->next!=rp=p->next) if(compare(p->next->next->data,p->next->data)==1) { q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; } !- r=p; } } int print(polynomail P) { int i; polynomail q; if(P==NULL) printf("无项！\n"); else if(P->next==NULL) printf("Y=0\n"); else { printf("该多项式为 Y=");q=P->next;i=1; if(q->data.coef!=0 i++; } if(q->data.expn==0 q=q->next; if(q==NULL) {printf("\n");return 1;} while(1) { if(q->data.coef!=0 printf("%.2fX^%d",q->data.coef,q->data.expn); i++; } if(q->data.expn==0 printf("%f",q->data.coef); } q=q->next; if(q==NULL) { printf("\n"); break; } } } return 1; } polynomail creat(polynomail P,int m) { polynomail r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode)); r=P; !- for(i=0;idata.coef, r->next=s; r=s; } r->next=NULL; if(P->next->next!=NULL) { for(q=P->next;q!=NULL/*q=q->next) for(p=q->next,r=q;p!=NULL;) if(q->data.expn==p->data.expn) { q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); } else { r=r->next; p=p->next; } } return P; } polynomail add(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r;int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p switch(compare(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef+q->data.coef; if(s->data.coef!=0.0) !- { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; } } while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; } while(q) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; for(q=newp->next;q->next!=NULL;q=q->next) for(p=q;p!=NULLp=p->next) if(q->data.expn==p->next->data.expn) { q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); } arrange(newp); return newp; !- } polynomail sub(polynomail pa,polynomail pb) { polynomail s,newp,q,p,r,Q; int j; p=pa->next;q=pb->next; newp=(LNode*)malloc(sizeof(LNode)); r=newp; while(p switch(compare(p->data,q->data)) {case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef-q->data.coef; if(s->data.coef!=0.0) { s->data.expn=p->data.expn; r->next=s; r=s; } p=p->next; q=q->next; break; case 1: s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; }//switch }//while while(p) { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; } while(q) !- { s=(LNode*)malloc(sizeof(LNode)); s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; } r->next=NULL; if(newp->next!=NULLq!=NULL;q=q->next) for(p=q->next,r=q;p!=NULL;) if(q->data.expn==p->data.expn) { q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); } else { r=r->next; p=p->next; } } arrange(newp); return newp;} void main() { polynomail pa=NULL,pb=NULL; polynomail p,q; polynomail addp=NULL,subp=NULL; int n,m; int sign=y; printf("*****************************************************\n"); printf("*** 菜 单 ***\n"); printf("*** 1、创建两个一元多项式 ***\n"); printf("*** 2、两多项式相加得一新多项式 ***\n"); printf("*** 3、两多项式相减得一新多项式 ***\n"); printf("*** 4、退出 ***\n"); printf("*****************************************************\n"); printf("\n"); while(sign!=n) { printf("请选择："); scanf("%d", switch(n) !- {case 1: if(pa!=NULL) { printf("已建立两个一元多项式，请选择其他操作！"); break; } printf("请输入第一个多项式：\n"); printf("要输入几项："); scanf("%d", while(m==0) { printf("m 不能为 0，请重新输入 m:"); scanf("%d", } pa=creatpolyn(pa,m); print(pa); printf("请输入第二个多项式：\n"); printf("要输入几项："); scanf("%d", pb=creatpolyn(pb,m); print(pb); break; case 2: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } addp=add(pa,pb); print(addp); break; case 3: if(pa==NULL) { printf("请先创建两个一元多项式！\n"); break; } subp=sub(pa,pb); print(subp); break; case 4: if(addp!=NULL) !- { p=addp; while(p!=NULL) { q=p; p=p->next; free(q); } } if(subp!=NULL) { p=subp; while(p!=NULL) { q=p; p=p->next; free(q); } } exit(-2); } } }