duoxiangshiqiuhe.cpp

线性表示最常用且最简单的一种数据结构。线性表除了常见的插入、删除、求长度等操作外

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef int datatype;
typedef struct  LNode
{
   float coef;   /*多项式系数*/
   int expn;     /*多项式指数*/
   struct LNode *next;
}LNode,*linklist;
/*---------创建带头结点的多项式链表--------*/
linklist creat()
{ linklist head,s,p,pre;
  float coef;
  int expn;
  head=(linklist)malloc(sizeof(LNode));   /*表头结点*/
  head->next=NULL;
  printf("输入系数：");
  scanf("%f",&coef);
  printf("输入指数：");
  scanf("%d",&expn);
  while (coef!=0.0)
  {  printf("当系数等于零的时候结束！");
     s=(linklist)malloc(sizeof(LNode));    /*生成新结点*/
     s->coef=coef;
     s->expn=expn;
     s->next=NULL;
     pre=head;                 /*插入到有序的多项式链表中去*/
     p=head->next;
while (p && p->expn <s->expn)
{ pre=p;
  p=p->next;
}
  s->next=p;
  pre->next=s;
  printf("读下一项：\n");
  printf("输入系数：\n");
  scanf("%f",&coef);
  printf("\n");
  printf("输入指数:");
  scanf("%d",&expn);
 }
return head;
}

/*-----------输出多项式链表-------------*/
void print(linklist head)
{ linklist p;
  p=head->next;
 while (p)
 {
  printf("%fX^%d+",p->coef,p->expn);
  p=p->next;
}
}

/*-------------多项式相加----------------*/
linklist add(linklist pa,linklist pb)
{
 linklist p,q,pre,r,head;
 float x;
 head=pa;
 p=pa->next;    //p,q 指向头接点的下一个接点，即多项式的第一个接点
 q=pb->next;
 pre=pa;       //pre指向p的前驱
 while((p!=NULL)&&(q!=NULL))  //处理多项式的相加的问题
 if(p->expn<q->expn)
 {
  pre=p;
  p=p->next;
 }
 else if (p->expn==q->expn)
 {
  x=p->coef+q->coef;
  if(x!=0)  //系数相加不为0的情况
  {
    p->coef=x;
    pre=p;
    p=p->next;
   }
else   //系数相加为0的情况
{
pre->next=p->next;
free(p);
p=pre->next;
}
r=q;
q=q->next;
free(r);
}

else
{
    r=q->next;
    q->next=p;
    pre->next=q;
    pre=q;
    q=r;
   }
    if(q!=NULL)
    pre->next=q;
    free(pb);
    return head;
}

/*----主程序------*/
void main()
{
   linklist a,b,c;
   printf("请输入第一个多项式：");
   a=creat();                      /*创建多项式链表a*/
   printf("请输入第二个多项式：");
   b=creat();                     /*创建多项式链表b*/
   cout<<"您输入的第一个多项式为："<<endl;
   print(a);
   cout<<"您输入的第二个多项式为："<<endl;
   print(b);
   cout<<endl;
   cout<<"两多项式相加后为："<<endl;
   c=add(a,b);                    /* 计算多项式a+b  */
   print(c);
}