dlist.cpp

用链表(单向链表或双向链表)实现 多项式之间的运算包括：多项式之间的加、减、乘、除*法等

#include "DList.h"

#define TRUE 1
#define FALSE 0
#define INVALIDATE -1

CPolynomial::CPolynomial()
{
	m_pHead = NULL;
}

//拷贝构造函数
/*
CPolynomial::CPolynomial(const CPolynomial &cp)
{
	CTerm *pTemp;
	
	if (cp.m_pHead)
	{
		pTemp = cp.m_pHead;
		if (!m_pHead)
		{
			Pushback(pTemp->m_nDegree, pTemp->m_dCoef);
			pTemp = pTemp->m_pNext;
		}
		while( pTemp != NULL )
		{
			Pushback(pTemp->m_nDegree, pTemp->m_dCoef);		
			pTemp = pTemp->m_pNext;
		}
	}
}*/


CPolynomial::~CPolynomial()
{
	//RemoveAll();
	CTerm *pTemp = m_pHead;
	while( pTemp )
	{
		CTerm *pCurrent = pTemp;
		pTemp = pTemp->m_pNext;
		delete pCurrent;
	}
}

int CPolynomial::IsEmpty()
{
	if( m_pHead )
		return FALSE;
	else
		return TRUE;
}

int CPolynomial::Size()
{
	int nNum = 0;
	CTerm *pTemp;

	pTemp = m_pHead;
	while( pTemp != NULL )
	{
		nNum++;
		pTemp = pTemp->m_pNext;
	}

	return nNum;
}


int CPolynomial::Locate(int degree, double value)
{
	int index = 0;
	CTerm *pTemp;

	pTemp = m_pHead;
	while( pTemp != NULL )
	{
		if( pTemp->m_dCoef == value && pTemp->m_nDegree == degree )
		{
			return index;
		}
		index++;
		pTemp = pTemp->m_pNext;
	}

	return INVALIDATE;
}

CTerm *CPolynomial::FindLast()
{
	CTerm *pTemp;

	pTemp = m_pHead;
	if( !IsEmpty() )
	{
		while( pTemp->m_pNext != NULL )
		{
			pTemp = pTemp->m_pNext;
		}
	}

	return pTemp;
}

int CPolynomial::Print( )
{
	CTerm *pTemp;

	pTemp = m_pHead;
	if( !IsEmpty() )
	{
		cout<<"P="<<Size()<<endl;
		while( pTemp != NULL )
		{
            cout<<pTemp->m_nDegree<<": "<<pTemp->m_dCoef<<endl;
			pTemp = pTemp->m_pNext;
		}
		cout<<endl;
	}

	return TRUE;
}

int CPolynomial::Pushback(int degree, double value)
{
	CTerm *pLast = FindLast();
	CTerm *pNewNode = new CTerm(degree, value);

	if( pLast != NULL )
	{
		pLast->m_pNext = pNewNode;
		pNewNode->m_pPrev = pLast;
	}
	else
	{
		m_pHead = pNewNode;
	}
	return TRUE;
}

CTerm *CPolynomial::FindAt(int index)
{
	if( index < 0 || index > Size()-1 )
	{
		return NULL;
	}

	CTerm *pTemp;
	pTemp = m_pHead;

	for( int i=0; i<index; i++ )
	{
		pTemp = pTemp->m_pNext;
	}

	return pTemp;
}

int	CPolynomial::InsertAt(int index, int degree, double value)
{
	CTerm *pNewNode = new CTerm(degree, value);
	CTerm *pCurrentNode = FindAt(index);

	if (index == Size())
	{
		Pushback(degree, value);
		return TRUE;
	}
	else if( pCurrentNode == NULL )
	{
		cout<<"index in InsertAt is illegal"<<endl;
		return FALSE;
	}

	CTerm *pPreNode = pCurrentNode->m_pPrev;

	if( pPreNode != NULL )
	{
		pPreNode->m_pNext = pNewNode;
		pNewNode->m_pNext = pCurrentNode;
		pCurrentNode->m_pPrev = pNewNode;
		pNewNode->m_pPrev = pPreNode;
	}
	else
	{
		pNewNode->m_pNext = pCurrentNode;
		pCurrentNode->m_pPrev = pNewNode;
		m_pHead = pNewNode;
	}
	return TRUE;
}

//void CPolynomial::RemoveAll()
//{
//	CTerm *pTemp = m_pHead;
//	while( pTemp )
//	{
//		CTerm *pCurrent = pTemp;
//		pTemp = pTemp->m_pNext;
//		delete pCurrent;
//	}
//}

int	CPolynomial::RemoveAt(int index)
{
	CTerm *pCurrentNode = FindAt(index);

	if( pCurrentNode == NULL )
	{
		cout<<"index in RemoveAt is illegal"<<endl;
		return FALSE;
	}
	else if (index == 0)
	{
		m_pHead = pCurrentNode->m_pNext;
		delete pCurrentNode;
		return TRUE;
	}
	else if (index == Size()-1)
	{
		pCurrentNode->m_pPrev->m_pNext = NULL;
		delete pCurrentNode;
		return TRUE;
	}
	else
	{
		pCurrentNode->m_pNext->m_pPrev = pCurrentNode->m_pPrev;
		pCurrentNode->m_pPrev->m_pNext = pCurrentNode->m_pNext;
		delete pCurrentNode;
		return TRUE;
	}
}

//合并同类项
void CPolynomial::Together()
{
	for (int i=0; i<Size()-1; i++)
	{
		for (int k=i+1; k<Size(); k++)
		{
			if (FindAt(i)->m_nDegree == FindAt(k)->m_nDegree)
			{
				FindAt(i)->m_dCoef += FindAt(k)->m_dCoef;
				RemoveAt(k);
			}			
		}
	}
	for (int j=0; j<Size(); j++)
	{
		if (FindAt(j)->m_dCoef == 0)
		{
			RemoveAt(j);
		}
	}	
}


//选择排序
void CPolynomial::Sort()
{
	for (int j=0; j<Size()-1; j++)
	{
		int k = j;
		for (int i=j+1; i<Size(); i++)
		{
			if ((FindAt(i)->m_nDegree) > (FindAt(k)->m_nDegree))
			{
				k = i;
			}
		}
		if (k != j)
		{
			int degree = FindAt(j)->m_nDegree;
			double coef = FindAt(j)->m_dCoef;
			FindAt(j)->m_nDegree = FindAt(k)->m_nDegree;
			FindAt(j)->m_dCoef = FindAt(k)->m_dCoef;
			FindAt(k)->m_nDegree = degree;
			FindAt(k)->m_dCoef = coef;
		}					
	}
}

//重载赋值运算符
CPolynomial& CPolynomial::operator= (const CPolynomial &C)
{
	CTerm *pTemp;

	pTemp = C.m_pHead;
	while( pTemp != NULL )
	{
		Pushback(pTemp->m_nDegree, pTemp->m_dCoef);
		pTemp = pTemp->m_pNext;
	}
	return *this;
}

//友元函数重载+运算符
CPolynomial& operator+(const CPolynomial &C1, const CPolynomial &C2)
{
    static CPolynomial cp;
	CTerm *pTemp1, *pTemp2;

	pTemp1 = C1.m_pHead;	
	while( pTemp1 != NULL )
	{
		cp.Pushback( pTemp1->m_nDegree, pTemp1->m_dCoef);		
		pTemp1 = pTemp1->m_pNext;
	}
	pTemp2 = C2.m_pHead;
	while(pTemp2 != NULL)
	{
		cp.Pushback( pTemp2->m_nDegree, pTemp2->m_dCoef);
		pTemp2 = pTemp2->m_pNext;
	}
	cp.Together();
	cp.Sort();
	return cp;
}
 
//友元函数重载-运算符
CPolynomial& operator-(const CPolynomial &C1, const CPolynomial &C2)
{
    static CPolynomial cp;
	CTerm *pTemp1, *pTemp2;
	
	pTemp1 = C1.m_pHead;	
	while( pTemp1 != NULL )
	{
		cp.Pushback( pTemp1->m_nDegree, pTemp1->m_dCoef);		
		pTemp1 = pTemp1->m_pNext;
	}
	pTemp2 = C2.m_pHead;
	while(pTemp2 != NULL)
	{
		cp.Pushback( pTemp2->m_nDegree, -pTemp2->m_dCoef);
		pTemp2 = pTemp2->m_pNext;
	}
	cp.Together();
	cp.Sort();
	return cp;
}

//友元函数重载*运算符
CPolynomial& operator*(const CPolynomial &C1, const CPolynomial &C2)
{
	static CPolynomial cp;
	CTerm *pTemp1, *pTemp2;
	pTemp1 = C1.m_pHead;
	
	while( pTemp1 != NULL )
	{
		pTemp2 = C2.m_pHead;
		while(pTemp2 != NULL)
		{
			cp.Pushback(pTemp1->m_nDegree + pTemp2->m_nDegree, pTemp1->m_dCoef * pTemp2->m_dCoef);
			pTemp2 = pTemp2->m_pNext;
		}
		pTemp1 = pTemp1->m_pNext;
	}
	cp.Together();
	cp.Sort();	
	return cp;
}