2022年课程方案—一元多项式计算器中国地图着色.docx

《2022年课程方案—一元多项式计算器中国地图着色.docx》由会员分享，可在线阅读，更多相关《2022年课程方案—一元多项式计算器中国地图着色.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 课程名称：个人资料整理仅限学习使用计科指导老师：姓名性别学号班级综合成果成果等级程序运行情形 能正确运行 基本能正确运行 能运行但结果不完善占总成果 20% ）20分） 15分） 10分）程序功能的完善 完善 基本完善 不完善程度占总成果 10% ）10分） 8分） 5分）程序结构的合理 性占总成果 10% ） 合理 基本合理 不太合理10分） 8分） 5分）对问题的答辩情 概念正确有创新 能正确回答全部问题 基本能正确回答况40分） 35分） 30分）占总成果 40% ） 部分问题回答概念不清楚20分）同学的工作态度 与独立工作才能 占总成果

2、 10% ）设计报告的规范 性占总成果 10% ） 工作态度仔细能独立完成任务 工作态度仔细但独立性较差10分） 8分） 工作态度基本仔细但缺乏独立性5分） 符合规范 基本符合规范 规范性较差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）设

4、计出主程序 main函数）,使其成为完整的程序；6、上机时间：上午 8:2011:50 ,下午 2:105:40 7、无论在校外、校内,都要严格遵守学校和所在单位的学习和劳动纪律、规章制度,同学有事离校必 须请假；课程设计期间,无故缺席按旷课处理；缺席时间达四分之一以上者,其成果按不及格处理；特殊说明： 数据结构、算法、输入输出方式、其他功能均可自行设计,勉励思路创新；课程设计一：一元多项式运算器 1）需求分析 设计一个一元多项式的运算器,功能包括1）输入并建立多项式一个多项式最多不超过20项）,可以从文件中读取相关数据；2）输出多项式,输出形式可以是图形方式,也可以是文本方式；3）实现两个多

5、项式相加,并输出和多项式；4）实现两个多项式相减,并输出差多项式；5）实现两个多项式相乘,并输出乘积多项式； 名师归纳总结 - - - - - - -第 2 页,共 11 页精选学习资料 - - - - - - - - - 名师归纳总结 个人资料整理仅限学习使用第 3 页,共 11 页/ 建立一个头指针为head、项数为 m的一元多项式 int i ； Polyn p； p=head=Polynmallocsizeofstruct Polynomial； head-next=NULL ； fori=0 ； i p=Polynmallocsizeofstruct Polynomial； /建立新

6、结点以接收数据 printf 请输入第 %d项的系数与指数:,i+1 ； scanf%f %d,&p-coef,&p-expn； Insertp,head； /调用 Insert函数插入结点 return head； -void InsertPolyn p,Polyn h ifp-coef=0 freep ； /系数为 0的话释放结点 else Polyn q1,q2 ； q1=h；q2=h-next ； whileq2&p-expnexpn /查找插入位置 q1=q2； q2=q2-next ； ifq2&p-expn=q2-expn /将指数相同相合并 q2-coef+=p-coef ；

7、freep； if.q2-coef /系数为 0的话释放结点 q1-next=q2-next ； freeq2； else / 指数为新时将结点插入 p-next=q2 ； q1-next=p ； -Polyn AddPolynPolyn pa,Polyn pb/求解并建立多项式a+b,返回其头指针 Polyn qa=pa-next ； Polyn qb=pb-next ； Polyn headc,hc,qc； hc=Polynmallocsizeofstruct Polynomial；/建立头结点 hc-next=NULL ； headc=hc； whileqa|qb qc=Polynmal

8、locsizeofstruct Polynomial； switchcompareqa,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

9、 ； break； /switch ifqc-coef.=0 qc-next=hc-next ； hc-next=qc ； hc=qc； else freeqc； /当相加系数为 0时,释放该结点 /while return headc； 多项式减号的重载跟加号的重载类似,这里不再累述-Polyn MultiplyPolynPolyn pa,Polyn pb/ 求解并建立多项式 a*b,返回其头指针 Polyn hf,pf ； Polyn qa=pa-next ； Polyn qb=pb-next ； hf=Polynmallocsizeofstruct Polynomial；/建立头结点 h

10、f-next=NULL ； for ；qa；qa=qa-next forqb=pb-next ；qb； qb=qb-next pf=Polynmallocsizeofstruct Polynomial； pf-coef=qa-coef*qb-coef ； pf-expn=qa-expn+qb-expn ； Insertpf,hf ；/调用 Insert函数以合并指数相同的项 return hf；-主程序及其主要模块的伪码流程int main 名师归纳总结 int m,n,flag=0 ；NULL第 4 页,共 11 页 float x ； Polyn pa=0,pb=0,pc,pd,pe,pf

11、 ；/定义各式的头指针,pa与pb在使用前付初值 printf 请输入 a的项数 :； scanf%d,&m ； pa=CreatePolynpa,m；/建立多项式 a printf 请输入 b的项数 :； scanf%d,&n ； pb=CreatePolynpb,n ；/建立多项式 a /输出菜单 printf*n； printf 操作提示： nt1. 输出多项式 a和b ； printfnt2. 输出多项式 a+b ； printfnt3. 输出多项式 a-b； printfnt4. 运算多项式 a在x处的值 ； printfnt5. 输出多项式 a*b ； printfnt6. 退出

12、n*n for ； flag=0 printf 请挑选操作 ； scanf%d,&flag ； ifflag=1 printf 多项式 a：； PrintPolynpa ； printf 多项式 b：； PrintPolynpb ；continue； - - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 ifflag=2 pc=AddPolynpa,pb ； printf 多项式 a+b： ；PrintPolynpc ； DestroyPolynpc ；continue； ifflag=3 pd=SubtractPolynpa,pb ； pri

13、ntf 多项式 a-b： ；PrintPolynpd ； DestroyPolynpd ；continue； ifflag=4 printf 输入 x的值： x= ； scanf%f,&x ； printf 多项式 a的值 %gn,ValuePolynpa,x ；continue ； ifflag=5 pf=MultiplyPolynpa,pb； printf 多项式 a*b： ；PrintPolynpf ； DestroyPolynpf ；continue； ifflag=6 break ； ifflag6 printfError.n；continue； /for DestroyPolynp

14、a ； DestroyPolynpb ； 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 ；/指数第 6 页,共 11 页 struct Polynomial *next ；*Polyn,Polynomial ； /Polyn 为结点指针类型void InsertPolyn p,Polyn h ifp-coef=0 freep ； /系数为 0的话释放结点 else - - - - - - -精选学习资料 - - - - - - - - - 名师归纳总结 个人资料整理仅限学习使用第 7 页,共 11 页 Polyn q1,q2 ； q1=h；q2=h-next ； whileq2&p-expnexpn /查找插入位置 q1=q2； q2=q2-next

17、； ifq2&p-expn=q2-expn /将指数相同相合并 q2-coef+=p-coef ； freep； if.q2-coef /系数为 0的话释放结点 q1-next=q2-next ； freeq2； else / 指数为新时将结点插入 p-next=q2 ； q1-next=p ； /Insert Polyn CreatePolynPolyn head,int m/ 建立一个头指针为head、项数为 m的一元多项式 int i ； Polyn p； p=head=Polynmallocsizeofstruct Polynomial； head-next=NULL ； fori=0

18、 ； i p=Polynmallocsizeofstruct Polynomial； /建立新结点以接收数据 printf 请输入第 %d项的系数与指数:,i+1 ； scanf%f %d,&p-coef,&p-expn； Insertp,head； /调用 Insert函数插入结点 return head；/CreatePolyn void DestroyPolynPolyn p/销毁多项式 p Polyn q1,q2 ； q1=p-next ； q2=q1-next ； whileq1-next freeq1； q1=q2； /指针后移 q2=q2-next ； void PrintPol

19、ynPolyn P Polyn q=P-next ； int flag=1 ；/项数计数器 if.q / 如多项式为空,输出0 putchar0； printfn ； return； while q ifq-coef0&flag.=1 putchar+； /系数大于 0且不是第一项 ifq-coef.=1&q-coef.=-1/系数非 1或-1的一般情形 printf%g,q-coef； ifq-expn=1 putcharX； else ifq-expn printfX%d,q-expn； else ifq-coef=1 if.q-expn putchar1 ； else ifq-expn=

20、1 putcharX ； else printfX%d,q-expn； - - - - - - -精选学习资料 - - - - - - - - - 名师归纳总结 个人资料整理仅限学习使用第 8 页,共 11 页 ifq-coef=-1 if.q-expn printf-1； else ifq-expn=1 printf-X； else printf-X%d,q-expn； q=q-next； flag+ ； /while printfn ；/PrintPolyn int comparePolyn a,Polyn b ifa&b if.b|a-expnb-expn return 1 ； else

21、 if.a|a-expnexpn return -1 ； else return 0； else if.a&b return -1；/a多项式已空,但b多项式非空 else return 1；/b多项式已空,但a多项式非空/compare Polyn AddPolynPolyn pa,Polyn pb/求解并建立多项式a+b,返回其头指针 Polyn qa=pa-next ； Polyn qb=pb-next ； Polyn headc,hc,qc； hc=Polynmallocsizeofstruct Polynomial；/建立头结点 hc-next=NULL ； headc=hc； wh

22、ileqa|qb qc=Polynmallocsizeofstruct Polynomial； switchcompareqa,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 ifqc-coef.=0

23、qc-next=hc-next ； hc-next=qc ； hc=qc； else freeqc； /当相加系数为 0时,释放该结点 /while return headc；/AddPolyn Polyn SubtractPolynPolyn pa,Polyn pb/求解并建立多项式a+b,返回其头指针 Polyn h=pb ；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 Polyn p=pb-next ； Polyn pd； whilep / 将pb的系数取反 p-coef*=-1 ； p=p-next； pd=AddPolynpa

24、,h ； forp=h-next ；p； p=p-next / 复原 pb的系数 p-coef*=-1 ； return pd；/SubtractPolyn float ValuePolynPolyn head,float x/ 输入 x值,运算并返回多项式的值 Polyn p； int i ； float sum=0,t ； forp=head-next ；p；p=p-next t=1； fori=p-expn ；i.=0 ； ifit/=x ； i+；/ 指数小于 0,进行除法 elset*=x ；i- ； / 指数大于 0,进行乘法 sum+=p-coef*t ； return sum；

25、/ValuePolyn Polyn MultiplyPolynPolyn pa,Polyn pb/ 求解并建立多项式 a*b,返回其头指针 Polyn hf,pf ； Polyn qa=pa-next ； Polyn qb=pb-next ； hf=Polynmallocsizeofstruct Polynomial；/建立头结点 hf-next=NULL ； for ；qa；qa=qa-next forqb=pb-next ；qb； qb=qb-next pf=Polynmallocsizeofstruct Polynomial； pf-coef=qa-coef*qb-coef ； pf-e

26、xpn=qa-expn+qb-expn ； Insertpf,hf ；/调用 Insert函数以合并指数相同的项 return hf；/MultiplyPolyn 名师归纳总结 int main NULL第 9 页,共 11 页 int m,n,flag=0 ； float x ； Polyn pa=0,pb=0,pc,pd,pe,pf ；/定义各式的头指针,pa与pb在使用前付初值 printf 请输入 a的项数 :； scanf%d,&m ； pa=CreatePolynpa,m；/建立多项式 a printf 请输入 b的项数 :； scanf%d,&n ； pb=CreatePolyn

27、pb,n ；/建立多项式 a /输出菜单 printf*n； printf 操作提示： nt1. 输出多项式 a和b ； printfnt2. 输出多项式 a+b ； printfnt3. 输出多项式 a-b； printfnt4. 运算多项式 a在x处的值 ； printfnt5. 输出多项式 a*b ； printfnt6. 退出 n*n for ； flag=0 printf 请挑选操作 ；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 scanf%d,&flag ； ifflag=1 printf 多项式 a：； PrintPol

28、ynpa ； printf 多项式 b：； PrintPolynpb ；continue； ifflag=2 pc=AddPolynpa,pb ； printf 多项式 a+b： ；PrintPolynpc ； DestroyPolynpc ；continue； ifflag=3 pd=SubtractPolynpa,pb ； printf 多项式 a-b： ；PrintPolynpd ； DestroyPolynpd ；continue； ifflag=4 printf 输入 x的值： x= ； scanf%f,&x ； printf 多项式 a的值 %gn,ValuePolynpa,x ；

29、continue ； ifflag=5 pf=MultiplyPolynpa,pb； printf 多项式 a*b： ；PrintPolynpf ； DestroyPolynpf ；continue； ifflag=6 break ； ifflag6 printfError.n；continue； /for DestroyPolynpa ； DestroyPolynpb ； return 0； 课题二 : 地图着色问题1）需求分析 程序设计的任务：设计地图着色软件,对地图上的区域进行着色,要求相邻的区域所使用的颜色不相同,并且要保证使用的颜色最少 地图数据可以从文件中读取,也可以由用户将地图抽

30、象成点线模型后输入）输出的形式：颜色代码 +点的名称 +与该点相邻的点的名称,最终统计所用的颜色的数目；输出示例如下：COLOR:0 v1 v2 COLOR:1 v2 v1 v3 COLOR:0 v3 v2 Color Used:2 程序功能包括：1） 数据结构的设计：地图可以采纳图的数据结构,每个省为一个节点,边表示对应的两个省相邻；2） 算法设计：设计着色算法,保证邻接点不是同一种颜色； 第 11 页,共 11 页 / 新建弧的指针ArcNode *p=new ArcNode ；/申请储备空间p-name=name；/设置该弧上点的名称p-nextarc=NULL ；/指向下一条弧的指针置

31、为空return p； /返回该弧的指针 -void AdjList:CreateVertexint m_vexnum / 创建地图模型中全部点的信息,参数m_vexnum 为点的数目vexnum=m_vexnum ； /依据参数设置点的数目vertices=new VNodevexnum ；/为vexnum个结点申请储备空间ifvertices=NULL exitEXIT_FAILURE；/如申请失败就退出forint i=0 ；i/ 依次设置各点的信息 cinvertices+i-name ；/输入点的名称vertices+i-color=-1 ；/将点的颜色初始化为-1 vertices+i-firstarc=NULL；/将第一条弧设置为空vertices+i-rear=NULL ；/将最终一条弧设置为空- - - - - - -