一元稀疏多项式计算器课程设计.docx

1、一元稀疏多项式计算器课程设计一元稀疏多项式计算器课程设计软 件 学 院课程设计报告书课程名称 数据结构 设计题目 一元稀疏多项式计算器 专业班级 软件工程11级1班 学 号 07 姓 名 指导教师 2013 年 1月1设计时间2013年1月21日至2013年1月27日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这

2、一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务 设计一个一元稀疏多项式简单计算器4设计内容 需求分析 4.1.1.程序所能达到的功能一元稀疏多项式简单计算器的基本功能是：(1)输入并建立多项式creatpolyn()；(2)输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数升序排列 printpolyn()；(3)多项式a和b相加，建立多项式a+b，输出相加的多项式addpolyn()；(4)多项式a和b相减，建立多项式a-b，输出相减的多项式subpo

3、lyn()。 4.1.2.输入的形式和输入值的范围一元稀疏多项式计算器需要输入多项式的各项的系数和指数。系数可以用实数来表示，指数可以用整数来表示，由于整形数据在内存里占用两个字节，所以它的取值范围为-3276832767。4.1.3.输出的形式本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且把计算加减后的运算结果按指数升序排列输出。4.1.4.测试数据(1)正确： 图1程序输出 (2)错误： 图2程序输出总体设计4.2.1.本程序中用到的所有抽象数据类型的定义ADT List 数据对象：D=ai| aiR,i=1,2,n,n0 数据关系：R1=| ai-1,aiD,

4、 ai-1,ai, i=1,2,3,.n 基本操作： InitList() 操作结果：构造一个空的有序表L。 DestroyList(L) 初始条件：有序表L已存在。 操作结果：销毁有序表L。 ListLength(L) 初始条件：有序表L已存在。 操作结果：返回有序表L的长度。 ClearList( L ) 初始条件：有序表L已存在。 操作结果：清空链表内容。 Ins_before ( N,N ) 初始条件：有序表L已存在。 操作结果：插入节点到链表。 ADT OrderedListADT Poly 数据对象：D=ai |ai为实数，i=1，2，n 数据关系：R1= 基本操作：CreateP

5、oly( L,N )初始条件：N为节点，L为有序表。操作结果：将N 插入多项式的适当位置。GetPoly( L )操作结果：将用户输入转换为节点。PrintPoly( L )初始条件：多项式L已存在。操作结果：显示多项式。AddPoly( L_1,L_2,L_add )初始条件：多项式L_1,L_2,L_add已存在。操作结果：生成L_1,L_2之和的多项式L_addDiffPoly( L ,L_diff) 初始条件：多项式L ,L_diff已存在。操作结果：生成L的导数多项式L_add。AlterPoly( L )初始条件：多项式L已存在。操作结果：将L多项式取相反数。ADT Poly4.2

6、.2.主程序的流程 图3主程序流程4.2.3.各程序模块之间的层次（调用）关系图4模块层次调用关系详细设计4.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法Typedef Polynomial 4.3.2主程序和其它主要函数伪码算法主函数和其他函数：void main() int m,n; Polyn pa=0,pb=0,pc; printf( -n); printf( | 软件11-1班 * |n); printf( -n); printf( 欢迎使用多项式操作程序n); printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa

7、,m); 4.3.3数的调用关系图图5函数调用关系测试与分析4.4.1测试输入：a=2X+3X2; b=2X3+7X4输出：a+b=2X+3X2+ 2X3+7X4 a-b=2X+3X2-2X3-7X4 图6程序输出4.4.2分析此一元稀疏计算器系统基本可能实现计算功能，其“加”与“减”方法都相对比较完整，在调试程序的时候总出现错误， 由于知识不全面，不熟练，总需要看书但在输入数据时，要按照严格的格式输入，否则有可能出现死去或崩溃。若本系统能加上保存功能就更好了，因为一个系统在使用过程中总会关机等，而此系统的缺点却是没有保存功能，关闭之后就要重新建立了。会慢慢完善。 附录#include#inc

8、lude .插入函数按指数增序插入.*/void Insert( Polyn p,Polyn h) /将p插入到h中 if(p-coef=0) free(p); /若p的系数是0则释放该节点 else Polyn q1,q2; q1=h; q2=h-next; while(q2&q2-expnexpn) /若p的指数大于q2的指数，则继续查找 q1=q2; q2=q2-next; if(q2&q2-expn=p-expn) /若q2的指数等于p的指数则将两者的系数相加并且赋给q2 q2-coef+=p-coef; free(p); if(!q2-coef); q1-next=q2-next;

9、free(q2); else /把p插入到h当中 q1-next=p; p-next=q2; 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); Insert(p,head); /调用Insert函数插入结点 return head;void DestroyPolyn(Polyn p) /销毁多项式p Polyn q1,

10、q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next; void PrintPolyn(Polyn P) Polyn q=P-next; 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); if(q-e

11、xpn=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+; printf(n);int compare(Polyn a,Polyn b

12、) if(a&b) if(!b|a-expnb-expn) return -1; else if(!a|a-expnexpn) return 1; else return 0; else if(!a&b) return -1; /a多项式已空，但b多项式非空 else return 1; /b多项式已空，但a多项式非空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

13、Polynomial); /建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 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=q

14、b-expn; qb=qb-next; break; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc); /当相加系数为0时，释放该结点 return headc;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-n

15、ext) /恢复pb的系数 p-coef*=-1; return pd;void main() int m,n; Polyn pa=0,pb=0,pc; printf( -n); printf( | 软件11-1班 * |n); printf( -n); printf( 欢迎使用多项式操作程序n); printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m); /建立多项式a printf(请输入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n); /建立多项式b printf(n输出多项式 a=); PrintP

16、olyn(pa); printf(n输出多项式 b=); PrintPolyn(pb); pc=AddPolyn(pa,pb); printf(n输出多项式之和a+b=); PrintPolyn(pc); pc=SubtractPolyn(pa,pb); printf(n输出多项式之差a-b=); PrintPolyn(pc); printf(n 感谢使用此程序！n); DestroyPolyn(pa); DestroyPolyn(pb); 5 总结与展望在编程过程中很容易发现程序中的错误，要尽快找出这些错误，使程序能正确运行。平时缺乏锻炼即使在明确的出错提示下也往往找不出错误，不知道该怎么办

17、，而求救于别人。但更重要的是通过自己的直接实践来累积。因此，在实验时千万不要在程序通过后就认为万事大吉、完成任务了，而应当在已通过的程序基础上作一些改动，再进行编译、连接和运行。我觉得我们对于数据结构的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次和同学讨论研究，逐渐能自己找出错误，并加以改正。此次的程序设计能够成功，是我和我的同学共同努力作用的结果。在这一段努力学习的过程中，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。参考文献1严蔚敏，吴伟民 数据结构（c语言版）清华大学出版社；2谭浩强 c程序设计（第四版）清华大学出版社；成绩评定成绩 教师签字