一元稀疏多项式简单计数器___实验报告

1、一元稀疏多项式简单计数器题目：编制一个演示一元稀疏多项式简单计数器的程序班级：计算机科学与技术1301班 姓名：刘濛 学号：201321091026 完成日期：2015.4.9一、需求分析1.1本演示程序中，多项式是以带头结点的单链表存储的，在单链表中有两个数据域，分别存储多项式的一个节点的系数，指数；还有一个指针域，存储指向下一个节点的指针。1.2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。1.3程序执行的命令包括：1）构造多项式a;2)构造多项式b；3）输出多项式，并且多项式的序

2、列按指数的降序排列；4）求a+b；5）求a-b；6）求a*b；7) 求多项式a的导函数a;8）求多项式在x处的值。1.4测试数据(1)（2x+5x8-3.1x11）+（7-5x8+11x9）=(-3.1x11+11x9+2x+7)(2)(6x(-3)-x+4.4x2-1.2x9)-(-6x(-3)+5.4x2-x2-x2+7.8x15)=(-7.8x15-1.2x9+12x(-3)-x)(3)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(4)(x+x3)+(-x-x3)=0(5)(x+x100)+(x100+x200)=(x+2x100+x200)(6)(x+x

3、2+x3)+0=x+x2+x3(7)互换上述测试数据中的前后两个多项式二、概要设计为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。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。DestoryLinkL

4、ist(&p)初始条件：一元多项式p已存在。操作结果：销毁一元多项式p. PrintLinkList(p)初始条件：一元多项式p已存在。操作结果：打印输出一元多项式p. AddLinkList（&pa,&pb）初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的相加运算，即：pa=pa+pb,并销毁一元多项式pb. SubtractLinkList(&pa,&pb)初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的想减运算，即：pa=pa-pb,并销毁一元多项式pb. MultiLinkList(&pa,&pb)初始条件

5、：一元多项式pa和pb已存在。操作结果：完成多项式相乘运算，即：pa=pa*pb,并销毁一元多项式pb.ADT LinkList2.2本程序包括个模块：1）主程序模块：Void main（） 初始化； 输出菜单； While（1） 接受命令； 处理命令；（循环一直为真直至接受退出命令）；2）单链表单元模块实现单链表的抽象数据类型；3）结点结构单元模块定义单链表的结点结构。各模块之间的调用关系如下：主程序模块 单链表单元模块 结点结构单元模块三、详细设计3.1元素类型、结点类型和指针类型typedef int Status; typedef int ElemType;typedef struct

6、 LNode    float     coef;                      /定义项的系数    ElemType  expn;              

7、60;    /定义项的指数    struct    LNode *next;              /指向下一个节点LNode,*LinkList;Status MakeNode(LinkList &p,LinkList head) /分配由p指向下一个多项式的头结点head、后继为空的结点，并返回TRUE， /若分配失败，则返回FALSE p= (LinkList)malloc(sizeof(str

8、uct LNode);if(!p)return false;p=head;p->next=null;return ture;void FreeNode(LinkList &p) /释放p所指结点free(q1);        q1=q2;        q2=q2->next;3.2单链表的基本操作设置如下：void Insert(LinkList p,LinkList h)； /将节点p插入到多项式链表hLinkList CreateLinkList(

9、LinkList head,int m);/建立一个头指针为head、项数为m的一元多项式,并返回该多项式的头结点；/若分配空间失败，则返回FALSEvoid DestroyLinkList(LinkList p); /销毁多项式pvoid PrintLinkList(LinkList P);/输出构造的一元多项式PStatus compare(LinkList a,LinkList b) /节点进行比较: a的指数 >b的指数   return 1; a的指数=b的指数   return 0;a的指数<b的指数    return

10、 -1.LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多项式a+b，返回其头指针LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多项式a-b，返回其头指针float ValueLinkList(LinkList head,int x) /输入x值，计算并返回多项式的值LinkList Derivative(LinkList head)/求解并建立导函数多项式，并返回其头指针LinkList MultiplyLinkList(LinkList pa,LinkList

11、pb) /求解并建立多项式a*b，返回其头指针其中部分操作的伪码如下：LinkList CreateLinkList(LinkList 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);   /建立新结点

12、以接收数据        printf("请输入第%d项的系数与指数:",i+1);        scanf("%f %d",&p->coef,&p->expn);        Insert(p,head);           

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

14、 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多项式非空/ comparefloat ValueLinkList(LinkList head,int x)  

15、;/输入x值，计算并返回多项式的值       for(p=head->next;p;p=p->next)        t=1; for(i=p->expn;i!=0;)       / i 为指数的系数 pow(x,i)  if(i<0)t/=x;i+;       /指数小于0，进行除法      

16、      elset*=x;i-;   /指数大于0，进行乘法        sum+=p->coef*t;  return sum;/ ValueLinkListLinkList MultiplyLinkList(LinkList pa,LinkList pb)/求解并建立多项式a*b，返回其头指针     LinkList qa=pa->next;    LinkList qb=pb->nex

17、t;    hf=(LinkList)malloc(sizeof(struct LNode);/建立头结点    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-

18、>coef*qb->coef;            pf->expn=qa->expn+qb->expn;            Insert(pf,hf); /调用Insert函数以合并指数相同的项  return hf;/ MultiplyLinkList3.3主函数和其他函数的伪码算法void main()/主函数Initiation();

19、  /多项式初始化     PrintCommand();/输出菜单      while(1)   /循环一直为真 知道选择j|J即退出命令时，程序退出        printf("n请选择操作：");        scanf("%c",&flag);        Interpter

20、(flag);  /具体的操作命令   /mainvoid Initiation()     printf("请输入a的项数:");    scanf("%d",&m);    pa=CreateLinkList(pa,m);/建立多项式a    printf("请输入b的项数:");    scanf("%d",&n);    p

21、b=CreateLinkList(pb,n);/建立多项式b printf("-多项式已创建-n");/ Initiationvoid PrintCommand()  /输出菜单显示键入命令的提示信息；Printf（A,B,C,D,E,F,G,H,I,J）;/ PrintCommand void Interpter(char flag)   /具体的操作命令  switch(flag)  case 'A': case 'a': PrintLinkList(pa); break;cas

22、e 'B':case 'b': PrintLinkList(pb); break;case'C': case'c':     pc=Derivative(pa); PrintLinkList(pc);break;case'D': case'd': Derivative(pb); PrintLinkList(pc); break;case'E': case'e': ValueLinkList(pa,x);break;case'F':&

23、#160;  case'f': ValueLinkList(pb,x);break;case'G': case'g': AddLinkList(pa,pb); PrintLinkList(pc); break;  case'H': case'h':  SubtractLinkList(pa,pb);PrintLinkList(pc); break; case'I':case'i':pc=MultiplyLinkList(pa,pb);); Pr

24、intLinkList(pc);break;  case'J':case'j': DestroyLinkList(pa); DestroyLinkList(pb);exit(0) ;    default:printf("n       您的选择错误，请重新选择!n"); / Interpter3.4函数的调用关系图反映了演示程序的层次结构:Main Initiation PrintCommand Interpter CreateLinkLis

25、t PrintLK Derivative ValueLK AddLK SubtractLK MultiplyLK DestroyLK PrintLK PrintLK PrintLK PrintLK exit(0)说明LK ：LinkList 即多项式节点函数说明：Initiation(); /多项式初始化PrintCommand(); /输出菜单Interpter() ; /具体的操作命令PrintLinkList() ; /打印多项式(降序输出)Derivative(); /多项式求导ValueLinkList(); /多项式求值AddLinkList() ; /两个多项式相加Subtrac

26、tLinkList(); /两个多项式相减MultiplyLinkList(); /两个多项式相乘DestroyLinkList(); /销毁多项式compare() ; /两个节点比较CreateLinkList(); /创建多项式Insert() ; /将节点插入已知多项式中四、调试分析4.1刚开始的时候由于对多项式的减法考虑不周全，代码很复杂，后来经过仔细思考，减法时把每项的系数变成它的相反数，然后调用加法的函数即可，但是实现了减法之后要把系数恢复，不然会影响后面的运算。4.2求多项式在x处的值的函数在刚开始的时候出现过警告，虽然警告不会影响程序的运行，但是运算的结果不精确。之前函数的类

27、型是int，但是里面的多项式的系数是浮点型的，而sum又是整型的，但是这样得不到小数点后面的数值，导致结果不精确。后来经改进，把函数的类型及sum的类型均改为float型。五、用户使用手册5.1此程序的整体架构：主函数里有三个函数，Initialization(初始化)、PrintCommand(打印命令)、Interpret(解释并执行命令)。在Interpret函数中调用了其他的函数，以达到执行命令的目的。5.2在输入命令时要注意在输入多项式的每一项的系数和指数必须有空格，否则可能会解释命令出错。在完成每一条的命令输入时要键入Enter.六、测试结果（程序输入的相关命令）七、附录（源代码）

28、：#include<stdio.h>#include<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 

29、60; float     coef;                      /定义项的系数    ElemType  expn;                  

30、 /定义项的指数    struct    LNode *next;              /指向下一个节点LNode,*LinkList;/*全局节点 初始化多项式节点为空*/static LinkList pa=NULL;static  LinkList pb=NULL;static  LinkList pc=NULL;/*将节点p插入到多项式链表h*/void Insert(LinkList p,LinkL

31、ist h)         if(p->coef=0) free(p);          /系数为0的话释放结点    else LinkList q1,q2;        q1=h;        q2=h->next;        while(q

32、2&&p->expn<q2->expn)                   /查找插入位置            q1=q2;            q2=q2->ne

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

34、#160;   if(!q2->coef)/系数为0的话释放结点                q1->next=q2->next;                free(q2);           

35、0; else                                  /指数为新时将结点插入            p->next=q2;&#

36、160;           q1->next=p;   /创建一元多项式 LinkList CreateLinkList(LinkList head,int m)         /建立一个头指针为head、项数为m的一元多项式    int i;    LinkList p;    p=head=(LinkList)malloc(sizeof(st

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

38、oef,&p->expn);        Insert(p,head);                     /调用Insert函数插入结点     return head;void DestroyLinkList(LinkList p) /销毁多项式p  &

39、#160; LinkList q1,q2;    q1=p->next;    q2=q1->next;    while(q1->next) free(q1);        q1=q2;        q2=q2->next; /输出构造的一元多项式Pvoid PrintLinkList(LinkList P) LinkList q=P->next; &

40、#160;   int flag=1;/项数计数器    if(!q)  /若多项式为空，输出0        putchar('0');         printf("n");        return;        while(q)     &

41、#160;   if(q->coef>0&&flag!=1) putchar('+'); /系数大于0且不是第一项        if(q->coef!=1&&q->coef!=-1)  /系数非1或-1的普通情况            printf("%g",q->coef);    &#

42、160;        if(q->expn=1) putchar('X');            else if(q->expn) printf("X%d",q->expn);          else          

43、;    if(q->coef=1)                   if(!q->expn) putchar('1');                 else if(q->expn=1) putchar('X'); &#

44、160;               else printf("X%d",q->expn);               if(q->coef=-1)               

45、;    if(!q->expn) printf("-1");                 else if(q->expn=1) printf("-X");                 else printf("-X%d"

46、;,q->expn);             q=q->next;         flag+;     printf("n");/ 节点进行比较/   a的指数 >b的指数   return 1/   a的指数=b的指数   return 0/   a的指数<b的指数    return -1Stat

47、us 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

48、;/a多项式已空，但b多项式非空    else return 1;/b多项式已空，但a多项式非空LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多项式a+b，返回其头指针    LinkList qa=pa->next;    LinkList qb=pb->next;    LinkList headc,hc,qc;    hc=(LinkList)malloc(sizeof(struct LNode);/建立头结点 

49、;   hc->next=NULL;    headc=hc;    while(qa|qb)        qc=(LinkList)malloc(sizeof(struct LNode);        switch(compare(qa,qb)        case 1:        

50、;         qc->coef=qa->coef;                qc->expn=qa->expn;                qa=qa->next;   &#

51、160;            break;           case 0:                 qc->coef=qa->coef+qb->coef;        

52、;        qc->expn=qa->expn;                qa=qa->next;                qb=qb->next;      

53、;          break;           case -1:                qc->coef=qb->coef;            &#

54、160;   qc->expn=qb->expn;                qb=qb->next;                break;             if(qc->coe

55、f!=0)  qc->next=hc->next;            hc->next=qc;            hc=qc;      else free(qc);/当相加系数为0时，释放该结点     return headc;LinkList SubtractLinkList(LinkList p

56、a,LinkList pb)/求解并建立多项式a-b，返回其头指针    LinkList h=pb;    LinkList p=pb->next;    LinkList pd;    while(p)            /将pb的系数取反        p->coef*=-1;     

57、   p=p->next;     pd=AddLinkList(pa,h);    for(p=h->next;p;p=p->next)    /恢复pb的系数        p->coef*=-1;    return pd;float ValueLinkList(LinkList head,int x) /输入x值，计算并返回多项式的值    LinkList p; 

58、   int i;    int t; float sum=0;    for(p=head->next;p;p=p->next)  t=1;        for(i=p->expn;i!=0;)       / i 为指数的系数 pow(x,i)              if(i<

59、;0)t/=x;i+;       /指数小于0，进行除法            elset*=x;i-;        /指数大于0，进行乘法          sum+=p->coef*t;     return sum;/求解并建立导函数多项式，并返回其头指针 对多项式进行求导

60、  y'=.LinkList Derivative(LinkList head) /求解并建立导函数多项式，并返回其头指针    LinkList q=head->next,p1,p2,hd;    hd=p1=(LinkList)malloc(sizeof(struct LNode);/建立头结点    hd->next=NULL;    while(q)        if(q->expn!=0) 

61、;              /该项不是常数项时            p2=(LinkList)malloc(sizeof(struct LNode);            p2->coef=q->coef*q->expn;   

62、;         p2->expn=q->expn-1;            p2->next=p1->next;/连接结点            p1->next=p2;           

63、p1=p2;          q=q->next;    return hd;LinkList MultiplyLinkList(LinkList pa,LinkList pb) /求解并建立多项式a*b，返回其头指针    LinkList hf,pf;    LinkList qa=pa->next;    LinkList qb=pb->next;    hf=(LinkList)

64、malloc(sizeof(struct LNode);/建立头结点    hf->next=NULL;    for(;qa;qa=qa->next)        for(qb=pb->next;qb;qb=qb->next)             pf=(LinkList)malloc(sizeof(struct LNode);   &

65、#160;        pf->coef=qa->coef*qb->coef;            pf->expn=qa->expn+qb->expn;            Insert(pf,hf);/调用Insert函数以合并指数相同的项      

66、return hf;/多项式初始化void Initiation()  int m, n ;    printf("请输入a的项数:");    scanf("%d",&m);    pa=CreateLinkList(pa,m);/建立多项式a    printf("请输入b的项数:");    scanf("%d",&n);    pb=CreateLinkList(

67、pb,n);/建立多项式b printf("-多项式已创建-n"); /输出菜单void PrintCommand() printf("*n"); printf("*n"); printf("   *               多项式操作程序      &#

68、160;             *n"); printf("   *                               

69、0;                     *n"); printf("   *       A:输出多项式a         B:输出多项式b        *n&q

70、uot;); printf("   *                                            &#

71、160;      *n"); printf("   *       C:输出a的导数        D:输出b的导数        *n"); printf("   *          

72、                                        *n"); printf("   *    E:代入x的值计算a

73、60;      :代入x的值计算b     *n"); printf("   *                                 &

74、#160;                *n")； printf("   *       G:输出a+b             H:输出a-b        

75、;    *n"); printf("   *                                         &

76、#160;        *n"); printf("   *       I:输出a*b             J:退出程序           *n"); printf("   *&#

77、160;                                               *n")； printf(&

78、quot;  *n"); printf("  *n");void Interpter(char flag)   /具体的操作命令 int x ; scanf("%c",&flag); switch(flag)   case 'A':   case 'a'： printf("n多项式a=");      

79、60;     PrintLinkList(pa);            break;          case 'B':      case 'b':printf("n       多项式b=");      &

80、#160; PrintLinkList(pb);        break;         case'C':     case'c': pc=Derivative(pa);        printf("n       多项式a的导函数为：a'=");  &

81、#160;     PrintLinkList(pc);        break;       case'D':   case'd':pc=Derivative(pb);        printf("n       多项式b的导函数为：b'=");      &