2022年多项式的输入输出设计报告 .pdf

《2022年多项式的输入输出设计报告 .pdf》由会员分享，可在线阅读，更多相关《2022年多项式的输入输出设计报告 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、江 西 理 工 大 学数 据 结 构 课 程 设 计 报 告选题：一元多项式的计算猴子选大王班级：信息安全 101 学号： 16 姓名：熊剑时间： 2011 年 12 月 25 日2012 年 1 月 6 日指导教师：罗会兰涂燕琼曾珽2012 年 01 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 一、 需求分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结

2、果二、 概要设计存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。 链表中的每一个结点存放多项式的一个系数非零项，它包含三个域， 分别存放该项的系数、 指数以及指向下一个多项式项结点的指针。创建一元多项式链表， 对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。基本算法：1、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1 所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入开始

3、申请结点空间输入多项式的项数输入多项式各项的系数 x, 指数 y 输出已输入的多项式合并同类项结束否是是否输入正确图表 1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 2 、多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2 所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。图表 2 开始定义存储结果的空链

4、r是否输出存储多项式的和的链r 结束是否同指数项系数相加后存入r直接把p 中各项存入r直接把q 中各项存入 r 存储多项式 2的空链 Q是否为空存储多项式1 的空链 P是否为空合并同类项名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - 3 、多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3 所示。（5）测试要点：两多项式是否为空，

5、为空则提示重新输入，否则，进行运算。开始定义存储结果的空链r是否输出存储多项式的和的链r 结束是否同指数项系数相加后存入r把 p 中各项系数改变符号后存入直接把 q 中各项存入 r 存储多项式 2的空链 Q是否为空存储多项式1 的空链 P是否为空合并同类项图表 3名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 三、 详细设计#include #include /动态内存分配typedef struct Polynomial /

6、 C中用于定义结构体类型多项式 float coef; /系数 int expn; /指数 struct Polynomial *next; /指针域*Polyn,Polynomial;/Polyn为结点指针类型void Insert(Polyn p,Polyn head) if(p-coef=0) free(p); /系数为 0 的话释放结点 else / head指针作为头指针 Polyn q1,q2; /p首先指向头结点 q1=head;q2=head-next; /第一次 q2 的值为 null while(q2&p-expnexpn) / 查找插入位置比较 q1=q2; /较大的 q

7、2 的值赋给前一个位置的q1 q2=q2-next; /q2指针后移 if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系数为 0 的话释放结点 q1-next=q2-next; /q1下一个位置就是q2 而 q2 及 q2 的下一个位置指向零 free(q2); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - else / p指向的

8、指数大于q2 时 p-next=q2; /把 q2 的值也就是开始null的那个赋给p 的下一个节点 q1-next=p; /把 p 指针指向的值赋给q2 /Insert Polyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial);/给头结点申请存储空间并强制转换 head-next=NULL; /将头节点的下一个位置置空 for(i=0;icoef,&p-expn); /当节点只有头结点和第一个节点时 p 指

9、向第一个节点 Insert(p,head); / 每次循环到此都要调用Insert函数插入结点 return head; / 返回头指针判断是那个多项式/CreatePolyn void DestroyPolyn(Polyn p) /销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) /q2指针指向空时不执行操作 free(q1); /释放 q1 指向的存储空间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共

10、13 页 - - - - - - - - - q1=q2; /指针后移 q2=q2-next; /位置不释放 void PrintPolyn(Polyn P) / 打印多项式 Polyn q=P-next; /第一个节点的值赋给q int flag=1; /项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系数大于 0 且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非 1 或-1 的普通情况 printf(%g,q-coef)

11、; /*%g的作用 if(q-expn=1) putchar(X); /指数为 1 时输出 X else if(q-expn) printf(X%d,q-expn); else /1与-1 的情况 if(q-coef=1) if(!q-expn) putchar(1); /指数为零时输出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); /指数为 1 时名师资料总结 - - -精品资料欢迎下载 -

12、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - else printf(-X%d,q-expn); q=q-next; /控制输出项的指针后移 flag+; /计数加一 /while printf(n);/循环结束换行/PrintPolyn int compare(Polyn a,Polyn b) /用于两个多项式项加减是时的比较 if(a&b) if(!b|a-expnb-expn) return 1; /B空或者 A比 B的指数大 else if(!a|a-expne

13、xpn) return -1; else return 0; /AB的指数相同时 else if(!a&b) return -1;/a多项式已空，但b 多项式非空 else return 1;/b多项式已空，但a 多项式非空/compare Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针 Polyn qa=pa-next; /pa的第一个位置 Polyn qb=pb-next; /pb的第一个位置 Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 h

14、c-next=NULL; headc=hc; /hc指针的作用相当于 p 指针 while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; /指向下一个 break; case

15、 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; /hc之后插入 qc 所指的节点 hc-next=qc; hc=qc; else free(qc);/当相加系数为0 时，释放该结点 /while return headc; 名师资料总结 - - -精品资料欢迎下载 - - - - - -

16、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - /AddPolyn 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; / 符合循环前两个条

17、件则又将pb 取反 return pd; /p指针后移/SubtractPolyn int main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa 与 pb 在使用前付初值NULL printf(请输入 a 的项数 :); /pc pd 为两多项式的相加减得到的多项式 scanf(%d,&m); pa=CreatePolyn(pa,m);/建立项数为m多项式 a printf(请输入 b 的项数 :); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立项数为n 多项式 a /输

18、出菜单 printf(*n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - printf(操作提示：nt1.输出多项式a 和 bnt2.建立多项式a+bnt3.建立多项式 a-bn); printf(t4.退出 n*n); for(;flag=0) /先赋值为零 printf(执行操作： ); scanf(%d,&flag); if(flag=1) printf(多项式 a： );PrintPolyn(pa); prin

19、tf(多项式 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) break; if(flag4) printf(Error!n);continue; /for DestroyPolyn(pa)

20、; DestroyPolyn(pb); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 4. 调试结果1.测试的数据及结果2.算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n ）, 减法运算的时间复杂度为O(m-n)，其中 m ，n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很

21、好的移动指针出现了数据重复输出或是输出系统缺省值， 不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -