数据结构(C语言)一元稀疏多项式计算器

1、实验报告一题目：编制一个一元稀疏多项式计算器班级：1302018 姓名：王雪 学号完成日期：2014.4.5一、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.3多项式a和b相加，建立多项式a+b；1.4 多项式a和b相减，建立多项式a-b。2、设计思路:2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。每次输入一项

2、的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1xe1+c2xe2+cnxen3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为序数coef指数expn指针域next运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于

3、单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则： 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。 若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

4、二、概要设计为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。2.1单链表的抽象数据类型定义ADT LinkList数据对象：D=ai|aiTermSet,i=1,2,m,m0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=<ai-1,ai>ai-1,aiD且ai-1中的指数值<ai中的指数值,i=2,n基本操作： CreatLinkList(&p,m)操作结果：输入m项的系数和指数，建立一元多项式p。DestoryLinkList(&p)初始条件：一元多项式p已存在。操作结果：销毁一元

5、多项式p. PrintLinkList(p)初始条件：一元多项式p已存在。操作结果：打印输出一元多项式p. AddLinkList（&pa,&pb）初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的相加运算，即：pa=pa+pb,并销毁一元多项式pb. SubtractLinkList(&pa,&pb)初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的想减运算，即：pa=pa-pb,并销毁一元多项式pb.ADT LinkList2.2本程序包括个模块：1）主程序模块：Void main（） 初始化； 输出菜单； While（1） 接受命令；

6、处理命令；（循环一直为真直至接受退出命令）；2）单链表单元模块实现单链表的抽象数据类型；3）结点结构单元模块定义单链表的结点结构。三、详细设计3.1元素类型、结点类型和指针类型typedef int Status; typedef int ElemType;typedef struct LNode    float     coef;                  

7、;    /系数    ElemType  expn;                   /指数    struct    LNode *next;            LNode,*LinkList;Status MakeN

8、ode(LinkList &p,LinkList head) /分配由p指向下一个多项式的头结点head、后继为空的结点，并返回TRUE， /若分配失败，则返回FALSE p= (LinkList)malloc(sizeof(struct LNode);if(!p)return false;p=head;p->next=null;return ture;void FreeNode(LinkList &p) /释放p所指结点free(q1);        q1=q2;    

9、;    q2=q2->next;3.2单链表的基本操作设置如下：void Insert(LinkList p,LinkList h)； /将节点p插入到多项式链表hLinkList CreateLinkList(LinkList head,int m);/建立一个头指针为head、项数为m的一元多项式,并返回该多项式的头结点；/若分配空间失败，则返回FALSEvoid DestroyLinkList(LinkList p); /销毁多项式pvoid PrintLinkList(LinkList P);/输出构造的一元多项式PStatus compare(L

10、inkList a,LinkList b) /节点进行比较: a的指数 >b的指数   return 1; a的指数=b的指数   return 0;a的指数<b的指数    return -1.LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多项式a+b，返回其头指针LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多项式a-b，返回其头指针其中部分操作的伪码如下：LinkList CreateLinkList(LinkLis

11、t head,int m)   p=head=(LinkList)malloc(sizeof(struct LNode);    head->next=NULL;    for(i=0;i<m;i+)         p=(LinkList)malloc(sizeof(struct LNode);   /建立新结点以接收数据        printf("请输入第%d项的系数与指数:&

12、quot;,i+1);        scanf("%f %d",&p->coef,&p->expn);        Insert(p,head);                       

13、60;     /调用Insert函数插入结点     return head;/ CreateLinkListStatus compare(LinkList a,LinkList b)    if(a&&b)        if(!b|a->expn>b->expn) return 1;        else if(!a|a->expn<b->

14、;expn) return -1;        else return 0;    else if(!a&&b) return -1;/a多项式已空，但b多项式非空    else return 1;/b多项式已空，但a多项式非空/ comparefloat ValueLinkList(LinkList head,int x)  /输入x值，计算并返回多项式的值       for(p=head->next;p;p=p-&

15、gt;next)        t=1; for(i=p->expn;i!=0;)       / i 为指数的系数 pow(x,i)  if(i<0)t/=x;i+;       /指数小于0，进行除法            elset*=x;i-;   /指数大于0，进行乘法 

16、60;      sum+=p->coef*t;  return sum;/ ValueLinkListLinkList MultiplyLinkList(LinkList pa,LinkList pb)/求解并建立多项式a*b，返回其头指针     LinkList qa=pa->next;    LinkList qb=pb->next;    hf=(LinkList)malloc(sizeof(struct LNode);/建立头结点  &

17、#160; hf->next=NULL;    for(;qa;qa=qa->next)  for(qb=pb->next;qb;qb=qb->next)  pf=(LinkList)malloc(sizeof(struct LNode);            pf->coef=qa->coef*qb->coef;        &#

18、160;   pf->expn=qa->expn+qb->expn;            Insert(pf,hf); /调用Insert函数以合并指数相同的项  return hf;/ MultiplyLinkList3.3主函数和其他函数的伪码算法void main()/主函数Initiation();  /多项式初始化     PrintCommand();/输出菜单   

19、60; while(1)   /循环一直为真 知道选择j|J即退出命令时，程序退出        printf("n请选择操作：");        scanf("%c",&flag);        Interpter(flag);  /具体的操作命令   /mainvoid Initiation() 

20、60;   printf("请输入a的项数:");    scanf("%d",&m);    pa=CreateLinkList(pa,m);/建立多项式a    printf("请输入b的项数:");    scanf("%d",&n);    pb=CreateLinkList(pb,n);/建立多项式b printf("多项式已创建n");/ Initi

21、ationvoid PrintCommand()  /输出菜单显示键入命令的提示信息；Printf（A,B,C,D,E）;/ PrintCommand void Interpter(char flag)   /具体的操作命令  switch(flag)  case 'A': case 'a': PrintLinkList(pa); break;case 'B':case 'b': PrintLinkList(pb); break;case'C': case'

22、c':   AddLinkList(pa,pb); PrintLinkList(pc); break;case'D': case'd': SubtractLinkList(pa,pb);PrintLinkList(pc); break;case'E': case'e': DestroyLinkList(pa); DestroyLinkList(pb);exit(0) ; default:printf("n       您的选择错误，请重新选择!

23、n"); / Interpter函数说明：Initiation(); /多项式初始化PrintCommand(); /输出菜单Interpter() ; /具体的操作命令PrintLinkList() ; /打印多项式(降序输出)AddLinkList() ; /两个多项式相加SubtractLinkList(); /两个多项式相减DestroyLinkList(); /销毁多项式compare() ; /两个节点比较CreateLinkList(); /创建多项式Insert() ; /将节点插入已知多项式中四、源程序#include<stdio.h>#include&

24、lt;malloc.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; typedef int ElemType;typedef struct LNode float coef; /系数 ElemType expn; /指数 struct LNode *next; LNode,*LinkList;/*全局节点 初始化多项式节点为空*/static LinkLi

25、st pa=NULL;static LinkList pb=NULL;static LinkList pc=NULL;/*将节点p插入到多项式链表h*/void Insert(LinkList p,LinkList h) if(p->coef=0) free(p); /系数为0的话释放结点 else LinkList q1,q2; q1=h; q2=h->next; while(q2&&p->expn<q2->expn) /查找插入位置 q1=q2; q2=q2->next; if(q2&&p->expn=q2->

26、expn)/将指数相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef)/系数为0的话释放结点 q1->next=q2->next; free(q2); else /指数为新时将结点插入 p->next=q2; q1->next=p; /创建一元多项式 LinkList CreateLinkList(LinkList head,int m) /建立一个头指针为head、项数为m的一元多项式 int i; LinkList p; p=head=(LinkList)malloc(sizeof(struct LNode

27、); head->next=NULL; for(i=0;i<m;i+) p=(LinkList)malloc(sizeof(struct LNode); /建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /调用Insert函数插入结点 return head;void DestroyLinkList(LinkList p) /销毁多项式p LinkList q1,q2; q1=p-&

28、gt;next; q2=q1->next; while(q1->next) free(q1); q1=q2; q2=q2->next; /输出构造的一元多项式Pvoid PrintLinkList(LinkList P) LinkList q=P->next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar('0'); printf("n"); return; while(q) if(q->coef>0&&flag!=1) putchar('+');

29、 /系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1) /系数非1或-1的普通情况 printf("%g",q->coef); if(q->expn=1) putchar('X'); else if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'

30、;); else printf("X%d",q->expn); if(q->coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; printf("n");/ 节点进行比较/ a的指数 >b的指数 return 1/ a的指数=b的指数 return 0/ a的指数<b的指数

31、 return -1Status compare(LinkList a,LinkList b) if(a&&b) if(!b|a->expn>b->expn) return 1; else if(!a|a->expn<b->expn) return -1; else return 0; else if(!a&&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多

32、项式a+b，返回其头指针 LinkList qa=pa->next; LinkList qb=pb->next; LinkList headc,hc,qc; hc=(LinkList)malloc(sizeof(struct LNode);/建立头结点 hc->next=NULL; headc=hc; while(qa|qb) qc=(LinkList)malloc(sizeof(struct LNode); switch(compare(qa,qb) case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=q

33、a->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; if(qc->coef!=0) qc->next=hc->next; hc->next=qc; hc=qc; else free(qc);/当相加系数为0时

34、，释放该结点 return headc;LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多项式a-b，返回其头指针 LinkList h=pb; LinkList p=pb->next; LinkList pd; while(p) /将pb的系数取反 p->coef*=-1; p=p->next; pd=AddLinkList(pa,h); for(p=h->next;p;p=p->next) /恢复pb的系数 p->coef*=-1; return pd;/多项式初始化void Initiation() int m, n ; printf("请输入a的项数:"); scanf("%d",&m); pa=CreateL