sparsetable.cpp

数据结构中的稀疏矩阵问题

// SparseTable.cpp: implementation of the CSparseTable class.
//
//////////////////////////////////////////////////////////////////////

#include "SparseTable.h"
#include "iostream.h"
#include "stdio.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CSparseTable::CSparseTable()
{
	m_nMaxLine=0;
	m_nMaxRow=0;
}
bool CSparseTable::Creat(TYPE OtherData,int Line,int Row)
{
	if(m_nMaxLine>0 || m_nMaxRow>0)
		return false;
	if(Line<=0 || Row <=0)
		return false;
	m_nMaxLine=Line;
	m_nMaxRow=Row;
	m_otherData=OtherData;
	return true;
}
void CSparseTable::Destroy()
{
	m_clList.DestroyList();
    m_nMaxLine=0;
	m_nMaxRow=0;
}

bool CSparseTable::IsEmpty()
{
	return m_nMaxLine<=0 ||m_nMaxRow<=0 ? true : false;
}
bool CSparseTable::GetData(int Line,int Row,TYPE & Data)
{
	ELEMENT value;
	int i;
	if(Line<0||Line>=m_nMaxLine)
		return false;
	if(Row<0||Row>=m_nMaxRow)
		return false;
	for(i=0;i<m_clList.GetLength();i++)
	{
		value=m_clList[i];
		if(value.Line==Line && value.Row==Row)
		{
			Data=value.Data;
			return true;
		}
	}
	Data=m_otherData;
	return true;
}
bool CSparseTable::SetData(int Line,int Row,TYPE Data)
{
	ELEMENT value;
	int i;
	if(Line<0||Line>=m_nMaxLine)
		return false;
	if(Row<0||Row>=m_nMaxRow)
		return false;
	for(i=0;i<m_clList.GetLength();i++)
	{
		value=m_clList[i];
		if(value.Line==Line)
		{
			if(value.Row==Row)
			{
				if(Data==m_otherData)
				{
                    m_clList.Delete(i);
                	return true;
				}
				m_clList[i].Data=Data;
			    return true;
			}
			else if(value.Row>Row)
			{
				if(Data==m_otherData)
                	return true;
				value.Line=Line;
				value.Row=Row;
				value.Data=Data;
				m_clList.Insert(i,value);
				return true;
			}
		}
		else if(value.Line>Line)
		{
			if(Data==m_otherData)
            	return true;
			value.Line=Line;
			value.Row=Row;
			value.Data=Data;
			m_clList.Insert(i,value);
			return true;
		}
	}
	if(Data==m_otherData)
    	return true;
	value.Line=Line;
	value.Row=Row;
	value.Data=Data;
	m_clList.Add(value);
	return true;
}
bool CSparseTable::TurnOver()
{
	int space;
    CListMZ<ELEMENT> list;
	ELEMENT value;
	list.Create(m_clList);
	space=m_nMaxLine;
	m_nMaxLine=m_nMaxRow;
	m_nMaxRow=space;
	m_clList.DestroyList();
	for(int i=0;i<list.GetLength();i++)
	{
		list.GetAt(i,value);
		SetData(value.Row,value.Line,value.Data);
	}
	return true;
}
void CSparseTable::ShowTable()
{
	TYPE value;
	int i,j;
	printf("     :");
	for(j=0;j<m_nMaxRow;j++)
		printf("%4d",j);
	cout<<endl;
	for(i=0;i<m_nMaxLine;i++)
	{
		printf("%4d :",i);
		for(j=0;j<m_nMaxRow;j++)
		{
			GetData(i,j,value);
			printf("%4d",value);
		}
		cout<<endl;
	}
}

void CSparseTable::Display()
{
	ELEMENT value;
	int i;
	for(i=0;i<m_clList.GetLength();i++)
	{
		m_clList.GetAt(i,value);
		cout<<value.Line<<' '<<value.Row<<' '<<value.Data<<endl;
	}
}