gridmatrix1.h

数据结构中稀疏矩阵的十字链表存取表示

// GridMatrix1.h: interface for the CGridMatrix class.
//
//////////////////////////////////////////////////////////////////////
#include "item.h"

#if !defined(AFX_GRIDMATRIX1_H__DDF56BE2_5287_4C7C_8C72_F3505DC65A9B__INCLUDED_)
#define AFX_GRIDMATRIX1_H__DDF56BE2_5287_4C7C_8C72_F3505DC65A9B__INCLUDED_
#define BOOL bool
#define TRUE true
#define FALSE false

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class CGridMatrix  
{
//Method:
public:
	CGridMatrix(int m,int n)//矩阵为m x n型
	{
		m_nLine=m;
		m_nRow=n;
		m_lpRow=NULL;
		m_lpLine=NULL;
		m_lpRow=new CItem *[m_nRow];
		m_lpLine=new CItem *[m_nLine];

		for(int i=0;i<m_nRow;i++)
			m_lpRow[i]=NULL;

		for(i=0;i<m_nLine;i++)
			m_lpLine[i]=NULL;
	}


	virtual ~CGridMatrix()
	{
		for(int i=0;i<m_nRow;i++)
		{				
			CItem *p=NULL;

			while(m_lpRow[i])
			{
				p=m_lpRow[i];
				m_lpRow[i]=m_lpRow[i]->m_lpNextLine;

				delete p;
				p=NULL;
			}
		}

		Clear();

		if(m_lpRow)
			delete []*m_lpRow;

		if(m_lpLine)
			delete []*m_lpLine;
	}

	inline int GetLineNum() const
	{
		return m_nLine;
	}

	inline int GetRowNum() const
	{
		return m_nRow;
	}


	void InsertData(CItem &it)
	{
	//数据拷贝
		CItem *item=new CItem;
		item->m_Data=it.m_Data;
		item->m_LineID=it.m_LineID;
		item->m_RowID=it.m_RowID;

	//行插入
		//若无任何数据
		if(m_lpRow[item->m_RowID-1]==NULL)
		{
			m_lpRow[item->m_RowID-1]=item;
		}
		//若有数据
		else
		{
			CItem *p=m_lpRow[item->m_RowID-1];
			CItem *pBef=m_lpRow[item->m_RowID-1];
			BOOL bFinish=FALSE;//任务完成判断符

			while(p!=NULL)
			{
				if(IsLeft(*item,*p))
				{
					//作为头插入
					if(pBef==p)
					{
						item->m_lpNextLine=p;
						m_lpRow[item->m_RowID-1]=item;
					}
					//中间插入
					else
					{
						pBef->m_lpNextLine=item;
						item->m_lpNextLine=p;
					}// if

					bFinish=TRUE;//插入完成
					break;
				}// if

				//指针后移
				if(pBef==p)
				{
					p=pBef->m_lpNextLine;
				}
				else
				{
					pBef=p;
					p=p->m_lpNextLine;
				}// if
			}// while

			if(!bFinish) pBef->m_lpNextLine=item;
			bFinish=TRUE;
		}

	//列插入
		//若无任何数据
		if(m_lpLine[item->m_LineID-1]==NULL)
		{
			m_lpLine[item->m_LineID-1]=item;
		}
		//若有数据
		else
		{
			CItem *p=m_lpLine[item->m_LineID-1];
			CItem *pUp=m_lpLine[item->m_LineID-1];
			BOOL bFinish=FALSE;//任务完成判断符

			while(p!=NULL)
			{
				if(IsUpper(*item,*p))
				{
					//作为头插入
					if(pUp==p)
					{
						item->m_lpNextRow=p;
						m_lpLine[item->m_LineID-1]=item;
					}
					//中间插入
					else
					{
						pUp->m_lpNextRow=item;
						item->m_lpNextRow=p;
					}// if

					bFinish=TRUE;//插入完成
					break;
				}// if

				//指针后移
				if(pUp==p)
				{
					p=pUp->m_lpNextRow;
				}
				else
				{
					pUp=p;
					p=p->m_lpNextRow;
				}// if
			}// while

			if(!bFinish) pUp->m_lpNextRow=item;
			bFinish=TRUE;
		}
	}

	void Add(const CGridMatrix &m)
	{
		//判断矩阵是否同型
		int a[2]={m.GetLineNum(),m.GetRowNum()};

		if(a[0]!=m_nLine||a[1]!=m_nRow)
			return;

		//两矩阵相加
		for(int i=0;i<m.GetRowNum();i++)
		{
			CItem *p=NULL;
			p=m.m_lpRow[i];
			while(p!=NULL)
			{
				Add(*p);
				p=p->m_lpNextLine;
			}
		}
	}

	void Add(CItem &item)
	{
		CItem* p=NULL;
		p=m_lpRow[item.m_RowID-1];
		BOOL bFinish=FALSE;

		while(p!=NULL)
		{
			//如果有此项,则相加
			if(p->m_LineID==item.m_LineID)
			{
				p->m_Data+=item.m_Data;
				bFinish=TRUE;
				break;
			}
			p=p->m_lpNextLine;
		}

		//如果没有此项,则插入
		if(!bFinish)
		{
			InsertData(item);
		}
	}

protected:
	void Clear()
	{
		for(int i=0;i<m_nRow;i++)
			m_lpRow[i]=NULL;

		for(i=0;i<m_nLine;i++)
			m_lpLine[i]=NULL;
	}

	BOOL IsUpper(CItem &UpItem,CItem &UnderItem)
	{
		if(UpItem.m_RowID<UnderItem.m_RowID)
			return TRUE;
		
		return FALSE;
	}

	BOOL IsLeft(CItem &LeftItem,CItem &RightItem)
	{
		if(LeftItem.m_LineID<RightItem.m_LineID)
			return TRUE;
		
		return FALSE;
	}

//Attribute:
public:
	CItem** m_lpRow;//行指针组
	CItem** m_lpLine;//列指针组
protected:
	int m_nLine;//列数
	int m_nRow;//行数
};

#endif // !defined(AFX_GRIDMATRIX1_H__DDF56BE2_5287_4C7C_8C72_F3505DC65A9B__INCLUDED_)