csm.cpp

利用十字链表的储存结构完成距阵的加,减,乘.数据结构实习题目,已完成选做内容.

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>

typedef struct OLNode 
{
	int i,j; // 该非零元的行和列下标
	int e; // 非零元素值
	OLNode *right,*down; // 该非零元所在行表和列表的后继链域
}OLNode, *OLink;

typedef struct 
{
	OLink *rhead,*chead; // 行和列链表头指针向量基址
	int mu,nu,tu; // 稀疏矩阵的行数、列数和非零元个数
}CrossList;

CrossList M[2];//定义稀疏距阵的全局变量

void InitSmatixList(CrossList &M)//初始化十字链表头指针向量
{
	int i;
	if(!(M.rhead=(OLink *)malloc((M.mu+1)*sizeof(OLink)))) cout<<"OVERFLOW";
	if(!(M.chead=(OLink *)malloc((M.nu+1)*sizeof(OLink)))) cout<<"OVERFLOW";
	for(i=0;i<=M.mu;i++)//初始化行头指针向量；各行链表为空链表
		M.rhead[i]=NULL;
	for(i=0;i<=M.nu;i++)//初始化列头指针向量；各列链表为空链表
		M.chead[i]=NULL;
}//InitSmatixList

void DestroySMatrix(CrossList &M)//销毁稀疏距阵M
{
	int i;
	OLink p,q;//定义结点p,q
	for(i=1;i<=M.mu;i++)//按行释放结点
	{
		p=*(M.rhead+i);
		while(p)
		{
			q=p;
			p=p->right;
			free(q);
		}
	}
	free(M.rhead);
	free(M.chead);
	M.rhead=M.chead=NULL;
	M.mu=M.nu=M.tu=0;
}//DestroySMatrix

void InsertSMartrix(CrossList &M,OLink p)//将结点p插入距阵M中
{
	OLink q=M.rhead[p->i];
	if(!q||p->j<q->j) 
	{
		p->right=M.rhead[p->i]; 
		M.rhead[p->i]=p;
	}//end if
	else
	{//查找在行表中的插入位置
		for(q;q->right&&q->right->j<p->j;q=q->right);
		p->right=q->right;
		q->right=p;
	}//完成行插入
	q=M.chead[p->j];
	if(!q||p->i<q->i) 
	{
		p->down=M.chead[p->j]; 
		M.chead[p->j]=p;
	}//end if
	else
	{//查找在列表中的插入位置
		for(q;q->down&&q->down->i<p->i;q=q->down);
		p->down=q->down; 
		q->down=p;
	}//完成列插入
}//InsertSMartrix

void GreeteSMatrix()//创建稀疏距阵M[m]，用十字链表储存
{
	OLink p;//定义结点p
	int i,j,e,m,n=0;
	for(m=0;m<2;m++)
	{
		if(M[m].rhead) DestroySMatrix(M[m]);//如果稀疏距阵M[m]已经存在，销毁稀疏距阵M[m]
		cout<<endl<<" *** 请输入第"<<m+1<<"个矩阵的行数:";
		cin>>M[m].mu;
		cout<<" *** 请输入第"<<m+1<<"个矩阵的列数:";
		cin>>M[m].nu;
		cout<<" *** 请输入第"<<m+1<<"个矩阵的非零元个数:";
		cin>>M[m].tu;
		InitSmatixList(M[m]);//初始化M[m]的头表指针向量
		for(n=1;n<=M[m].tu;n++)
		{	 
			do
			{
				cout<<" *** 请输入第"<<m+1<<"个矩阵的第"<<n<<"个非零元的行数:";
				cin>>i;
				if(i>M[m].mu) cout<<" *** 输入错误! ***"<<endl;
			}while(i>M[m].mu);
			do
			{
				cout<<" *** 请输入第"<<m+1<<"个矩阵的第"<<n<<"个非零元的列数:";
				cin>>j;
				if(j>M[m].nu) cout<<"输入错误!"<<endl;
			}while(j>M[m].nu);
			cout<<" *** 请输入第"<<m+1<<"个矩阵的第"<<n<<"个非零元的值:";
			cin>>e;
			if(!(p=(OLNode *)malloc(sizeof(OLNode)))) cout<<"OVERFLW";
			p->i=i; p->j=j; p->e=e;//生成结点
			InsertSMartrix(M[m],p);//将结点p插入距阵M[m]中
		}//end for
	}//end for
}//GreeteSMatrix

void Print(CrossList &M)//按距阵形式输出M
{
	int i,j;
	OLink p;
	for(i=1;i<=M.mu;i++)
	{
		p=M.rhead[i];
		for(j=1;j<=M.nu;j++)
		{
			if(!p||p->j!=j) cout<<setw(4)<<"0";
			else {cout<<setw(4)<<p->e;p=p->right;}
		}//end for
		cout<<endl;
	}//end for
}//Print

void Add(int x)//将距阵M[0]和距阵M[1]进行加法运算
{
	CrossList T;//定义距阵T
	OLink d,d0,d1;//定义结点d,d0,d1
	int i,l;
	if(x==0) GreeteSMatrix();//创建稀疏距阵
	if(M[0].mu==M[1].mu&&M[0].nu==M[1].nu) 
	{
		T.mu=M[0].mu;//初始化距阵T
		T.nu=M[0].nu;
		InitSmatixList(T);
		for(i=1;i<=M[0].mu;i++)//按行顺序相加
		{
			d0=M[0].rhead[i];//指向第一个结点
			d1=M[1].rhead[i];
			for(l=1;l<=M[0].nu;l++)
			{
				if(d0&&d1)//d0和d1都不为空时
				{
					if(!(d=(OLNode *)malloc(sizeof(OLNode)))) cout<<"OVERFLW";
					if(d0->j==d1->j)//当前结点所在的列数相等时 
					{
						*d=*d0;
						d->e+=d1->e;
						if(d->e!=0) InsertSMartrix(T,d);
						else free(d);
						d0=d0->right;
						d1=d1->right;
					}
					else if(d0->j<d1->j)  {*d=*d0;InsertSMartrix(T,d);d0=d0->right;}
						 else  {*d=*d1;InsertSMartrix(T,d);d1=d1->right;}
					continue;				
				}//end if
				if(d0)//d0不为空时
				{
					if(!(d=(OLNode *)malloc(sizeof(OLNode)))) cout<<"OVERFLW";	
					*d=*d0;
					InsertSMartrix(T,d);
					d0=d0->right;
					continue;
				}//end if
				if(d1)//d1不为空时
				{
					if(!(d=(OLNode *)malloc(sizeof(OLNode)))) cout<<"OVERFLW";	
					*d=*d1;
					InsertSMartrix(T,d);
					d1=d1->right;
					continue;
				}//end if
			}//end for
		}//end for
		if(x==0) cout<<endl<<" *** 加法运算结果为:"<<endl;
		else cout<<endl<<" *** 减法运算结果为:"<<endl;
		Print(T);
		DestroySMatrix(T);//如果稀疏距阵T已经存在，销毁稀疏距阵T
	}//end if
	else cout<<endl<<"\t\t *** 两个距阵的行、列数不相匹配!不能进行加法运算! ***"<<endl;	
}//Add

void Reduce()//将距阵M[0]和距阵M[1]进行减法运算
{
	OLink d;//定义结点d
	int i;
	GreeteSMatrix();//创建稀疏距阵
	for(i=1;i<=M[1].mu;i++)//将稀疏距阵M[1]取反
	{
		d=M[1].rhead[i];
		while(d)
		{
			d->e*=-1;
			d=d->right;
		}
	}//end for
	Add(1);//M[0]+(-M[1])
}//Reduce

void Multi()//将距阵M[0]和距阵M[1]进行乘法运算
{
	CrossList T;//定义稀疏距阵T
	OLink d,d0,d1;//定义结点d,d0,d1
	int i,j,e;
	GreeteSMatrix();//创建稀疏距阵
	if(M[0].nu==M[1].mu)
	{
		T.mu=M[0].mu;//初始化距阵T
		T.nu=M[1].nu;
		InitSmatixList(T);
		for(i=1;i<=M[0].mu;i++)
		{
			for(j=1;j<=M[1].nu;j++)
			{
				d0=M[0].rhead[i];
				d1=M[1].chead[j];
				e=0;
				while(d0&&d1)
				{								
					if(d0->j==d1->i) 
					{
						e+=d0->e*d1->e;
						d0=d0->right;
						d1=d1->down;
					}//end if
					else if(d0->j<d1->i) d0=d0->right;
						 else d1=d1->down;
				}//end while
				if(e)
				{
					if(!(d=(OLNode *)malloc(sizeof(OLNode)))) cout<<"OVERFLW";
					d->i=i;d->j=j;d->e=e;
					InsertSMartrix(T,d);//将结点d插入距阵T中
				}//end if
			}//end for
		}//end for
		cout<<endl<<" *** 乘法运算结果为:"<<endl;
		Print(T);
		DestroySMatrix(T);//如果稀疏距阵T已经存在，销毁稀疏距阵T
	}//end if
	else cout<<endl<<"\t\t *** 两个距阵的行、列数不相匹配!不能进行乘法运算! ***"<<endl;	
}//Multi

void Exit()
{
	if(M[0].rhead) DestroySMatrix(M[0]);//如果稀疏距阵M[0]已经存在，销毁稀疏距阵M[0]
	if(M[1].rhead) DestroySMatrix(M[1]);//如果稀疏距阵M[1]已经存在，销毁稀疏距阵M[1]
	cout<<"\n\t\t\t   *** 欢迎使用稀疏距阵运算器! ***"<<endl;
}//Exit

void main()
{
	char c;	
	do
	{
		cout<<"\n\t\t\t  ******************************\n";
		cout<<"  \t\t\t  *    稀 疏 矩 阵 运 算 器    *\n";
		cout<<"  \t\t\t  ******************************\n";
		cout<<"  \t\t\t  *         1-->加法运算       *\n";
		cout<<"  \t\t\t  *         2-->减法运算       *\n";
		cout<<"  \t\t\t  *         3-->乘法运算       *\n";
		cout<<"  \t\t\t  *         4-->退出           *\n";
		cout<<"  \t\t\t  ******************************\n";
		cout<<"\t\t\t\t请输入(1--4):";
		cin>>c;
		switch(c)
		{
			case '1':Add(0);break;
			case '2':Reduce();break;
			case '3':Multi();break;
			case '4':Exit();break;
			default:cout<<"\n\n\t\t\t   *** 输入错误!请重新输入! ***"<<endl;
		}
		if(c=='4') break;
	}while(c!='4');
}//main