《计算机程序训练》设计.doc

计算机程序训练设计说明书指导老师: 杨 树 恒姓名: 罗 邦 仁学号:0705010120日期:2009年06月12日目 录一 题目内容描述1二 课程基本要求1三 程序算法描述1四 所用到的头文件说明2五 应用程序功能说明2六 程序运行过程举例 3七 参考文献4八 源程序代码5九 总结与体会9C语言程序设计报告 一 题目内容描述 题目：多项式计算要求：1主要功能：(1)输入并建立多项式；(2)输出多项式；(3)两个多项式相加，建立并输出和多项式；(4)两个多项式相减，建立并输出差多项式。2.要求：一元多项式简单计算器的基本功能二课程基本要求1设计程序，上机调试2写出实验报告三程序算法描述基本上分三大部分来实现一元多项式的功能，基本上都用到了链表。首先是采用头插法的方法来实现一元多项式的建立，其次是实现一元多项式的显示，最后才是实现一元多项式的加减法运算，输出所需要的计算结果。（1）.问题描述 用C语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。本程序的特点是主要运用指针数组、结构体和链表，其中在建立链表的时候用数组指针，然后通过数组指针完成多项式的创建。（2）.数据结构设计 此程序的数据结构是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结构表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费了巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表的结构体可以用来存储多项式的系数，指数，下一个指针3个元素，这样便于实现任意多项式的加法，减法运算。（3）一元多项式的建立 输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。 （4）显示一元多项式 如果系数是大于0的话就输出+系数x指数的形式；如果系数是小于0的话就输出系数x指数的形式；如果指数为0的话，直接输出系数；如果系数是1的话就直接输出+x；如果系数是-1的话就直接输出-x。 （5）一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二多项式用新节点产生。通过Apolyn实现多项式加法：Pa=Pa+Pb,利用两个多项式的结点构成和“和多项式”。 （6）一元多项式减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节 点产生，并且建立的节点的系数为原来的相反数。通过Bpolyn实现多项式减法：Pa=Pa-Pb,利用两个多项式的结点构成和“差多项式”。四所用到的头文件说明：(1)#include /*标准输入输出函数*/(2)#include /*标准库函数，调用动态分布函数和随机函数*/(3)#include /*标准库函数，调用字符函数*/五应用程序功能说明(1) typedef struct term /*定义一个结构体类型的变量term，多项式的项作为LinkList的数据元素*(2) term* CreatPolyn(term *P,int m) /* 输入m项的系数和指数，建立表示一元多项式的有序链表P*/(3) if(m = 0) return NULL /*如果m不大于零，则返回一个空指针NULL*(4) (term*)malloc(sizeof(term) 声明了一个动态分布函数，这个函数的返回值是指针类型，函数返回一个整形变量地址（5）term* selsort(term *h) 对以h指针指向的一个一元多项式链表进行选择排序，按照指数由高到低的原则(6) PrintfPoly(term *P) 输出多项式P(7) Compare(term *a, term *b) 表示函数的返回值是一个指向整型数据的指针(8) term* APolyn(term *Pa, term *Pb) 多项式加法：Pa = PaPb，利用两个多项式的结点构成和多项式（9）if (sum != 0.0) 修改多项式PA中当前结点的系数值 （10）term* BPolyn(term *Pa, term *Pb) 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成差多项式(11) if(s1!=0 | !isdigit(*s) 判断一个字符是不是0-9之间任意一个，如果是则返回1，不是则返回0六程序运行过程举例 一元多项式计算： 输入第一个一元多项式的项数 1 依次输入2个数（前一个为系数，后一个为指数） 1 2 x2 1:加 2：减 3：下一步 1 输入第二个一元多项式的项数 1 依次输入2个数（前一个为系数，后一个为指数） 3 2x2+2x2=3x2 1:加 2：减 3：下一步 2 输入第二个一元多项式的项数 1 依次输入2个数（前一个为系数，后一个为指数） 2 2 3x2-(2x2)=x2 1:加 2：减 3：下一步 (下一步即提示退出)七参考文献1.陈文博，朱青.数据结构与算法M，机械工业出版社，1996.09 125-1272.谭浩强编著.C程序设计题解与上机指导（第二版）.北京:清华大学出版社，19993. 晋良颍.数据结构M.人民邮电出版社，2002.05 34-414. 谭浩强.C+程序设计（第三版）清华大学出版社，2004八源程序代码#include*调用动态分布函数和随机函数*#include #include*调用字符函数* typedef struct term /项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 struct term *next; term; term* CreatPolyn(term *P,int m) / 算法 / 输入m项的系数和指数，建立表示一元多项式的有序链表P if(m coef = 0.0; int i; printf(依次输入%d个数（前一个为系数，后一个为指数）n,m*2); for (i = 1; i coef,&P-expn); if(P-coef) q = P; P = P-next = (term*)malloc(sizeof(term); q-next = NULL; free(P); return h; / CreatPolyn term* selsort(term *h) term *g, *p, *q; if(!h) return NULL; float f; int i, fini = 1; for(g = h;g-next&fini;g = g-next) fini = 0; for(p = h,q = h-next;q;p = p-next,q = q-next) if (p-expn expn) f = p-coef;i = p-expn; p-coef = q-coef;p-expn = q-expn; q-coef = f;q-expn = i; fini = 1; for(g = h,p = g-next;p;) if(g-expn=p-expn) g-coef += p-coef; g-next = p-next; q = p; p = p-next; free(q); else if(g-next) g = g-next; p = p-next; return h; void PrintfPoly(term *P) term *q = P; if(!q) putchar(0); return; if(q-coef!=1) printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); q = q-next; while (q) if(q-coef 0) putchar(+); if(q-coef!=1) printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); q = q-next; Compare(term *a, term *b) *表示函数的返回值是一个指向整型数据的指针*if (a-expn expn) return -1; if (a-expn b-expn) return 1; return 0; term* APolyn(term *Pa, term *Pb) / 算法 / 多项式加法：Pa = PaPb，利用两个多项式的结点构成和多项式。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p-next = NULL; while (qa & qb) / Pa和Pb均非空 switch (Compare(qa,qb) case -1: / 多项式PA中当前结点的指数值小 p-next = qb; p = qb; qb = qb-next; break; case 0: / 两者的指数值相等 sum = qa-coef + qb-coef; if (sum != 0.0) / 修改多项式PA中当前结点的系数值 p-next = qa; qa-coef = sum; p = qa; qa = qa-next; else / 删除多项式PA中当前结点 q = qa; qa = qa-next; free(q); q = qb; qb = qb-next; free(q); break; case 1: / 多项式PB中当前结点的指数值小 p-next = qa; p = qa; qa = qa-next; break; / switch / while if (Pa) p-next = qa; / 链接Pa中剩余结点 if (Pb) p-next = qb; / 链接Pb中剩余结点 q = h; h = h-next; free(q); return h; / APolyn term* A(term *Pa, term *Pb) int n; puts(输入第二个一元多项式的项数); scanf(%d,&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); *对n-1个元素选择排序*PrintfPoly(Pa); if(Pb & Pb-coef0) printf( + ); PrintfPoly(Pb); Pa = APolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; term* BPolyn(term *Pa, term *Pb) / 算法 / 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成差多项式。 term *p = Pb; while(p) p-coef *= -1; p = p-next; return APolyn(Pa,Pb); / BPolyn term* B(term *Pa, term *Pb) int n; puts(输入第二个一元多项式的项数); scanf(%d,&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); printf( - ); putchar();PrintfPoly(Pb);putchar(); Pa = BPolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() term *M,*N; char s2; int i,n; puts(一元多项式计算:n输入第一个一元多项式的项数); scanf(%d,&n); M = CreatPolyn(M,n); M = selsort(M); PrintfPoly(M); p: puts(n1:加n2:减n3:下一步); getchar(); q: gets(s); if(s1!=0 | !isdi