《2022年课程方案—一元多项式计算器中国地图着色》由会员分享，可在线阅读，更多相关《2022年课程方案—一元多项式计算器中国地图着色（11页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用课程名称：指导教师：姓名性别学号班级计科综合成绩成绩等级程序运行情况占总成绩 20%）能正确运行基本能正确运行能运行但结果不完善20分） 15分） 10 分）程序功能的完善程度占总成绩 10%）完善基本完善不完善10分） 8分） 5分）程序结构的合理性占总成绩 10%）合理基本合理不太合理10分） 8分） 5分）对问题的答辩情况占总成绩 40%）概念正确有创新能正确回答所有问题基本能正确回答40分） 35分） 30分）部分问题回答概念不清晰20分）学生的工作态度与独立工作能力占总成绩 10%）工作态度认真能独立完成任务工作态度认真但独立性较差10分） 8 分）工作态度基
2、本认真但缺乏独立性5分）设计报告的规范性占总成绩 10%）符合规范基本符合规范规范性较差10分） 8分） 5分）优秀： 90分100分 良好： 80分89分 中等： 7079分 及格： 6069分 不及格 0分59分武汉科技大学计算机科学与技术学院制表数据结构课程设计任务书【设计目的】数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C 语言的算法转换成CC+）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软
3、件工作者工作作风的训练，将起到显著的促进作用。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 11 页个人资料整理仅限学习使用【设计要求】1、课程设计题目共二题，每个学生必须独立完成；2、课程设计时间为1.5 周；3、设计语言 CC+ ）不限；4、课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。5、上机任务1）选择合适的数据结构，并定义数据结构的结构体；2）根据程序所要完成的基本要求，设计出完整的算法；3）设计出主程序main函数），使其成为完整的程序。6、上机时间：上午8:2011:50 ，下午 2:105:4
4、0 7、无论在校外、校内，都要严格遵守学校和所在单位的学习和劳动纪律、规章制度，学生有事离校必须请假。课程设计期间，无故缺席按旷课处理；缺席时间达四分之一以上者，其成绩按不及格处理。特别说明： 数据结构、算法、输入输出方式、其他功能均可自行设计，鼓励思路创新。课程设计一：一元多项式计算器1）需求分析设计一个一元多项式的计算器，功能包括1）输入并建立多项式一个多项式最多不超过20项），可以从文件中读取相关数据；2）输出多项式，输出形式可以是图形方式，也可以是文本方式；3）实现两个多项式相加，并输出和多项式；4）实现两个多项式相减，并输出差多项式；5）实现两个多项式相乘，并输出乘积多项式； 精选学
5、习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 11 页个人资料整理仅限学习使用/ 建立一个头指针为head、项数为 m的一元多项式 int i。 Polyn p。 p=head=(Polynmalloc(sizeof(struct Polynomial。 head-next=NULL 。 for(i=0 。 i p=(Polynmalloc(sizeof(struct Polynomial。 /建立新结点以接收数据 printf( 请输入第 %d项的系数与指数:,i+1 。 scanf(%f %d,&p-coef,&p-expn。 Inse
6、rt(p,head。 /调用 Insert函数插入结点 return head。 -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
7、 / 指数为新时将结点插入 p-next=q2。 q1-next=p。 -Polyn AddPolyn(Polyn pa,Polyn pb/求解并建立多项式a+b，返回其头指针 Polyn qa=pa-next。 Polyn qb=pb-next 。 Polyn headc,hc,qc。 hc=(Polynmalloc(sizeof(struct Polynomial。/建立头结点 hc-next=NULL 。 headc=hc。 while(qa|qb qc=(Polynmalloc(sizeof(struct Polynomial。 switch(compare(qa,qb case 1:
8、 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。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 11 页个人资料整理仅限学习使用 case -1: qc-coef=qb-coef 。 qc-expn=qb-expn 。 qb=qb-next 。 break。 /switch if(qc-coef!=0 qc-n
9、ext=hc-next 。 hc-next=qc。 hc=qc。 else free(qc。 /当相加系数为0时，释放该结点 /while return headc。 多项式减号的重载跟加号的重载类似，这里不再累述-Polyn MultiplyPolyn(Polyn pa,Polyn pb/求解并建立多项式a*b，返回其头指针 Polyn hf,pf 。 Polyn qa=pa-next。 Polyn qb=pb-next 。 hf=(Polynmalloc(sizeof(struct Polynomial。/建立头结点 hf-next=NULL 。 for(。qa。qa=qa-next fo
10、r(qb=pb-next 。qb。 qb=qb-next pf=(Polynmalloc(sizeof(struct Polynomial。 pf-coef=qa-coef*qb-coef 。 pf-expn=qa-expn+qb-expn 。 Insert(pf,hf 。/调用 Insert函数以合并指数相同的项 return hf。-主程序及其主要模块的伪码流程int main( int m,n,flag=0 。 float x。 Polyn pa=0,pb=0,pc,pd,pe,pf 。/定义各式的头指针，pa与pb在使用前付初值NULL printf( 请输入 a的项数 :。 scan
11、f(%d,&m 。 pa=CreatePolyn(pa,m。/建立多项式 a printf( 请输入 b的项数 :。 scanf(%d,&n 。 pb=CreatePolyn(pb,n 。/建立多项式 a /输出菜单 printf(*n。 printf( 操作提示： nt1.输出多项式 a和b 。 printf(nt2. 输出多项式 a+b。 printf(nt3. 输出多项式 a-b。 printf(nt4. 计算多项式 a在x处的值 。 printf(nt5. 输出多项式 a*b 。 printf(nt6. 退出 n*n。 for(。 flag=0 printf( 请选择操作 。 scan
12、f(%d,&flag 。 if(flag=1 printf( 多项式 a：。 PrintPolyn(pa 。 printf( 多项式 b：。 PrintPolyn(pb 。continue。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 11 页个人资料整理仅限学习使用 if(flag=2 pc=AddPolyn(pa,pb 。 printf( 多项式 a+b： 。PrintPolyn(pc 。 DestroyPolyn(pc 。continue。 if(flag=3 pd=SubtractPolyn(pa,pb 。 printf(
13、多项式 a-b：。PrintPolyn(pd 。 DestroyPolyn(pd 。continue。 if(flag=4 printf( 输入 x的值： x= 。 scanf(%f,&x 。 printf( 多项式 a的值 %gn,ValuePolyn(pa,x 。continue。 if(flag=5 pf=MultiplyPolyn(pa,pb。 printf( 多项式 a*b：。PrintPolyn(pf 。 DestroyPolyn(pf 。continue。 if(flag=6 break 。 if(flag6 printf(Error!n。continue。 /for Destr
14、oyPolyn(pa 。 DestroyPolyn(pb 。 return 0。 3）调试分析对设计和实践的回顾和分析在建立多项式，考虑到实际中多项式的次数可能很高且变化很大，若采用顺序存储结构将面临难以确定顺序存储结构的最大长度的问题，还有在实现多项式之间的运算时多项式的系数和指数又会发生变化，采用顺序存储结构将使得操作异常复杂，而采用链式存储结构能避免这些问题。在设计多项式之间的加、减和乘运算时，将运算符进行了重载。为了保证未知数的值在多项式中有意义，特地设置了观察比较两个多项式指数状况。经验和体会在学习的过程中要注意学习和实践，在学习过程中要由一种问题拓展到多种问题，考虑实际操作中可能遇
15、到的情况，并找到解决问题的方案，注重积累。很多知识课本上可能都没有提及到，不少内容是我们可以通过上机实验获得答案的。学习的东西必须要通过实践不断巩固和深化，不然很快就忘了。4）用户手册运行程序后首先输入多项式a的项数 以3项为例，输入3），接着依次输入1,2,3项的系数，然后输入多项式b的数据 如下图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 11 页个人资料整理仅限学习使用5）测试结果 如下图）6）附录 带注释的源程序）#include #include typedef struct Polynomial float coef。
16、/系数 int expn。/指数 struct Polynomial *next 。*Polyn,Polynomial 。 /Polyn 为结点指针类型void Insert(Polyn p,Polyn h if(p-coef=0 free(p 。 /系数为 0的话释放结点 else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 11 页个人资料整理仅限学习使用 Polyn q1,q2。 q1=h。q2=h-next 。 while(q2&p-expnexpn /查找插入位置 q1=q2。 q2=q2-next 。 if(q2&p-e
17、xpn=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=(Polynmalloc(sizeof(struct Polynomial。 head-next=NULL 。 for(i=0 。 i
18、p=(Polynmalloc(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 PrintPol
19、yn(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-expn=1 putchar(X。 else if(q-expn printf(X%d,q-expn。 else if(q-coef=1 if(!q-expn putchar(1
20、。 else if(q-expn=1 putchar(X 。 else printf(X%d,q-expn。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 11 页个人资料整理仅限学习使用 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
21、|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多项式非空/compare Polyn AddPolyn(Polyn pa,Polyn pb/求解并建立多项式a+b，返回其头指针 Polyn qa=pa-next。 Polyn qb=pb-next 。 Polyn headc,hc,qc。 hc=(Polynmalloc(sizeof(struct Polynomial。
22、/建立头结点 hc-next=NULL 。 headc=hc。 while(qa|qb qc=(Polynmalloc(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 。 q
23、b=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 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 11 页个人资料整理仅限学习使用 Polyn p=pb-next 。 Polyn
24、 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 float ValuePolyn(Polyn head,float x/输入 x值，计算并返回多项式的值 Polyn p。 int i。 float sum=0,t 。 for(p=head-next 。p。p=p-next t=1。 for(i=p-expn 。i!=0 。 if(it/=x 。 i+。/ 指数小于
25、 0，进行除法 elset*=x 。i-。 / 指数大于 0，进行乘法 sum+=p-coef*t 。 return sum。/ValuePolyn Polyn MultiplyPolyn(Polyn pa,Polyn pb/求解并建立多项式a*b，返回其头指针 Polyn hf,pf 。 Polyn qa=pa-next。 Polyn qb=pb-next 。 hf=(Polynmalloc(sizeof(struct Polynomial。/建立头结点 hf-next=NULL 。 for(。qa。qa=qa-next for(qb=pb-next 。qb。 qb=qb-next pf=(
26、Polynmalloc(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。/建立
27、多项式 a printf( 请输入 b的项数 :。 scanf(%d,&n 。 pb=CreatePolyn(pb,n 。/建立多项式 a /输出菜单 printf(*n。 printf( 操作提示： nt1.输出多项式 a和b。 printf(nt2. 输出多项式 a+b。 printf(nt3. 输出多项式 a-b。 printf(nt4. 计算多项式 a在x处的值 。 printf(nt5. 输出多项式 a*b 。 printf(nt6. 退出 n*n。 for(。 flag=0 printf( 请选择操作 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
28、 - - -第 9 页，共 11 页个人资料整理仅限学习使用 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 。 DestroyPol
29、yn(pd 。continue。 if(flag=4 printf( 输入 x的值： x= 。 scanf(%f,&x 。 printf( 多项式 a的值 %gn,ValuePolyn(pa,x 。continue。 if(flag=5 pf=MultiplyPolyn(pa,pb。 printf( 多项式 a*b：。PrintPolyn(pf 。 DestroyPolyn(pf 。continue。 if(flag=6 break 。 if(flag6 printf(Error!n。continue。 /for DestroyPolyn(pa 。 DestroyPolyn(pb 。 retu
30、rn 0。 课题二 : 地图着色问题1）需求分析程序设计的任务：设计地图着色软件，对地图上的区域进行着色，要求相邻的区域所使用的颜色不相同，并且要保证使用的颜色最少地图数据可以从文件中读取，也可以由用户将地图抽象成点线模型后输入）输出的形式：颜色代码+点的名称 +与该点相邻的点的名称，最后统计所用的颜色的数目。输出示例如下：COLOR:0 v1 v2 COLOR:1 v2 v1 v3 COLOR:0 v3 v2 Color Used:2 程序功能包括：1） 数据结构的设计：地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。2） 算法设计：设计着色算法，保证邻接点不是同一种颜色
31、。 / 新建弧的指针ArcNode *p=new ArcNode 。/申请存储空间p-name=name。/设置该弧上点的名称p-nextarc=NULL 。/指向下一条弧的指针置为空return p。 /返回该弧的指针 -void AdjList:CreateVertex(int m_vexnum / 创建地图模型中所有点的信息，参数m_vexnum 为点的数目vexnum=m_vexnum 。 /根据参数设置点的数目vertices=new VNodevexnum 。/为vexnum个结点申请存储空间if(vertices=NULL exit(EXIT_FAILURE。/若申请失败就退出for(int i=0 。i/ 依次设置各点的信息 cin(vertices+i-name 。/输入点的名称(vertices+i-color=-1 。/将点的颜色初始化为-1 (vertices+i-firstarc=NULL。/将第一条弧设置为空(vertices+i-rear=NULL 。/将最后一条弧设置为空精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 11 页
