武汉理工大学华夏学院 课程设计报告书
课程名称：
数据结构
题 目：用C 语言实现多项式简单计算器的设计
系 名： 信息工程系
专业班级： 软件工程1121班
姓 名： 邓 燕 蓉 指导教师: 王 绪 梅
2013 年 6月 28日
课程设计任务书
学生姓名： 邓燕蓉 专业班级： 软件工程1121班 指导教师： 王绪梅 工作单位：华夏学院计算机教研室 设计题目：用C 语言实现多项式简单计算器的设计 设计目的
1. 巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法； 2. 选择合适的数据的逻辑结构和存储结构以及相应操作，实现简单的多项式计算； 3. 提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养 ；
设计任务 （在规定的时间内完成下列任务）
〔问题描述〕输入并建立两个多项式并输出多项式
设计一个程序：对两个多项式进行加、减法及乘法运算, 建立一个新多项式并输出.
或设计一个程序对其中一个多项式求导。 〔实现提示〕
选择带头结点的单链表或循环链表存储多项式, 头结点中存放多项式的参数及单链表的数据 具体要完成的任务是：
A . 编制完成上述问题的C 语言程序、进行程序调试并能得出正确的运行结果。 B . 写出规范的课程设计报告书；
时间安排：6月24日---28日
具体要求
1. 课程设计报告按统一通用格式书写，具体内容如下： ① 设计任务与要求 ② 总体方案与说明
③ 软件主要模块的流程图 ④ 源程序清单与注释
⑤ 问题分析与解决方案（包括调式记录、调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）； ⑥ 小结与体会
附录：① 源程序（必须有简单注释） ② 使用说明 ③ 参考资料 2. 每位学生应独立完成各自的任务且每天至少在设计室工作半天；
指 导 教 师 签 名： 王绪梅 2013 年 6月 22日
教研室主任（或责任教师）签名： 2013年 6月 24日
目 录
1. 设计题目 .............................................................................................................................1 2. 需求分析.............................................................................................................................1 2.1 一元多项式的简单计算器的基本功能 ................................................1 2.2 设计思路 ...............................................................................................................1 3. 系统过程 ............................................................................................................................2 3.1 概要设计 ...............................................................................................................2 3.2 详细设计 ...............................................................................................................3 4. 调用关系图 . ........................................................................................................................3
4.1 总流程图 ...............................................................................................................4 4.2 加法流程图 . .........................................................................................................5 4.3 减法流程图 . .........................................................................................................6 5. 测试 . ........................................................................................................................................7
5.1 测试数据 ...............................................................................................................7 5.2 打开程序时的主界面 . ....................................................................................7 5.3 输入并建立多项式 ..........................................................................................8 5.4 选择执行的操作及执行的结果 ...............................................................9 6. 心得体会及总结 ............................................................................................................10 7. 参考文献 ............................................................................................................................10 附录 ........................................................................................................................................ 11
数据结构课程设计报告书
1 设计题目
用C 语言实现多项式简单计算器的设计
2 需求分析
2. 1 一元多项式的简单计算器的基本功能
（1）输入并建立多项式； （2）输出多项式；
（3）多项式a 和b 相加，建立多项式a+b； （4） 多项式a 和b 相减，建立多项式a-b ； （5）多项式a 和b 相乘，建立多项式a*b。
2.2 设计思路
（1）定义线性表的动态分配顺序存储结构； （2）建立多项式存储结构，定义指针*next；
（3）利用链表实现队列的构造，每次输入一项的系数和指数，可以构造一元多项式；
（4）演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的数据进行输入建立多项式以及多项式相加，减，乘的运行结果在屏幕上显示。 设计思路分析：
要解决多项式相加，相减，相乘，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为：
运用尾插法建立两个单链表，以单链表Polyn p和Polyn h分别表示一元多项式a 和b ，a+b的求和运算等同于单链表的插入问题（将Polyn p中的结点插入到单链表Polyn h中），因此“和多项式”的结点无须另生成。
为了实现处理，设p 、q2分别指向单链表polya 和polyb 的当前项，比较p 、q2结点的指数 由此得到下列运算规则：
① 若p->expnexpn，则结点q2所指的结点应是“和多项式”中的一项，令指针q2后移。 ② 若p->expn=q2->expn，则将两个结点中的系数相加，当和不为0时修改结点q2的系数。 ③ 若p->expn>q2->expn，则结点p 所指的结点应是“和多项式”中的一项，将结点p 插入在结点q2之前，且令指针p 在原来的链表上后移。
3 系统设计
3.1 概要设计
系统的主功能模块结构如图3—1所示。
图3—1 系统的主功能模块结构
3.2 详细设计
1、元素类型、结点类型和指针类型：
typedef struct Polynomial {
float coef; //系数 int expn; //指数 struct Polynomial *next;
}*Polyn,Polynomial;
2、建立一个头指针为head 、项数为m 的一元多项式, 建立新结点以接收数据, 调用Insert 函数插入结点:
Polyn CreatePolyn(Polyn head,int m){ int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i
{
p=(Polyn)malloc(sizeof(struct Polynomial)); printf(" 请输入第%d项的系数与指数:",i+1); scanf("%f %d",&p->coef,&p->expn);
Insert(p,head); //调用Insert 函数插入结点
}
return head; }
3、主函数和其他函数：
int main() {
int m,n,flag=0; float x;
Polyn pa=0,pb=0,pc,pd,pe,pf; }
void PrintPolyn(Polyn P) //输出多项式a 和b
Polyn AddPolyn(Polyn pa,Polyn pb) //求解并建立多项式a+b，返回其头指针 Polyn SubtractPolyn(Polyn pa,Polyn pb) //求解并建立多项式a-b ，返回其头指针 Polyn MultiplyPolyn(Polyn pa,Polyn pb) //求解并建立多项式a*b，返回其头指针
4 调用关系图
4.1 总流程图
总流程图如图4—1所示。
4.2 执行加法流程图
执行加法流程图如图4—2所示。
图4—2 执行加法流程图
4.3
执行减法流程图
执行减法流程图如图4—3所示。
图4—3 执行减法流程图
5 测试 5.1 测试数据
1、(-3x11+5x8 +4x)+( 11x9-5x 8+7)=(-3x11+11x9+4x+7);
2、(7x-3 +4.4x2-1.2x 9-x)-(-6x-3+5.4x2-x 2+7.8x15)=(-7.8x15-1.2x 9+13x-3-x); 3、(9x8+4x6-5x 4+8x)*( x14+2x4)=（9x 22+4x20-5x 18+8x15+18x12+8x10-10x 8+16x5); 4、(x+x3)+(-x-x3)=0;
5、(1-x+x2+x3-x 4)*(-x3-x 4)=(x8-2x 6-x 3) 。
5.2. 打开程序时的主界面
打开程序时的主界面如图5—1所示。
图 5—1 打开程序时的主界面
5.3 .输入并建立多项式
输入并建立多项式如图5—2所示。
图5—2 输入并建立多项式
5.4 选择执行的操作及执行操作的结果
选择执行的操作及执行操作的结果如图5—3、5—4、5—5所示
。
图 5—3 选择执行的操作及执行操作的结果
图 5—4 选择执行的操作及执行操作的结果
图5—5 选择执行的操作及执行操作的结果
6 心得体会及总结
通过这次课程设计，我感觉到要自己动手真正做出一个程序并不很容易, 但只要用心去做，总会有收获, 特别是当我遇到问题, 问老师，问同学，想尽办法去解决, 最后终于找到方法时, 心里的那份喜悦之情真是难以形容. 编写程序中遇到问题再所难免, 应耐心探究其中的原因, 从出现问题的地方起, 并联系前后程序, 仔细推敲, 逐个排查. 直到最终搞清为止。
对于数据结构有了更深层次的理解, 数据结构体现的是解决问题的一种思想，怎样把这种思想体现出来，需要我们对每个方面的系统了解。并发现了许多自己的不足，平时没掌握的的知识在实践中暴露，经过不断的思考，查阅书籍和上网查资料及上机运行，解决了大部分的问题，还有一些小问题。但是，我相信在今后的学习中，一定能把它解决好。当今计算机应用在生活中可以说是无处不在。因此作为二十一世纪的大学生来说掌握程序开发技术是十分重要的，而C 语言又是最常见，功能最强大的一种高级语言，因此做好c 语言版数据结构课程设计是十分必要的。我不仅巩固了数据结构程序设计的内容，掌握设计的基本方法，强化了上机动手能力，还进一步掌握了以下知识：数据类型，分支控制，循环控制，结构体及数组，指针，文件操作，编译预处理等；通过课程设计，掌握了程序的局部测试，调试方法，建立程序系统调试，测试的基本概念和思想，学会较大程序的系统测试和调试方法。当我选择通讯录管理系统时，首先系统分析主要思路和框架哦，与同学讨论，联系所学的知识。我知道书上和老师讲的有限，所以上网搜也是一种利用资源的表现。在编程中，特别是结构体，指针的部分，几乎是一片空白。不过经过几天的努力，大体把课本上的知识点看了一遍，知识点也基本上掌握了，所以下一步就是开始正式的编程序了。当读懂了C 语言编程的基本过程和方法，经过一波三折，终于开始正式编程。
通过这次的课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的知识与实际结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力。
在课程设计过程中，收获知识，提高能力的同时，我也学到了很多的人生哲理，懂得了怎么去制定计划，怎么去实现这个计划，并掌握了在执行的过程中怎样去克服心理上的不良情绪。因此在以后的生活和学习的过程中，我一定把课程设计的精神带到生活中，使生活变得更好。
7 参考文献
[1]唐国民，王国均. 数据结构（C 语言版）·北京：清华大学出版社.
[2] 严蔚敏，吴伟民. 数据结构（C 语言版）. 北京：清华大学出版社，1997. [3] 詹春华，杨沙. 《C 语言程序设计教程》 科学出版社，2011.8
[4]董志民，崔建平，肖利娜. 《C 语言程序设计》教学改革探索与实践[J].福建电脑. [5] 王路明•C 语言程序设计教程•北京：北京邮电大学出版社，2005年5月 [6] 谭浩强·C++程序设计·北京：清华大学出版社·2004 [7]范策. 算法与数据结构（C 语言版）. 北京：机械工业出版社，2004.
附录
#include #include typedef struct Polynomial { float coef; int expn;
struct Polynomial *next;
}*Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h)
{ if(p->coef==0) free(p); //系数为0的话释放结点 else { Polyn q1,q2; q1=h;q2=h->next;
while(q2&&p->expnexpn) //查找插入位置 { q1=q2; q2=q2->next; }
if(q2&&p->expn==q2->expn) //将指数相同相合并 { q2->coef+=p->coef; free(p);
if(!q2->coef) //系数为0的话释放结点 { q1->next=q2->next; free(q2); } }
else //指数为新时将结点插入 { p->next=q2; q1->next=p; } } }//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;i
{ p=(Polyn)malloc(sizeof(struct Polynomial)); //建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); //调用Insert 函数插入结点 }
return head; }//CreatePolyn
void DestroyPolyn(Polyn p) //销毁多项式p { Polyn q1,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->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1) //系数非1或-1的普通情况 { printf("%g",q->coef); if(q->expn==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++; }//while printf("\n"); }//PrintPolyn
int compare(Polyn a,Polyn b) { if(a&&b)
{ if(!b||a->expn>b->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 多项式非空 }//compare
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 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=qb->expn; qb=qb->next; break; } }//switch if(qc->coef!=0) {
qc->next=hc->next; hc->next=qc; hc=qc; }
else free(qc);//当相加系数为0时，释放该结点 }//while return headc; }//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; return pd; }//SubtractPolyn
Polyn MultiplyPolyn(Polyn pa,Polyn pb) //求解并建立多项式a*b，返回其头指针 { Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next;
hf=(Polyn)malloc(sizeof(struct Polynomial)); //建立头结点 hf->next=NULL; for(;qa;qa=qa->next)
{ for(qb=pb->next;qb;qb=qb->next)
{ pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn;
Insert(pf,hf); //调用Insert 函数以合并指数相同的项 } } return hf; }//MultiplyPolyn int main() {
int m,n,flag=0; float x;
Polyn pa=0,pb=0,pc,pd,pe,pf; //定义各式的头指针，pa 与pb 在使用前赋初值NULL printf("请输入a 的项数:"); scanf("%d",&m);
pa=CreatePolyn(pa,m); //建立多项式a printf("请输入b 的项数:"); scanf("%d",&n);
pb=CreatePolyn(pb,n); //建立多项式b //输出菜单
printf("********************操作提示**************************\n"); printf("\t 1.输出多项式a 和b\n");
printf("\t 2.建立多项式a+b\n"); printf("\t 3.建立多项式a-b\n"); printf("\t 4.建立多项式a*b\n");
printf("\t 5.退出\n*******************************************\n"); for(;;flag=0) {
printf("执行操作"); scanf("%d",&flag); if(flag==1){
printf("多项式a ：");PrintPolyn(pa); printf("多项式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){
pf=MultiplyPolyn(pa,pb);
printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);continue; }
if(flag==5) break;
if(flag8) printf("Error!!!\n");continue; }//for
DestroyPolyn(pa); DestroyPolyn(pb); return 0; }