一元多项式计算.doc

xx学院 《数据结构与算法》课程设计 报 告 书 课程设计题目 一元多项式计算 院系名称计算机科学与技术系 专 业 （班 级） 姓 名 （学 号） 指 导 教 师 完 成 时 间  一．问题分析和任务定义 1．问题分析 设计要求是对于从键盘输入的任意两个一元多项式概要设计和数据结构的选择{ int coef; //系数coefficient int power; //幂 node *next;//指向结点的指针，连接后项构成多项式链表 }node; 具体流程是：首先调用建表函数create()依次建立两个单链表，分别表示待处理的两个一元多项式，然后对两个多项式按指数大小进行降幂排列，由sort()函数实现，接下来便是调用计算函数calculate()将二者进行计算，这是整个算法的核心，最后通过输出函数output()输出，据此思想算法，程序流程图如下： 图 1. 建表 三．详细设计和编码 在本次设计的程序中，共使用了四个子函数，其详细设计和编码如下： １．当用户从键盘输入系数和幂以后，建立链表，存储该一元多项式。 node *create() //根据用户输入的数据建立一个多项式链表 { int co,po,i=1; node *head,*s,*pre; //head是头结点指针,s为在建结点指针,pre是在建结点的前一结点的指针 printf(请输入一元多项式,以(0，n)的形式结束本次输入(n为任意非零整数):\n); head=(node*)malloc(size); //申请头结点空间 head-next=NULL; //将head的next域置为空 pre=head; do //运用do-while循环建立一元多项式链表 { printf(第%d次-系数,幂:,i++); scanf(%d,%d,co,po); if(co==0po==0) //判断是结束标志时， exit(0); //则跳出 if (co!=0) //输入的系数值非空，用于判断该结点是否建立 { s=(node*)malloc(size); //建立一个新结点，表示多项式的一项 s-coef=co; //分别将系数、 s-power=po;//指数赋值 s-next=NULL;//将s的next域置为空 pre-next=s;//前项与后项链接 pre=s;//pre前项指针后移至s上，以便下一项的建立 } } while (co!=0); //当系数不为零时，继续循环 printf(\n); return(head); //返回头结点指针，即表头，标识整个多项式 } 2．由于多项式系数和幂是随机输入的，根据要求，需要对其按指数进行降幂排列，在这个程序模块中，使用链表，根据指数大小的比较，对各种情况进行处理。此处由于反复使用指针对各个结点先定位，找到合适位置，再进行链接插入，实现时很不容易，投入了很多的时间和精力。 void sort(item * T) //对任意输入的一元多项式进行降幂排列 { item *p=T-next; //p指向待处理的第一个结点，初始指向原表头结点 T-next=NULL; //T仍为待建立的有序表的表头指针，初始值为空 while(p!=NULL) { //把原单链表中的结点依次进行有序链接 item *q=p; //q指向待处理的结点 p=p-next; //p指向下一个待处理的结点 item *ap=NULL,*cp=T-next; //cp指向有序表中待比较的结点，ap指向其前驱结点 while(cp!=NULL) { //为插入q结点寻找插入位置 if(q-powercp-power) break; else { ap=cp; cp=cp-next; } } //将q结点插入到ap和cp结点之间 q-next=cp; } 3．在该程序中，最关键的一步是实现两个一元多项式的加减运算并输出。由于加减算法原理是一样的，减法可通过系数为负的加法实现，故只按运算规则编写加法函数，便可实现计算。若读者需要进行减法运算，只需将被减多项式的系数全部取反输入通过加法即可实