80j.cpp

一元多项式加乘法的算法实现数据结构算法练习

#define  TRUE 1
#define   FALSE 0
#define  OK 1
#define  ERROR 0

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

typedef float COEF;//元素类型
typedef int EXPN;
typedef struct NodeType
{
	COEF co;
	EXPN ex;
	NodeType *next;
}NodeType,*LinkType;

int MakeNode(LinkType &p,COEF c,EXPN e)
{
	p=(LinkType)malloc(sizeof(NodeType));
	if(!p)return FALSE;
	p->co=c;
	p->ex=e;
	p->next=NULL;
	return TRUE;
}
void FreeNode(LinkType &p)
{
	if(p) free(p);
}

COEF Elemco(LinkType p)
{
	if(p!=NULL)
		return(p->co);
	else 
		return FALSE;
}
EXPN Elemex(LinkType p)
{
	if(p!=NULL)
		return(p->ex);
	else
		return FALSE;
}
LinkType SuccNode(LinkType p)
{
	if(p!=NULL)
		return(p->next);
	else
		return NULL;
}


//有序表
typedef struct
{
	LinkType head,tail;
	int size;
}OrderedList;

int Initlist(OrderedList &L)
{
	COEF a=0.0;
	 EXPN b=-1;
	if(MakeNode(L.head,a,b))
	{
		L.tail=L.head;
		L.size=0;
		return TRUE;
	}
	else
	{
		L.head=NULL;
		return FALSE;
	}
}

void DestroyList(OrderedList &L)
{
	LinkType p,q;
	p=L.head;
	while(p)
	{
		q=p;
		p=SuccNode(p);
		FreeNode(q);
	}
	L.head=L.tail=NULL;
}

int cmp(LinkType x,LinkType y)
{
	int z;
	if(x->ex < y->ex)
		z=-1;
	if(x->ex == y->ex)
		z=0;
	if(x->ex > y->ex)
		z=1;
	return(z);
}

int LocateElem(OrderedList L,EXPN e,LinkType &p)
{
	LinkType pre;
	if(L.head)
	{
			pre=L.head;
			p=pre->next;
			while(p&&p->ex<e)
			{
				pre=p;
				p=SuccNode(p);
			}
			if(p&&p->ex==e)
				return TRUE;
			else
			{
				p=pre;//防止悬挂指针
				return FALSE;
			}
	}
	else 
			return FALSE;
}

LinkType GetHead(OrderedList L)
{
	LinkType p=L.head;
	return p;
}

LinkType NextPos(OrderedList L,LinkType &p)
{
	p=p->next;
	return p;
}

int SetCurElem(LinkType &p,COEF c,EXPN e)
{	p->ex=e;
	if(p->co=c)
		return OK;
	else
		return ERROR;
}

int DelFirst(LinkType h,LinkType q)
{
	LinkType p;
	p=q=h->next;
	h->next=q->next;

		return OK;
}

int InsFirst(LinkType &h,LinkType &s)
{
	s->next=h->next;
	h->next=s;
	return OK;
}

int ListEmpty(OrderedList L)
{
	if(L.head==NULL)
		return TRUE;
	else
		return ERROR;
}

void Append(OrderedList &L,LinkType ha,LinkType s)
{
	if(L.head&&s)
	{
		if(ha!=L.head)
			ha->next=s;
		else L.head->next=s;
		ha=s;
		while(s)
		{
		++L.size;
		s=s->next;
		}
	}

}


//Polynomial
typedef OrderedList Polynomial;

void CreatPolyn(Polynomial &p,int m)
{
	NodeType x;
	LinkType s,q;
	int i,j=0;
	Initlist(p);
	x.co=0.0;
	x.ex=-1;
	SetCurElem(p.head,x.co,x.ex);
	for(i=1;i<=m;i++)
	{
		printf("请输入多项式系数和指数:\n");
		scanf("%f %d,",&x.co,&x.ex);
		if(!LocateElem(p,x.ex,q))
		{
		if(MakeNode(s,x.co,x.ex))
			InsFirst(q,s);
		}
	}
	p.tail=s;
	p.size=m;
}

void DestroyPolyn(Polynomial &p)
{
	DestroyList(p);
}

void PrintPolyn(Polynomial &p)
{
	LinkType q;
	q=p.head->next;
	printf("是%d项多项式：",p.size);

		while(q)
		{
		printf("%+fx`(%d)",q->co,q->ex);
		q=q->next;}
		printf("\n");
}

int PolynLength(Polynomial p)
{return(p.size);}

void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{
	LinkType ha,hb,qa,qb;
	int j=0;
	COEF a,b,sum;
	ha=GetHead(Pa);
	hb=GetHead(Pb);
	qa=Pa.head->next;
	qb=Pb.head->next;
while(qa&&qb)
	{
		a=Elemco(qa);
		b=Elemco(qb);
		switch(cmp(qa,qb))
		{
		case -1: ha=qa;qa=qa->next;++j;break;
		case 0:
			sum=a+b;
			if(sum!=0.0)
			{
				qa->co=sum;
				ha=qa;
				++j;
			}
			else
			{
				DelFirst(ha,qa);
				FreeNode(qa);
			}
			DelFirst(hb,qb);
			FreeNode(qb);
				qb=hb->next;
				qa=ha->next;
				break;
		case 1:
			DelFirst(hb,qb);
			InsFirst(ha,qb);
			qb=hb->next;
			ha=ha->next;
		    ++j;
			break;
		}
	}
        Pa.size=j;
		if(!ListEmpty(Pb))
			Append(Pa,ha,qb);
		FreeNode(hb);
	
}

void Subtract(Polynomial &Pa,Polynomial &Pb)
{
		LinkType p=Pb.head->next;
		while(p)
		{
			p->co=-p->co;
		p=p->next;
		}
		AddPolyn(Pa,Pb);
}

void Mutiply(Polynomial &Pa,Polynomial &Pb,Polynomial &Pm)
{
	Polynomial Pc;
    LinkType p=Pa.head->next,q=Pb.head->next,s,pre;
	Initlist(Pm);
	while(q)
	{
		Initlist(Pc);
		pre=Pc.head;
		while(p)//链成Pc有序表用来存储Pb的某结点与Pa每个结点的积的链表
	{
        
		if(MakeNode(s,p->co*q->co,p->ex+q->ex))
		{
			pre->next=s;
			pre=pre->next;
		}
		p=p->next;
	}
		p=Pa.head->next;
	AddPolyn(Pm,Pc);
	q=q->next;
	}
}

//主函数
void scan(Polynomial &Pa,Polynomial &Pb)
{
	int m,n;
	printf("请输入a多项式项数：\n");
    scanf("%d",&m);
	CreatPolyn(Pa,m);
	printf("a");PrintPolyn(Pa);	
	printf("\n");
	printf("请输入b多项式项数：\n");
	scanf("%d",&n);
	CreatPolyn(Pb,n);
	printf("b");PrintPolyn(Pb);
}



void main()
{
	char cmd;
	Polynomial Pa,Pb,Pm;
    scan(Pa,Pb);	
	printf("请输入指令：\na【两一元多项式加和】;\n");
	printf("s【做差-a多项式减去b多项式】；\nm【两一元多项式相乘】\n");
    scanf(" %c",&cmd);
	switch(cmd)
	{	
	    case'a':
	    AddPolyn(Pa,Pb);
		printf("加和");
		PrintPolyn(Pa);
		break;
		case's':
		Subtract(Pa,Pb);
		printf("相减");
		PrintPolyn(Pa);
		break;
		case'm':
			Mutiply(Pa,Pb,Pm);
			printf("相乘");
			PrintPolyn(Pm);
			break;
	}
}