xiangcheng.cpp

1问题描述： 设计一个实现稀疏多项式乘法的程序 2需求分析： 编程实现两个一元多项式相乘

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

#define NULL 0

typedef struct pnode  //存储结构定义
{
	float coef;
	int exp;
	struct pnode *link;
}pnode,*node;

pnode *head;    

pnode *Creat(int k,char c)//输入并建立多项式，其项数为k
{  
	  pnode *p,*s,*first;
	  int i;
	 
	  head=(pnode*)malloc(sizeof(pnode));
	  head->link=NULL;
	  p=head;
      
	  for(i=1;i<=k;i++)
	  {
		s=(pnode*)malloc(sizeof(pnode));//生成结点，存放输入的信息，并将其链接到表p后面去
		s->link=NULL;

        printf("\n请按降序输入多项式%c的系数m%d=",c,i);
		scanf("%f",&(s->coef));
        
		while(s->coef==0.0)//当输入的系数零时要求重新输入
	                                      
			{printf("输入有错请重新输入m%d=",i);
		    scanf("%f",&(s->coef));
			}


		printf("\n请按降序输入多项式%c的指数n%d=",c,i);
		scanf("%d",&(s->exp));    
		
		    while(p!=head&&p->exp<=s->exp)//当输入的指数不比上一个结点的指数小时，
	                                      //要求重新输入，即保证链表是降序存储
			{printf("输入有错请重新输入n%d=",i);
		    scanf("%d",&(s->exp));
			}
		p->link=s;
		p=s;//每链接上一 个结点后，p后移
	  }
	  
      first=head;
	  return(first);
 }

void output(pnode *head)
{ pnode *t;
   int i=1;
	head=head->link;
	t=head;
	while(t->link)//确定链表的长度，即多项式的项数。
	{
	    t=t->link;
		i=i+1;
	}
  printf("%d",i);
	while(head)//输出每个结点的信息，即多项式每一项的系数和指数
	{
		 printf("(");
		 printf("%f,%d",head->coef,head->exp);
		 printf(")");
		 head=head->link;//结点后移
	}
	 
 }

pnode *multiply(pnode *heada,pnode *headb)
{  
	pnode *pa,*pb;	
	pnode *pcNew;
	pnode *pc;
	pnode *pcRemark;//标记指针，记录每次操作的位置
	pnode *pcDel;
    float coef;
	int exp;
	pa=heada->link;
	pb=headb->link;

	pc=(pnode *)malloc(sizeof(pnode));//生成c的头结点
	pc->link=NULL;

	while(pa)
	{
		pcRemark=pc;//当a的一项和b中的每一项都乘完之后,将pcRemark重新回到头结点以便新结点插入
		             //的查找

		while(pb)
		{
			coef=pa->coef*pb->coef;
			exp=pa->exp+pb->exp;

			pcNew=(pnode *)malloc(sizeof(pnode));
			pcNew->coef=coef;
			pcNew->exp=exp;
			pcNew->link=NULL;

			while(pcRemark->link && exp<pcRemark->link->exp)//当的下一个结点的指数仍比pcNew
				pcRemark=pcRemark->link;//的大的时候将pcRemark后移

			if(pcRemark->link && exp==pcRemark->link->exp)//当pcRemark的下一个结点的指数和
			{                                  //  pcNew相等的情况
				if(coef+pcRemark->link->coef==0.0)//如果它们系数相加为零，就释放链表中的那个结点
				{
					pcDel=pcRemark->link;
					pcRemark->link=pcDel->link;

					free(pcDel);
				}
				else//否则话将pcRemark->link的指数修改为它们相加之和
				{
					pcRemark->link->coef=pcRemark->link->coef+coef;
				}
			}
			else//否则的话在pcRemark为尾结点的情况下，将pcNew直接链到其后
			{
				pcNew->link=pcRemark->link;
		        pcRemark->link=pcNew;
			}

			pb=pb->link;//将的结点后移
		}

		pa=pa->link;//用a的一项去乘b的每一项
		pb=headb->link;//当a的一项和b中的每一项都乘完之后，将pb
	}//重新回到头结点

	return(pc);
}


void main()
{ 
	 pnode *heada,*headb,*headc;
	
	  int a,b;
	  char c,d;
	  
	  c='a';
	  d='b';
	  printf("请输入多项式的a的项数Na=");
	  scanf("%d",&a); 
	  heada=Creat(a,c); 
	  printf("建立好的多项式a如下:\n");
	  output(heada);
	 
	  printf("\n请输入多项式b的项数Nb=");
	  scanf("%d",&b);
      headb=Creat(b,d);
	  printf("建立好的多项式b如下:\n");
	  output(headb);

	  headc=multiply(heada,headb);
	  printf("\n多项式a与多项式b相乘后的结果如下:\n");
      output(headc);
 }