queue.cpp

这是一个简单队列数据结构计算的源代码

#include "stdafx.h"
#include "Queue.h"
#include "afxtempl.h"

CQueue::CQueue()
{
	pHead=NULL;
}

CQueue::CQueue(int n)
{
	if(n==0) return;
	pHead=NULL;

	pHead=new CNode;

	pNext=pHead;
	pHead->value.number=n;

	for(int i=1;i<=n;++i)
	{
		CNode* pNew=new CNode;
		pNext->pPNext=pNew;
		pNew->pPNext=NULL;

		pNext=pNext->pPNext;
	}
	pNext->pPNext=pHead->pPNext;
}

CQueue::CQueue(int n,float* pData)
{
	pHead=NULL;
	Create(n,pData);
}

CQueue::CQueue(const CQueue &src)
{
	pHead=NULL;
	Copy(src);
}

void CQueue::Create(int n,float* pData)
{
	if(pHead!=NULL) return;

	pHead=new CNode;

	pHead->value.number=n;

	pNext=pHead;

	for(int i=1;i<=n;++i)
	{
		CNode* pNew=new CNode;
		pNew->value.data=*(pData+i-1);
		pNext->pPNext=pNew;
		pNew->pPNext=NULL;

		pNext=pNext->pPNext;
	}
	pNext->pPNext=pHead->pPNext;
}

void CQueue::Copy(const CQueue &src)
{

	if(pHead!=NULL) return;

	pHead=new CNode;

	pHead->value.number=src.pHead->value.number;
	pNext=pHead;
	CNode* psrc=src.pHead;
	psrc=psrc->pPNext;

	for(int i=1;i<=pHead->value.number;++i)
	{
		CNode* pNew=new CNode;
		pNew->value.data=psrc->value.data;
		pNext->pPNext=pNew;
		pNew->pPNext=NULL;

		pNext=pNext->pPNext;
		psrc=psrc->pPNext;
	}
	pNext->pPNext=pHead->pPNext;
}

void CQueue::Empty()
{
	if(pHead==NULL)
		return;
	CNode* pCurrent=pHead->pPNext;

	CNode* pTemp=pHead->pPNext;
	for(int i=1;i<pHead->value.number;++i)
		pTemp=pTemp->pPNext;

	pTemp->pPNext=NULL;


	delete pHead;
	pHead=NULL;
	pNext=NULL;

	while(pCurrent->pPNext!=NULL)
	{
		CNode* pData=pCurrent;
		pCurrent=pCurrent->pPNext;

		pData->pPNext=NULL;

		delete pData;
	}

	delete pCurrent;
}

bool CQueue::IsEmpty()
{
	if(pHead==NULL)
		return TRUE;
	return FALSE;
}


void CQueue::Delete(int key,int number)
{
	if(key<=0)key=1;
	if(key>=pHead->value.number)return;

	int n=number;
	if((key+number)>pHead->value.number)
		n=key+number-pHead->value.number;

	pHead->value.number-=number;
	pNext=pHead->pPNext;

	CNode* pP=pHead->pPNext;

	if(key==1||(key+number)>pHead->value.number)
	{
		for(int i=1;i<=n;++i)
			pP=pP->pPNext;
	}
	pHead->pPNext=pP;

	for(int i=1;i<key;++i)
		pNext=pNext->pPNext;

	CNode* pNew=pNext->pPNext;

	CNode* pTemp=pNext->pPNext;
	for(i=1;i<number;++i)
		pTemp=pTemp->pPNext;
	CNode* p=pTemp;
	pTemp=pTemp->pPNext;
	p->pPNext=NULL;

	pNext->pPNext=pTemp;

	//delete 

	for(i=1;i<number;++i)
	{
		CNode* pNode=pNew;
		pNew=pNew->pPNext;
		delete pNode;
	}
	delete pNew;

	pNext=pHead->pPNext;
	for(i=1;i<=pHead->value.number;++i)
	{
		TRACE("\t%f",pNext->value.data);
		pNext=pNext->pPNext;
	}
}
		

void CQueue::Push(float value)
{
	if(pHead==NULL)return;

	pNext=pHead->pPNext;
	pNext->value.data=value;
	pHead->pPNext=pNext->pPNext;
}

void CQueue::Pop(float &value)
{
	if(pHead==NULL)return;

	pNext=pHead->pPNext;
	value=pNext->value.data;
}


void CQueue::Add(int key,int number,float* pData)
{
	if(key>pHead->value.number||key<=0)key=pHead->value.number;

	pHead->value.number+=number;

	pNext=pHead->pPNext;

	for(int i=1;i<key;++i)
		pNext=pNext->pPNext;

	CNode* pTemp=pNext->pPNext;

	for(i=1;i<=number;++i)
	{
		CNode* pNew=new CNode;
		pNew->value.data=*(pData+i-1);
		pNew->pPNext=NULL;

		//add a node

		pNext->pPNext=pNew;
		pNew->pPNext=pTemp;
		pNext=pNext->pPNext;
	}

	pNext=pHead->pPNext;
	for(i=1;i<=pHead->value.number;++i)
	{
		TRACE("\t%f",pNext->value.data);
		pNext=pNext->pPNext;
	}
}

CQueue::~CQueue()
{
	Empty();
}


void CQueue::operator=(const CQueue &src)
{
	if(pHead!=NULL)
		Empty();

	Copy(src);
}

CQueue CQueue::operator*(const float value)
{
	if(pHead==NULL)
	{
		CQueue newsrc;
		return newsrc;
	}

	CQueue newsrc(pHead->value.number);

	newsrc.pNext=newsrc.pHead->pPNext;

	pNext=pHead->pPNext;
	for(int i=1;i<=pHead->value.number;++i)
	{
		newsrc.pNext->value.data=pNext->value.data*value;
		newsrc.pNext=newsrc.pNext->pPNext;
		pNext=pNext->pPNext;
	}
	return newsrc;
}

void CQueue::operator *=(const float value)
{
	if(pHead==NULL)return;

	pNext=pHead->pPNext;
	for(int i=1;i<=pHead->value.number;++i)
	{
		pNext->value.data*=value;
		pNext=pNext->pPNext;
	}
}

CQueue CQueue::operator +(const CQueue &src)
{
	if(pHead==NULL||src.pHead==NULL||pHead->value.number!=src.pHead->value.number)
	{
		CQueue newsrc;
		return newsrc;
	}

	CQueue newsrc(pHead->value.number);

	newsrc.pNext=newsrc.pHead->pPNext;
	CNode* psrc=src.pHead->pPNext;
	pNext=pHead->pPNext;

	for(int i=1;i<=pHead->value.number;++i)
	{
		newsrc.pNext->value.data=pNext->value.data+psrc->value.data;
		newsrc.pNext=newsrc.pNext->pPNext;
		psrc=psrc->pPNext;
		pNext=pNext->pPNext;
	}

	return newsrc;
}

CQueue CQueue::operator -(const CQueue &src)
{
	if(pHead==NULL||src.pHead==NULL||pHead->value.number!=src.pHead->value.number)
	{
		CQueue newsrc;
		return newsrc;
	}

	CQueue newsrc(pHead->value.number);

	newsrc.pNext=newsrc.pHead->pPNext;
	CNode* psrc=src.pHead->pPNext;
	pNext=pHead->pPNext;

	for(int i=1;i<=pHead->value.number;++i)
	{
		newsrc.pNext->value.data=pNext->value.data-psrc->value.data;
		newsrc.pNext=newsrc.pNext->pPNext;
		psrc=psrc->pPNext;
		pNext=pNext->pPNext;
	}

	return newsrc;
}

void CQueue::operator -()
{
	if(pHead==NULL)return;

	pNext=pHead->pPNext;
	for(int i=1;i<=pHead->value.number;++i)
	{
		pNext->value.data=-pNext->value.data;
		pNext=pNext->pPNext;
	}
}

void CQueue::operator+=(const CQueue &src)
{
	
	if(pHead==NULL||src.pHead==NULL||pHead->value.number!=src.pHead->value.number)
		return;

	CQueue newsrc=*this;
	Empty();
	*this=newsrc+src;
}

void CQueue::operator-=(const CQueue &src)
{
	
	if(pHead==NULL||src.pHead==NULL||pHead->value.number!=src.pHead->value.number)
		return;

	CQueue newsrc=*this;
	Empty();
	*this=newsrc-src;
}

CQueue CQueue::operator /(const float value)
{

	if(pHead==NULL)
	{
		CQueue newsrc;
		return newsrc;
	}

	CQueue newsrc(pHead->value.number);

	newsrc.pNext=newsrc.pHead->pPNext;

	pNext=pHead->pPNext;
	for(int i=1;i<=pHead->value.number;++i)
	{
		newsrc.pNext->value.data=pNext->value.data/value;
		pNext=pNext->pPNext;
		newsrc.pNext=newsrc.pNext->pPNext;
	}
	return newsrc;
}

void CQueue::operator /=(const float value)
{
	if(pHead==NULL)return;

	pNext=pHead->pPNext;
	for(int i=1;i<=pHead->value.number;++i)
	{
		pNext->value.data/=value;
		pNext=pNext->pPNext;
	}
}

float CQueue::operator [](int nIndex)
{
	if(nIndex<1||nIndex>pHead->value.number)return 0.0;

	pNext=pHead->pPNext;
	for(int i=1;i<=nIndex-1;++i)
		pNext=pNext->pPNext;

	return pNext->value.data;
}