assignment_1.txt

用Ｃ＋＋写的两个多项式相加

//程序描述 : 
/*由创建链表Creat,合并多项式AddPolyn,和打印3个大模块组成*/

//程序题目描述 : 一元多项式相加


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define NULL 0

typedef struct NODE {
 float  coef;                  //系数
 int    expn;                  //指数
 struct NODE *next;  
}NODE;


NODE *Creat(int n);
void print(NODE *head);
NODE *AddPolyn(NODE *head1, NODE *head2);
NODE *Delfirst(NODE *head, NODE *q);
void InsertBefore(NODE *p1, NODE *p2);
int  compare(int a, int b);


main()
{
 NODE *head1, *head2, *head3;
 int n1, n2;

 printf("请输入你需要的多项数的数目 n1  : ");
  scanf("%d", &n1);
 head1 = Creat(n1);
 printf("第一个多项式的显示 : \n");
 print(head1);
    

 printf("\n请输入你需要的多项数的数目 n2  : ");
  scanf("%d", &n2);
 head2 = Creat(n2);
 printf("\n第二个多项式的显示 : \n");
 print(head2);


 head3 = AddPolyn(head1, head2);
 printf("\n合并后的多项式的显示 : \n");
 print(head3);
 printf("\n");
}


/*创建链表*/

NODE *Creat(int n)
{
 NODE *current, *previous, *head;
 int i;

 head = (NODE *)malloc(sizeof(NODE)); /*创建头结点*/
 previous = head;
 

 for(i = 0; i < n; i++)
 {
  current = (NODE *)malloc(sizeof(NODE));
  
  printf("请输入系数和指数 : ");
  scanf("%f%d", &current->coef, &current->expn);
  previous->next = current;
  previous = current; 
 }
 previous->next = NULL;
 return head;
}


/*一元多项式的想加，总体考虑，可分qa的指数比qb小，或等于pb(如果系数相加等于0和不等于0),或大于pb
里面由InsertBefore和Delfirst两个小模块组成一部分*/
NODE  *AddPolyn(NODE *head1, NODE *head2)
{
 NODE *ha, *hb, *qa, *qb;
 int a, b;
 float sum;

 ha = head1;                  /*ha和hb指向头结点*/
 hb = head2;
 qa = ha->next;             /*qa和qb指向头结点的下一个结点*/
 qb = hb->next;

 

 while(qa && qb)             /*qa和qb均非空*/
 {
  a = qa->expn; 
  b = qb->expn;

  switch(compare(a, b)) {
  case -1 :              /*qa->expn < qb->expn*/
   ha = qa;
   qa = qa->next;
   break;
     
  case 0 :
   sum = qa->coef + qb->coef;  /*系数的和*/

   if(sum != 0.0) {            /*如果不是0.0*/
    qa->coef = sum;         /*改变系数*/ 
    ha = qa;                                  
   }else {
    free(Delfirst(ha, qa));
   }                               
   free(Delfirst(hb, qb));
   qa = ha->next;              
   qb = hb->next;              /*qb释放后要重新赋值*/
   break;
  
  case 1 :                        /*如果qa-> expn > qb -> expn*/ 
   Delfirst(hb, qb);
   InsertBefore(ha, qb);       /*把qb插入到ha下一个结点之前*/
   qb = hb->next;
   ha = ha->next;
   break;
  }
 }
 if(qb)
  ha->next = qb;                  /*插入剩余的pb*/

 free(head2);

 return head1;
}
             

/*比较*/

int compare(int a, int b)
{
 if(a < b)
  return -1;
 else if(a > b)
  return 1;
 else
  return 0;
}


/*删除结点q*/

NODE *Delfirst(NODE *p1, NODE *q)
{
 p1 -> next = q -> next;
 return (q);
}
 

/*插入结点,引入结点p,可以让p插入到p2和p1之间*/

void InsertBefore(NODE *p1, NODE *p2)
{
 NODE *p;
 p = p1->next;
 p1->next = p2;
 p2->next = p;
}


/*打印,为了美观程序分开打印*/

void print(NODE *head)
{
 NODE *current;
 
 current = head->next;
 while(current->next != NULL)
 {
  printf("%0.f * x^%d + ", current->coef, current->expn);
  current = current -> next;
 }
 printf("%0.f * x^%d", current->coef, current->expn);
}