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

1、 数据结构数据结构 课程设计报告课程设计报告 题题目目：一元多项式计算一元多项式计算 院（系）：院（系）： 计算机与信息科学学院 专专 业：业： 软件工程 班班 级：级： 软件1202班 学学 号：号： 02 05 40 姓姓 名：名： 陈潇潇 刘敏 易庆鹏 指导教师：指导教师： 彭代文 20132013 年年 1212 月月 目目 录录 一、一、 课程设计介绍课程设计介绍 .1 1 1.1 课程设计目的.1 1.2 课程设计内容.1 1.2 课程设计要求.1 二、二、 需求设计需求设计 .3 3 2.1 课设题目粗略分析.3 2.2 原理图介绍.4 2.2.1 功能模块图 .4 2.2.2

2、流程图分析 .4 三、需求分析三、需求分析 .6 6 3.1 存储结构.6 3.2 算法描述.6 四、调试与分析四、调试与分析 .1010 （1）调试过程.10 （2） 程序执行过程.10 参考文献参考文献 .1212 总结总结 .1313 附附 录（关键部分程序清单）录（关键部分程序清单） .1414 一、一、课程设计介绍课程设计介绍 1.11.1 课程设计目的课程设计目的 熟悉使用 c 语言编码程序，解决实际问题； 了解数据结构与算法的设计方法，具备初步的独立分析和设计能力。 初步掌握软件开发过程的分析能力，系统设计，程序编码，测试等基本能力。 提高综合运用的能力，运用所学理论知识与独立分

3、析能力。 1.21.2 课程设计内容课程设计内容 一元多项式计算 任务：能够按照指数降序排列建立并输出多项式 能够完成两个多项式的相加，并将结果输入 在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可 以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可 以提出算法的改进方法 1.31.3 课程设计要求课程设计要求 学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。 有问题及时主动通过各种方式与教师联系沟通。 学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在 课设过程中不断检测自己的计划完成情况，及时的向教师汇报。 课程设计按照教学要求

4、需要一周时间完成，一周中每天（按每周 5 天）至少 要上 3-4 小时的机来调试 C 语言设计的程序，总共至少要上机调试程序 30 小时。 课程设计在期末考试之前交。最好一起上交。 同班同学之间最好不要相同。源代码可以打印，但是下面模块要求的内容必 须手写。 二、二、 需求设计需求设计 2.12.1 课设题目粗略分析课设题目粗略分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储 在内存中，能够完成两个多项式的加减运算并输出结果 2.22.2 流程图分析流程图分析 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）

5、数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图 1 所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入 图表图表 1 1 2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图 2 所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 图表图表 1 1 开始 申请结点空间 + + + + num 输入多项式的项数 指针数组tempi中 （i=1num） 输入多项式各项的系数 x, 指数 y 输出已输入的多项式 合并同类项 结束

6、 否 是 是否输入正确 三、需求分析三、需求分析 3.13.1 存储结构存储结构 一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只 存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零 项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点 的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况 进行分析，实现一元多项式的相加、相减操作。 开始 定义存储结果的空链 r r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 中 直接把 p 中 各项存入 r 中 直接把 q 中 各项存入 r 存储多项式 2 的

7、 空链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 3.23.2 算法描述算法描述 #include#include #include#include typedeftypedef structstruct PolynomialPolynomial floatfloat coef;coef; intint expn;expn; structstruct PolynomialPolynomial *next;*next; *Polyn,Polynomial;*Polyn,Polynomial; /Polyn/Polyn 为结点指针类型为结点指针类型 voidvoid Ins

8、ert(PolynInsert(Polyn p,Polynp,Polyn h)h) if(p-coef=0)if(p-coef=0) free(p);free(p); /系数为系数为 0 0 的话释放结点的话释放结点 elseelse PolynPolyn q1,q2;q1,q2; q1=h;q2=h-next;q1=h;q2=h-next; while(q2q1=q2; q2=q2-next;q2=q2-next; if(q2q2-coef+=p-coef; free(p);free(p); if(!q2-coef)if(!q2-coef) /系数为系数为 0 0 的话释放结点的话释放结点

9、q1-next=q2-next;q1-next=q2-next; free(q2);free(q2); elseelse /指数为新时将结点插入指数为新时将结点插入 p-next=q2;p-next=q2; q1-next=p;q1-next=p; /Insert/Insert PolynPolyn CreatePolyn(PolynCreatePolyn(Polyn head,inthead,int m)/m)/建立一个头指针为建立一个头指针为 headhead、项数、项数 为为 m m 的一元多项式的一元多项式 intint i;i; PolynPolyn p;p; p=head=(Pol

10、yn)malloc(sizeof(structp=head=(Polyn)malloc(sizeof(struct Polynomial);Polynomial); head-next=NULL;head-next=NULL; for(i=0;im;i+)for(i=0;icoef,%d, Insert(p,head);Insert(p,head); /调用调用 InsertInsert 函数插入结点函数插入结点 returnreturn head;head; /CreatePolyn/CreatePolyn voidvoid DestroyPolyn(PolynDestroyPolyn(Po

11、lyn p)/p)/销毁多项式销毁多项式 p p PolynPolyn q1,q2;q1,q2; q1=p-next;q1=p-next; q2=q1-next;q2=q1-next; while(q1-next)while(q1-next) free(q1);free(q1); q1=q2;/q1=q2;/指针后移指针后移 q2=q2-next;q2=q2-next; voidvoid PrintPolyn(PolynPrintPolyn(Polyn P)P) PolynPolyn q=P-next;q=P-next; intint flag=1;/flag=1;/项数计数器项数计数器 if

12、(!q)if(!q) /若多项式为空，输出若多项式为空，输出 0 0 putchar(0);putchar(0); printf(n);printf(n); return;return; whilewhile (q)(q) if(q-coef0putchar(+); /系数大于系数大于 0 0 且不是第一项且不是第一项 if(q-coef!=1printf(%g,q-coef); if(q-expn=1)if(q-expn=1) putchar(X);putchar(X); elseelse if(q-expn)if(q-expn) printf(X%d,q-expn);printf(X%d,

13、q-expn); elseelse if(q-coef=1)if(q-coef=1) if(!q-expn)if(!q-expn) putchar(1);putchar(1); elseelse if(q-expn=1)if(q-expn=1) putchar(X);putchar(X); elseelse printf(X%d,q-expn);printf(X%d,q-expn); if(q-coef=-1)if(q-coef=-1) if(!q-expn)if(!q-expn) printf(-1);printf(-1); elseelse if(q-expn=1)if(q-expn=1)

14、 printf(-X);printf(-X); elseelse printf(-X%d,q-expn);printf(-X%d,q-expn); q=q-next;q=q-next; flag+;flag+; /while/while printf(n);printf(n); /PrintPolyn/PrintPolyn intint compare(Polyncompare(Polyn a,Polyna,Polyn b)b) if(a1; elseelse if(!a|a-expnexpn)if(!a|a-expnexpn) returnreturn -1;-1; elseelse ret

15、urnreturn 0;0; elseelse if(!a/a-1;/a 多项式已空，但多项式已空，但 b b 多项式非空多项式非空 elseelse returnreturn 1;/b1;/b 多项式已空，但多项式已空，但 a a 多项式非空多项式非空 /compare/compare PolynPolyn AddPolyn(PolynAddPolyn(Polyn pa,Polynpa,Polyn pb)/pb)/求解并建立多项式求解并建立多项式 a+ba+b，返回其，返回其 头指针头指针 PolynPolyn qa=pa-next;qa=pa-next; PolynPolyn qb=pb-

16、next;qb=pb-next; PolynPolyn headc,hc,qc;headc,hc,qc; hc=(Polyn)malloc(sizeof(structhc=(Polyn)malloc(sizeof(struct Polynomial);/Polynomial);/建立头结点建立头结点 hc-next=NULL;hc-next=NULL; headc=hc;headc=hc; while(qa|qb)while(qa|qb) qc=(Polyn)malloc(sizeof(structqc=(Polyn)malloc(sizeof(struct Polynomial);Polyn

17、omial); switch(compare(qa,qb)switch(compare(qa,qb) casecase 1:1: qc-coef=qa-coef;qc-coef=qa-coef; qc-expn=qa-expn;qc-expn=qa-expn; qa=qa-next;qa=qa-next; break;break; casecase 0:0: qc-coef=qa-coef+qb-coef;qc-coef=qa-coef+qb-coef; qc-expn=qa-expn;qc-expn=qa-expn; qa=qa-next;qa=qa-next; qb=qb-next;qb=

18、qb-next; break;break; casecase -1:-1: qc-coef=qb-coef;qc-coef=qb-coef; qc-expn=qb-expn;qc-expn=qb-expn; qb=qb-next;qb=qb-next; break;break; /switch/switch if(qc-coef!=0)if(qc-coef!=0) qc-next=hc-next;qc-next=hc-next; hc-next=qc;hc-next=qc; hc=qc;hc=qc; elseelse free(qc);/free(qc);/当相加系数为当相加系数为 0 0 时

19、，释放该结点时，释放该结点 /while/while returnreturn headc;headc; /AddPolyn/AddPolyn PolynPolyn SubtractPolyn(PolynSubtractPolyn(Polyn pa,Polynpa,Polyn pb)/pb)/求解并建立多项式求解并建立多项式 a+ba+b，返，返 回其头指针回其头指针 PolynPolyn h=pb;h=pb; PolynPolyn p=pb-next;p=pb-next; PolynPolyn pd;pd; while(p)while(p) /将将 pbpb 的系数取反的系数取反 p-coe

20、f*=-1;p-coef*=-1; p=p-next;p=p-next; pd=AddPolyn(pa,h);pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next)for(p=h-next;p;p=p-next) /恢复恢复 pbpb 的系数的系数 p-coef*=-1;p-coef*=-1; returnreturn pd;pd; /SubtractPolyn/SubtractPolyn intint main()main() intint m,n,flag=0;m,n,flag=0; floatfloat x;x; PolynPolyn pa=0,pb=0,

21、pc,pd,pe,pf;/pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，定义各式的头指针，papa 与与 pbpb 在使用前在使用前 付初值付初值 NULLNULL printf(printf(请输入请输入 a a 的项数的项数:);:); scanf(%d,scanf(%d, pa=CreatePolyn(pa,m);/pa=CreatePolyn(pa,m);/建立多项式建立多项式 a a printf(printf(请输入请输入 b b 的项数的项数:);:); scanf(%d,scanf(%d, pb=CreatePolyn(pb,n);/pb=CreatePoly

22、n(pb,n);/建立多项式建立多项式 a a /输出菜单输出菜单 printf(*n);printf(*n); printf(printf(操作提示：操作提示：nt1.nt1.输出多项式输出多项式 a a 和和 bnt2.bnt2.建立多项式建立多项式 a+bnt3.a+bnt3.建建 立多项式立多项式 a-bn);a-bn); printf(t4.printf(t4.退出退出 n*n);n*n); for(;flag=0)for(;flag=0) printf(printf(执行操作：执行操作：);); scanf(%d,scanf(%d, if(flag=1)if(flag=1) pri

23、ntf(printf(多项式多项式 a a：);PrintPolyn(pa););PrintPolyn(pa); printf(printf(多项式多项式 b b：);PrintPolyn(pb);continue;);PrintPolyn(pb);continue; if(flag=2)if(flag=2) pc=AddPolyn(pa,pb);pc=AddPolyn(pa,pb); printf(printf(多项式多项式 a+ba+b：);PrintPolyn(pc););PrintPolyn(pc); DestroyPolyn(pc);continue;DestroyPolyn(pc);continue; if(flag=3)if(flag=3) pd=SubtractPolyn(pa,pb);pd=SubtractPolyn(pa,pb); printf(printf(多项式多项式 a-ba-b：);PrintPolyn(pd););PrintPolyn(pd); DestroyPolyn(pd);continue;DestroyPol