数据结构课程设计报告一元多项式的实现

数据结构数据结构课程设计课程设计 题题 目目 一元多项式的实现一元多项式的实现 学 号 学生姓名 院 系 计算机 专 业 指导教师 二Ｏ一二二Ｏ一二 年年 1212 月月 1717 日日 一、 需求需求分析分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中， 能够完成两个多项式的加减运算并输出结果 二、二、 概要设计概要设计 存储结构存储结构 一元多项式的表示在计算机内可以用链表来表示， 为了节省存储空间， 只存储多项式中系数非零的项。 链表中的每一个结点存放多项式的一个系数非零 项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的 指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行 分析，实现一元多项式的相加、相减操作。 基本算法基本算法 1、输入输出 （1）功能将要进行运算的多项式输入输出。 （2）数据流入要输入的多项式的系数与指数。 （3）数据流出合并同类项后的多项式。 （4）程序流程图多项式输入流程图如图 1 所示。 （5）测试要点输入的多项式是否正确，若输入错误则重新输入 开始 申请结点空间 输入多项式的项数 输入多项式各项的系数 x, 指数 y 输出已输入的多项式 合并同类项 结束 否 是 是否输入正确 图表 1 2、多项式的加法 （1）功能将两多项式相加。 （2）数据流入输入函数。 （3）数据流出多项式相加后的结果。 （4）程序流程图多项式的加法流程图如图 2 所示。 （5）测试要点两多项式是否为空，为空则提示重新输入，否则，进行运算。 图表 2 开始 定义存储结果的空链 r r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 直接把 p 中 各项存入 r 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 3、多项式的减法 （1）功能将两多项式相减。 （2）数据流入调用输入函数。 （3）数据流出多项式相减后的结果。 （4）程序流程图多项式的减法流程图如图 3 所示。 （5）测试要点两多项式是否为空，为空则提示重新输入，否则，进行运算。 开始 定义存储结果的空链 r r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 把 p 中各项系数 改变符号后存入 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 图表 3 三、三、 详细设计详细设计 include include typedef struct Polynomial{ float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; //Polyn 为结点指针类型 void InsertPolyn p,Polyn h{ ifp-coef0 freep; //系数为 0 的话释放结点 else{ Polyn q1,q2; q1h;q2h-next; whileq2 q2q2-next; } ifq2 freep; ifq2-coef{ //系数为 0 的话释放结点 q1-nextq2-next; freeq2; } } else{ //指数为新时将结点插入 p-nextq2; q1-nextp; } } }//Insert Polyn CreatePolynPolyn head,int m{//建立一个头指针为 head、项数为 m 的一元 多项式 int i; Polyn p; pheadPolynmallocsizeofstruct Polynomial; head-nextNULL; fori0;icoef, Insertp,head; //调用 Insert 函数插入结点 } return head; }//CreatePolyn void DestroyPolynPolyn p{//销毁多项式 p Polyn q1,q2; q1p-next; q2q1-next; whileq1-next{ freeq1; q1q2;//指针后移 q2q2-next; } } void PrintPolynPolyn P{ Polyn qP-next; int flag1;//项数计数器 ifq { //若多项式为空，输