quantic.cpp

实验1：链表的应用--求两个一元多项式之和 1、实验目的：掌握单链表的各种基本操作

// quantic.cpp : Defines the entry point for the console application.
// 

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

typedef struct ElemType //多项式的元素
{
	float coef; // 系数
	int expn; // 指数
}ElemType;

typedef struct LNode //链表基本元素
{
	ElemType data;
	struct LNode *next;
}LNode,*Link;//注意的是这里的头节点不是指针，而是一个实际元素，并不是直接指向第一个元素，要用next才行

typedef struct polynomial //我这儿是升序多项式
{
	Link head,tail;
	int len; // 长度
}polynomial;

//这些函数的参数和书上写得不一样，自以为这样更好些
void InsertElem(polynomial &P,Link p,Link s); //在p节点之后入节点s
void DeleteElem(polynomial &L,Link h,Link &q);  //删除第一个元素
int LocateElem(polynomial L,ElemType e,Link &q);
void CreatPolyn(polynomial &P);
void AddPolyn(polynomial &Pa,polynomial &Pb);

int main()
{
	polynomial p,q;
	Link r;
	int i;

	printf("实验一：多项式相乘\n\n");
	CreatPolyn(p);
	CreatPolyn(q);

	AddPolyn(p,q);
	printf("\n升幂排列结果：\n");

	//以下开始输出
	r=p.head->next;
	i=1;
	while(r!=NULL)
	{
		printf("第%d项 - 系数：%f 指数：%d\n",i++,r->data.coef,r->data.expn);
		r=r->next;
	}
	getchar();
	getchar();
	return 0;
}

void InsertElem(polynomial &P,Link p,Link s) //在p节点之后入节点s
{
	s->next=p->next;
	p->next=s;
	if(p==P.tail) P.tail=p->next; 
	P.len++;
}

void DeleteElem(polynomial &P,Link p,Link &q) //删除p之后的的节点q
{ 
	q=p->next;
	p->next=q->next;
	if(!p->next) 
		P.tail=p; 
	P.len--;
	//free(q); 加上这句就错了，这里不一定需要释放他的存储空间
} 
int LocateElem(polynomial P,ElemType e,Link &q)//查找找元素，非常关键
{
	Link p=P.head->next;
	Link p1=P.head; //p1为p之前的元素

	while(p!=NULL && p->data.expn<e.expn) 
	{
		p1=p;
		p=p->next;//往下查找
	}
	
	if(p==NULL || p->data.expn>e.expn) 
	{
		q=p1; //返回比e小的最高位
		return 0; //没找到
	}
	else
	{
		q=p;
		return 1;
	}
}
void CreatPolyn(polynomial &P) //创建多项式
{
	Link q,s;
	ElemType e;
	int i,n;
	Link p=(Link)malloc(sizeof(LNode)); // 头结点
	p->next=NULL; //空多项式
	P.head=P.tail=p;
	P.len=0;
	//初始化完成

	printf("请输入要创建的多项式的项数：");
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		printf("第%d项系数：",i);
		scanf("%f",&e.coef);
		printf("第%d项指数：",i);
		scanf("%d",&e.expn);
		if(LocateElem(P,e,q)==0) //找到插入的位置
		{
			s=(Link)malloc(sizeof(LNode)); //分配新节点
			s->data=e; 
			InsertElem(P,q,s);//插入多项式
		}
	}
	printf("\n");
}

void AddPolyn(polynomial &Pa,polynomial &Pb)
{
	int i=1;
	ElemType a,b;
	Link ha=Pa.head,hb=Pb.head,qa=ha->next,qb=hb->next;

	while(Pa.len>0 && Pb.len>0 && qa!=NULL)
	{ 
		a=qa->data;
		b=qb->data;

		if(a.expn-b.expn<0)
		{
			ha=qa; 
			qa=ha->next;
		}
		else if(a.expn-b.expn==0) //指数相等，系数相加
		{
			qa->data.coef+=qb->data.coef;

			if(qa->data.coef==0) 
			{
				DeleteElem(Pa,ha,qa);
				free(qa);
				qa=NULL;
			}
			else ha=qa;

			DeleteElem(Pb,hb,qb);//删除pb的用过的节点
			free(qb);
			qb=NULL;
			qb=hb->next;
			qa=ha->next;
		}
		else //这是pb的节点指数比较小的情况
		{
			DeleteElem(Pb,hb,qb); //删除pb的相应节点并加入pa
			InsertElem(Pa,ha,qb); //ha肯定是qb的前趋
			ha=ha->next;
			qb=hb->next; //两个指针后移
		}
	}//主循环结束
	if(Pb.len>0) //如果pb还有元素，就一古脑加进去
	{
		Pa.tail->next=qb;//两个表接起来
		while(qb->next)
		{
			qb=qb->next;
			i++;
		}
		Pa.tail=qb;//找到真正的表尾
		Pa.len+=i; 
	}
	free(hb);//释放他的头节点
}