数据结构与算法课程设计

1、高校LOGO位置课程设计报告课程设计题目：一元多项式的加减计算学生姓名：星毅专业:自疋义班级:自疋义指导教师：邹老师2015年乙月2日高校名称课程设计评分表学生姓名：星毅课程设计题目：班级：自定义学号：自定义项目内容满分实评选 题能结合所学课程知识、有一定的能力训练。符合选题要求 （5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、 制图等10能体现创造性思维，或有独特见解10成 果 质 量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练

2、完整，概念清楚、立论正确、技术用语准确、 结论严谨合理；分析处理科学、条理分明、语言流畅、结构 严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总分100指导教师评语：指导教师签名：年月日课程设计报告要求：结构要求：1、问题分析：要求用自己的话概括出本课题的内容、功能结构2、结构分析：根据问题分析的结果，进一步分析出系统的类结构及相互关系3、实现流程分析：概述自己的实现过程：如工程建立流程、类创建流程等4、个性功能介绍：应介绍自己在系统中的程序改进与新增的功能模块的意义、价值5、课程设计小结：

3、简述自己课程设计的收获 格式要求：中文正文使用五号字体，英文及代码使用小五号字体1、问题分析能够按照指数降序排列建立多项式； 能够完成两个多项式的相加和相减，并将结果输出。2 、 结构分析这个程序的关键是多项式的创建和排列， 相同指数的系数相加、 相减时相同指数的系数 相减。由于多项式拥有指数和系数（假设基数已定） ，所以可以定义一个包含指数系数的结 构体，用单链表存储多项式的数据，所以结构体包含 next 指针。数据插入时比较两数的指数，按照降序排序，从表头的 next 开始，直至找到合适的位 置，然后开始链表中数值的插入， 如果相等则直接将指数相加， 如果大于就将新数据插入到 当前指向的前

4、面，否则将新数据插入到最后。输入完数据后选择计算方式（相加、相减） 多项式运算时要循环遍历整个多项式， 多项式的每一组数据都要和另一个多项式整组数据相 运算（每一个运算值都存储到新建的“多项式”链表中） ，直到两个多项式都遍历完结束。3 、 实现流程分析存储结构类型：单链表。在模拟多项式对象时，为了简化处理，只取最核心的两个数据：多项式的系数和指数。前面提到，要用单链表操作，所以要加上个 next 指针，再由该结构体定义一 个结点类型和指针类型。具体数据结构定义如下：typedef struct nodeint xs; /* 系数 */int zs;/* 指数 */struct node *

5、next;/*next 指针 */Dnode,* Dnodelist;多项式相加的基本过程的算法? 链表初始化函数 Creat_node()带有头结点的头指针 D 指向空( NULL )。? 多项式数据的创建函数 Creat_Dmeth()当链表初始化成功后，开始创建多项式。分别循环输入两个多项式的系数和指 数，其中要用到插入函数。? 数据的插入函数 Insert_node()当创建多项式时， 要用到此函数， 即利用插入的方式将多项式的数据连接起来。 再输入一组数据后，程序自动调用此函数，插入时也进行着排序，从表头的 next 开始， 一一比较指数大小， 直到大于或等于当前指向的数据或遍历完所

6、有 数据时停止，然后开始链表中数值的插入，如果相等则直接将指数相加，如果 大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。? 多项式的运算函数：新建链表存储计算后的多项式? 多项式相加 Addresult()创建两个指针分别指向两个多项式表头的 next ，分别使用两个 while 函数独自 循环，遍历各自的每一组数据，每遍历一次都将系数与指数存储到新建多项式 的链表中。因为存储时利用到插入函数，而插入函数中有相同指数的系数相加 功能，所以直接将两个多项式的数据依次插入到新的多项式中即可完成多项式 相加。? 多项式相减 Subresult()创建两个指针分别指向两个多项式表头的 n

7、ext ，以两个指针同时不为空为条件 循环遍历，如果当前多项式 1 的指数小于多项式 2 ，则将当前多项式 2 的系数 置负，指数不变，存入新建多项式中，指向多项式 2 的指针指向下一个；如果如果当前多项式 1 的指数大于多项式 2，则将当前多项式 1 的系数指数不变， 存入新建多项式中， 指向多项式 1 的指针指向下一个； 否则将多项式 1 的系数 减去 2 的系数后存入新建多项式中， 指数不变存入， 再将两个指针同时指向下 一个。结束循环后判断是哪一个多项式遍历完了，将未遍历完的多项式剩下的 数据全部插入到新建多项式中。? 选择运算方式的函数 select()两种选择： 1 为相加， 2

8、为相减；每一种选择调用相应的运算函数。? 多项式的显示函数 Show()从多项式表头的 next 开始，直到指向空( NULL )，将系数与指数一一显示。? 主函数 main() 创建两个多项式的链表并且初始化，分别调用相应的多项式创建函数，创建成 功后选择运算方式，再将运算结果输出显示。源程序#include#includetypedef struct nodeint xs;int zs;struct node * next;Dnode,* Dnodelist;/* 定义结构体 */Dnodelist Creat_node(void)/* 链表初始化 */Dnodelist D;D=(Dno

9、delist)malloc(sizeof(Dnode);if(D)D-next=NULL;return D;int Insert_node(Dnodelist D,int xs,int zs)/* 插入函数 */Dnodelist p;Dnodelist q;Dnodelist r;p=D;while(p-next)r=p;p=p-next;if(zs=p-zs) /* 指数相等，系数直接相加，结束 */ p-xs=p-xs+xs; return 1;else if(zsp-zs)/* 指数大于当前数据的， 将数据插入当前数据之前， 结束 */q=Creat_node(); q-xs=xs;

10、q-zs=zs; r-next=q; q-next=p;return 1;/*while(p-next)*/* 要插入的数据指数最小， 直接插入至链表最后 */* 创建多项式 */q=Creat_node();q-xs=xs;q-zs=zs; q-next=p-next; p-next=q;return 1;free(p);free(q);free(r);Dnodelist Creat_Dmeth(int length)int i,m,n;Dnodelist D;D=Creat_node();for(i=0;inext;q=D2-next;while(q)x=q-xs;z=q-zs;Inser

11、t_node(D,x,z);q=q-next;while(p)x=p-xs;z=p-zs;利用插入函数可完成该功能Insert_node(D,x,z);p=p-next; /* 直接插入数据，*/ return D;Dnodelist Subresult(Dnodelist D1,Dnodelist D2)Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1-next;q=D2-next;while(p&q)if(p-zs)zs)*/x=-(q-xs);z=q-zs;Insert_node(D,x,z); q=q-next;else if(

12、p-zs)(q-zs)*/x=p-xs;z=p-zs;Insert_node(D,x,z); p=p-next;elsez=q-zs;x=(p-xs)-(q-xs);Insert_node(D,x,z); p=p-next; q=q-next;/* 多项式相减 */* 指数小（ 1 的数据在 2 中不存在）/* 由于是式 1 减式 2，所以系数置负/* 指数大（ 2 的数据在 1 中不存在）/* 指数相同的先将系数相减，再插入直接插入*/直接插入*/*while(p&q)*/while(p)x=p-xs; z=p-zs; Insert_node(D,x,z); p=p-next; while(

13、q) x=-(q-zs); z=q-zs;Insert_node(D,x,z); q=q-next;return D;Dnodelist select(Dnodelist D1,Dnodelist D2)Dnodelist D;int s;printf(n* 请选择 :n1: 相加 n2: 相减 n); printf(n 你的选择是： %d:n ， &s); scanf(%d,&s);switch(s)case 1: D=Addresult(D1,D2);printf( 相加结果 (系数,指数 ):n); break;case 2: D=Subresult(D1,D2);printf( 相减结

14、果 (系数 ,指数 ):n); break;default:printf( 无此选项 n); break;return D;void Show(Dnodelist D)/* 将未遍历完的数据直接插入 */* 选择函数 */* 调用相加函数 */* 调用相减函数 */* 显示（输出）函数 */Dnodelist r;r=D-next; while(r) printf(n (%d,%d)+,r-xs,r-zs);r=r-next;printf(n);void main()Dnodelist D1,D2,D;int length;D1=Creat_node();D2=Creat_node(); /*

15、D1 为多项式 1 ，D2 为多项式 2，初始化 */printf( 格式说明： n* 先输入系数，再输入指数。 n* 系数与指数之间使用英文逗号隔开 n* 同一多项式中，子项之间使用空格隔开 n* 按下回车键进入下一步 n ” );printf(n 输入多项式 1 的组数： n ”);scanf( “ %d ”,&length);printf(n 输入多项式1系数,指数：(d组)n,length);D1=Creat_Dmeth(length);/* 创建多项式 1*/printf(n 输入多项式 2 的组数： n ”);scanf( “%d ”,&length);printf(n 输入多项式

16、2系数,指数：(d组)n,length);D2=Creat_Dmeth(length);/* 创建多项式 2*/D=select(D1,D2);/* 选择运算方式 */Show(D);/* 输出显示 */printf(n* 按任意键退出程序 *n);测试数据与结果格式说明：* 先输入系数，再输入指数。* 系数与指数之间使用英文逗号隔开* 同一多项式中，子项之间使用空格隔开* 按下回车键进入下一步输入多项式 1 的组数：2输入多项式 1 系数 ,指数：1,2 2,3输入多项式 2 的组数：3输入多项式 2 系数 ,指数：1,3 3,2 3,1请选择 :1:相加2:相减你的选择是： 1相加结果(系数，指数) ：(3,3)+(4,2)+(3,1)+* 按任意键退出程序 *Press any key to contince4 、 个性功能介绍相比最初的程序设计，有以下特色增加了程序运行的格式说明； 在源程序中增加了必要的中文注释； 增加了退出程序时的中文提示； 增加了选择相加 / 相减函数时，输入错误的提示； 增加了选择相加 / 相减函数时，选择结果的返回； 增加了换行字符，使运行界面更宽敞、舒适； 增加了多项式组数的自定义功能以及当前输入的