稀疏矩阵的正交链表解析

拼搏现实的明天。 2022-10-13 12:35 105阅读 0赞

稀疏矩阵是科学与工程领域经常使用的一种逻辑结构，它是元素大部分为零的一种矩阵。

我们知道在计算机中存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存储零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。而在实际应用时，需要处理的稀疏矩阵常常很大。例如，建立计算机网络时，用999条线路把1000个站点连接起来。用以表示这个网络的连接矩阵有1000\*1000个矩阵元素，其中有999个非零元素，999001个零元素。显然，把所有零元素都存在计算机中是不经济的。所以必须考虑稀疏矩阵压缩存储。

而针对稀疏矩阵的压缩存储，正交链表（十字链表）表示方法是一种非常有效率的方法，它能够有效地表示动态变化的矩阵结构，克服顺序表示的缺点。

在稀疏矩阵的正交链表表示中，矩阵的每一行设置为一个带附加结点头的循环链表（称为行链表），每一列也设置为一个带附加结点的循环链表（称为列链表）。

typedef struct OLNode{
    	int i,j;
    	ElemType e;
    	struct OLNode *right,*down;//该非零元所在的行表和列表的后续链域
    }OLNode, *OLink;
    
    typedef struct{
    	OLink *rhead, *chead;//rhead中存放着指向OLNode的指针的地址。
    	int mu, nu, tu;
    }CrossList;
    
    Status CreateSMatrix OL(CrossList &M){
    	// 创建稀疏矩阵M。采用十字链表
    	 if (M)free(M);
    	 scanf(&m, &n, &t);//输入M的行数、列数、和非零个数
    	 M.mu:=m;
    	 M.nu:=n;
    	 M.tu:=t;
    
    	 if(!(M.rhead=(OLink*)malloc(m+1)*sizeof(OLink))) exit(OVERFLOW);
    	 if(!(M.chead=(OLink*)malloc(n+1)*sizeof(OLink))) exit(OVERFLOW);
    
    	 M.rhead[]=M.chead[]=NULL;
    
    	 for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){// 按任意次序输入非零元
    		 if(!(p=(OLNode*)malloc(sizeof(OLNode)))) exit(OVERFLOW);
    			 
    			 p->i=i;
    			 p->j=j;
    			 p->e=e;//生成结点
    
    			 if(M.rhead[i]==NULL|| M.rhead[i]->j  > j){p->right=M.rhead[i];M.rhead[i]=p;}
    			 else{ //寻找在行表中的插入位置
    				 for(q=M.rhead[i]; (q->right)&&q->right->j <j;q=q->right);
    				 p->right=q->right;q->right=p;}
    
    				
    			 }
    	 
    	 }
    }