smatrix.cpp

数据库课程设计

/*课程题目：数据结构与算法课程设计*/
/*题目：稀疏矩阵的完全链表表示及其运算*/
/*设计日期：2005年8月29日至9月2日 */



#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#define MaxNum 10 //定义一个全局常量，用来改变装头结点的数组的长度


/********************  定义结构   ***********************/
typedef struct Node
{
	int row,col; 
	int value;
	struct Node *right,*down;
}SMNode, *SMLink; //定义节点，每个节点含有五个域，矩阵元素的行号row，列号col，值e,指向下一个节点的指针right和down

typedef struct SMatrix
{
	SMLink h;
	int mu,nu,tu;
}SMatrix;//定义矩阵，该结构含四个域：头节点，矩阵的行数mu，列数nu，以及矩阵中非零元的个数

SMatrix sm[MaxNum];//定义一个数组，用来存放矩阵的头节点，该系统可处理矩阵的最大数量为MaxNum


/********************  函数声明   ***********************/
void InitSMatix();//初始化函数
void CreateSMatrix();//建立矩阵函数
void InsertSMatrix(SMatrix &smm,int i,int j,int e); //插入节点函数，在建立矩阵时需要调用
void DestroySMatrix(int n); //删除矩阵函数
int PrintSMatrix(int n); //打印矩阵函数
void AddSMatrix(); //矩阵加法函数
void SubSMatrix();  //矩阵减法函数
void MultSMatrix(); //矩阵乘法函数
void TransposeSMatrix(int n);//矩阵转置函数
int show();//界面提示函数


/******************** 初始化函数  ***********************/
void InitSMatix()
{
	SMLink p;
    int i;
	for(i=0;i<MaxNum;i++)
	{
		if(!(p=(SMLink)malloc(sizeof(SMNode))))
            cout<<"OVERFLOW";
            sm[i].h=p;//建立头节点，并把头节点置空
	           p->row=NULL;
	           p->col=NULL;
	           p->value=NULL;
	           p->right=NULL;
	           p->down=NULL;
    }
}//InitSmatixList


/********************  矩阵创建函数  ***********************/
void CreateSMatrix()
{
	SMLink p;
	int i,j,e,m,n;
	int temp;

	for(m=0;m<MaxNum;m++)
		if((sm[m].h)->right==NULL)
			break;
	if(m==MaxNum)
	{
		cout<<"内存已满！"<<endl;
		return;
	}//查找空的存储空间，确认有足够的存储空间
		
	cout<<endl<<"请输入矩阵的行数:";
	cin>>sm[m].mu;
	cout<<"请输入矩阵的列数:";
	cin>>sm[m].nu;
	temp=sm[m].mu*sm[m].nu;//输入矩阵的特征值：行数，列数，非零元个数
    do
	{
	   cout<<"请输入矩阵的非零元个数:";
	   cin>>sm[m].tu;
	   if(sm[m].tu>temp)
	       cout<<"结点数超出矩阵范围，请确认输入！"<<endl;
    }while(sm[m].tu>temp);//确认节点个数正确
		
	for(n=1;n<=sm[m].tu;n++)
	{
		do
		{
			cout<<"请输入第"<<n<<"个非零元的行号:";
			cin>>i;
			if(i>sm[m].mu) cout<<"ERROR!"<<endl;
		}while(i>sm[m].mu);
		do
		{
			cout<<"请输入第"<<n<<"个非零元的列号:";
			cin>>j;
			if(j>sm[m].nu) cout<<"ERROR!"<<endl;
		}while(j>sm[m].nu);
		cout<<"请输入第"<<n<<"个非零元的值:";
		cin>>e;
		InsertSMatrix(sm[m],i,j,e); //输入一个新的节点，并利用插入函数将其联入链表中
	}
	
	p=sm[m].h;
	while(p->right!=NULL)
		p=p->right;
	p->right=sm[m].h;
	p=sm[m].h;
	while(p->down!=NULL)
		p=p->down;
	p->down=sm[m].h;//最后连上头结点形成循环链表
}//CreateSMatrix

/********************  插入结点函数  ***********************/
void InsertSMatrix(SMatrix &smm,int i,int j,int e)
{
	SMLink p,q,r;
	p=smm.h;
	while(p->right!=NULL&&p->row<i)
	{
		q=p;
		p=p->right;
	}//用两个指针找到插入节点的位置
	if(p->row>i)//情况一:插入节点的行号刚好介于p,q指针所指节点的行号之间，插在它们之间即可
	{
		if(!(r=(SMLink)malloc(sizeof(SMNode))))
			cout<<"OVERFLOW";
		r->row=i;
		r->col=j;
		r->value=e;
		r->right=p;
		r->down=NULL;
		q->right=r;
	}
	else if(p->row==i) //情况二：p的行号与插入节点的行号相等，
	{
		while((p->right!=NULL)&&(p->col<j)&&(p->row==i))
		{
			q=p;
			p=p->right;
		}
		if(p->row==i&&p->col==j) //确定插入的位置没有节点
		{
			cout<<"已存在,请确认输入!";
			return;
		}
		else if(p->row==i&&p->col>j)//在行号相等时,若列号位于p,q之间时插在其间即可
		{

			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=p;
			r->down=NULL;
			q->right=r;
		}
		else if(p->row>i)
		{
			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=p;
			r->down=NULL;
			q->right=r;
		}
		else if(p->right==NULL)//新插入的节点为行号列号最大的节点，直接插在末尾即可
		{
			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=NULL;
			r->down=NULL;
			p->right=r;
		}
	}
	else if(p->right==NULL)  //新插入的节点为行号列号最大的节点，直接插在末尾即可
	{
		if(!(r=(SMLink)malloc(sizeof(SMNode))))
			cout<<"OVERFLOW";
		r->row=i;
		r->col=j;
		r->value=e;
		r->right=NULL;
		r->down=NULL;
		p->right=r;
	}

    //以下为将节点安列再次插入，其算法与按行插入完全相同
	p=smm.h;
	while(p->down!=NULL&&p->col<j)
	{
		q=p;
		p=p->down;
	}
	if(p->col>j)
	{
		if(!(r=(SMLink)malloc(sizeof(SMNode))))
			cout<<"OVERFLOW";
		r->row=i;
		r->col=j;
		r->value=e;
		r->right=NULL;
		r->down=p;
		q->down=r;
	}
	else if(p->col==j)
	{
		while((p->down!=NULL)&&(p->row<i)&&(p->col==j))
		{
			q=p;
			p=p->down;
		}
		if(p->col==j&&p->row==i)
		{
			cout<<"已存在,请确认输入!";
			return;
		}
		else if(p->col==j&&p->row>i)
		{

			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=NULL;
			r->down=p;
			q->down=r;
		}
		else if(p->col>j)
		{
			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=NULL;
			r->down=p;
			q->down=r;
		}
		else if(p->down==NULL)
		{
			if(!(r=(SMLink)malloc(sizeof(SMNode))))
				cout<<"OVERFLOW";
			r->row=i;
			r->col=j;
			r->value=e;
			r->right=NULL;
			r->down=NULL;
			p->down=r;
		}
	}
	else if(p->down==NULL)
	{
		if(!(r=(SMLink)malloc(sizeof(SMNode))))
			cout<<"OVERFLOW";
		r->row=i;
		r->col=j;
		r->value=e;
		r->right=NULL;
		r->down=NULL;
		p->down=r;
	}//按列插入结束
}//InsertSMartrix


/********************  矩阵删除函数  ***********************/
void DestroySMatrix(int n)
{
	SMLink p,q,r;
	p=sm[n].h;
	if(p->right==NULL)
	{
	    cout<<"矩阵不存在，请确定输入！"<<endl;
        return;
     }     
	q=p->right;
	r=p->down;
	
	while(q!=sm[n].h)
	{
		p=q;
		q=q->right;
		delete p;
	}
	while(r!=sm[n].h)
	{
		p=r;
		r=r->down;
		delete p;
	}
	sm[n].h->right=NULL;//在删除后将头节点置为空
	sm[n].h->down=NULL;
	sm[n].mu=NULL;
	sm[n].nu=NULL;
	sm[n].tu=NULL;
	cout<<"删除成功！"<<endl; 
}//DestroySMatrix

/********************  打印函数  ***********************/

int PrintSMatrix(int n)
{
	SMLink p;
	int i,j;