crosschain.cpp

常用算法与数据结构原代码

#include <iostream.h>

typedef struct ele{
	int row,col;
	double val;
	ele *right,*down;
} ELENODE;

ELENODE *createNullMat(int m,int n)
{
	ELENODE *h,*p;
	int k;
	h=new ELENODE;
	h->row=m;
	h->col=n;
	h->val=0;
	h->right=new ELENODE[n];
	h->down=new ELENODE[m];
	for (p=h->down,k=0;k<m;k++,p++)
	{
		p->col=1000;
		p->right=p;
		p->down=k<m-1 ? p+1 : h->down;
	}
	for (p=h->right,k=0;k<m;k++,p++)
	{
		p->row=1000;
		p->down=p;
		p->right=k<m-1 ? p+1 : h->right;
	}
	return h;
}

int insertNode(ELENODE *a,int row,int col,double val)
{
	ELENODE *p,*q,*r,*u,*v;
	if (row>=a->row || col>=a->col)
		return -2;
	r=new ELENODE;
	r->row=row;
	r->col=col;
	r->val=val;
	p=a->down+row;
	q=p->right;
	while (q->col<col)
	{
		p=q;
		q=q->right;
	}
	if (q->col==col)
	{
		delete r;
		return -1;
	}
	u=a->right+col;
	v=u->down;
	while (v->row<row)
	{
		u=v;
		v=v->down;
	}
	if (v->row<row)
	{
		delete r;
		return -1;
	}
	p->right=r;r->right=q;
	u->down=r;r->down=v;
	a->val+=1.0;
	return 0;
}

ELENODE *readMat()
{
	ELENODE *h;
	int i,j,m,n;
	double v;
	cout<<"输入稀疏矩阵的行数和列数:"<<endl;
	cin>>m >>n;
	h=createNullMat(m,n);
	h->row=m;
	h->col=n;
	cout<<"输入有非零元素的行号:"<<endl;
	cin>>i;
	while (i>=0)
	{
		cout<<"输入非零元素的列号:"<<endl;
		cin>>j;
		while (j>=0)
		{
			cout<<"输入非零元素的值:"<<endl;
			cin>>v;
			insertNode(h,i,j,v);
			cout<<"输入当前行下一个非零元素的列号（-1表示当前行结束）:"<<endl;
			cin>>j;
		}
		cout<<"输入下一列有非零元素的列号（-1表示输入结束）:"<<endl;
		cin>>i;
	}
	return h;
}

ELENODE *matAdd(ELENODE *a,ELENODE *b)
{
	ELENODE *r,*p,*q,*u,*v;
	r=createNullMat(a->row,a->col);
	p=a->down;
	u=b->down;
	do{
		q=p->right;
		v=u->right;
		while (q!=p || v!=u)
			if (q->col==v->col)
			{
				if (q->val+v->val!=0.0)
					insertNode(r,q->row,q->col,q->val+v->val);
				q=q->right;
				v=v->right;
			}
			else
			{
				if (q->col<v->col)
				{
					insertNode(r,q->row,q->col,q->val);
					q=q->right;
				}
				else
				{
					insertNode(r,v->row,v->col,v->val);
					v=v->right;
				}
			}
			p=p->down;
			u=u->down;
	}
	while (p!=a->down);
	return r;
}