text1.cpp

两个多项式相加操作演示程序

//Release Date : Apr 1st 07
//Author : MeteorJ
//Code Compile : VC++ 6.0

//Program Describing : 

/*
Part 1:Create a Linklist Data Struct
Part 2:Add the Polynomial
Part 3:Print the Result
*/

//Add two Unitary Polynomials


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

typedef struct NODE {
 float  coef;                  //coefficient
 int    expn;                  //exponential
 struct NODE *next;  
}NODE;


NODE *Creat(int n);                                //Declaration of the Create Function
void print(NODE *head);                            //Declaration of the Print Function
NODE *AddPolyn(NODE *head1, NODE *head2);          //Declaration of the Add Function
NODE *Delfirst(NODE *head, NODE *q);
void InsertBefore(NODE *p1, NODE *p2);
int  compare(int a, int b);


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

 printf("Input the Item Number of the Polynmial A: ");
  scanf("%d", &n1);
 head1 = Creat(n1);
 printf("\nDisplay the Polynmial A: \n");
 print(head1);
    

 printf("\nInput the Item Number of the Polynmial B: ");
  scanf("%d", &n2);
 head2 = Creat(n2);
 printf("\nDisplay the Polynmial B:\n");
 print(head2);


 head3 = AddPolyn(head1, head2);
 printf("\nDisplay the Polynmial after Added: \n");
 print(head3);
 printf("\n");
}


/*Create the Linklist*/

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

 head = (NODE *)malloc(sizeof(NODE)); /*Create the Head Node*/
 previous = head;
 

 for(i = 0; i < n; i++)
 {
  current = (NODE *)malloc(sizeof(NODE));
  
  printf("Input the coefficient of the Polynmial:");
  scanf("%f", &current->coef);
  printf("Input the exponential of the Polynmial:");
  scanf("%d", &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);
}