3.线性表的应用-一元多项式的计算

现在的位置: 首页 > 综合 > 正文

3.线性表的应用-一元多项式的计算

2014年09月05日 ⁄ 综合 ⁄ 共 3882字 ⁄ 字号小中大 ⁄ 评论关闭

文章目录

1.理论
2.实现程序
3.运行结果

1.理论

一元多项式可以很容易的表示为线性表如：2*X^8-9*X^5+5*X^2+8，构成的线性表为{{2,8}, {-9,5}, {5,2}, {8,0}}，线性表的每个数据元素为{系数，上标}的形式。考虑到多项式的次数可能很高且变化很大，我们采用双向链表的形式来作为多项式的逻辑结构。

我们假设输入的多项式按照次数的高低从前往后排列，不满足这一条件的使用排序来达到这样的效果。这样进行多项式的加、减操作时，只需要分配一个新的链表，从前往后遍历两个相加、减的多项式，比较多项式项次数的高低来插入较高次数的多项式到新链表，次数相等的多项式项加、减对应的基数后再插入。多项式的乘法就是展开各个项相乘后再累加起来，原理是一样的。

下面是部分实现程序，其中注意完整程序加减法都提供了一个Slow版本和一个Fast版本：Slow版本就是新分配一个链表，遍历多项式的两个链表项复制它们的值来插入，需要动态开辟内存，相对较慢；Fast版本利用了指针的特性，直接将各个项串接起来，相对较快，但是这样导致原来相加、减的两个多项式项的链表发生了变化，这是我们不希望看到的，如果非要这个函数，必须先复制两个多项式做备份，这里放上这个Fast函数只是为了补充说明链表合并的方便性。

2.实现程序

链表存储结构

typedef struct
{
	int base;				//多项式系数，头节点用它保存长度
	int superscript;		//多项式次数(上标)
} JWListElem;

typedef struct tagJWListNode
{
	JWListElem				elem;		//数据元素
	struct tagJWListNode	*pNext;		//下一个节点指针
	struct tagJWListNode	*pPrior;	//上一个节点指针
}JWListNode, *PJWListNode, JWList, *PJWList;

typedef PJWList Poly ;

多项式操作函数

/*
功能：将两个从高次到低次排序好的多项式相加
输入：多项式p1和p2
输出:相加后的多项式
说明:由于结果的生成要不断的重新申请空间运行速度相对较慢，但是p1和p2保持不变
*/
Poly PolyAddSlow(Poly p1, Poly p2)
{
	Poly		pAdd,pTemp1,pTemp2;
	JWListElem	AddTemp;						//相加过程中的临时变量

	pAdd	= JWListCreateFromHead(0, NULL);	//相加的结果pAdd
	pTemp1	= p1->pNext;						//多项式p1的移动指针pTemp1
	pTemp2	= p2->pNext;						//多项式p2的移动指针pTemp2

	//两者交替比较，上标大的先插入,相同上标时基数累加
	while(pTemp1 != NULL && pTemp2 != NULL)
	{
		if(pTemp1->elem.superscript > pTemp2->elem.superscript)
		{
			JWListInsert(pAdd, JWListGetLength(pAdd), pTemp1->elem);

			pTemp1 = pTemp1->pNext;
		}
		else if(pTemp1->elem.superscript < pTemp2->elem.superscript)
		{
			JWListInsert(pAdd, JWListGetLength(pAdd), pTemp2->elem);

			pTemp2 = pTemp2->pNext;
		}
		else
		{
			AddTemp.base = pTemp1->elem.base + pTemp2->elem.base;

			if(0 != AddTemp.base)//剔除相加后基数变为0的情况
			{
				AddTemp.superscript = pTemp1->elem.superscript;
				
				JWListInsert(pAdd, JWListGetLength(pAdd), AddTemp);
			}

			pTemp1 = pTemp1->pNext;
			pTemp2 = pTemp2->pNext;
		}
	}

	//将剩余的全部插在链表结尾
	while(pTemp1 != NULL)
	{
		JWListInsert(pAdd, JWListGetLength(pAdd), pTemp1->elem);

		pTemp1 = pTemp1->pNext;
	}
	while(pTemp2 != NULL)
	{
		JWListInsert(pAdd, JWListGetLength(pAdd), pTemp2->elem);

		pTemp2 = pTemp2->pNext;
	}

	return pAdd;
}

/*
功能：将两个从高次到低次排序好的多项式相减
输入：多项式p1和p2,p1-p2
输出:相减后的多项式
说明:由于结果的生成要不断的重新申请空间运行速度相对较慢，但是p1和p2保持不变
*/
Poly PolySubtractSlow(Poly p1, Poly p2)
{
	Poly		pSub,pTemp1,pTemp2;
	JWListElem	SubTemp;						//相减过程中的临时变量

	pSub	= JWListCreateFromHead(0, NULL);	//相减的结果pSub
	pTemp1	= p1->pNext;						//多项式p1的移动指针pTemp1
	pTemp2	= p2->pNext;						//多项式p2的移动指针pTemp2

	//两者交替比较，上标大的先插入,相同上标时基数相减
	while(pTemp1 != NULL && pTemp2 != NULL)
	{
		if(pTemp1->elem.superscript > pTemp2->elem.superscript)
		{
			JWListInsert(pSub, JWListGetLength(pSub), pTemp1->elem);

			pTemp1 = pTemp1->pNext;
		}
		else if(pTemp1->elem.superscript < pTemp2->elem.superscript)
		{
			SubTemp.base = 0 - pTemp2->elem.base;
			SubTemp.superscript = pTemp2->elem.superscript;
			JWListInsert(pSub, JWListGetLength(pSub), SubTemp);

			pTemp2 = pTemp2->pNext;
		}
		else
		{
			SubTemp.base = pTemp1->elem.base - pTemp2->elem.base;

			if(0 != SubTemp.base)//剔除相减后基数变为0的情况
			{
				SubTemp.superscript = pTemp1->elem.superscript;

				JWListInsert(pSub, JWListGetLength(pSub), SubTemp);
			}

			pTemp1 = pTemp1->pNext;
			pTemp2 = pTemp2->pNext;
		}
	}

	//将剩余的全部插在链表结尾
	while(pTemp1 != NULL)
	{
		JWListInsert(pSub, JWListGetLength(pSub), pTemp1->elem);

		pTemp1 = pTemp1->pNext;
	}
	while(pTemp2 != NULL)
	{
		SubTemp.base = 0 - pTemp2->elem.base;
		SubTemp.superscript = pTemp2->elem.superscript;
		JWListInsert(pSub, JWListGetLength(pSub), SubTemp);

		pTemp2 = pTemp2->pNext;
	}

	return pSub;
}

/*
功能:将两个从高次到低次排序好的多项式相乘
输入:两个多项式p1和p2
输出:相乘后的多项式
*/
Poly PolyMultiply(Poly p1, Poly p2)
{
	Poly		pMulti, pMultiTemp, pTemp1, pTemp2, pLine;
	JWListElem	eTemp;

	pMultiTemp	= pMulti = JWListCreateFromHead(0, NULL);
	pTemp1		= p1->pNext;

	//循环展开多项式
	while(pTemp1 != NULL)
	{
		pLine = JWListCreateFromHead(0, NULL);				//创建新的一次展开计算
		pTemp2 = p2->pNext;									//重置pTemp2循环初始值

		while(pTemp2 != NULL)
		{
			eTemp.base = pTemp1->elem.base * pTemp2->elem.base;
			eTemp.superscript = pTemp1->elem.superscript * pTemp2->elem.superscript;

			JWListInsert(pLine, JWListGetLength(pLine), eTemp);//展开项构成新的多项式

			pTemp2 = pTemp2->pNext;
		}

		//将已有结果累加
		PolySort(pLine);//调整pTemp1的负上标和pTemp2相乘后上标排列顺序还是从高到低！！！
		pMulti = PolyAddSlow(pMultiTemp, pLine);

		//删除上一次展开计算的结果
		JWListDestroy(pMultiTemp);
		JWListDestroy(pLine);

		pMultiTemp = pMulti;
		pTemp1 = pTemp1->pNext;
	}

	return pMulti;
}