十字链表相加.cpp

实现了数据结构数组算法中的十字链表的相加

/*试按教科书5.3.2节中定义的十字链表存储表示编写将稀疏矩阵B加到稀疏A上的算法。*/
#include<stdio.h> 
#include<stdlib.h> 
#include<iostream.h> 
#include<process.h> 

typedef int ElemType; 

struct OLNode 
{ 
    int i,j; /*非零元所在行、列*/ 
    ElemType e;/*非零元值 */
    OLNode *right,*down; /*定义域的左针，右指针*/
};
 
typedef OLNode *OLink; 

struct CrossList 
{ 
	OLink *row_head,*rank_head;/*行、列表头的头节点*/ 
	int mu,nu,tu;/*矩阵的行、列和非零元个数 */
};
 
int Create(CrossList &M) 
{ 
	int i,j,k,m,n,t; 
	ElemType e; 
	OLNode *p,*q; 
	cout<<"请输入距阵的行数:"<<endl;
	cin>>m;
    cout<<"请输入距阵列数:"<<endl;
	cin>>n;
	cout<<"请输入距阵非零元的个数:"<<endl;
	cin>>t;	
	M.mu=m; 
	M.nu=n; 
	M.tu=t; 
	M.row_head=new OLink [50]; /*分配内存*/
	if(!M.row_head) 
		exit(-1); 
	M.rank_head=new OLink [50]; /*分配内存*/
	if(!M.rank_head) 
		exit(-1); 
	for(k=1;k<=m;k++)/*初始化行头指针*/ 
		M.row_head[k]=NULL; 
	for(k=1;k<=n;k++)/*初始化列头指针*/ 
		M.rank_head[k]=NULL; 
	cout<<"请输入"<<M.tu<<"个非零元素的行,列,元素值"<<endl; 
	for(k=0;k<t;k++) 
	{ 
		cin>>i>>j>>e; 
		if(i>m||j>n) 
		{ 
			cout<<"你输入的元素在矩阵中不存在！请重输:"<<endl; 
			exit(-1); 
		} 
		else 
		{ 
			p=(OLNode*)malloc(sizeof(OLNode));  
			if(!p) 
				exit(-1); 
			p->i=i; 
			p->j=j; 
			p->e=e; 
			if(M.row_head[i]==NULL||M.row_head[i]->j>j)/*p插入该行第一节点处*/ 
			{ 
				p->right=M.row_head[i]; 
				M.row_head[i]=p; 
			} 
			else/*寻找行表插入位置 */
			{ 
				for(q=M.row_head[i];q->right&&q->right->j<j;q=q->right); 
				p->right=q->right;/*完成行插入 */
				q->right=p; 
			} 
			if(M.rank_head[j]==NULL||M.rank_head[j]->i>i)/*p插入该列第一节点处 */
			{ 
				p->down=M.rank_head[j]; 
				M.rank_head[j]=p; 
			} 
			else/*寻找列表插入位置*/ 
			{ 
				for(q=M.rank_head[j];q->down&&q->down->i<i;q=q->down); 
				p->down=q->down;/*完成列插入*/ 
				q->down=p; 
			} 
		} 
	} 
	return 1; 
} 

int put_out(CrossList M) 
{ 
	int i,j,k; 
	OLink p; 
	int array[100][100]={0}; /*定义一个二维数组，并赋初值*/
	for(k=1;k<=M.nu;k++) 
	{ 
		p=M.rank_head[k]; 
		while(p) 
		{ 
			array[p->i][p->j]=p->e;/*将非零元存入数组中*/ 
			p=p->down; 
		} 
	} 
	for(i=1;i<=M.mu;i++) 
	{ 
		for(j=1;j<=M.nu;j++) 
		{ 
			if(j==M.nu) 
				cout<<array[i][j]<<endl; 
			else 
				cout<<array[i][j]<<" ";/*以矩阵的显示方式显示稀疏矩阵*/ 
		} 
	} 
	return 1; 
} 

int Addition(CrossList M,CrossList N,CrossList &Q) 
{ 
	int i,k; 
	OLink p,pq,pm,pn; 
	OLink *col; 
	if(M.mu!=N.mu||M.nu!=N.nu) /*判断矩阵是否可以相加*/
	{ 
		cout<<"两个距阵不是同类型的，不能进行此操作"<<endl; 
		exit(-1); 
	} 
	Q.mu=M.mu;/*初始化Q */
	Q.nu=M.nu; 
	Q.tu=0; 
	Q.row_head=new OLink [50]; 
	if(!Q.row_head) 
		exit(-1); 
	Q.rank_head=new OLink [50]; 
	if(!Q.rank_head) 
		exit(-1); 
	for(k=1;k<=Q.mu;k++)/*初始化行*/ 
		Q.row_head[k]=NULL; 
	for(k=1;k<=Q.nu;k++)/*初始化列 */
		Q.rank_head[k]=NULL; 
	col=new OLink [50];/*生成指向列的最后节点的数组*/ 
	if(!col) 
		exit(-1); 
	for(k=1;k<=Q.nu;k++)/*赋初始值*/ 
		col[k]=NULL; 
	for(i=1;i<=M.mu;i++)/*按行序相加*/
	{ 
		pm=M.row_head[i]; 
		pn=N.row_head[i]; 
		while(pm&&pn) 
		{ 
			if(pm->j<pn->j)/*矩阵M当情前结点的列小于矩阵N当前结点的列 */
			{ 
				p=(OLink)malloc(sizeof(OLNode));/*生成Q的结点*/ 
				if(!p) 
					exit(-1); 
				Q.tu++; /*非零元个数＋1 */
				p->i=i; /*赋值*/ 
				p->j=pm->j; 
				p->e=pm->e; 
				p->right=NULL; 
				pm=pm->right; /*pm右移*/ 
			} 
			else if(pm->j>pn->j) 
			{ 
				p=(OLink)malloc(sizeof(OLNode)); 
				if(!p) 
					exit
					(-1); 
				Q.tu++; 
				p->i=i; 
				p->j=pn->j; 
				p->e=pn->e; 
				p->right=NULL; 
				pn=pn->right; 
			} 
			else if(pm->e+pn->e)/*M,N当前结点的列相同并且两元素之和非零*/ 
			{ 
				p=(OLink)malloc(sizeof(OLNode)); 
				if(!p) 
					exit(-1);
				Q.tu++; 
				p->i=i; 
				p->j=pn->j; 
				p->e=pm->e+pn->e; 
				p->right=NULL; 
				pm=pm->right;/*pm右移*/ 
				pn=pn->right;/* pn右移 */
			} 
			else/*两元素相加为零*/ 
			{ 
				pm=pm->right; 
				pn=pn->right; 
				continue; 
			} 
			if(Q.row_head[i]==NULL) 
				Q.row_head[i]=pq=p; 
			else 
			{ 
				pq->right=p;/*完成行插入*/ 
				pq=pq->right; 
			} 
			if(Q.rank_head[p->j]==NULL) 
				Q.rank_head[p->j]=col[p->j]=p; 
			else 
			{ 
				col[p->j]->down=p;/*完成列插入*/
				col[p->j]=col[p->j]->down; 
			} 
		} 
		while(pm)/* 将矩阵M该行的剩余元素插入矩阵Q */
		{ 
			p=(OLink)malloc(sizeof(OLNode)); 
			if(!p) 
				exit(-1); 
			Q.tu++; 
			p->i=i; 
			p->j=pm->j; 
			p->e=pm->e; 
			p->right=NULL; 
			pm=pm->right; 
			if(Q.row_head[i]==NULL) 
				Q.row_head[i]=pq=p; 
			else 
			{ 
				pq->right=p; 
				pq=pq->right; 
			} 
			if(Q.rank_head[p->j]==NULL) 
				Q.rank_head[p->j]=col[p->j]=p; 
			else 
			{ 
				col[p->j]->down=p; 
				col[p->j]=col[p->j]->down; 
			} 
		} 
		while(pn)/*将矩阵N该行的剩余元素插入矩阵Q*/ 
		{ 
			p=(OLink)malloc(sizeof(OLNode)); 
			if(!p) 
				exit(-1); 
			Q.tu++; 
			p->i=i; 
			p->j=pn->j; 
			p->e=pn->e; 
			p->right=NULL; 
			pn=pn->right; 
			if(Q.row_head[i]==NULL) 
				Q.row_head[i]=pq=p; 
			else 
			{ 
				pq->right=p; 
				pq=pq->right; 
			} 
			if(Q.rank_head[p->j]==NULL) 
				Q.rank_head[p->j]=col[p->j]=p; 
			else 
			{ 
				col[p->j]->down=p; 
				col[p->j]=col[p->j]->down; 
			} 
		} 
	}
    for(k=1;k<=Q.nu;k++) 
        if(col[k]) 
            col[k]->down=NULL; 
        free(col); 
        return 1; 
} 
void main() 
{ 
    CrossList A,B,C;/*定义三个矩阵*/
    cout<<"十字链表存储表示编写将稀疏矩阵B加到稀疏A上的算法"<<endl;
    cout<<endl;
    Create(A);/*调用输入矩阵函数*/
    cout<<endl; 
    Create(B); 
    cout<<"你输入的是的第一个矩阵是："<<endl; 
    put_out(A); 
    cout<<"你输入的第二个矩阵是："<<endl; 
    put_out(B); 
    Addition(A,B,C); 
    cout<<"两个矩阵相加的结果是："<<endl; 
    put_out(C); /*用二维数组输出矩阵*/
}