数据结构课程设计--- 一元稀疏多项式简单计数器.doc

课程设计说明书 NO.1 一元稀疏多项式简单计数器 1.课程设计的目的 (1)通过对数据结构所学知识的综合运用，融会贯通课程中所学的理论知识，初步；（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3) 图1 2.2.3模块划分 (1) 带头结点的多项式的建立函数Polylist Polycreate() (2) 带头结点的多项式的降幂输出函数void printf(Polylist poly) (3) 带头结点的多项式的相加函数Polylist Polyadd(Polylist a,Polylist b) (4) 带头结点的多项式的相减函数Polylist Polysub(Polylist a,Polylist b) (5) 主函数void main() 沈 阳 大 学 课程设计说明书 NO.4 2.2.4抽象数据类型 带头结点单链表抽象数据类型的结点结构定义如下： typedef struct Polynode //多项式结点 { int coef; //系数 int exp; //指数 Polynode *next; }Polynode ,*Polylist;void DestroyPoly(Poly p){//销毁多项式p Poly q1,q2; q1=p-next; q2=q1-next; while(q1-next){ free(q1); q1=q2;//指针后移 q2=q2-next; } } void main() { int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; } 沈 阳 大 学 课程设计说明书 NO.5 2.2.5算法的分析 建立多项式的时间复杂度为O(n),降幂输出多项式序列算法，由于是对指数做的循环，每次循环都需要从首元结点查找到表尾，假设多项式开始为升幂排列，如x1+x2+x3+x4+……xn,（这里n=20）其时间复杂度为n(n+1)/2,若指数不是连续的，则其时间复杂度加上O(n),所以此算法的时间复杂度为O（n2）。假设a有M项，b有N项，则加法和减法算法的时间复杂度度为M+N，算法中两多项式相加和相减时，a,b均需按升幂顺序输入结点。 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为 序数coef 指数exp指针域next 运用尾插法建立两条单链表，以单链表和poly分别表示两个一元多项式和，的求和运算等同于单链表的插入问题（将单链表poly中的结点插入到单链表poly中），因此“和多项式”中的结点无须另生成。 为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则： ① 若p-expq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 ② 若p-exp=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。 ③ 若p-expq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。(2x+5x8-3.1x11)+(7-5x8+11x9) 分别输入a,b的项数是3，并且输入各项对应的系数与指数。例如输入a的第1项的系数与指数是2和1，输入a的第2项的系数与指数是5和8，输入a的第3项的系数与指数是-3.1和11。输入b的第1项的系数与指数是7和0，输入的第2项的系数与指数是-5和8，输入的第3项的系数与指数是11和9。输入执行相应的操作1和2。 程序运行结果为： 图2 （2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x