多项式的输入输出设计报告(内附详细注释)

江西理工大学

数据结构课程设计报告

选 题 ：一元多项式的计算 班 级：

学 号： 姓 名： 时 间： 指导教师：

2012年01月

一、 需求分析

建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果

二、 概要设计

存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。

基本算法： 1、输入输出

（1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。

（4）程序流程图：多项式输入流程图如图1所示。

（5）测试要点：输入的多项式是否正确，若输入错误则重新输入

图表 1

开始

申请结点空间 输入多项式的项数 输入多项式各项的系数 x, 指数 y 输出已输入的多项式 否 是 是否输入正确 合并同类项 结束

2、多项式的加法

（1）功能：将两多项式相加。 （2）数据流入：输入函数。

（3）数据流出：多项式相加后的结果。

（4）程序流程图：多项式的加法流程图如图2所示。

（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。

图表 2 开始 定义存储结果的空链 r 存储多项式1的空 链P是否为空 否 存储多项式2的空 链Q是否为空 否 同指数项系数相加后存入r 输出存储多项式的和的链r 合并同类项

结束 是 是 直接把q中各项存入r 直接把p中各项存入r 3、多项式的减法

（1）功能：将两多项式相减。 （2）数据流入：调用输入函数。

（3）数据流出：多项式相减后的结果。

（4）程序流程图：多项式的减法流程图如图3所示。

（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 合并同类项 输出存储多项式的和的链r 否 同指数项系数相加后存入r直接把q中各项存入r 把p中各项系数改变符号后存入存储多项式2的空链Q是否为空 存储多项式1的空链P是否为空 否 是 是 定义存储结果的空链 r 开始 图表 3

结束

三、 详细设计

#include

#include //动态内存分配

typedef struct Polynomial{ // C中用于定义结构体类型 多项式 float coef; //系数 int expn; //指数

struct Polynomial *next; //指针域 }*Polyn,Polynomial;//Polyn为结点指针类型

void Insert(Polyn p,Polyn head){

if(p->coef==0) free(p); //系数为0的话释放结点 else{ // head指针作为头指针 Polyn q1,q2; //p首先指向头结点

q1=head;q2=head->next; //第一次q2的值为null while(q2&&p->expnexpn){ // 查找插入位置 比较

q1=q2; //较大的q2的值 赋给前一个位置的q1 q2=q2->next; //q2指针 后移 }

if(q2&&p->expn==q2->expn){ //将指数相同相合并 q2->coef+=p->coef; free(p);

if(!q2->coef){ //系数为0的话释放结点

q1->next=q2->next; //q1下一个位置就是q2 而q2及q2的下一个位置

指向零

free(q2); } }

else{ // p指向的指数大于q2时

p->next=q2; //把q2的值也就是开始null的那个赋给p的下一个节点 q1->next=p; //把p指针指向的值赋给q2 } } }//Insert

Polyn CreatePolyn(Polyn head,int m){//建立一个头指针为head、项数为m的

一元多项式

int i; Polyn p;

p=head=(Polyn)malloc(sizeof(struct Polynomial));//给头结点申请存储空间

并强制转换

head->next=NULL; //将头节点的下一个位置置空 for(i=0;ip=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(\"请输入第%d项的系数与指数:\首先输入第一项的 scanf(\"%f %d\当节点只有头结点和第一个节点

时p指向第一个节点

Insert(p,head); // 每次循环到此都要调用Insert函数插入结点 }

return head; // 返回头指针 判断是那个多项式 }//CreatePolyn

void DestroyPolyn(Polyn p){ //销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next;

while(q1->next){ //q2指针指向空时不执行操作 free(q1); //释放q1指向的存储空间

q1=q2; //指针后移 q2=q2->next; //位置不释放 } }

void PrintPolyn(Polyn P){ // 打印多项式 Polyn q=P->next; //第一个节点的值赋给q int flag=1; //项数计数器 if(!q) { //若多项式为空，输出0 putchar('0'); printf(\"\\n\"); return; } while (q){

if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况 printf(\"%g\的作用 if(q->expn==1) putchar('X'); //指数为1时输出 X else if(q->expn) printf(\"X^%d\ }

else{ //1与-1的情况 if(q->coef==1){

if(!q->expn) putchar('1'); //指数为零时输出1 else if(q->expn==1) putchar('X'); else printf(\"X^%d\ }

if(q->coef==-1){

if(!q->expn) printf(\"-1\");

else if(q->expn==1) printf(\"-X\"); //指数为1时

else printf(\"-X^%d\ } }

q=q->next; //控制输出项的指针后移 flag++; //计数加一 }//while

printf(\"\\n\");//循环结束换行 }//PrintPolyn

int compare(Polyn a,Polyn b){ //用于两个多项式项加减是时的比较 if(a&&b){

if(!b||a->expn>b->expn) return 1; //B空或者A比B的指数大 else if(!a||a->expnexpn) return -1; else return 0; //AB的指数相同时 }

else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 }//compare

Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针

Polyn qa=pa->next; //pa的第一个位置 Polyn qb=pb->next; //pb的第一个位置 Polyn headc,hc,qc;

hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL;

headc=hc; //hc指针的作用 相当于p指针 while(qa||qb){

qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,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 if(qc->coef!=0){

qc->next=hc->next; //hc之后插入qc所指的节点 hc->next=qc; hc=qc; }

else free(qc);//当相加系数为0时，释放该结点 }//while return headc;

指针

NULL

}//AddPolyn

Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头

Polyn h=pb; Polyn p=pb->next; Polyn pd;

while(p){ //pb的系数取反 p->coef*=-1; p=p->next; }

pd=AddPolyn(pa,h);

for(p=h->next;p;p=p->next) //恢复pb的系数

p->coef*=-1; // 符合循环前两个条件则又将pb取反 return pd; //p指针后移 }//SubtractPolyn

int main(){ int m,n,flag=0; float x;

Polyn pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值

printf(\"请输入a的项数:\"); //pc pd 为两多项式的相加减得到的多项式 scanf(\"%d\

pa=CreatePolyn(pa,m);//建立项数为m多项式a printf(\"请输入b的项数:\"); scanf(\"%d\

pb=CreatePolyn(pb,n);//建立项数为n多项式a //输出菜单

printf(\"**********************************************\\n\");

printf(\"操作提示：\\n\1.输出多项式a和b\\n\2.建立多项式a+b\\n\3.建立多

项式a-b\\n\");

printf(\"\4.退出\\n**********************************************\\n\"); for(;;flag=0){ //先赋值为零 printf(\"执行操作：\"); scanf(\"%d\ if(flag==1){

printf(\"多项式a：\");PrintPolyn(pa);

printf(\"多项式b：\");PrintPolyn(pb);continue; }

if(flag==2){ pc=AddPolyn(pa,pb);

printf(\"多项式a+b：\");PrintPolyn(pc); DestroyPolyn(pc);continue; }

if(flag==3){

pd=SubtractPolyn(pa,pb);

printf(\"多项式a-b：\");PrintPolyn(pd); DestroyPolyn(pd);continue; }

if(flag==4) break;

if(flag<1||flag>4) printf(\"Error!!!\\n\");continue; }//for

DestroyPolyn(pa); DestroyPolyn(pb); return 0; }

4.调试结果

1.

测试的数据及结果

2. 算法的时间复杂度及改进

算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。

问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。